Physical Sciences and Mathematics 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 …

Data Anonymization That Leads To The Most Accurate Estimates Of Statistical Characteristics: Fuzzy-Motivated Approach, G. Xiang, S. Ferson, L. Ginzburg, L. Longpre, E. Mayorga, O. Kosheleva

Departmental Technical Reports (CS)

To preserve privacy, the original data points (with exact values) are replaced by boxes containing each (inaccessible) data point. This privacy-motivated uncertainty leads to uncertainty in the statistical characteristics computed based on this data. In a previous paper, we described how to minimize this uncertainty under the assumption that we use the same standard statistical estimates for the desired characteristics. In this paper, we show that we can further decrease the resulting uncertainty if we allow fuzzy-motivated weighted estimates, and we explain how to optimally select the corresponding weights.

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 …

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.

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 …

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 …

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 …

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 …

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 …

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.

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 …

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 …

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 …

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 …

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.

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 …

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 …