Computer Engineering Commons^™

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 …

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, …

Joggler: Data Harvest And Analysis Tool, Ondrej Nebesky

Departmental Technical Reports (CS)

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

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 …

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 …

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 …

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.

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 …

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)

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

Departmental Technical Reports (CS)

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

Departmental Technical Reports (CS)

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 …

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

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 …

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.

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

Departmental Technical Reports (CS)

Designing, Understanding, And Analyzing Unconventional Computation: The Important Role Of Logic And Constructive Mathematics, Vladik Kreinovich

Departmental Technical Reports (CS)

In this paper, we explain why, in our opinion, logic and constructive mathematics are playing -- and should play -- an important role in the design, understanding, and analysis of unconventional computation.

Towards A General Description Of Translation-Invariant And Translation-Covariant Linear Transformations: A Natural Justification Of Fourier Transforms And Fuzzy Transforms, Irina Perfilieva, Vladik Kreinovich

Departmental Technical Reports (CS)

In many practical situations, we are interested in the dependencies that do not change with time, i.e., that do not change when we change the origin of the time axis. The corresponding translation-invariant transformations are easy to describe: they correspond to convolutions, or, equivalently, to fuzzy transforms.

It turns out that if we relax the invariance condition and require only that the transformation be translation-covariant (i.e., that it appropriately changes under translation), we get exactly two classes of transformations: Fourier transforms and fuzzy transforms. This result explain why both transforms have been successfully used in data processing.

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 …

Towards Optimal Few-Parametric Representation Of Spatial Variation: Geometric Approach And Environmental Applications, Misha Kosheleva, Octavio Lerma, Craig Tweedie

Departmental Technical Reports (CS)

In this paper, we use geometric approach to showthat under reasonable assumption, the spatialvariability of a field f(x), i.e., the expectedvalue F(z)=E[(f(x+z)-f(x))²], has the formF(z)=|Σ g_ij*z_i*z_j|^α.We explain how to find g_ij and αfrom the observations, and how to optimally place sensorsin view of this spatial variability.

Measures Of Deviation (And Dependence) For Heavy-Tailed Distributions And Heir Estimation Under Interval And Fuzzy Uncertainty, Nitaya Buntao, Vladik Kreinovich

Departmental Technical Reports (CS)

Traditionally, in science and engineering, most statistical techniques are based on the assumption that the random variables are normally distributed. For such distributions, a natural characteristic of the "average" value is the mean, and a natural characteristic of the deviation from the average is the variance. However, in many practical situations, e.g., in economics and finance, we encounter probability distributions for which the variance is infinite; such distributions are called heavy-tailed. For such distributions, we describe which characteristics can be used to describe the average and the deviation from the average, and how to estimate these characteristics under interval …

Estimating Mean Under Interval Uncertainty And Variance Constraint, Ali Jalal-Kamali, Luc Longpre, Misha Kosheleva

Departmental Technical Reports (CS)

Universal Approximation With Uninorm-Based Fuzzy Neural Networks, Andre Lemos, Vladik Kreinovich, Walmir Caminhas, Fernando Gomide

Departmental Technical Reports (CS)

Fuzzy neural networks are hybrid models capable to approximate functions with high precision and to generate transparent models, enabling the extraction of valuable information from the resulting topology. In this paper we will show that the recently proposed fuzzy neural network based on weighted uninorms aggregations uniformly approximates any real functions on any compact set. We will describe the network topology and inference mechanism and show that the universal approximation property of this network is valid for a given choice of operators.

Testing Shock Absorbers: Towards A Faster Parallelizable Algorithm, Christian Servin

Departmental Technical Reports (CS)

Cars are equipped with shock absorbers, which are designed to smooth out the shocks on the road. In practice, there is a need to test them. To test the shock absorbers, we need to estimate the values of the shock absorber's parameters. If we did not have any measurement errors, then two measurements would be sufficient to determine the parameters. However, in reality, there are measurement errors. Usually, in engineering practice, it is assumed that the errors are normally distributed with 0 mean, so we can use least squares method to test it. In practice, we often only know the …

Fundamental Physical Equations Can Be Derived By Applying Fuzzy Methodology To Informal Physical Ideas, Eric Gutierrez, Vladik Kreinovich

Departmental Technical Reports (CS)

Fuzzy methodology transforms expert ideas -- formulated in terms of words from natural language -- into precise rules and formulas. In this paper, we show that by applying this methodology to intuitive physical ideas, we can get fundamental physical equations. This fact provides an additional justification for the fuzzy methodology.

From Single To Double Use Expressions, With Applications To Parametric Interval Linear Systems: On Computational Complexity Of Fuzzy And Interval Computations, Joseph A Lorkowski

Departmental Technical Reports (CS)

In many practical problems, we need to estimate the range of a given expression f(x1, ..., xn) when each input xi belongs to a known interval [xi] -- or when each input xi is described by a known fuzzy set. It is known that this problem is easy to solve when we have a Single Use Expression, i.e., an expression in which each variable xi occurs only once. In this paper, we show that for similarly defined Double Use Expressions, the corresponding range estimation problem is NP-hard. Similar problems are analyzed for the problem of solving linear systems under interval …

Reducing Over-Conservative Expert Failure Rate Estimates In The Presence Of Limited Data: A New Probabilistic/Fuzzy Approach, Carlos M. Ferregut, F. Joshua Campos, Vladik Kreinovich

Departmental Technical Reports (CS)

Unique highly reliable components are typical for aerospace industry. For such components, due to their high reliability and uniqueness, we do not have enough empirical data to make statistically reliable estimates about their failure rate. To overcome this limitation, the empirical data is usually supplemented with expert estimates for the failure rate. The problem is that experts tend to be -- especially in aerospace industry -- over-cautious, over-conservative; their estimates for the failure rate are usually much higher than the actual observed failure rate. In this paper, we provide a new fuzzy-related statistically justified approach for reducing this over-estimation.

Least Sensitive (Most Robust) Fuzzy "Exclusive Or" Operations, Jesus E. Hernandez, Jaime Nava

Departmental Technical Reports (CS)

In natural language, "or" sometimes means "inclusive or" and sometimes means "exclusive or". To adequately describe commonsense and expert knowledge, it is therefore important to have not only t-conorms describing fuzzy "inclusive or" operations, but also fuzzy "exclusive or" operations f(a,b). Since the degrees of certainty are only approximately defined, it is reasonable to require that the corresponding operation be the least sensitive to small changes in the inputs. In this paper, we show that the least sensitive fuzzy "exclusive or" operation has the form f(a,b)=min(max(a,b),max(1-a,1-b)).