Computer Sciences Commons^™

How To Transform Partial Order Between Degrees Into Numerical Values, Olga Kosheleva, Vladik Kreinovich, Joe Lorkowski, Martha Osegueda Escobar

Departmental Technical Reports (CS)

Fuzzy techniques are a successful way to handle expert knowledge, enabling us to capture different degrees of expert's certainty in their statements. To use fuzzy techniques, we need to describe expert's degree of certainty in numerical terms. Some experts can provide such numbers, but others can only describe their degrees by using natural-language words like "very", "somewhat", "to some extent", etc. In general, all we know about these word-valued degrees is that there is a natural partial order between these degrees: e.g., "very small" is clearly smaller than "somewhat small". In this paper, we propose a natural way to transform …

Which Robust Versions Of Sample Variance And Sample Covariance Are Most Appropriate For Econometrics: Symmetry-Based Analysis, Songsak Sriboonchitta, Ildar Batyrshin, Vladik Kreinovich

Departmental Technical Reports (CS)

In many practical situations, we do not know the shape of the corresponding probability distributions and therefore, we need to use robust statistical techniques, i.e., techniques that are applicable to all possible distributions. Empirically, it turns out the the most efficient robust version of sample variance is the average value of the p-th powers of the deviations |x_i- a| from the (estimated) mean a. In this paper, we use natural symmetries to provide a theoretical explanation for this empirical success, and to show how this optimal robust version of sample variance can be naturally extended to a robust …

Empirically Successful Transformations From Non-Gaussian To Close-To-Gaussian Distributions: Theoretical Justification, Thongchai Dumrongpokaphan, Perdo Barragan, Vladik Kreinovich

Departmental Technical Reports (CS)

A large number of efficient statistical methods have been designed for a frequent case when the distributions are normal (Gaussian). In practice, many probability distributions are not normal. In this case, Gaussian-based techniques cannot directly applied. In many cases, however, we can apply these techniques indirectly -- by first applying an appropriate transformation to the original variables, after which their distribution becomes close to normal. Empirical analysis of different transformations has shown that the most successful are the power transformations X → X^h and their modifications. In this paper, we provide a symmetry-based explanation for this empirical success.

Big Data: A Geometric Explanation Of A Seemingly Counterintuitive Strategy, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

Traditionally, the progress in science was usually achieved by gradually modifying known problem-solving techniques -- so that the modified techniques can solve problems similar to the already-solved ones. Recently, however, a different -- successful -- paradigm of big data appeared. In the big data paradigm, we, in contrast, look for problems which cannot be solved by gradual modifications of the existing methods. In this paper, we propose a geometric explanation for the empirical success of this new paradigm.

Bayesian Approach To Intelligent Control And Its Relation To Fuzzy Control, Kongliang Zhu, Vladik Kreinovich, Olga Kosheleva

Departmental Technical Reports (CS)

In many application areas including economics, experts describe their knowledge by using imprecise ("fuzzy") words from natural language. To design an automatic control system, it is therefore necessary to translate this knowledge into precise computer-understandable terms. To perform such a translation, a special semi-heuristic fuzzy methodology was designed. This methodology has been successfully applied to many practical problem, but its semi-heuristic character is a big obstacle to its use: without a theoretical justification, we are never 100% sure that this methodology will be successful in other applications as well. It is therefore desirable to come up with either a theoretical …

Need For Most Accurate Discrete Approximations Explains Heavy-Tailed Distributions, Songsak Sriboonchitta, Vladik Kreinovich, Olga Kosheleva, Hung T. Nguyen

Departmental Technical Reports (CS)

In many practical situations, we encounter Gaussian distributions, for which the distribution tails are light -- in the sense that as the value increases, the corresponding probability density tends to 0 very fast. There are many theoretical explanations for the Gaussian distributions and for similar light-tail distributions. In practice, however, we often encounter heavy-tailed distributions, in which the probability density is asymptotically described, e.g., by a power law. In contrast to the light-tail distributions, there is no convincing theoretical explanation for the heavy-tailed ones. In this paper, we provide such a theoretical explanation. This explanation is based on the fact …

How To Predict Nesting Sites And How To Measure Shoreline Erosion: Fuzzy And Probabilistic Techniques For Environment-Related Spatial Data Processing, Stephen Escarzaga, Craig Tweedie, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

In this paper, we show how fuzzy and probabilistic techniques can be used in environment-related data processing. Specifically, we will show that these methods help in solving two environment-related problems: how to predict the birds' nesting sites and how to measure shoreline erosion.

How To Describe Measurement Uncertainty And Uncertainty Of Expert Estimates?, Nicolas Madrid, Irina Perfilieva, Vladik Kreinovich

Departmental Technical Reports (CS)

Measurement and expert estimates are never absolutely accurate. Thus, when we know the result M(u) of measurement or expert estimate, the actual value A(u) of the corresponding quantity may be somewhat different from M(u). In practical applications, it is desirable to know how different it can be, i.e., what are the bounds f(M(u)) <= A(u) <= g(M(u)). Ideally, we would like to know the tightest bounds, i.e., the largest possible values f(x) and the smallest possible values g(x). In this paper, we analyze for which (partially ordered) sets of values such tightest bounds always exist: it turns out that they always exist only for complete lattices.

How To Introduce Technical Details Of Quantum Computing In A Theory Of Computation Class: Using The Basic Case Of The Deutsch-Jozsa Algorithm, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

Many students taking the theory of computation class have heard about quantum computing and are curious about it. However, the usual technical description of quantum computing requires a large amount of preliminary information, too much to fit into an already packed class. In this paper, we propose a way to introduce technical details of quantum computing that does not require much time -- it can be described in less than an hour. As such an introduction, we use a simplified description of the basic case of one of the pioneering algorithms of quantum computing.

How To Estimate Resilient Modulus For Unbound Aggregate Materials: A Theoretical Explanation Of An Empirical Formula, Pedro Barragan Olague, Soheil Nazarian, Vladik Kreinovich, Afshin Gholamy

Departmental Technical Reports (CS)

To ensure the quality of pavement, it is important to make sure that the resilient moduli -- that describe the stiffness of all the pavement layers -- exceed a certain threshold. From the mechanical viewpoint, pavement is a non-linear medium. Several empirical formulas have been proposed to describe this non-linearity. In this paper, we describe a theoretical explanation for the most accurate of these empirical formulas.

How To Make A Solution To A Territorial Dispute More Realistic: Taking Into Account Uncertainty, Emotions, And Step-By-Step Approach, Mahdokhat Afravi, Vladik Kreinovich

Departmental Technical Reports (CS)

In many real-life situations, it is necessary to divide a disputed territory between several interested parties. The usual way to perform this division is by using Nash's bargaining solution, i.e., by finding a partition that maximizes the product of the participants' utilities. However, this solution is based on several idealized assumptions: that we know the exact values of all the utilities, that division is performed on a purely rational basis, with no emotions involved, and that the entire decision is made once. In practice, we only know the utilities with some uncertainty, emotions are often involved, and the solution is …

Chemical Kinetics In Situations Intermediate Between Usual And High Concentrations: Fuzzy-Motivated Derivation Of The Formulas, Olga Kosheleva, Vladik Kreinovich, Laécio Carvalho Barros

Departmental Technical Reports (CS)

In the traditional chemical kinetics, the rate of each reaction A + ... + B --> ... is proportional to the product cA * ... * cB of the concentrations of all the input substances A, ..., B. For high concentrations cA, ..., cB, the reaction rate is known to be proportional to the minimum min(cA, ..., cB). In this paper, we use fuzzy-related ideas to derive the formula of the reaction rate for situations intermediate between usual and high concentrations.

Why Sparse? Fuzzy Techniques Explain Empirical Efficiency Of Sparsity-Based Data- And Image-Processing Algorithms, Fernando Cervantes, Bryan E. Usevitch, Leobardo Valera, Vladik Kreinovich

Departmental Technical Reports (CS)

In many practical applications, it turned out to be efficient to assume that the signal or an image is sparse, i.e., that when we decompose it into appropriate basic functions (e.g., sinusoids or wavelets), most of the coefficients in this decomposition will be zeros. At present, the empirical efficiency of sparsity-based techniques remains somewhat a mystery. In this paper, we show that fuzzy-related techniques can explain this empirical efficiency. A similar explanation can be obtained by using probabilistic techniques; this fact increases our confidence that our explanation is correct.

Fuzzy Techniques Provide A Theoretical Explanation For The Heuristic L^P-Regularization Of Signals And Images, Fernando Cervantes, Bryan E. Usevitch, Leobardo Valera, Vladik Kreinovich, Olga Kosheleva

Departmental Technical Reports (CS)

One of the main techniques used to de-noise and de-blur signals and images is regularization, which is based on the fact that signals and images are usually smoother than noise. Traditional Tikhonov regularization assumes that signals and images are differentiable, but, as Mandelbrot has shown in his fractal theory, many signals and images are not differentiable. To de-noise and de-blur such images, researchers have designed a heuristic method of l^p-regularization.

l^p-regularization leads to good results, but it is not used as widely as should be, because it lacks a convincing theoretical explanation -- and thus, practitioners are often reluctant to …

Membership Functions Representing A Number Vs. Representing A Set: Proof Of Unique Reconstruction, Hung T. Nguyen, Vladik Kreinovich, Olga Kosheleva

Departmental Technical Reports (CS)

In some cases, a membership function m(x) represents an unknown number, but in many other cases, it represents an unknown crisp set. In this case, for each crisp set S, we can estimate the degree m(S) to which this set S is the desired one. A natural question is: once we know the values m(S) corresponding to all possible crisp sets S, can we reconstruct the original membership function? In this paper, we show that the original membership function m(x) can indeed be uniquely reconstructed from the values m(S).

Why Lp-Methods In Signal And Image Processing: A Fuzzy-Based Explanation, Fernando Cervantes, Bryan E. Usevitch, Vladik Kreinovich

Departmental Technical Reports (CS)

In signal and image processing, it is often beneficial to use semi-heuristic Lp-methods, i.e., methods that minimize the sum of the p-th powers of the discrepancies. In this paper, we show that a fuzzy-based analysis of the corresponding intuitive idea leads exactly to the Lp-methods.

Model-Order Reduction Using Interval Constraint Solving Techniques, Leobardo Valera, Martine Ceberio

Departmental Technical Reports (CS)

Many natural phenomena can be modeled as ordinary or partial differential equations. A way to find solutions of such equations is to discretize them and to solve the corresponding (possibly) nonlinear large systems of equations.

Solving a large nonlinear system of equations is very computationally complex due to several numerical issues, such as high linear-algebra cost and large memory requirements. Model-Order Reduction (MOR) has been proposed as a way to overcome the issues associated with large dimensions, the most used approach for doing so being Proper Orthogonal Decomposition (POD). The key idea of POD is to reduce a large number …

Limitations Of Realistic Monte-Carlo Techniques, Andrzej Pownuk, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

Because of the measurement errors, the result Y = f(X1, ..., Xn) of processing the measurement results X1, ..., Xn is, in general, different from the value y = f(x1, ..., xn) that we would obtain if we knew the exact values x1, ..., xn of all the inputs. In the linearized case, we can use numerical differentiation to estimate the resulting difference Y -- y; however, this requires >n calls to an algorithm computing f, and for complex algorithms and large $n$ this can take too long. In situations when for each input xi, we know the probability distribution …

How To Estimate Amount Of Useful Information, In Particular Under Imprecise Probability, Luc Longpre, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

Traditional Shannon's information theory describes the overall amount of information, without distinguishing between useful and unimportant information. Such a distinction is needed, e.g., in privacy protection, where it is crucial to protect important information while it is not that crucial to protect unimportant information. In this paper, we show how Shannon's definition can be modified so that it will describe only the amount of useful information.

Adjoint Fuzzy Partition And Generalized Sampling Theorem, Irina Perfilieva, Michal Holčapek, Vladik Kreinovich

Departmental Technical Reports (CS)

A new notion of adjoint fuzzy partition is introduced and the reconstruction of a function from its F-transform components is analyzed. An analogy with the Nyquist-Shannon-Kotelnikov sampling theorem is discussed.

Comparison Of Formulations Of Applied Tasks With Interval, Fuzzy Set And Probability Approaches, Boris Kovalerchuk, Vladik Kreinovich

Departmental Technical Reports (CS)

The focus of this paper is to clarify the concepts of solutions in linear equations in interval, probabilistic and fuzzy sets setting for real word tasks. There is a fundamental difference between formal definitions of the solutions and physically meaningful concept of solution in applied tasks when equations have uncertain components. For instance, a formal definition of the solution in terms of Moore interval analysis can be completely irrelevant for solving a real world task. We show that formal definitions must follow meaningful concept of the solution in the real world. The paper proposed several formalized definitions of the concept …

Robustness As A Criterion For Selecting A Probability Distribution Under Uncertainty, Songsak Sriboonchitta, Hung T. Nguyen, Vladik Kreinovich, Olga Kosheleva

Departmental Technical Reports (CS)

Often, we only have partial knowledge about a probability distribution, and we would like to select a single probability distribution $\rho(x)$ out of all probability distributions which are consistent with the available knowledge. One way to make this selection is to take into account that usually, the values $x$ of the corresponding quantity are also known only with some accuracy. It is therefore desirable to select a distribution which is the most robust -- in the sense the x-inaccuracy leads to the smallest possible inaccuracy in the resulting probabilities. In this paper, we describe the corresponding most robust probability distributions, …

Why Dependence Of Productivity On Group Size Is Log-Normal, Francisco Zapata, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

Empirical analysis shows that, on average, the productivity of a group log-normally depends on its size. The current explanations for this empirical fact are based on reasonably complex assumptions about the human behavior. In this paper, we show that the same conclusion can be made in effect, from first principles, without making these complex assumptions.

Voting Aggregation Leads To (Interval) Median, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

When we have several results of measuring or estimating the same quantities, it is desirable to aggregate them into a single estimate for the desired quantities. A natural requirement is that if the majority of estimates has some property, then the aggregate estimate should have the same property. It turns out that it is not possible to require this forall possible properties -- but we can require it for bounds, i.e., for properties that the value of the quantity is in between given bounds a and b. In this paper, we prove that if we restrict the …

Why Superellipsoids: A Probability-Based Explanation, Pedro Barragan Olague, Vladik Kreinovich

Departmental Technical Reports (CS)

In many practical situations, it turns out that the set of possible values of the deviation vector is (approximately) a super-ellipsoid. In this paper, we provide a theoretical explanation for this empirical fact -- an explanation based on the natural notion of scale-invariance.

Toward Unification Of Explicit And Implicit Invocation-Style Programming, Yoonsik Cheon

Departmental Technical Reports (CS)

Subprograms like procedures and methods can be invoked explicitly or implicitly; in implicit invocation, an event implicitly causes the invocation of subprograms that are registered an interest in the event. Mixing these two styles is common in programming and often unavoidable in developing such software as GUI applications and event-based control systems. However, it isn't also uncommon for the mixed use to complicate programming logic and thus produce unclean code, code that is hard to read and understand. We show, through a small but realistic example, that the problem is not much on mixing two different styles itself but more …

A Systematic Derivation Of Loop Specifications Using Patterns, Aditi Barua, Yoonsik Cheon

Departmental Technical Reports (CS)

Any non-trivial program contains loop control structures such as while, for and do statements. A formal correctness proof of code containing loop control structures is typically performed using an induction-based technique, and oftentimes the most challenging step of an inductive proof is formulating a correct induction hypothesis. An incorrectly-formulated induction hypothesis will surely lead to a failure of the proof. In this paper we propose a systematic approach for formulating and driving specifications of loop control structures for formal analysis and verification of programs. We explain our approach using while loops and a functional program verification technique in which a …

Why The Graph Isomorphism Problem Is Easier Than Propositional Satisfiability: A Possible Qualitative Explanation, Vladik Kreinovich, Olga Kosheleva

Departmental Technical Reports (CS)

A recent result has shown that the graph isomorphism problem can be solved in quasi-polynomial time, while the general belief is that only exponential time algorithms are possible for propositional satisfiability. This is somewhat counter-intuitive, since for propositional satisfiability, we need to look for one of 2ⁿ options, while in graph isomorphism, we need to look for one of n! options, and n! is much larger than 2ⁿ. Our qualitative explanation for this counter-intuitive fact comes from the fact that, in general, a graph isomorphism problem has a unique solution -- in contrast to propositional satisfiability which, …

How To Explain The Empirical Success Of Generalized Trigonometric Functions In Processing Discontinuous Signals, Pedro Barragan Olague, Vladik Kreinovich

Departmental Technical Reports (CS)

Trigonometric functions form the basis of Fourier analysis - one of the main signal processing tools. However, while they are very efficient in describing smooth signals, they do not work well for signals that contain discontinuities - such as signals describing phase transitions, earthquakes, etc. It turns out that empirically, one of the most efficient ways of describing and processing such signals is to use a certain generalization of trigonometric functions. In this paper, we provide a theoretical explanation of why this particular generalization is the most empirically efficient one.

How To Make Sure That Everyone Works Towards A Common Goal: Towards Optimal Incentives, Christian Servin, Vladik Kreinovich

Departmental Technical Reports (CS)

No abstract provided.