Engineering Commons^™

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.

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

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 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.

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 …

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.

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.

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.

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.

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 …

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

Departmental Technical Reports (CS)

No abstract provided.

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.

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.

Computational Complexity Of Planning Based On Partial Information About The System's Present And Past States, Chitta Baral, Le Chi Tuan, Raul A. Trejo, Vladik Kreinovich

Departmental Technical Reports (CS)

Planning is a very important AI problem, and it is also a very time-consuming AI problem. To get an idea of how complex different planning problems are, it is useful to describe the computational complexity of different general planning problems. This complexity has been described for problems in which planning is based on the (complete or partial) information about the current state of the system. In real-life planning, in addition to this information, we often also use the knowledge about the system's past behavior. To describe such more realistic planning situations, a special language L was developed in 1997 by …

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.

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.

The Use Of Fuzzy Measures In Pain Relief Control, Vladik Kreinovich, Nadipuram R. Prasad

Departmental Technical Reports (CS)

Many people suffer from a continuous strong pain which is caused solely by the malfunction of the pain mechanism itself. One way to ease their pain is to electrically stimulate the spinal cord. Since the equations of pain are not known, we must use heuristic methods to find the optimal pain relief stimulation. In this paper, we show how fuzzy measures and similar nonlinear models can be used in pain relief control: they can be used to determine the parameters of the model which describes the dependence of the pain relief on the applied stimulation. Thus, fuzzy measures lead to …

A Comment On The Shape Of The Solution Set For Systems Of Interval Linear Equations With Dependent Coefficients, Goetz Alefeld, Vladik Kreinovich, Guenter Mayer, Michael Huth

Departmental Technical Reports (CS)

This article is a short supplement to our previously published paper, in which we prove that each semialgebraic set can be represented as a projection of a solution set of some system of linear equations with dependent coefficients. The new results says that interval occurring can be chosen as narrow as wanted. This new result is proven by a simple linear transformation.

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

Departmental Technical Reports (CS)

No abstract provided.

Fuzzy (Granular) Levels Of Quality, With Applications To Data Mining And To Structural Integrity Of Aerospace Structures, Roberto A. Osegueda, Carlos Ferregut, Vladik Kreinovich, Seelam Seetharami, Harry Schulte

Departmental Technical Reports (CS)

Experts usually describe quality by using words from natural language such as "perfect", "good", etc. In this paper, we deduce natural numerical values corresponding to these words, and show that these values explain empirical dependencies uncovered in data mining and in the analysis of structural integrity of aerospace structures.

Why Two Sigma? A Theoretical Justification, Hung T. Nguyen, Vladik Kreinovich, Gennady N. Solopchencko, Ching-Wang Tao

Departmental Technical Reports (CS)

For a normal distribution, the probability density is everywhere positive, so in principle, all real numbers are possible. In reality, the probability that a random variable is far away from the mean is so small that this possibility can be often safely ignored. Usually, a small real number k is picked (e.g., 2 or 3); then, with a probability P0(k)~1 (depending on k), the normally distributed random variable with mean a and standard deviation sigma belongs to the interval A=[a-k*sigma,a+k*sigma].

The actual error distribution may be non-Gaussian; hence, the probability P(k) that a random variable belongs to A differs from …

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.

Towards Optimal Mosaicking Of Multi-Spectral Images, Francisco Garcia, Roberto Araiza, Brain Rzycki

Departmental Technical Reports (CS)

To cover a certain area, it is often necessary to combine several satellite photos. To get a proper combination, we need to appropriately position and orient these photos relative to one another, i.e., mosaic these photos. With the new generation of multi-spectral satellites, for each area, we have several hundred images which correspond to different wavelengths. At present, when we mosaic two images, we only use one of the wavelengths and ignore the information from the other wavelengths. It is reasonable to decrease the mosaicking error by using images corresponding to all possible wavelengths in mosaicking. In this paper, we …

Towards Feasible Approach To Plan Checking Under Probabilistic Uncertainty: Interval Methods, Raul A. Trejo, Vladik Kreinovich, Chitta Baral

Departmental Technical Reports (CS)

The main problem of planning is to find a sequence of actions that an agent must perform to achieve a given objective. An important part of planning is checking whether a given plan achieves the desired objective. Historically, in AI, the planning and plan checking problems were mainly formulated and solved in a deterministic environment, when the initial state is known precisely and when the results of each action in each state is known (and uniquely determined). In this deterministic case, planning is difficult, but plan checking is straightforward. In many real-life situations, we only know the probabilities of different …

Fundamental Properties Of Pair-Wise Interactions Naturally Lead To Quarks And Quark Confinement: A Theorem Motivated By Neural Universal Approximation Results, Vladik Kreinovich

Departmental Technical Reports (CS)

In traditional mechanics, most interactions are pair-wise; if we omit one of the particles from our description, then the original pair-wise interaction can sometimes only be represented as interaction between triples, etc. It turns out that, vice versa, every possible interaction between N particles can be represented as pair-wise interaction if we represent each of the original N particles as a triple of new ones (and two new ones are not enough for this representation). The resulting three "particles" actually represent a single directly observable particles and in this sense, cannot be separated. So, this representation gives a fundamental reason …

Allowing Two Moves In Succession Increases The Game's Bias: A Theorem, Vladik Kreinovich

Departmental Technical Reports (CS)

No abstract provided.