Computer Engineering Commons^™

No-Free-Lunch Result For Interval And Fuzzy Computing: When Bounds Are Unusually Good, Their Computation Is Unusually Slow, Ildar Batyrshin, Martine Ceberio, Vladik Kreinovich

Departmental Technical Reports (CS)

On several examples from interval and fuzzy computations and from related areas, we show that when the results of data processing are unusually good, their computation is unusually complex. This makes us think that there should be an analog of Heisenberg's uncertainty principle well known in quantum mechanics: when we an unusually beneficial situation in terms of results, it is not as perfect in terms of computations leading to these results. In short, nothing is perfect.

Extreme Distributions On Intervals, Monchaya Chiangpradit, Wararit Panichkitkosolkul, Hung T. Nguyen, Vladik Kreinovich

Departmental Technical Reports (CS)

One of the main tasks of interval computation is to analyze situations in which we only know the lower and upper bounds on the desired quantity, i.e., we only know an interval that contains this quantity. One of the objectives of such analysis is to make decisions. According to decision theory, a consistent decision making procedure is equivalent to assigning probabilities to different values within each interval. Thus, we arrive at the problem of describing a natural probability distribution on an interval. In this paper, we describe such a distribution for the practically important case of the "weakest link" arrangement, …

A Heuristic For Selecting The Cycle Length For Fairio, Sarala Arunagiri, Y. Kwok, Patricia J. Teller, R. A. Portillo, S. Seelam

Departmental Technical Reports (CS)

FAIRIO is a cycle-based I/O scheduling algorithm that provides differentiated service to workloads concurrently accessing a consolidated RAID storage system. FAIRIO enforces proportional sharing of I/O service through fair scheduling of disk time. During each cycle of the algorithm, I/O requests are scheduled according to workload weights and disk-time utilization history. There are several parameters in the FAIRIO scheduler that can affect its behavior. One parameter in particular, the length of a scheduling cycle, can affect the scheduler's ability to react to and compensate for changes in workload access characteristics. Unfortunately, there is no cycle length that is optimal for …

Efficient Geophysical Technique Of Vertical Line Elements As A Natural Consequence Of General Constraints Techniques, Rolando Cardenas, Martine Ceberio

Departmental Technical Reports (CS)

One of the main objectives of geophysics is to find how density d and other physical characteristics depend on a 3-D location (x,y,z). In general, in numerical methods, a way to find the dependence d(x,y,z) is to discretize the space, and to consider, as unknown, e.g., values d(x,y,z) on a 3-D rectangular grid. In this case, the desired density distribution is represented as a combination of point-wise density distributions. In geophysics, it turns out that a more efficient way to find the desired distribution is to represent it as a combination of thin vertical line elements that start at some …

Prediction In Econometrics: Towards Mathematical Justification Of Simple (And Successful) Heuristics, Vladik Kreinovich, Hung T. Nguyen, Songsak Sriboonchitta

Departmental Technical Reports (CS)

Many heuristic and semi-heuristic methods have been proposed to predict economic and financial processes. Some of these heuristic processes are intuitively reasonable, some seemingly contradict to our intuition. The success of these heuristics leads to a reasonable conjecture that these heuristic methods must have a more fundamental justification. In this paper, we provide such a justification for two simple (and successful) prediction heuristics: of an intuitive exponential smoothing that provides a reasonable prediction for slowly changing processes, and of a seemingly counter-intuitive idea of an increase in volatility as a predictor of trend reversal. As a possible application of these …

Reconstructing An Open Order From Its Closure, With Applications To Space-Time Physics And To Logic, Francisco Zapata, Vladik Kreinovich

Departmental Technical Reports (CS)

In his logical papers, Leo Esakia studied corresponding ordered topological spaces and order-preserving mappings. Similar spaces and mappings appear in many other application areas such the analysis of causality in space-time. It is known that under reasonable conditions, both the topology and the original order relation can be uniquely reconstructed if we know the "interior" < of the order relation. It is also known that in some cases, we can uniquely reconstruct < (and hence, topology) from the original order relation. In this paper, we show that, in general, under reasonable conditions, the open order < (and hence, the corresponding topology) can be uniquely determined from its closure.

The Cleanjava Language For Functional Program Verification, Yoonsik Cheon, Cesar Yeep, Melisa Vela

Departmental Technical Reports (CS)

Unlike Hoare-style program verification, functional program verification supports forward reasoning by viewing a program as a mathematical function from one program state to another and proving its correctness by essentially comparing two mathematical functions, the function computed by the program and its specification. Since it requires a minimal mathematical background and reflects the way that programmers reason about the correctness of a program informally, it can be taught and practiced effectively. However, there is no formal notation supporting the functional program verification. In this article, we describe a formal notation for writing functional program specifications for Java programs. The notation, …

High-Concentration Chemical Computing Techniques For Solving Hard-To-Solve Problems, And Their Relation To Numerical Optimization, Neural Computing, Reasoning Under Uncertainty, And Freedom Of Choice, Vladik Kreinovich, Olac Fuentes

Departmental Technical Reports (CS)

Chemical computing -- using chemical reactions to perform computations -- is a promising way to solve computationally intensive problems. Chemical computing is promising because it has the potential of using up to 10^{23} molecules as processors working in parallel -- and thus, has a potential of an enormous speedup. Unfortunately, for hard-to-solve (NP-complete) problems a natural chemical computing approach for solving them is exponentially slow. In this chapter, we show that the corresponding computations can become significantly faster if we use very-high-concentration chemical reactions, concentrations at which the usual equations of chemical kinetics no longer apply. We also show that …

All Kinds Of Behavior Are Possible In Chemical Kinetics: A Theorem And Its Potential Applications To Chemical Computing, Vladik Kreinovich

Departmental Technical Reports (CS)

Linear Neural Networks Revisited: From Pagerank To Family Happiness, Vladik Kreinovich

Departmental Technical Reports (CS)

The study of Artificial Neural Networks started with the analysis of linear neurons. It was then discovered that networks consisting only of linear neurons cannot describe non-linear phenomena. As a result, most currently used neural networks consist of non-linear neurons. In this paper, we show that in many cases, linear neurons can still be successfully applied. This idea is illustrated by two examples: the PageRank algorithm underlying the successful Google search engine and the analysis of family happiness.

Density-Based Fuzzy Clustering As A First Step To Learning The Rules: Challenges And Possible Solutions, Gözde Ulutagay, Vladik Kreinovich

Departmental Technical Reports (CS)

In many practical situations, it is necessary to cluster given situations, i.e., to divide them into groups so that situations within each group are similar to each other. This is how we humans usually make decisions: instead of taking into account all the tiny details of a situation, we classify the situation into one of the few groups, and then make a decision depending on the group containing a given situation. When we have many situations, we can describe the probability density of different situations. In terms of this density, clusters are connected sets with higher density separated by sets …

How To Encourage Imperfect Individuals To Care More About Society In General: A Utility-Theory Approach, Vladik Kreinovich

Departmental Technical Reports (CS)

A Simple Physics-Motivated Equivalent Reformulation Of P=Np That Makes This Equality (Slighty) More Plausible, Jaime Nava, Vladik Kreinovich

Departmental Technical Reports (CS)

In our opinion, one of the reasons why the problem P=NP? is so difficult is that while there are good intuitive arguments in favor of P=/=NP, there is a lack of intuitive arguments in favor of P=NP. In this paper, we provide such an argument -- based on the fact that in physics, many dependencies are scale-invariant, their expression does not change if we simply change the unit in which we measure the corresponding input quantity (e.g., replace meters by centimeters). It is reasonable to imagine similar behavior for time complexity t_A(n) of algorithms A: that the form …

How Accurately Should We Write On The Board? When Marking Comments On Student Papers?, Martine Ceberio, Olga Kosheleva

Departmental Technical Reports (CS)

Writing on the board is an important part of a lecture. Lecturers' handwriting is not always perfect. Usually, a lecturer can write slower and more legibly, this will increase understandability but slow down the lecture. In this paper, we analyze an optimal trade-off between speed and legibility.

I-Complexity And Discrete Derivative Of Logarithms: A Symmetry-Based Explanation, Vladik Kreinovich, Jaime Nava

Departmental Technical Reports (CS)

In many practical applications, it is useful to consider Kolmogorov complexity K(s) of a given string s, i.e., the shortest length of a program that generates this string. Since Kolmogorov complexity is, in general, not computable, it is necessary to use computable approximations K_~(s) to K(s). Usually, to describe such an approximations, we take a compression algorithm and use the length of the compressed string as K_~(s). This approximation, however, is not perfect: e.g., for most compression algorithms, adding a single bit to the string $s$ can drastically change the value K_~(s) -- while …

A New Justification For Weighted Average Aggregation In Fuzzy Techniques, Jaime Nava

Departmental Technical Reports (CS)

In many practical situations, we need to decide whether a given solution is good enough, based on the degrees a_i to which different criteria are satisfied. In this paper, we show that natural requirements lead to the weighted average decision, according to which a solution is acceptable if w₁ * a₁ + ... + w_n * a_n > t for some weights w_i and threshold t.

Computation In Quantum Space-Time Could Lead To A Super-Polynomial Speedup, Vladik Kreinovich, Michael Zakharevich

Departmental Technical Reports (CS)

How To Tell When A Product Of Two Partially Ordered Spaces Has A Certain Property?, Francisco Zapata, Olga Kosheleva, Karen Villaverde

Departmental Technical Reports (CS)

In this paper, we describe how checking whether a givenproperty F is true for a product A₁ X A₂ of partiallyordered spaces can be reduced to checking several relatedproperties of the original spaces A_i.

This result can be useful in the analysis of propertiesof intervals [a,b] = {x: a <= x <= b}over general partially ordered spaces -- such as the spaceof all vectors with component-wise order or the set of allfunctions with component-wise ordering f <= g <-->for all x (f(x) <= g(x)). When we consider sets of pairs ofsuch objects A₁ X A₂, it is natural to define the orderon this set in terms of orders in A₁ and A₂ -- this is, e.g.,how ordering and intervals are defined on the set R² of all2-D vectors.

This result …

Theoretical Explanation Of Bernstein Polynomials' Efficiency: They Are Optimal Combination Of Optimal Endpoint-Related Functions, Jaime Nava, Vladik Kreinovich

Departmental Technical Reports (CS)

In many applications of interval computations, it turned out to be beneficial to represent polynomials on a given interval [x_-, x₊] as linear combinations of Bernstein polynomials (x- x _- )^k * (x₊ - x)^n-k. In this paper, we provide a theoretical explanation for this empirical success: namely, we show that under reasonable optimality criteria, Bernstein polynomials can be uniquely determined from the requirement that they are optimal combinations of optimal polynomials corresponding to the interval's endpoints.

Why Neural Networks Are Computationally Efficient Approximators: An Explanation, Jaime Nava, Vladik Kreinovich

Departmental Technical Reports (CS)

Many real-life dependencies can be reasonably accurately described by linear functions. If we want a more accurate description, we need to take non-linear terms into account. To take nonlinear terms into account, we can either explicitly add quadratic terms to the regression equation, or, alternatively, we can use a neural network with a non-linear activation function. At first glance, regression algorithms would work faster, but in practice, often, a neural network approximation turns out to be a more computationally efficient one. In this paper, we provide a reasonable explanation for this empirical fact.

Towards Fast And Accurate Algorithms For Processing Fuzzy Data: Interval Computations Revisited, Gang Xiang, Vladik Kreinovich

Departmental Technical Reports (CS)

Maximum Likelihood Approach To Pointwise Estimation In Statistical Data Processing Under Interval Uncertainty, Nitaya Buntao, Sa-Aat Niwitpong, Vladik Kreinovich

Departmental Technical Reports (CS)

Traditional statistical estimates C(x₁, ..., x_n) for different statistical characteristics (such as mean, variance, etc.) implicitly assume that we know the sample values x₁, ..., x_n exactly. In practice, the sample values X_i come from measurements and are, therefore, in general, different from the actual (unknown) values X_i of the corresponding quantities. Sometimes, we know the probabilities of different values of the measurement error ΔX_i = X_i - x_i, but often, the only information that we have about the measurement error is the upper bound Δ_{i …}

Why Fuzzy Transform Is Efficient In Large-Scale Prediction Problems: A Theoretical Explanation, Irina Perfilieva, Vladik Kreinovich

Departmental Technical Reports (CS)

Tropical (Idempotent) Algebras As A Way To Optimize Fuzzy Control, Jaime Nava

Departmental Technical Reports (CS)

Fuzzy control is a methodology that transforms control rules (described by an expert in words of a natural language) into a precise control strategy. There exist several versions of this transformation. The main difference between these versions is in how they interpret logical connectives "and" and "or", i.e., in other words, what reasoning method a version uses. Which of these versions should we choose? It turns out that on different stages of control, different reasoning methods lead to better control results. In this paper, we describe the choice of reasoning methods that optimize control results in terms of smoothness and …

Processing Interval Sensor Data In The Presence Of Outliers, With Potential Applications To Localizing Underwater Robots, Jan Sliwka, Luc Jaulin, Martine Ceberio, Vladik Kreinovich

Departmental Technical Reports (CS)

Measurements are never absolutely accurate, the measurement result X is, in general, different from the actual (unknown) values x of the corresponding quantity. In many practical problems, we only know upper bounds D on the measurement errors d = X - x. In such situations, once we know the measurement result, the only conclusion that we can make about the actual value x is that this value belongs to the interval [X - D, X + D]. There exist many efficient algorithms for processing such interval data. However, these algorithms usually assume that all the measurement results are valid. In …

Towards A "Generic" Notion Of Genericity: From "Typical" And "Random" To Meager, Shy, Etc., Ali Jalal-Kamali, Ondrej Nebesky, Michael H. Durcholz, Vladik Kreinovich, Luc Longpre

Departmental Technical Reports (CS)

In many application areas, it is important to study "generic" properties, i.e., properties which hold for ``typical'' examples. For example, if we know the probabilities of different events, we can consider a "random" object -- i.e., an object that, crudely speaking, does not belong to any class of "unusual" events (i.e., to any class with a small probability). In other cases, "typical" may mean not belonging to an "unusual" subset which is small in some other sense -- e.g., a subset of a smaller dimension. The corresponding notion of "typicalness" has been formalized for several cases, including the case of …

Is It Possible To Have A Feasible Enclosure-Computing Method Which Is Independent Of The Equivalent Form?, Marcin Michalak, Vladik Kreinovich

Departmental Technical Reports (CS)

The problem of computing the range [y] of a given function f(x1, ..., xn) over given intervals [xi] -- often called the main problem of interval computations -- is, in general, NP-hard. This means that unless P = NP, it is not possible to have a feasible (= polynomial time) algorithm that always computes the desired range. Instead, interval computations algorithms compute an enclosure [Y] for the desired range. For all known feasible enclosure-computing methods -- starting with straightforward interval computations -- there exist two expressions f(x1, ..., xn) and g(x1, ..., xn) for computing the same function that lead …

Estimating Probability Of Failure Of A Complex System Based On Inexact Information About Subsystems And Components, With Potential Applications To Aircraft Maintenance, Vladik Kreinovich, Christelle Jacob, Didier Dubois, Janette Cardoso, Martine Ceberio, Ildar Batyrshin

Departmental Technical Reports (CS)

In many real-life applications (e.g., in aircraft maintenance), we need to estimate the probability of failure of a complex system (such as an aircraft as a whole or one of its subsystems). Complex systems are usually built with redundancy allowing them to withstand the failure of a small number of components. In this paper, we assume that we know the structure of the system, and, as a result, for each possible set of failed components, we can tell whether this set will lead to a system failure. For each component A, we know the probability P(A) of its failure with …

Product Of Partially Ordered Sets (Posets), With Potential Applications To Uncertainty Logic And Space-Time Geometry, Francisco Zapata, Olga Kosheleva, Karen Villaverde

Departmental Technical Reports (CS)

Orthogonal Bases Are The Best: A Theorem Justifying Bruno Apolloni's Heuristic Neural Network Idea, Jaime Nava, Vladik Kreinovich

Departmental Technical Reports (CS)

One of the main problems with neural networks is that they are often very slow in learning the desired dependence. To speed up neural networks, Bruno Apolloni proposed to othogonalize neurons during training, i.e., to select neurons whose output functions are orthogonal to each other. In this paper, we use symmetries to provide a theoretical explanation for this heuristic idea.