Engineering topics

Kreinovich, Vladik YA.

Publications and source records attributed to Kreinovich, Vladik YA..

11 records

NASA NTRS1993

Fast parallel algorithms that compute transitive closure of a fuzzy relation

The notion of a transitive closure of a fuzzy relation is very useful for clustering in pattern recognition, for fuzzy databases, etc. The original algorithm proposed by L. Zadeh (1971) requires the computation time O(n(sup 4)), where n is the number of elements in the relation. In 1974, J. C. Dunn proposed a O(n(sup 2)) algorithm. Since we must compute n(n-1)/2 different values s(a, b) (a not equal to b) that represent the fuzzy relation, and we need at least one computational step to compute each of these values, we cannot compute all of them in less than O(n(sup 2)) steps. So, Dunn's algorithm is in this sense optimal. For small n, it is ok. However, for big n (e.g., for big databases), it is still a lot, so it would be desirable to decrease the computation time (this problem was formulated by J. Bezdek). Since this decrease cannot be done on a sequential computer, the only way to do it is to use a computer with several processors working in parallel. We show that on a parallel computer, transitive closure can be computed in time O((log(sub 2)(n))2).

Kreinovich, Vladik YA.↗

NASA NTRS1992

Maximum entropy approach to fuzzy control

For the same expert knowledge, if one uses different &- and V-operations in a fuzzy control methodology, one ends up with different control strategies. Each choice of these operations restricts the set of possible control strategies. Since a wrong choice can lead to a low quality control, it is reasonable to try to loose as few possibilities as possible. This idea is formalized and it is shown that it leads to the choice of min(a + b,1) for V and min(a,b) for &. This choice was tried on NASA Shuttle simulator; it leads to a maximally stable control.

Ramer, Arthur↗

NASA NTRS1992

How to control if even experts are not sure: Robust fuzzy control

In real life, the degrees of certainty that correspond to one of the same expert can differ drastically, and fuzzy control algorithms translate these different degrees of uncertainty into different control strategies. In such situations, it is reasonable to choose a fuzzy control methodology that is the least vulnerable to this kind of uncertainty. It is shown that this 'robustness' demand leads to min and max for &- and V-operations, to 1-x for negation, and to centroid as a defuzzification procedure.

Nguyen, Hung T.↗

NASA NTRS1992

Strongly transitive fuzzy relations: A more adequate way to describe similarity

The notion of a transitive closure of a fuzzy relation is very useful for clustering in pattern recognition, for fuzzy databases, etc. It is based on translating the standard definition of transitivity and transitive closure into fuzzy terms. This definition works fine, but to some extent it does not fully capture our understanding of transitivity. The reason is that this definition is based on fuzzifying only the positive side of transitivity: if R(a,b) and R(b,c), then R(a,c); but transitivity also includes a negative side: if R(a,b) and not R(a,c), then not R(b,c). In classical logic, this negative statement follows from the standard 'positive' definition of transitivity. In fuzzy logic, this negative part of the transitivity has to be formulated as an additional demand. A strongly transitive fuzzy relation as the one that satisfies both the positive and the negative transitivity demands is defined, the existence of strongly transitive closure is proven, and the relationship between strongly transitive similarity and clustering are found.

Kreinovich, Vladik YA.↗

NASA NTRS1991

How to combine probabilistic and fuzzy uncertainties in fuzzy control

Fuzzy control is a methodology that translates natural-language rules, formulated by expert controllers, into the actual control strategy that can be implemented in an automated controller. In many cases, in addition to the experts' rules, additional statistical information about the system is known. It is explained how to use this additional information in fuzzy control methodology.

Nguyen, Hung T.↗

NASA NTRS1991

How far we are from the complete knowledge: Complexity of knowledge acquisition in Dempster-Shafer approach

When a knowledge base represents the experts' uncertainty, then it is reasonable to ask how far we are from the complete knowledge, that is, how many more questions do we have to ask (to these experts, to nature by means of experimenting, etc) in order to attain the complete knowledge. Of course, since we do not know what the real world is, we cannot get the precise number of questions from the very beginning: it is quite possible, for example, that we ask the right question first and thus guess the real state of the world after the first question. So we have to estimate this number and use this estimate as a natural measure of completeness for a given knowledge base. We give such estimates for Dempster-Shafer formalism. Namely, we show that this average number of questions can be obtained by solving a simple mathematical optimization problem. In principle this characteristic is not always sufficient to express the fact that sometimes we have more knowledge. For example, it has the same value if we have an event with two possible outcomes and nothing else is known, and if there is an additional knowledge that the probability of every outcome is 0.5. We'll show that from the practical viewpoint this is not a problem, because the difference between the necessary number of questions in both cases is practically negligible.

Chokr, Bassam A.↗

NASA NTRS1991

Monte-Carlo methods make Dempster-Shafer formalism feasible

One of the main obstacles to the applications of Dempster-Shafer formalism is its computational complexity. If we combine m different pieces of knowledge, then in general case we have to perform up to 2(sup m) computational steps, which for large m is infeasible. For several important cases algorithms with smaller running time were proposed. We prove, however, that if we want to compute the belief bel(Q) in any given query Q, then exponential time is inevitable. It is still inevitable, if we want to compute bel(Q) with given precision epsilon. This restriction corresponds to the natural idea that since initial masses are known only approximately, there is no sense in trying to compute bel(Q) precisely. A further idea is that there is always some doubt in the whole knowledge, so there is always a probability p(sub o) that the expert's knowledge is wrong. In view of that it is sufficient to have an algorithm that gives a correct answer a probability greater than 1-p(sub o). If we use the original Dempster's combination rule, this possibility diminishes the running time, but still leaves the problem infeasible in the general case. We show that for the alternative combination rules proposed by Smets and Yager feasible methods exist. We also show how these methods can be parallelized, and what parallelization model fits this problem best.

Kreinovich, Vladik YA.↗

NASA NTRS1991

How to help intelligent systems with different uncertainty representations cooperate with each other

In order to solve a complicated problem one must use the knowledge from different domains. Therefore, if one wants to automatize the solution of these problems, one has to help the knowledge-based systems that correspond to these domains cooperate, that is, communicate facts and conclusions to each other in the process of decision making. One of the main obstacles to such cooperation is the fact that different intelligent systems use different methods of knowledge acquisition and different methods and formalisms for uncertainty representation. So an interface f is needed, 'translating' the values x, y, which represent uncertainty of the experts' knowledge in one system, into the values f(x), f(y) appropriate for another one. The problem of designing such an interface as a mathematical problem is formulated and solved. It is shown that the interface must be fractionally linear: f(x) = (ax + b)/(cx + d).

Kreinovich, Vladik YA.↗

NASA NTRS1991

Neural networks: What non-linearity to choose

Neural networks are now one of the most successful learning formalisms. Neurons transform inputs (x(sub 1),...,x(sub n)) into an output f(w(sub 1)x(sub 1) + ... + w(sub n)x(sub n)), where f is a non-linear function and w, are adjustable weights. What f to choose? Usually the logistic function is chosen, but sometimes the use of different functions improves the practical efficiency of the network. The problem of choosing f as a mathematical optimization problem is formulated and solved under different optimality criteria. As a result, a list of functions f that are optimal under these criteria are determined. This list includes both the functions that were empirically proved to be the best for some problems, and some new functions that may be worth trying.

Kreinovich, Vladik YA.↗

NASA NTRS1991

What procedure to choose while designing a fuzzy control? Towards mathematical foundations of fuzzy control

Fuzzy control has been successfully applied in industrial systems. However, there is some caution in using it. The reason is that it is based on quite reasonable ideas, but each of these ideas can be implemented in several different ways, and depending on which of the implementations chosen different results are achieved. Some implementations lead to a high quality control, some of them not. And since there are no theoretical methods for choosing the implementation, the basic way to choose it now is experimental. But if one chooses a method that is good for several examples, there is no guarantee that it will work fine in all of them. Hence the caution. A theoretical basis for choosing the fuzzy control procedures is provided. In order to choose a procedure that transforms a fuzzy knowledge into a control, one needs, first, to choose a membership function for each of the fuzzy terms that the experts use, second, to choose operations of uncertainty values that corresponds to 'and' and 'or', and third, when a membership function for control is obtained, one must defuzzy it, that is, somehow generate a value of the control u that will be actually used. A general approach that will help to make all these choices is described: namely, it is proved that under reasonable assumptions membership functions should be linear or fractionally linear, defuzzification must be described by a centroid rule and describe all possible 'and' and 'or' operations. Thus, a theoretical explanation of the existing semi-heuristic choices is given and the basis for the further research on optimal fuzzy control is formulated.

Kreinovich, Vladik YA.↗

NASA NTRS1991

Arbitrary nonlinearity is sufficient to represent all functions by neural networks - A theorem

It is proved that if we have neurons implementing arbitrary linear functions and a neuron implementing one (arbitrary but smooth) nonlinear function g(x), then for every continuous function f(x sub 1,..., x sub m) of arbitrarily many variables, and for arbitrary e above 0, we can construct a network that consists of g-neurons and linear neurons, and computes f with precision e.

Kreinovich, Vladik YA.↗