Engineering Commons^™

In The Beginning Was The Word, And The Word Was Fuzzy, Vladik Kreinovich

Departmental Technical Reports (CS)

No abstract provided.

Why Bernstein Polynomials Are Better: Fuzzy-Inspired Justification, Jaime Nava, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

It is well known that an arbitrary continuous function on a bounded set -- e.g., on an interval [a,b] -- can be, with any given accuracy, approximated by a polynomial. Usually, polynomials are described as linear combinations of monomials. It turns out that in many computational problems, it is more efficient to represent a polynomial as Bernstein polynomials -- e.g., for functions of one variable, a linear combination of terms (x-a)^k * (b-x)^n-k. In this paper, we provide a simple fuzzy-based explanation of why Bernstein polynomials are often more efficient, and we show how this informal explanation …

Constraint Optimization: From Efficient Computation Of What Can Be Achieved To Efficient Computation Of A Way To Achieve The Corresponding Optimum, Ali Jalal-Kamali, Martine Ceberio, Vladik Kreinovich

Departmental Technical Reports (CS)

In many practically useful cases, we know how to efficiently compute the exact range of a function over given intervals (and, possibly, under additional constraints). In other words, we know how to efficiently compute the minimum and maximum of a given function f(x₁, ..., x_n) on any box. From the practical viewpoint, it is important not only to find the value of the corresponding maximum or minimum, but also to know for what values of the parameters x_i this optimum is attained. We prove a general result: that if we can efficiently compute the optimum, …

Semi-Heuristic Poverty Measures Used By Economists: Justification Motivated By Fuzzy Techniques, Karen Villaverde, Nagwa Albehery, Tonghui Wang, Vladik Kreinovich

Departmental Technical Reports (CS)

To properly gauge the extent of poverty in a country or in a region, economists use semi-heuristic poverty measures such as the Foster-Greer-Thorbecke (FGT) metric. These measures are used because it was empirically shown that they capture the commonsense meaning of the extent of poverty better than previously proposed measures. However, the fact that these measures are better then a few earlier proposed ones does not necessarily mean that these measures are the best possible; so, it is desirable to look for optimal poverty measures. In this paper, we first use fuzzy techniques to provide a commonsense interpretation of FGT …

Assessment Of Functional Impairment In Human Locomotion: A Fuzzy-Motivated Approach, Murad Alaqtash, Thompson Sarkodie-Gyan, Vladik Kreinovich

Departmental Technical Reports (CS)

Many neurological disorders result in disordered motion. The effects of a disorder can be decrease by an appropriate rehabilitation. To make rehabilitation efficient, we need to monitor the patient and check how well he or she improves. In our previous papers, we proposed a fuzzy-based semi-heuristic method of gauging how well a patient improved. Surprisingly, this semi-heuristic method turned out to be more efficient that we expected. In this paper, we provide a justification for this efficiency.

In the future, it is desirable to combine this fuzzy-assessment approach with results by Alavarez-Alvarez, Trivino, and Cordon who use fuzzy techniques …

Efficient Approximation For Security Games With Interval Uncertainty, Chris Kiekintveld, Vladik Kreinovich

Departmental Technical Reports (CS)

There are an increasing number of applications of security games. One of the key challenges for this field going forward is to address the problem of model uncertainty and the robustness of the game-theoretic solutions. Most existing methods for dealing with payoff uncertainty are Bayesian methods which are NP-hard and have difficulty scaling to very large problems. In this work we consider an alternative approach based on interval uncertainty. For a variant of security games with interval uncertainty we introduce a polynomial-time approximation algorithm that can compute very accurate solutions within a given error bound.

Constraint Problems: Computability Is Equivalent To Continuity, Martine Ceberio, Vladik Kreinovich

Departmental Technical Reports (CS)

In many practical situations, we would like to compute the set of all possible values that satisfy given constraints. It is known that even for computable (constructive) constraints, computing such set is not always algorithmically possible. One reason for this algorithmic impossibility is that sometimes, the dependence of the desired set on the parameters of the problem is not continuous, while all computable functions of real variables are continuous. In this paper, we show that this discontinuity is the only case when the desired set cannot be computed. Specifically, we provide an algorithm that computes such a set for all …

Estimating Correlation Under Interval Uncertainty, Ali Jalal-Kamali, Vladik Kreinovich

Departmental Technical Reports (CS)

In many engineering situations, we are interested in finding the correlation ρ between different quantities x and y based on the values x_i and y_i of these quantities measured in different situations i. Measurements are never absolutely accurate; it is therefore necessary to take this inaccuracy into account when estimating the correlation ρ. Sometimes, we know the probabilities of different values of measurement errors, but in many cases, we only know the upper bounds Δ_xi and Δ_yi on the corresponding measurement errors. In such situations, after we get the measurement results X_i and Y_{i …}

Visko: Semantic Web Support For Information And Science Visualization, Nicholas Del Rio, Paulo Pinheiro Da Silva

Departmental Technical Reports (CS)

Towards Interval Techniques For Model Validation, Jaime Nava, Vladik Kreinovich

Departmental Technical Reports (CS)

Most physical models are approximate. It is therefore important to find out how accurate are the predictions of a given model. This can be done by validating the model, i.e., by comparing its predictions with the experimental data. In some practical situations, it is difficult to directly compare the predictions with the experimental data, since models usually contain (physically meaningful) parameters, and the exact values of these parameters are often not known. One way to overcome this difficulty is to get a statistical distribution of the corresponding parameters. Once we substitute these distributions into a model, we get statistical predictions …

Propagating Range (Uncertainty) And Continuity Information Through Computations: From Real-Valued Intervals To General Sets, Vladik Kreinovich

Departmental Technical Reports (CS)

One of the main problems of interval computations is to find an enclosure Y that contains the range f(X₁, ..., X_n) of a given function f(x₁, ..., x_n) over given intervals X₁, ..., X_n. Most of the techniques for estimating this range are based on propagating the range through computations. Specifically, we follow the computations of f(x₁, ..., x_n) step-by-step: we start with ranges X₁, ..., X_n of the inputs, and then we sequentially compute the enclosures for the ranges of …

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.

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 …

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, …

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

Departmental Technical Reports (CS)

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.

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 …

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 …

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.

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 …

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

Departmental Technical Reports (CS)

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 …

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.

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 …

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

Departmental Technical Reports (CS)

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 …

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, …

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.

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 …

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.