Engineering Commons^™

Towards Fast And Accurate Algorithms For Processing Fuzzy Data: Interval Computations Revisited, Gang Xiang, Vladik Kreinovich

Departmental Technical Reports (CS)

Maximum Likelihood Approach To Pointwise Estimation In Statistical Data Processing Under Interval Uncertainty, Nitaya Buntao, Sa-Aat Niwitpong, Vladik Kreinovich

Departmental Technical Reports (CS)

Traditional statistical estimates C(x₁, ..., x_n) for different statistical characteristics (such as mean, variance, etc.) implicitly assume that we know the sample values x₁, ..., x_n exactly. In practice, the sample values X_i come from measurements and are, therefore, in general, different from the actual (unknown) values X_i of the corresponding quantities. Sometimes, we know the probabilities of different values of the measurement error ΔX_i = X_i - x_i, but often, the only information that we have about the measurement error is the upper bound Δ_{i …}

Why Neural Networks Are Computationally Efficient Approximators: An Explanation, Jaime Nava, Vladik Kreinovich

Departmental Technical Reports (CS)

Many real-life dependencies can be reasonably accurately described by linear functions. If we want a more accurate description, we need to take non-linear terms into account. To take nonlinear terms into account, we can either explicitly add quadratic terms to the regression equation, or, alternatively, we can use a neural network with a non-linear activation function. At first glance, regression algorithms would work faster, but in practice, often, a neural network approximation turns out to be a more computationally efficient one. In this paper, we provide a reasonable explanation for this empirical fact.

Processing Interval Sensor Data In The Presence Of Outliers, With Potential Applications To Localizing Underwater Robots, Jan Sliwka, Luc Jaulin, Martine Ceberio, Vladik Kreinovich

Departmental Technical Reports (CS)

Measurements are never absolutely accurate, the measurement result X is, in general, different from the actual (unknown) values x of the corresponding quantity. In many practical problems, we only know upper bounds D on the measurement errors d = X - x. In such situations, once we know the measurement result, the only conclusion that we can make about the actual value x is that this value belongs to the interval [X - D, X + D]. There exist many efficient algorithms for processing such interval data. However, these algorithms usually assume that all the measurement results are valid. In …

Why Fuzzy Transform Is Efficient In Large-Scale Prediction Problems: A Theoretical Explanation, Irina Perfilieva, Vladik Kreinovich

Departmental Technical Reports (CS)

Estimating Mean And Variance Under Interval Uncertainty: Dynamic Case, Rafik Aliev, Vladik Kreinovich

Departmental Technical Reports (CS)

In many practical situations, it is important to estimate themean E and the variance V from the sample valuesx₁, ..., x_n. Usually, in statistics,we consider the case when the parameters like E and V do not change with timeand when the sample values x_i are known exactly. Inpractice, the values x_icome from measurements, andmeasurements are never 100% accurate. In many cases, we onlyknow the upper bound D_i on the measurement error. Inthis case, once we know the measured value X_i, wecan conclude that the actual (unknown) value x_i belongs …

Product Of Partially Ordered Sets (Posets), With Potential Applications To Uncertainty Logic And Space-Time Geometry, Francisco Zapata, Olga Kosheleva, Karen Villaverde

Departmental Technical Reports (CS)

Dynamic Fuzzy Logic Leads To More Adequate "And" And "Or" Operations, Vladik Kreinovich

Departmental Technical Reports (CS)

In the traditional (static) fuzzy logic approach, we select an "and"-operation (t-norm) and an "or"-operation (t-conorm). The result of applying these selected operations may be somewhat different from the actual expert's degrees of belief in the corresponding logical combinations A & B and A \/ B of the original statements -- since these degrees depend not only on the expert's degrees of belief in statements A and B, but also in the extent to which the statements A and B are dependent. We show that dynamic fuzzy logic enables us to automatically take this dependence into account -- and thus, …

Estimating Probability Of Failure Of A Complex System Based On Inexact Information About Subsystems And Components, With Potential Applications To Aircraft Maintenance, Vladik Kreinovich, Christelle Jacob, Didier Dubois, Janette Cardoso, Martine Ceberio, Ildar Batyrshin

Departmental Technical Reports (CS)

In many real-life applications (e.g., in aircraft maintenance), we need to estimate the probability of failure of a complex system (such as an aircraft as a whole or one of its subsystems). Complex systems are usually built with redundancy allowing them to withstand the failure of a small number of components. In this paper, we assume that we know the structure of the system, and, as a result, for each possible set of failed components, we can tell whether this set will lead to a system failure. For each component A, we know the probability P(A) of its failure with …

Tropical (Idempotent) Algebras As A Way To Optimize Fuzzy Control, Jaime Nava

Departmental Technical Reports (CS)

Fuzzy control is a methodology that transforms control rules (described by an expert in words of a natural language) into a precise control strategy. There exist several versions of this transformation. The main difference between these versions is in how they interpret logical connectives "and" and "or", i.e., in other words, what reasoning method a version uses. Which of these versions should we choose? It turns out that on different stages of control, different reasoning methods lead to better control results. In this paper, we describe the choice of reasoning methods that optimize control results in terms of smoothness and …

Is It Possible To Have A Feasible Enclosure-Computing Method Which Is Independent Of The Equivalent Form?, Marcin Michalak, Vladik Kreinovich

Departmental Technical Reports (CS)

The problem of computing the range [y] of a given function f(x1, ..., xn) over given intervals [xi] -- often called the main problem of interval computations -- is, in general, NP-hard. This means that unless P = NP, it is not possible to have a feasible (= polynomial time) algorithm that always computes the desired range. Instead, interval computations algorithms compute an enclosure [Y] for the desired range. For all known feasible enclosure-computing methods -- starting with straightforward interval computations -- there exist two expressions f(x1, ..., xn) and g(x1, ..., xn) for computing the same function that lead …

Towards A "Generic" Notion Of Genericity: From "Typical" And "Random" To Meager, Shy, Etc., Ali Jalal-Kamali, Ondrej Nebesky, Michael H. Durcholz, Vladik Kreinovich, Luc Longpre

Departmental Technical Reports (CS)

In many application areas, it is important to study "generic" properties, i.e., properties which hold for ``typical'' examples. For example, if we know the probabilities of different events, we can consider a "random" object -- i.e., an object that, crudely speaking, does not belong to any class of "unusual" events (i.e., to any class with a small probability). In other cases, "typical" may mean not belonging to an "unusual" subset which is small in some other sense -- e.g., a subset of a smaller dimension. The corresponding notion of "typicalness" has been formalized for several cases, including the case of …

Orthogonal Bases Are The Best: A Theorem Justifying Bruno Apolloni's Heuristic Neural Network Idea, Jaime Nava, Vladik Kreinovich

Departmental Technical Reports (CS)

One of the main problems with neural networks is that they are often very slow in learning the desired dependence. To speed up neural networks, Bruno Apolloni proposed to othogonalize neurons during training, i.e., to select neurons whose output functions are orthogonal to each other. In this paper, we use symmetries to provide a theoretical explanation for this heuristic idea.

Uniqueness Of Reconstruction For Yager's T-Norm Combination Of Probabilistic And Possibilistic Knowledge, Nitaya Buntao, Vladik Kreinovich

Departmental Technical Reports (CS)

Often, about the same real-life system, we have both measurement-related probabilistic information expressed by a probability measure P(S) and expert-related possibilistic information expressed by a possibility measure M(S). To get the most adequate idea about the system, we must combine these two pieces of information. For this combination, R. Yager -- borrowing an idea from fuzzy logic -- proposed to use a t-norm f(a,b)$ such as the product f(a,b)=a*b, i.e., to consider a set function f(S)=f(P(S),M(S)). A natural question is: can we uniquely reconstruct the two parts of knowledge from this function f(S)? In our previous paper, we showed that …

Linear-Time Resource Allocation In Security Games With Identical Fully Protective Resources, Octavio Lerma, Vladik Kreinovich, Chris Kiekintveld

Departmental Technical Reports (CS)

Game theory has become an important tools for making resource allocations decision in security domains, including critical infrastructure protection. Many of these games are formulated as Stackelberg security games. We present new analysis and algorithms for a class of Stackelberg security games with identical, fully protective defender resources. The first algorithm has worst-case complexity linear in the number of possible targets, but works only for a restricted case. The second algorithm can find and optimal resource allocation for the general case in time O(n log(n)).

Joggler: Data Harvest And Analysis Tool, Ondrej Nebesky

Departmental Technical Reports (CS)

Towards Optimal Knowledge Processing: From Centralization Through Cyberinsfrastructure To Cloud Computing, Octavio Lerma, Eric Gutierrez, Chris Kiekintveld, Vladik Kreinovich

Departmental Technical Reports (CS)

One of the most efficient way to store and process data is cloud computing, when we store the data so as to minimize the expenses and increase the efficiency. In this paper, we provide an analytical solution to the corresponding optimization problem.

When Is Busemann Product A Lattice? A Relation Between Metric Spaces And Corresponding Space-Time Models, Hans-Peter Künzi, Francisco Zapata, Vladik Kreinovich

Departmental Technical Reports (CS)

The causality relation of special relativity is based on the assumption that the speed of all physical processes is limited by the speed of light. As a result, an event (t,x) occurring at moment t at location x can influence an event (y,s) if and only if s >= t+d(x,y)/c. We can simplify this formula if we use units of time and distance in which c=1 (e.g., by using a light second as a unit of distance). In this case, the above causality relation takes the form s >= t+d(x,y). Since the actual space can be non-Euclidean, H. Busemann generalized …

Functional Verification Of Class Invariants In Cleanjava, Carmen Avila, Yoonsik Cheon

Departmental Technical Reports (CS)

In a Cleanroom-style functional program verification, a program is viewed as a mathematical function from one program state to another, and a verification is done by comparing two functions, the implemented and the expected behaviors of a program. The technique requires a minimal mathematical background and supports forward reasoning, but it doesn't support assertions such as class invariants. However, assertions such as class invariants are not only a practical programming tool but also play a key role in the correctness proof of a program by specifying conditions and constraints that an object has to satisfy and thus defining valid states …

Computations Under Time Constraints: Algorithms Developed For Fuzzy Computations Can Help, Karen Villaverde, Olga Kosheleva, Martine Ceberio

Departmental Technical Reports (CS)

In usual computers -- that use binary representation of real numbers -- an irrational real number (and even a rational number like 1.3 or 1.2) can only be computed with a finite accuracy. The more accuracy we need, the larger the computation time. It is therefore reasonable to characterize the complexity of computing a real number a by the accuracy D(t) that we can achieve in time t. Once we know this characteristic for two numbers a and b, how can we compute a similar characteristic for, e.g., c = a + b$? In this paper, we show that the …

Estimating Probability Of Failure Of A Complex System Based On Partial Information About Subsystems And Components, With Potential Applications To Aircraft Maintenance, Christelle Jacob, Didier Dubois, Janette Cardoso, Martine Ceberio, Vladik Kreinovich

Departmental Technical Reports (CS)

Modified Fourier-Motzkin Elimination Algorithm For Reducing Systems Of Linear Inequalities With Unconstrained Parameters, Mario Bencomo, Luis Gutierrez, Martine Ceberio

Departmental Technical Reports (CS)

The need for eliminating redundancies in systems of linear inequalities arises in many applications. In linear programming (LP), one seeks a solution that optimizes a given linear objective function subject to a set of linear constraints, sometimes posed as linear inequalities. Linear inequalities also arise in the context of tensor decomposition. Due to the lack of uniqueness in higher-order tensor decomposition, non-negativity constraints are imposed on the decomposition factors, yielding systems of linear inequalities. Eliminating redundancies in such systems can reduce the number of computations, and hence improve computation times in applications.

Towards Faster Estimation Of Statistics And Odes Under Interval, P-Box, And Fuzzy Uncertainty: From Interval Computations To Rough Set-Related Computations, Vladik Kreinovich

Departmental Technical Reports (CS)

Interval computations estimate the uncertainty of the result of data processing in situations in which we only know the upper bounds $\Delta$ on the measurement errors. In interval computations, at each intermediate stage of the computation, we have intervals of possible values of the corresponding quantities. As a result, we often have bounds with excess width. One way to remedy this problem is to extend interval technique to rough-set computations, where on each stage, in addition to intervals of possible values of the quantities, we also keep rough sets representing possible values of pairs (triples, etc.).

Estimating Risk Of Extreme And Catastrophic Events Under Interval Uncertainty, Nitaya Buntao, Vladik Kreinovich

Departmental Technical Reports (CS)

In many application areas, we encounter heavy-taildistributions -- for example, such distributions are ubiquitousin financial applications. These distributions are oftendescribed by Pareto law. There exist techniques for estimatingthe parameters of such the corresponding Pareto distributionsbased on the sample x₁, ..., x_n. In practice, we oftenonly know the values x_i with interval uncertainty. In thispaper, we show how to estimate the parameters of the Paretodistribution under such uncertainty and how to describe deviationand dependence for general heavy-tailed distributions.

How To Combine Probabilistic And Possibilistic (Expert) Knowledge: Uniqueness Of Reconstruction In Yager's (Product) Approach, Nitaya Buntao, Vladik Kreinovich

Departmental Technical Reports (CS)

Often, about the same real-life system, we have both measurement-related probabilistic information expressed by a probability measure P(S) and expert-related possibilistic information expressed by a possibility measure M(S). To get the most adequate idea about the system, we must combine these two pieces of information. For this combination, R. Yager -- borrowing an idea from fuzzy logic -- proposed to use the simple product t-norm, i.e., to consider a set function f(S) = P(S) * M(S). A natural question is: can we uniquely reconstruct the two parts of knowledge from this function f(S)? In this paper, we prove that while …

Knowledge Annotations In Scientific Workflows: An Implementation In Kepler, Aida Gandara, George Chin Jr., Paulo Pinheiro Da Silva, Signe White, Chandrika Sivaramakrishnan, Terence Critchlow

Departmental Technical Reports (CS)

Scientific research products are the result of long-term collaborations between teams. Scientific workflows are capable of helping scientists in many ways including collecting information about how research was conducted (e.g., scientific workflow tools often collect and manage information about datasets used and data transformations). However, knowledge about why data was collected is rarely documented in scientific workflows. In this paper we describe a prototype system built to support the collection of scientific expertise that influences scientific analysis. Through evaluating a scientific research effort underway at the Pacific Northwest National Laboratory, we identified features that would most benefit PNNL scientists in …

Estimating Covariance For Privacy Case Under Interval (And Fuzzy) Uncertainty, Ali Jalal-Kamali, Vladik Kreinovich, Luc Longpre

Departmental Technical Reports (CS)

Optimizing Trajectories For Unmanned Aerial Vehicles (Uavs) Patrolling The Border, Chris Kiekintveld, Vladik Kreinovich, Octavio Lerma

Departmental Technical Reports (CS)

From Processing Interval-Valued Fuzzy Data To General Type-2: Towards Fast Algorithms, Vladik Kreinovich

Departmental Technical Reports (CS)

Pwisegen: Generating Test Cases For Pairwise Testing Using Genetic Algorithms, Pedro Flores, Yoonsik Cheon

Departmental Technical Reports (CS)

Pairwise testing is a combinatorial testing technique that tests all possible pairs of input values. Although, finding a smallest set of test cases for pairwise testing is NP-complete, pairwise testing is regarded as a reasonable cost-benefit compromise among combinatorial testing methods. In this paper we formulate the problem of finding a pairwise test set as a search problem and apply a genetic algorithm to solve it. We also describe an open-source tool called PWiseGen for generating pairwise test sets. According to our experiments, PWiseGen produces competitive results compared with existing pairwise testing tools. Besides, it provides a framework and a …