Computer Sciences Commons^™

Towards Fuzzy Method For Estimating Prediction Accuracy For Discrete Inputs, With Application To Predicting At-Risk Students, Xiaojing Wang, Martine Ceberio, Angel F. Garcia Contreras

Departmental Technical Reports (CS)

In many practical situations, we need, given the values of the observed quantities x1, ..., xn, to predict the value of a desired quantity y. To estimate the accuracy of a prediction algorithm f(x1, ..., xn), we need to compare the results of this algorithm's prediction with the actually observed values.

The value y usually depends not only on the values x1, ..., xn, but also on values of other quantities which we do not measure. As a result, even when we have the exact same values of the quantities x1, ..., xn, we may get somewhat different values of …

For Describing Uncertainty, Ellipsoids Are Better Than Generic Polyhedra And Probably Better Than Boxes: A Remark, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

For a single quantity, the set of all possible values is usually an interval. An interval is easy to represent in a computer: e.g., we can store its two endpoints. For several quantities, the set of possible values may have an arbitrary shape. An exact description of this shape requires infinitely many parameters, so in a computer, we have to use a finite-parametric approximation family of sets. One of the widely used methods for selecting such a family is to pick a symmetric convex set and to use its images under all linear transformations. If we pick a unit ball, …

Estimating Third Central Moment C3 For Privacy Case Under Interval And Fuzzy Uncertainty, Ali Jalal-Kamali, Vladik Kreinovich

Departmental Technical Reports (CS)

Some probability distributions (e.g., Gaussian) are symmetric, some (e.g., lognormal) are non-symmetric ({\em skewed}). How can we gauge the skeweness? For symmetric distributions, the third central moment C₃ = E[(x - E(x))³] is equal to 0; thus, this moment is used to characterize skewness. This moment is usually estimated, based on the observed (sample) values x₁, ..., x_n, as C₃ = (1/n) * ((x₁ - E)³ + ... + (x_n - E)³), where E = (1/n) * (x₁ + ... + x_n). In many …

How To Generate Worst-Case Scenarios When Testing Already Deployed Systems Against Unexpected Situations, Francisco Zapata, Ricardo Pineda, Martine Ceberio

Departmental Technical Reports (CS)

Before a complex system is deployed, it is tested -- but it is tested against known operational mission, under several known operational scenarios. Once the system is deployed, new possible unexpected and/or uncertain operational scenarios emerge. It is desirable to develop methodologies to test the system against such scenarios. A possible methodology to test the system would be to generate the worst case scenario that we can think of -- to understand, in principle, the behavior of the system. So, we face a question of generating such worst-case scenarios. In this paper, we provide some guidance on how to generate …

Security Games With Interval Uncertainty, Christopher Kiekintveld, Towhidul Islam, Vladik Kreinovich

Departmental Technical Reports (CS)

Security games provide a framework for allocating limited security resources in adversarial domains, and are currently used in applications including security at the LAX airport, scheduling for the Federal Air Marshals, and patrolling strategies for the U.S. Coast Guard. One of the major challenges in security games is finding solutions that are robust to uncertainty about the game model. Bayesian game models have been developed to model uncertainty, but algorithms for these games do not scale well enough for many applications, and the problem is NP-hard.

We take an alternative approach based on using intervals to model uncertainty in security …

Brans-Dicke Scalar-Tensor Theory Of Gravitation May Explain Time Asymmetry Of Physical Processes, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

Most fundamental physical equations remain valid if we reverse the time order. Thus, if we start with a physical process (which satisfies these equations) and reverse time order, the resulting process also satisfies all the equations and thus, should also be physically reasonable. In practice, however, many physical processes are not reversible: e.g., a cup can break into pieces, but the pieces cannot magically get together and become a whole cup. In this paper, we show that the Brans-Dicke Scalar-Tensor Theory of Gravitation, one of the most widely used generalizations of Einstein's General relativity, is, in effect, time-asymmetric. This time-asymmetry …

Comparing Intervals And Moments For The Quantification Of Coarse Information, Michael Beer, Vladik Kreinovich

Departmental Technical Reports (CS)

In this paper the problem of the most appropriate modeling of scarce information for an engineering analysis is investigated. This investigation is focused on a comparison between a rough probabilistic modeling based on the first two moments and interval modeling. In many practical cases, the available information is limited to such an extent that a more thorough modeling cannot be pursued. The engineer has to make a decision regarding the modeling of this limited and coarse information so that the results of the analysis provide the most suitable basis for conclusions. We approach this problem from the angle of information …

Constructing Verifiably Correct Java Programs Using Ocl And Cleanjava, Yoonsik Cheon, Carmen Avila

Departmental Technical Reports (CS)

A recent trend in software development is building a precise model that can be used as a basis for the software development. Such a model may enable an automatic generation of working code, and more importantly it provides a foundation for correctness reasoning of code. In this paper we propose a practical approach for constructing a verifiably correct program from such a model. The key idea of our approach is (a) to systematically translate formally-specified design constraints such as class invariants and operation pre and postconditions to code-level annotations and (b) to use the annotations for the correctness proof of …

Use Of Grothendieck Inequality In Interval Computations: Quadratic Terms Are Estimated Accurately Modulo A Constant Factor, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

One of the main problems of interval computations is to compute the range of a given function f over given intervals. For a linear function, we can feasibly estimate its range, but for quadratic (and for more complex) functions, the problem of computing the exact range is NP-hard. So, if we limit ourselves to feasible algorithms, we have to compute enclosures instead of the actual ranges. It is known that asymptotically the smallest possible excess width of these enclosures is O(Δ²), where Δ is the largest half-width of the input intervals. This asymptotics is attained for the Mean …

Filtering Out High Frequencies In Time Series Using F-Transform, Vilém Novák, Irina Perfilieva, Michal Holčapek, Vladik Kreinovich

Departmental Technical Reports (CS)

In this paper, we will focus on the application of fuzzy transform (F-transform) in the analysis of time series. We assume that the time series can be decomposed into three constituent components: the trend-cycle, seasonal component and random noise. We will demonstrate that by using F-transform, we can approximate the trend-cycle of a given time series with high accuracy.

Checking Monotonicity Is Np-Hard Even For Cubic Polynomials, Andrzej Pownuk, Luc Longpre, Vladik Kreinovich

Departmental Technical Reports (CS)

One of the main problems of interval computations is to compute the range of a given function over given intervals. In general, this problem is computationally intractable (NP-hard) -- that is why we usually compute an enclosure and not the exact range. However, there are cases when it is possible to feasibly compute the exact range; one of these cases is when the function is monotonic with respect to each of its variables. The monotonicity assumption holds when the derivatives at a midpoint are different from 0 and the intervals are sufficiently narrow; because of this, monotonicity-based estimates are often …

Why Complex-Valued Fuzzy? Why Complex Values In General? A Computational Explanation, Olga Kosheleva, Vladik Kreinovich, Thavatchai Ngamsantivong

Departmental Technical Reports (CS)

In the traditional fuzzy logic, as truth values, we take all real numbers from the interval [0,1]. In some situations, this set is not fully adequate for describing expert uncertainty, so a more general set is needed. From the mathematical viewpoint, a natural extension of real numbers is the set of complex numbers. Complex-valued fuzzy sets have indeed been successfully used in applications of fuzzy techniques. This practical success leaves us with a puzzling question: why complex-valued degree of belief, degrees which do not seem to have a direct intuitive meaning, have been so successful? In this paper, we use …

F-Transform In View Of Aggregation Functions, Irina Perfilieva, Vladik Kreinovich

Departmental Technical Reports (CS)

A relationship between the discrete F-transform and aggregation functions is analyzed. We show that the discrete F-transform (direct or inverse) can be associated with a set of linear aggregation functions that respect a fuzzy partition of a universe. On the other side, we discover conditions that should be added to a set of linear aggregation functions in order to obtain the discrete F-transform. Last but not least, the relationship between two analyzed notions is based on a new (generalized) definition of a fuzzy partition without the Ruspini condition.

Bayesian Approach For Inconsistent Information, M. Stein, Michael Beer, Vladik Kreinovich

Departmental Technical Reports (CS)

In engineering situations, we usually have a large amount of prior knowledge that needs to be taken into account when processing data. Traditionally, the Bayesian approach is used to process data in the presence of prior knowledge. Sometimes, when we apply the traditional Bayesian techniques to engineering data, we get inconsistencies between the data and prior knowledge. These inconsistencies are usually caused by the fact that in the traditional approach, we assume that we know the {\it exact} sample values, that the prior distribution is {\it exactly} known, etc. In reality, the data is imprecise due to measurement errors, the …

From P-Boxes To P-Ellipsoids: Towards An Optimal Representation Of Imprecise Probabilities, Konstantin K. Semenov, Vladik Kreinovich

Departmental Technical Reports (CS)

One of the most widely used ways to represent a probability distribution is by describing its cumulative distribution function (cdf) F(x). In practice, we rarely know the exact values of F(x): for each x, we only know F(x) with uncertainty. In such situations, it is reasonable to describe, for each x, the interval [F(x)] of possible values of x. This representation of imprecise probabilities is known as a p-box; it is effectively used in many applications.

Similar interval bounds are possible for probability density function, for moments, etc. The problem is that when we transform from one of such representations …

Why Inverse F-Transform? A Compression-Based Explanation, Vladik Kreinovich, Irina Perlieva, Vilém Novák

Departmental Technical Reports (CS)

In many practical situations, e.g., in signal processing, image processing, analysis of temporal data, it is very useful to use fuzzy (F-) transforms. In an F-transform, we first replace a function x(t) by a few local averages (this is called forward F-transform), and then reconstruct the original function from these averages (this is called inverse F-transform). While the formula for the forward F-transform makes perfect intuitive sense, the formula for the inverse F-transform seems, at first glance, somewhat counter-intuitive. On the other hand, its empirical success shows that this formula must have a good justification. In this paper, we provide …

Relation Between Polling And Likert-Scale Approaches To Eliciting Membership Degrees Clarified By Quantum Computing, Renata Hax Sander Reiser, Adriano Maron, Lidiane Visintin, Ana Maria Abeijon, Vladik Kreinovich

Departmental Technical Reports (CS)

In fuzzy logic, there are two main approaches to eliciting membership degrees: an approach based on polling experts, and a Likert-scale approach, in which we ask experts to indicate their degree of confidence on a scale -- e.g., on a scale form 0 to 10. Both approaches are reasonable, but they often lead to different membership degrees. In this paper, we analyze the relation between these two approaches, and we show that this relation can be made much clearer if we use models from quantum computing.

Aggregation Operations From Quantum Computing, Lidiane Visintin, Adriano Maron, Renata Reiser, Ana Maria Abeijon, Vladik Kreinovich

Departmental Technical Reports (CS)

Computer systems based on fuzzy logic should be able to generate an output from the handling of inaccurate data input by applying a rule based system. The main contribution of this paper is to show that quantum computing can be used to extend the class of fuzzy sets. The central idea associates the states of a quantum register to membership functions (mFs) of fuzzy subsets, and the rules for the processes of fuzzyfication are performed by unitary qTs. This paper introduces an interpretation of aggregations obtained by classical fuzzy states, that is, by multi-dimensional quantum register associated to mFs on …

A Symmetry-Based Approach To Selecting Membership Functions And Its Relation To Chemical Kinetics, Vladik Kreinovich, Olga Kosheleva, Jorge Y. Cabrera, Mario Gutierrez, Thavatchai Ngamsantivong

Departmental Technical Reports (CS)

In many practical situations, we encounter physical quantities like time for which there is no fixed starting point for measurements: physical properties do not change if we simply change (shift) the starting point. To describe knowledge about such properties, it is desirable to select membership functions which are similarly shift-invariant. We show that while we cannot require that each membership function is shift-invariant, we can require that the linear space of all linear combinations of given membership functions is shift-invariant. We describe all such shift-invariant families of membership functions, and we show that they are naturally related to the corresponding …

Data Anonymization That Leads To The Most Accurate Estimates Of Statistical Characteristics, Gang Xiang, Vladik Kreinovich

Departmental Technical Reports (CS)

To preserve privacy, we divide the data space into boxes, and instead of original data points, only store the corresponding boxes. In accordance with the current practice, the desired level of privacy is established by having at least k different records in each box, for a given value k (the larger the value k, the higher the privacy level).

When we process the data, then the use of boxes instead of the original exact values leads to uncertainty. In this paper, we find the (asymptotically) optimal subdivision of data into boxes, a subdivision that provides, for a given statistical characteristic …

Metrological Self-Assurance Of Data Processing Software, Vladik Kreinovich, Leonid Reznik, Konstantin K. Semenov, Gennady N. Solopchenko

Departmental Technical Reports (CS)

The metrological self-assurance for data processing software is discussed. The way to achieve this property for software is presented.

F-Transform In View Of Trend Extraction, Irina Perfilieva, Vladik Kreinovich, Vilém Novák

Departmental Technical Reports (CS)

In the analysis of time series, it is important to decompose the original values into trend, cycle, seasonal component, and noise. In this paper, we provide a theoretical justification of the fact that the F-transform can be used for this purpose. We formulate "natural" requirements on the trend extraction procedure and then show that the inverse F-transform fulfils all of them.

Zadeh's Vision Of Going From Fuzzy To Computing With Words: From The Idea's Origin To Current Successes To Remaining Challenges, Vladik Kreinovich

Departmental Technical Reports (CS)

No abstract provided.

Thirty-Two Sample Audio Search Tasks, Nigel G. Ward, Steven D. Werner

Departmental Technical Reports (CS)

Searching in audio archives is potentially very useful, and good evaluations can guide development to realize that promise. However most current evaluation programs are technology-centric, rather than user-oriented and task-centric. This paper examines current and potential audio search needs and scenarios, and presents a sample set of thirty-two diverse audio search tasks to support more realistic evaluations.

Ubiquity Of Data And Model Fusion: From Geophysics And Environmental Sciences To Estimating Individual Risk During An Epidemic, Omar Ochoa, Aline Jaimes, Christian Servin, Craig Tweedie, Aaron Velasco, Martine Ceberio, Vladik Kreinovich

Departmental Technical Reports (CS)

In many practical situations, we need to combine the results of measuring a local value of a certain quantity with results of measuring average values of this same quantity. For example, in geosciences, we need to combine the seismic models (which describe density at different locations and depths) with gravity models which describe density averaged over certain regions. Similarly, in estimating the risk of an epidemic to an individual, we need to combine probabilities describe the risk to people of the corresponding age group, to people of the corresponding geographical region, etc. In this paper, we provide general techniques for …

Interval Uncertainty As The Basis For A General Description Of Uncertainty: A Position Paper, Vladik Kreinovich

Departmental Technical Reports (CS)

Uncertainty is ubiquitous. Depending on what information we have, we get different types of uncertainty. For each type of uncertainty, techniques have been developed for efficient representation and processing of this uncertainty. However, the plethora of different uncertainty techniques is often confusing for practitioners. The situation is especially difficult in frequent situations when we need to gauge the uncertainty of the result of complex multi-stage data processing, and different data inputs are known with different types of uncertainty. To avoid this problem, it is necessary to develop and implement a general approach to representing and processing different types of uncertainty. …

Orders On Intervals Over Partially Ordered Sets: Extending Allen's Algebra And Interval Graph Results, Francisco Zapata, Vladik Kreinovich, Cliff Joslyn, Emilie Hogan

Departmental Technical Reports (CS)

To make a decision, we need to compare the values of quantities. In many practical situations, we know the values with interval uncertainty. In such situations, we need to compare intervals. Allen's algebra describes all possible relations between intervals on the real line which are generated by the ordering of endpoints; ordering relations between such intervals have also been well studied. In this paper, we extend this description to intervals in an arbitrary partially ordered set (poset). In particular, we explicitly describe ordering relations between intervals that generalize relation between points. As auxiliary results, we provide a logical interpretation of …

Kansei Engineering: Towards Optimal Set Of Designs, Van-Nam Huynh, Octavio Lerma, Vladik Kreinovich

Departmental Technical Reports (CS)

In many engineering situations, we need to take into account subjective user preferences; taking such preference into account is known as {\em Kansei Engineering}. In this paper, we formulate the problem of selecting optimal set of designs in Kansei engineering as a mathematical optimization problem, and we provide an explicit solution to this optimization problem.

How To Define Mean, Variance, Etc., For Heavy-Tailed Distributions: A Fractal-Motivated Approach, Vladik Kreinovich, Olga Kosheleva

Departmental Technical Reports (CS)

In many practical situations, we encounter heavy-tailed distributions for which the variance -- and even sometimes the mean -- are infinite. We propose a fractal-motivated approach that enables us to gauge the mean and variance of such distributions.

How To Divide Students Into Groups So As To Optimize Learning: Towards A Solution To A Pedagogy-Related Optimization Problem, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

To enhance learning, it is desirable to also let students learn from each other, e.g., by working in groups. It is known that such groupwork can improve learning, but the effect strongly depends on how we divide students into groups. In this paper, based on a first approximation model of student interaction, we describe how to optimally divide students into groups so as to optimize the resulting learning. We hope that, by taking into account other aspects of student interaction, it will be possible to transform our solution into truly optimal practical recommendations.