Computer Engineering Commons^™

Interval Computations As A Particular Case Of A General Scheme Involving Classes Of Probability Distributions, Scott Ferson, Lev Ginzburg, Vladik Kreinovich, Harry Schulte

Departmental Technical Reports (CS)

Traditionally, in science and engineering, measurement uncertainty is characterized by a probability distribution; however, we don't know this probability distribution exactly, so we must consider classes of probability distributions. Interval computations deal with a very specific type of such classes: classes of all distributions which are located on a given interval. We show that in general, we need all convex classes of probability distributions.

1st Order, 2nd Order, What Next? Do We Really Need Third-Order Descriptions: A View From A Realistic (Granular) Viewpoint, Vladik Kreinovich, Hung T. Nguyen

Departmental Technical Reports (CS)

To describe experts' uncertainty in a knowledge-based system, we usually use numbers from the interval [0,1] (subjective probabilities, degrees of certainty, etc.). The most direct way to get these numbers is to ask the expert; however, the expert may not be 100\% certain what exactly number describes his uncertainty; so, we end up with a second-order uncertainty - a degree of certainty describing to what extent a given number d adequately describes the expert's uncertainty about a given statement A. At first glance, it looks like we should not stop at this second order: the expert is probably as uncertain …

Computing The Shape Of The Image Of A Multi-Linear Mapping Is Possible But Computationally Intractable: Theorems, Raul A. Trejo, Vladik Kreinovich

Departmental Technical Reports (CS)

In systems without inertia (or with negligible inertia), a change in the values of control variables x1,...,xn leads to the immediate change in the state z of the system. In more precise terms, for such systems, every component zi of the state vector z=(z1,...,zd) is a function of the control variables. When we know what state z we want to achieve, the natural question is: can we achieve this state, i.e., are there values of the control variables which lead to this very state?

The simplest possible functional dependence is described by linear functions. For such functions, the question of …

An Even More Realistic (Non-Associative) Interval Logic And Its Relation To Psychology Of Human Reasoning, I. R. Goodman, Raul Trejo, Vladik Kreinovich, Jesus Martinez, Reginaldo Gonzalez

Departmental Technical Reports (CS)

No abstract provided.

Why Unary And Binary Operations In Logic: General Result Motivated By Interval-Valued Logics, Hung T. Nguyen, Vladik Kreinovich, I. R. Goodman

Departmental Technical Reports (CS)

Traditionally, in logic, only unary and binary operations are used as basic ones - e.g., "not", "and", "or" - while the only ternary (and higher order) operations are the operations which come from a combination of unary and binary ones. For the classical logic, with the binary set of truth values {0,1}, the possibility to express an arbitrary operation in terms of unary and binary ones is well known: it follows, e.g., from the well known possibility to express an arbitrary operation in DNF form. A similar representation result for [0,1]-based logic was proven in our previous paper. In this …

How To Make Sure That "~100" + 1 Is ~100 In Fuzzy Arithmetic: Solution And Its (Inevitable) Drawbacks, Vladik Kreinovich, Hung T. Nguyen, Witold Pedrycz

Departmental Technical Reports (CS)

From the commonsense viewpoint, if a person who weighs around 100 kilograms gains one more kilogram, his weight is still around 100 kilograms. Alas, not so in traditional fuzzy arithmetic. In this paper, we propose a modification of fuzzy arithmetic which does have this property. We gain the desired property, but there is no free lunch, we have to lose two important properties of the traditional fuzzy arithmetic: first, addition is no longer always associative; second, addition is no longer always easily computable.

What Is The Best Way To Draw A Cube? A Hypercube?, Brian D'Auriol, Vladik Kreinovich, Bindu George, Florence Muganda, Pramod Kumar Chikkpaiah

Departmental Technical Reports (CS)

One of the possible connections between processors is a hypercube. The simplest case of a hypercube - a 4-vertex square - can be naturally represented on a 2-D page. To represent a 3-dimensional (or higher-dimensional) hypercube, we must project additional dimensions onto a 2-D page. In general, when we project a multi-D space into a 2-D plane, different points project into the same one. To get the best visualization, we must select a projection in such a way that the projections of different points are as distant from each other as possible. In this paper, we formalize and solve the …

On Fusion Of Soft And Hard Computing: Traditional ("Hard Computing") Optimal Rescaling Techniques Simplify Fuzzy Control, Hugh F. Vanlandingham, Vladik Kreinovich

Departmental Technical Reports (CS)

One of the main objectives of fuzzy control is to translate expert rules - formulated in imprecise ("fuzzy") words from natural language - into a precise control strategy. This translation is usually done is two steps. First, we apply a fuzzy control methodology to get a rough approximation to the expert's control strategy, and then we tune the resulting fuzzy control system. The first step (getting a rough approximation) is well-analyzed, and the fact that we have expert's intuitive understanding enables us to use soft computing techniques to perform this step. The second (tuning) step is much more difficult: we …

The Prospect For Answer Sets Computation By A Genetic Model, A. Bertoni, G. Grossi, A. Provetti, Vladik Kreinovich, L. Tari

Departmental Technical Reports (CS)

We combine recent results from both Logic Programming and Genetic Algorithms to design a new method for the efficent computation of Answer Sets of logic programs. First of all the problem is reduced to the problem of finding a suitable coloring on directed graphs. Then the problem of finding a suitable coloring is relaxed to a combinatorial optimization problem and solved (in an approximate way) by a continuous discrete time system derived by a genetic model.

Itanium's New Basic Operation Of Fused Multiply-Add: Theoretical Explanation And Theoretical Challenge, Vladik Kreinovich

Departmental Technical Reports (CS)

A new Intel's 64-bit chip Itanium has a new instruction set which includes a fused multiply-add instruction x1+x2*x3. In this short article, we explain the empirical reasons behind the choice of this instruction, give possible theoretical explanation for this choice, and mention a related theoretical challenge.

Strassen's Algorithm Made (Somewhat) More Natural: A Pedagogical Remark, Ann Q. Gates, Vladik Kreinovich

Departmental Technical Reports (CS)

Strassen's 1969 algorithm for fast matrix multiplication is based on the possibility to multiply two 2 x 2 matrices A and B by using 7 multiplications instead of the usual 8. The corresponding formulas are an important part of any algorithms course, but, unfortunately, even in the best textbook expositions. they look very ad hoc. In this paper, we show that the use of natural symmetries can make these formulas more natural.

Geombinatorics Of "Smart Dust", Edward Vidal, Luc Longpre, Vladik Kreinovich, Huang Haitao

Departmental Technical Reports (CS)

Smart Dust is a collection of small sensor-equipped leaves which send their information to two or more receivers. When a receiver gets a signal from a sensor, it can determine the direction from which this signal came. By combining the directions from two different receivers, we can determine the 3-D locations of all the leaves, and thus, transform their sensor readings into a 3-D picture of the corresponding parameters (temperature, moisture, etc.). The more leaves we send, the more information we gather. However, since the direction can only be measured with a certain accuracy, when we send too many leaves, …

Aerospace Applications Of Soft Computing And Interval Computations (With An Emphasis On Simulation And Modeling), Scott A. Starks, Vladik Kreinovich

Departmental Technical Reports (CS)

This paper presents a brief overview of our research in applications of soft computing and interval computations to aerospace problems, with a special emphasis on simulation and modeling.

Optimal Elimination Of Inconsistency In Expert Knowledge: Formulation Of The Problem, Fast Algorithms, Timothy J. Ross, Berlin Wu, Vladik Kreinovich

Departmental Technical Reports (CS)

Expert knowledge is sometimes inconsistent. In this paper, we describe the problem of eliminating this inconsistency as an optimization problem, and present fast algorithms for solving this problem.

On Approximation Of Fuzzy Sets By Crisp Sets: From Continuous Control-Oriented Defuzzification To Discrete Decision Making, Hung T. Nguyen, Witold Pedrycz, Vladik Kreinovich

Departmental Technical Reports (CS)

In this paper, we show that the necessity to make crisp decisions in uncertain (fuzzy) situations leads to the necessity to "approximate" fuzzy sets by crisp sets. We show that seemingly natural approximation ideas - such as using alpha-cut for a given alpha - often do not work, and we describe new approximations which not only work, but which are optimal in some reasonable sense

Fuzzy Logic And Its Applications In Medicine, Nguyen Hoang Phuong, Vladik Kreinovich

Departmental Technical Reports (CS)

Fuzzy set theory and fuzzy logic are a highly suitable and applicable basis for developing knowledge-based systems in medicine for tasks such as the interpretation of sets of medical findings, syndrome differentiation in Eastern medicine, diagnosis of diseases in Western medicine, mixed diagnosis of Integrated western and Eastern medicine, the optimal selection of medical treatments integrating western and eastern medicine, and for real-time monitoring of patient data etc. This was verified by trials with the following systems which were developed by our group in Vietnam: a fuzzy Expert System for Syndromes Differentiation in Oriental Traditional Medicine, an Expert System for …

On The Optimal Choice Of Quality Metric In Image Compression A Soft Computing Approach, Hung T. Nguyen, Olga Kosheleva, Vladik Kreinovich, Liya Ding

Departmental Technical Reports (CS)

In a lossy compression, the reconstructed image I' differs from the original image I. In different situations, different compressions lead to different quality reconstruction, so it is important to select, in each situation, the best compression method. It's natural to select the compression method for which the average value of some quality metric d(I,I') is the smallest. Which quality metric should we choose? We show that under reasonable symmetry conditions, L^p metrics d(I,I')=integral of |I(x)-I'(x)|^p are the best, and how to compute the optimal value of p from the expected relative size of the informative part of the image.

Computational Complexity Of Planning And Approximate Planning In Presence Of Incompleteness, Chitta Baral, Vladik Kreinovich, Raul Trejo

Departmental Technical Reports (CS)

In the last several years, there have been several studies about the computational complexity of classical planning assuming that the planner has complete knowledge about the initial situation. Recently, there has been proposal to use "sensing" actions to plan in presence of incompleteness. In this paper we study the complexity of planning in such cases. In our study we use the action description language A proposed in 1991 by Gelfond and Lifschitz, and its extensions.

It is known that if we consider only plans of feasible (polynomial) length, planning - with complete information about the initial situation - in A …

Why 95% And Two Sigma? A Theoretical Justification For An Empirical Measurement Practice, Hung T. Nguyen, Vladik Kreinovich, Chin-Wang Tao

Departmental Technical Reports (CS)

The probability p(k) that the value of a random variable is far away from the mean (e.g. further than k standard deviations away) is so small that this possibility can be often safely ignored. It is desirable to select k for which the dependence of the probability p(k) on the distribution is the smallest possible. Empirically, this dependence is the smallest for k between 1.5 and 2.5. In this paper, we give a theoretical explanation for this empirical result.

On Representation And Approximation Of Operations In Boolean Algebras, I. R. Goodman, Vladik Kreinovich

Departmental Technical Reports (CS)

Several universal approximation and universal representation results are known for non-Boolean multi-valued logics such as fuzzy logics. In this paper, we show that similar results can be proven for multi-valued Boolean logics as well.

Extracting Fuzzy Sparse Rule Base By Cartesian Representation And Clustering, Yeung Yam, Vladik Kreinovich, Hung T. Nguyen

Departmental Technical Reports (CS)

Sparse rule base and interpolation have been proposed as possible solution to alleviate the geometric complexity problem of large fuzzy set. However, no formal method to extract sparse rule base is yet available. This paper combines the recently introduced Cartesian representation of membership functions and a mountain method-based clustering technique for extraction. A case study is included to demonstrate the effectiveness of the approach.

Asymptotically Optimal Algorithms For Weather Applications Of Smart Dust, Edward Vidal, Luc Longpre, Vladik Kreinovich, Huang Haitao, Yeung Yam

Departmental Technical Reports (CS)

No abstract provided.

On The Optimal Choice Of Quality Metric In Image Compression, Olga Kosheleva, Vladik Kreinovich, Yeung Yam

Departmental Technical Reports (CS)

No abstract provided.

Towards Reliable Sub-Division Of Geological Areas: Interval Approach, David D. Coblentz, Vladik Kreinovich, Brian S. Penn, Scott A. Starks

Departmental Technical Reports (CS)

An appropriate subdivision of a geophysical area into segments enables us to extrapolate the results obtained in some locations within the segment (where extensive research was done) to other locations within the same segment, and thus, get a good understanding of the locations which weren't thoroughly analyzed.

Often, different evidence and different experts' intuition support different subdivisions schemes. For example, in our area - Rio Grande rift zone - there is some geochemical evidence that this zone is divided into three segments, but, in the viewpoint of many researchers, this evidence is not yet sufficiently convincing.

We show that if …

Some Practical Applications Of Soft Computing And Data Mining, Hung T. Nguyen, Nadipuram R. Prasad, Vladik Kreinovich, Habib Gassoumi

Departmental Technical Reports (CS)

Traditional data mining techniques mainly deal with a search for patterns in traditional databases, where data consists of numbers and words. In many application areas, however, data is more complicated: real-life data is often obtained as an image from a camera rather than a few measurements. Furthermore, this image can also change dynamically. In this paper, we present several examples of how soft computing is related to mining such data.

A New Universal Approximation Result For Fuzzy Systems, Which Reflects Cnf-Dnf Duality, Irina Perfilieva, Vladik Kreinovich

Departmental Technical Reports (CS)

There are two main fuzzy system methodologies for translating expert rules into a logical formula: In Mamdani's methodology, we get a DNF formula (disjunction of conjunctions), and in a methodology which uses logical implications, we get, in effect, a CNF formula (conjunction of disjunctions). For both methodologies, universal approximation results have been proven which produce, for each approximated function f(x), two different approximating relations RDNF(x,y) and RCNF(x,y). Since in fuzzy logic, there is a known relation FCNF(x)<=FDNF(x) between CNF and DNF forms of a propositional formula F, it is reasonable to expect that we would be able to prove the existence of approximations for which a similar relation RCNF(x,y)<=RDNF(x,y) holds. Such existence is proved in our paper.

Integrating Domain Knowledge With Data: From Crisp To Probabilistic And Fuzzy Knowledge, Hung T. Nguyen, Vladik Kreinovich, Leonid Reznik

Departmental Technical Reports (CS)

It is well known that prior knowledge about the domain can improve (often drastically) the accuracy of the estimates of the physical quantities in comparison with the estimates which are solely based on the measurement results. In this paper, we show how a known method of integrating crisp domain knowledge with data can be (naturally) extended to the case when the domain knowledge is described in statistical or fuzzy terms.

How Important Is Theory For Practical Problems? A Partial Explanation Of Hartmanis' Observation, Vladik Kreinovich, Luc Longpre

Departmental Technical Reports (CS)

No abstract provided.

Granularity As An Optimal Approach To Uncertainty - A General Mathematical Idea With Applications To Sleep, Consumption, Traffic Control, Learning, Etc., Vladik Kreinovich, Hung T. Nguyen

Departmental Technical Reports (CS)

Traditional statistical and fuzzy approaches to describing uncertainty are continuous in the sense that we use a (potentially infinite) set of values from the interval [0,1] to characterize possible degrees of uncertainty. In reality, experts describe their degree of belief by using one of the finitely many words from natural language; in this sense, the actual description of expert uncertainty is granular.

In this paper, we show that in some reasonable sense, granularity is the optimal way of describing uncertainty. A similar mathematical idea explains similar "granularity" in such diverse areas as sleep, consumption, traffic control, and learning.

A New Graph Characteristic And Its Application To Numerical Computability, Frank Harary, Vladik Kreinovich, Luc Longpre

Departmental Technical Reports (CS)

Many traditional numerical algorithms include a step on which we check whether a given real number a is equal to 0. This checking is easy for rational numbers, but for constructive real numbers, whether a number is 0 or not is an algorithmically undecidable problem. It is therefore desirable to re-formulate the existing algorithms with as few such comparisons as possible. We describe a new graph characteristic; this characteristic describes how the number of comparisons in an algorithm can be reduced.