Computer Engineering Commons^™

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.

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 …

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 …

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 …

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 …

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 …

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 …

Chu Spaces: Towards New Justification For Fuzzy Heuristics, Nhu Nguyen, Hung T. Nguyen, Vladik Kreinovich

Departmental Technical Reports (CS)

We show that Chu spaces, a new formalism used to describe parallelism and information flow, provide uniform explanations for different choices of fuzzy methodology, such as choices of fuzzy logical operations, of membership functions, of defuzzification, etc.

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

Departmental Technical Reports (CS)

No abstract provided.

On Granularity In Fuzzy Logic: Minimum And Maximum Are The Only Absolutely Granular T-Norm And T-Conorm, Vladik Kreinovich, Bernadette Bouchon-Meunier

Departmental Technical Reports (CS)

No abstract provided.

Error Estimations For Indirect Measurements: Randomized Vs. Deterministic Algorithms For "Black-Box" Programs, Vladik Kreinovich, Raul A. Trejo

Departmental Technical Reports (CS)

In many real-life situations, it is very difficult or even impossible to directly measure the quantity y in which we are interested: e.g., we cannot directly measure a distance to a distant galaxy or the amount of oil in a given well. Since we cannot measure such quantities directly, we can measure them indirectly: by first measuring some relating quantities x1,...,xn, and then by using the known relation between xi and y to reconstruct the value of the desired quantity y.

In practice, it is often very important to estimate the error of the resulting indirect measurement. In this paper, …

Choosing A Physical Model: Why Symmetries?, Raul A. Trejo, Vladik Kreinovich, Luc Longpre

Departmental Technical Reports (CS)

No abstract provided.

Which Sensor Set Is Better For Monitoring Spacecraft Subsystems? A Geometric Answer And Its Probabilistic Generalization, Matthew Barry, Vladik Kreinovich

Departmental Technical Reports (CS)

Each Space Shuttle mission produces more than 25,000 real-time measurements in NASA's mission control center. Within the mission control center, dozens of computer programs analyze these measurements and present results to mission control personnel. Because these programs support the practice of human-in-the-loop control, they serve primarily to present information to mission controllers. The controller's job is to interpret the displayed information to monitor spacecraft and astronaut performance, taking decisions and control actions when necessary for mission success or crew safety.

A single mission controller clearly cannot monitor all 25,000 real-time measurements. The experience of human space flight has evolved into …

Intelligent Mining In Image Databases, With Applications To Satellite Imaging And To Web Search, Stephen Gibson, Vladik Kreinovich, Luc Longpre, Brian Penn, Scott A. Starks

Departmental Technical Reports (CS)

An important part of our knowledge is in the form of images. For example, a large amount of geophysical and environmental data comes from satellite photos, a large amount of the information stored on the Web is in the form of images, etc. It is therefore desirable to use this image information in data mining. Unfortunately, most existing data mining techniques have been designed for mining numerical data and are thus not well suited for image databases. Hence, new methods are needed for image mining. In this paper, we show how data mining can be used to find common patterns …

Discrete (Granular) Logics: A New (Natural) Notion Of Continuity, With A Complete Description Of All Continuous Granular Logics, Hung T. Nguyen, Vladik Kreinovich

Departmental Technical Reports (CS)

In most knowledge-based systems, the experts' uncertainty is described by a real number from the interval [0,1] (this number is called subjective probability, degree of certainty, etc.). However, experts usually use a small finite set of words to describe their degree of unecratinty; thus, to adequately describe the expert's optinion, it is desirable to use a finite (granular) logic. If all we know about the expert's opinion on two statements A and B is this expert's degrees of certainty d(A) and d(B) in these two statements, and the user asks a query "A and B?", then we need to estimate …

Complex Fuzzy Sets: Towards New Foundations, Hung T. Nguyen, Abraham Kandel, Vladik Kreinovich

Departmental Technical Reports (CS)

Uncertainty of complex-valued physical quantities z=x+iy can be described by complex fuzzy sets. Such sets can be described by membership functions m(x,y) which map the universe of discourse (complex plane) into the interval [0,1]. The problem with this description is that it is difficult to directly translate into words from natural language. To make this translation easier, several authors have proposed to use, instead of a single membership function for describing the complex number, several membership functions which describe different real-valued characteristics of this numbers, such as its real part, its imaginary part, its absolute value, etc. The quality of …

Aircraft Integrity And Reliability, Carlos M. Ferregut, Roberto A. Osegueda, Yohanz Mendoza, Vladik Kreinovich, Timothy J. Ross

Departmental Technical Reports (CS)

In his recent paper "Probability theory needs an infusion of fuzzy logic to enhance its ability to deal with real-world problems", L. A. Zadeh explains that probability theory needs an infusion of fuzzy logic to enhance its ability to deal with real-world problems. In this paper, we give an example of a real-world problem for which such an infusion is indeed successful: the problems of aircraft integrity and reliability.

Computational Complexity Of Planning, Diagnosis, And Diagnostic Planning In The Presence Of Static Causal Laws, Chitta Baral, Le Chi Tuan, 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 the result res(a,s) of applying an action a to a system in a state s is uniquely determined by the action a and by the state s. In real-life planning, some consequences of certain actions are non-deterministic. In this paper, we expand the known results about computational complexity of planning (with …

Invariance-Based Justification Of The Maximum Entropy Method And Of Generalized Maximum Entropy Methods In Data Processing, Hung T. Nguyen, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

Maximum entropy method and its generalizations are very useful in data processing. In this paper, we show that these methods naturally follow from reasonable invariance requirements.

Shadows Of Fuzzy Sets - A Natural Approach Towards Describing 2-D And Multi-D Fuzzy Uncertainty In Linguistic Terms, Hung T. Nguyen, Berlin Wu, Vladik Kreinovich

Departmental Technical Reports (CS)

Fuzzy information processing systems start with expert knowledge which is usually formulated in terms of words from natural language. This knowledge is then usually reformulated in computer-friendly terms of membership functions, and the system transform these input membership functions into the membership functions which describe the result of fuzzy data processing. It is then desirable to translate this fuzzy information back from the computer-friendly membership functions language to the human-friendly natural language. In general, this is difficult even in a 1-D case, when we are interested in a single quantity y; however, the fuzzy research community has accumulated some expertise …

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.

Intervals (Pairs Of Fuzzy Values), Triples, Etc.: Can We Thus Get An Arbitrary Ordering?, Vladik Kreinovich, Masao Mukaidono

Departmental Technical Reports (CS)

Traditional fuzzy logic uses real numbers as truth values. This description is not always adequate, so in interval-valued fuzzy logic, we use pairs (t-,t+) of real numbers, t-<=t+, to describe a truth value. To make this description even more adequate, instead of using real numbers to described each value t- and t+, we can use intervals, and thus get fuzzy values which can be described by 4 real numbers each. We can iterate this procedure again and again. The question is: can we get an arbitrary partially ordered set in this manner? An arbitrary lattice? In this paper, we show that although we cannot thus generate arbitrary lattices, we can actually generate an arbitrary partially ordered set in this manner. In this sense, the "intervalization" operation is indeed universal.

Aerospace Applications Of Soft Computing And Interval Computations (With An Emphasis On Multi-Spectral Satellite Imaging), 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 multi-spectralsatellite imaging.

For Interval Computations, If Absolute-Accuracy Optimization Is Np-Hard, Then So Is Relative-Accuracy Optimization, Vladik Kreinovich

Departmental Technical Reports (CS)

One of the basic problems of interval computations is to compute a range of a given function f(x1,...,xn) over a given box (i.e., to compute the maximum and the minimum of the function on the box). For many classes of functions (e.g., for quadratic functions) this problem is NP-hard; it is even NP-hard if instead of computing the minimum and maximum exactly, we want to compute them with a given (absolute) accuracy. In practical situations, it is more realistic to ask for a relative accuracy; are the corresponding problems still NP-hard? We show that under some reasonable conditions, NP-hardness of …

Geombinatoric Aspects Of Processing Large Images And Large Spatial Databases, Jan Beck, Vladik Kreinovich, Brian Penn

Departmental Technical Reports (CS)

Computer processing can drastically improve the quality of an image and the reliability and accuracy of a spatial database. A large image (database) does not easily fit into the computer memory, so we process it by downloading pieces of the image. Each downloading takes a lot of time, so, to speed up the entire processing, we must use as few pieces as possible.

Many algorithms for processing images and spatial databases consist of comparing the value at a certain spatial location with values at nearby locations. For such algorithms, we must select (possibly overlapping) sub-images in such a way that …

An Optimal Fft-Based Algorithm For Mosaicking Images, With Applications To Satellite Imaging And Web Search, Stephen Gibson, Olga Kosheleva, Luc Longpre, Brian Penn, Scott A. Starks

Departmental Technical Reports (CS)

Digital data storage is becoming ever more abundant and cheap. This, along with other technological advances, has brought about an age of mass storage of information, much of it in the form of images. In order to be able to process these stockpiles of image data, new and faster computer algorithms are needed.

One area of interest is that of image mosaicking, i.e., comparing two overlapping images and finding the proper scaling, angle of rotation, and translation needed to fit one with the other. Early methods for mosaicking images included visual inspection or exhaustive, pixel by pixel, search for the …

Towards Mathematical Foundations Of Information Retrieval: Dependence Of Website's Relevance On The Number Of Occurrences Of A Queried Word, Laszlo Koczy, Vladik Kreinovich, Yohanz Mendoza, Hung T. Nguyen, Harry Schulte

Departmental Technical Reports (CS)

In response to a query, web search tools often return many websites which are not really relevant. One reason for this is that the queried word may have several meanings different to the one which the user has in mind. To eliminate these undesirable meanings, it is reasonable to look for occurrences not only of the queried word itself, but also for other words related to this particular meaning, and then select only the websites for which, based on this information, we are confident about their relevance. For this strategy to work, we must be able to estimate the degree …

Candidate Sets For Complex Interval Arithmetic, Juergen Wolff Von Gundenberg, Vladik Kreinovich

Departmental Technical Reports (CS)

Uncertainty of measuring complex-valued physical quantities can be described by complex sets. These sets can have complicated shapes, so we would like to find a good approximating family of sets. Which approximating family is the best? We reduce the corresponding optimization problem to a geometric one: namely, we prove that, under some reasonable conditions, an optimal family must be shift-, rotation- and scale-invariant. We then use this geometric reduction to conclude that the best approximating low-dimensional families consist of sets with linear or circular boundaries. This result is consistent with the fact that such sets have indeed been successful in …

A Geometric Approach To Classification Of Trash In Ginned Cotton, Murali Siddaiah, Michael A. Lieberman, Nadipuram R. Prasad, Vladik Kreinovich

Departmental Technical Reports (CS)

This paper discusses the use of geometric approach to classify different types of trash (non-lint, non-fiber material) in ginned cotton. Pieces of trash can have complicated shapes, so we would like to find a good approximating family of sets. Which approximating family is the best? We reduce the corresponding optimization problem to a geometric one: namely, we show that, under some reasonable conditions, an optimal family must be shift-, rotation- and scale-invariant. We then use this geometric reduction to conclude that the best approximating low-dimensional families consist of sets with linear or circular boundaries.

This result is in good agreement …