Computer Sciences Commons^™

Computing Covariance And Correlation In Optimally Privacy-Protected Statistical Databases: Feasible Algorithms, Joshua Day, Ali Jalal-Kamali, Vladik Kreinovich

Departmental Technical Reports (CS)

In many real-life situations, e.g., in medicine, it is necessary to process data while preserving the patients' confidentiality. One of the most efficient methods of preserving privacy is to replace the exact values with intervals that contain these values. For example, instead of an exact age, a privacy-protected database only contains the information that the age is, e.g., between 10 and 20, or between 20 and 30, etc. Based on this data, it is important to compute correlation and covariance between different quantities. For privacy-protected data, different values from the intervals lead, in general, to different estimates for the desired …

Fuzzy Sets Can Be Interpreted As Limits Of Crisp Sets, And This Can Help To Fuzzify Crisp Notions, Olga Kosheleva, Vladik Kreinovich, Thavatchai Ngamsantivong

Departmental Technical Reports (CS)

Fuzzy sets have been originally introduced as generalizations of crisp sets, and this is how they are usually considered. From the mathematical viewpoint, the problem with this approach is that most notions allow many different generalizations, so every time we try to generalize some notions to fuzzy sets, we have numerous alternatives. In this paper, we show that fuzzy sets can be alternatively viewed as limits of crisp sets. As a result, for some notions, we can come up with a unique generalization -- as the limit of the results of applying this notion to the corresponding crisp sets.

Lexical And Prosodic Indicators Of Importance In Spoken Dialog, Nigel G. Ward, Karen A. Richart-Ruiz

Departmental Technical Reports (CS)

This technical report complements the paper, Patterns of Importance Variation in Spoken Dialog (Ward and Richart-Ruiz, 2013), providing additional evidence for the claims, additional findings, and more analysis. In particular, we report more on inter-annotator disagreement, on words that correlate with importance, on prosodic features and patterns that correlate with importance, and on how our predictive model of importance might be improved.

Solving Interval Linear Systems Is Np-Hard Even When All Inputs Are Known With The Same Accuracy, Ralph Kelsey, Vladik Kreinovich

Departmental Technical Reports (CS)

It is known that in general, solving interval linear systems is NP-hard. There exist several proofs of this NP-hardness, and all these proofs use examples with intervals of different width -- corresponding to different accuracy in measuring different coefficients. For some classes of interval linear systems with the same accuracy, feasible algorithms are known. We show, however, that in general, solving interval linear systems is NP-hard even when all inputs are known with the same accuracy.

How To Gauge Accuracy Of Measurements And Of Expert Estimates: Beyond Normal Distributions, Christian Servin, Aline Jaimes, Craig Tweedie, Aaron A. Velasco, Omar Ochoa, Vladik Kreinovich

Departmental Technical Reports (CS)

To properly process data, we need to know the accuracy of different data points, i.e., accuracy of different measurement results and expert estimates. Often, this accuracy is not given. For such situations, we describe how this accuracy can be estimated based on the available data.

How To Explain (And Overcome) 2% Barrier In Teaching Computer Science: Fuzzy Ideas Can Help, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

Computer science educators observed that in the present way of teaching computing, only 2% of students can easily handle computational concepts -- and, as a result, only 2% of the students specialize in computer science. With the increasing role of computers in the modern world, and the increasing need for computer-related jobs, this 2% barrier creates a shortage of computer scientists. We notice that the current way of teaching computer science is based on easiness of using two-valued logic, on easiness of dividing all situations, with respect to each property, into three classes: yes, no, and unknown. The fact that …

How To Detect Linear Dependence On The Copula Level?, Vladik Kreinovich, Hung T. Nguyen, Songsak Sriboonchitta

Departmental Technical Reports (CS)

In many practical situations, the dependence between the quantities is linear or approximately linear. Knowing that the dependence is linear simplifies computations; so, is is desirable to detect linear dependencies. If we know the joint probability distribution, we can detect linear dependence by computing Pearson's correlation coefficient. In practice, we often have a copula instead of a full distribution; in this case, we face a problem of detecting linear dependence based on the copula. Also, distributions are often heavy-tailed, with infinite variances, in which case Pearson's formulas cannot be applied. In this paper, we show how to modify Pearson's formula …

Computing With Words: Towards A New Tuple-Based Formalization, Olga Kosheleva, Vladik Kreinovich, Ariel Garcia, Felipe Jovel, Luis A. Torres Escobedo, Thavatchai Ngamsantivong

Departmental Technical Reports (CS)

An expert opinion describes his or her opinion about a quantity by using imprecise ("fuzzy") words from a natural language, such as "small", "medium", "large", etc. Each of these words provides a rather crude description of the corresponding quantity. A natural way to refine this description is to assign degrees to which the observed quantity fits each of the selected words. For example, an expert can say that the value is reasonable small, but to some extent it is medium. In this refined description, we represent each quantity by a tuple of the corresponding degrees.

Once we have such a …

Images Are Easier To Restore Than 1-D Signals: A Theoretical Explanation Of A Surprising Empirical Phenomenon, Christian Servin, Vladik Kreinovich

Departmental Technical Reports (CS)

Similar techniques are often used to restore 1-D signals and 2-D images from distorted ("blurred") observations. From the purely mathematical viewpoint, 1-D signals are simpler, so it should be easier to restore signals than images. However, in practice, it is often easier to restore a 2-D image than to restore a 1-D signal. In this paper, we provide a theoretical explanation for this surprising empirical phenomenon.

Is Langrangian Formalism Adequately Describing Energy Conservation?, Vladik Kreinovich, Olga Kosheleva

Departmental Technical Reports (CS)

In most physical theories, total energy is conserved. For example, when the kinetic energy of a particle decreases, the potential energy increase accordingly. For some physical systems, energy is not conserved. For example, if we consider a particle moving with friction, the energy of the particle itself is not conserved: it is transformed into thermal energy of the surrounding medium. For simple systems, energy is easy to define. For more complex physical systems, such a definition is not easy. To describe energy of generic systems, physicists came up with a general notion of energy based on the Lagrangian formalism -- …

Stochastic Causality Is Inconsistent With The Lorentz Group, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

According to modern physics, all physical processes are described by quantum theory. In particular, due to quantum fluctuations, even in the empty space, the causal relation is, in general, slightly different from the usual Minkowski one. Since quantum effects are probabilistic, to properly represent the corresponding stochastic causality, we need to describe, for every two events e and e', the probability p(e,e') that e can causally influence e'. Surprisingly, it turns out that such a probability functions cannot be Lorentz-invariant. In other words, once we take into account quantum effects in causality, Lorentz-invariance is violated -- similarly to the fact …

Minimization Of Average Sensitivity As A Method Of Selecting Fuzzy Functions And Operations: Successes And Limitations, Riya George, Suresh Subramanian, Alejandro Vega, Olga Kosheleva

Departmental Technical Reports (CS)

Fuzzy logic is an extension of the standard 2-valued logic -- with two possible truth values 0 ("false") and ("true") -- to values (degrees of certainty) represented by arbitrary numbers from the interval [0,1]. One of the main challenges in fuzzy logic is that we need to extend the usual logical operations from the set {0,1} to the entire interval, and there are many possible extensions. One promising technique for selecting a reasonable extension is to take into account that the fuzzy degrees of certainty are themselves only known with uncertainty; so, it makes sense to select an operation which …

Towards Discrete Interval, Set, And Fuzzy Computations, Enrique Portillo, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

In many applications, we know the function f(x1,...,xn), we know the intervals [xi] of possible values of each quantity xi, and we are interested in the range of possible values of y=f(x1,...,xn); this problem is known as the problem of interval computations. In other applications, we know the function f(x1,...,xn), we know the fuzzy sets Xi that describe what we know about each quantity xi, and we are interested in finding the fuzzy set Y corresponding to the quantity y=f(x1,...,xn); this problem is known as the problem of fuzzy computations. There are many efficient algorithms for solving these problems; however, …

Towards A Localized Version Of Pearson's Correlation Coefficient, Vladik Kreinovich, Hung T. Nguyen, Berlin Wu

Departmental Technical Reports (CS)

Pearson's correlation coefficient is used to describe dependence between random variables X and Y. In some practical situations, however, we have strong correlation for some values X and/or Y and no correlation for other values of X and Y. To describe such a local dependence, we come up with a natural localized version of Pearson's correlation coefficient. We also study the properties of the newly defined localized coefficient.

Space-Time Assumptions Behind Np-Hardness Of Propositional Satisfiability, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

For some problems, we know feasible algorithms for solving them. Other computational problems (such as propositional satisfiability) are known to be NP-hard, which means that, unless P=NP (which most computer scientists believe to be impossible), no feasible algorithm is possible for solving all possible instances of the corresponding problem. Most usual proofs of NP-hardness, however, use Turing machine -- a very simplified version of a computer -- as a computation model. While Turing machine has been convincingly shown to be adequate to describe what can be computed in principle, it is much less intuitive that these oversimplified machine are …

Enhancing The Expressiveness Of The Cleanjava Language, Melisa Vela, Yoonsik Cheon

Departmental Technical Reports (CS)

The CleanJava language is a formal annotation language for Java to support Cleanroom-style functional program verification that views a program as a mathematical function from one program state to another. The CleanJava notation is based on the Java expression syntax with a few extensions, and thus its vocabulary is somewhat limited to that of Java. This often makes it difficult to specify the rich semantics of a Java program in a succinct and natural way that is easy to manipulate for formal correctness reasoning. In this paper we propose to make the CleanJava language more expressive by supporting user-defined mathematical …

√(X2 + Μ) Is The Most Computationally Efficient Smooth Approximation To |X|: A Proof, Carlos Ramirez, Reinaldo Sanchez, Vladik Kreinovich, Miguel Argaez

Departmental Technical Reports (CS)

In many practical situations, we need to minimize an expression of the type |c₁| + ... + |c_n|. The problem is that most efficient optimization techniques use the derivative of the objective function, but the function |x| is not differentiable at 0. To make optimization efficient, it is therefore reasonable to approximate |x| by a smooth function. We show that in some reasonable sense, the most computationally efficient smooth approximation to |x| is the function √(x² + μ), a function which has indeed been successfully used in such optimization.

Beyond Traditional Chemical Kinetics Formulas: Group-Theoretic Approach, Vladik Kreinovich

Departmental Technical Reports (CS)

According to the traditional formulas of chemical kinetics, the rate is proportional to the product of concentrations of reagents. This formula leads to a reasonable description of interactions both in chemistry and in other disciplines (e.g., in ecology). However, in many cases, these formulas are only approximate. Several semi-empirical formulas have been designed to more accurately describe the interaction rate. The problem is that most of these formulas are purely empirical, they lack a convincing theoretical explanation. In this paper, we show that a group-theoretic approach -- taking into account natural symmetries of the systems -- leads to the desired …

Processing Quantities With Heavy-Tailed Distribution Of Measurement Uncertainty: How To Estimate The Tails Of The Results Of Data Processing, Michal Holčapek, Vladik Kreinovich

Departmental Technical Reports (CS)

Measurements are never absolutely accurate; so, it is important to estimate how the measurement uncertainty affects the result of data processing. Traditionally, this problem is solved under the assumption that the probability distributions of measurement errors are normal -- or at least are concentrated, with high certainty, on a reasonably small interval. In practice, the distribution of measurement errors is sometimes heavy-tailed, when very large values have a reasonable probability. In this paper, we analyze the corresponding problem of estimating the tail of the result of data processing in such situations.

Necessary And Sufficient Conditions For Generalized Uniform Fuzzy Partitions, Michal Holčapek, Irina Perfilieva, Vilém Novák, Vladik Kreinovich

Departmental Technical Reports (CS)

The fundamental concept in the theory of fuzzy transform (F-transform) is that of fuzzy partition. The original definition assumes that each two fuzzy subsets overlap in such a way that sum of membership degrees in each point is equal to 1. However, this condition can be generalized to obtain a denser fuzzy partition that leads to improvement of approximation properties of F-transform. However, a problem arises how one can effectively construct such type of fuzzy partitions. We use a generating function having special properties and it is not immediately clear whether it really defines a general uniform fuzzy partition. In …

Using Symmetries (Beyond Geometric Symmetries) In Chemical Computations: Computing Parameters Of Multiple Binding Sites, Andres Ortiz, Vladik Kreinovich

Departmental Technical Reports (CS)

We show how group-theoretic ideas can be naturally used to generate efficient algorithms for scientific computations. The general group-theoretic approach is illustrated on the example of determining, from the experimental data, the dissociation constants related to multiple binding sites. We also explain how the general group-theoretic approach is related to the standard (backpropagation) neural networks; this relation justifies the potential universal applicability of the group-theoretic approach.

Cjc: An Extensible Checker For The Cleanjava Annotation Language, Cesar Yeep

Departmental Technical Reports (CS)

CleanJava is a formal annotation language for the Java programming language to support a Cleanroom-style functional program verification technique that views programs as mathematical functions. It needs a suite of support tools including a checker that can parse annotations and check them for syntactic and static semantic correctness. The two key requirements of the checker are flexibility and extensibility. Since the language is still under development and refinement, it should be flexible to facilitate language experimentation and accommodate language changes. It should be also extensible to provide base code for developing more advanced support tools like an automated theorem prover. …

Towards A Physically Meaningful Definition Of Computable Discontinuous And Multi-Valued Functions (Constraints), Martine Ceberio, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

In computable mathematics, there are known definitions of computable numbers, computable metric spaces, computable compact sets, and computable functions. A traditional definition of a computable function, however, covers only continuous functions. In many applications (e.g., in phase transitions), physical phenomena are described by discontinuous or multi-valued functions (a.k.a. constraints). In this paper, we provide a physics-motivated definition of computable discontinuous and multi-valued functions, and we analyze properties of this definition.

Full Superposition Principle Is Inconsistent With Non-Deterministic Versions Of Quantum Physics, Andres Ortiz, Vladik Kreinovich

Departmental Technical Reports (CS)

Many practical systems are non-deterministic, in the sense that available information about the initial states and control values does not uniquely determine the future states. For some such systems, it is important to take quantum effects into account. For that, we need to develop non-deterministic versions of quantum physics. In this paper, we show that for non-deterministic versions of quantum physics, we cannot require superposition principle -- one of the main fundamental principles of modern quantum mechanics. Specifically, while we can consider superpositions of states corresponding to the same version of the future dynamics, it is not consistently possible to …

A New Analog Optical Processing Scheme For Solving Np-Hard Problems, Michael Zakharevich, Vladik Kreinovich

Departmental Technical Reports (CS)

Many real-life problems are, in general, NP-hard, i.e., informally speaking, are difficult to solve. To be more precise, a problem p is NP-hard means that every problem from the class NP can be reduced to this problem p. Thus, if we have an efficient algorithm for solving one NP-hard problem, we can use this reduction to get a more efficient way of solving all the problems from the class NP. To speed up computations, it is reasonable to base them on the fastest possible physical process -- i.e., on light. It is known that analog optical processing indeed speeds up …

An Ontological Approach To Capture Data Provenance Across Multiple Platforms, Leonardo Salayandia

Departmental Technical Reports (CS)

The process of collecting and transforming data can extend across different platforms, both physical and digital. Capturing provenance that reflects the actions involved in such a process in a consistent manner can be difficult and involve the use of multiple tools. An approach based on formal ontologies and software engineering practices is presented to capture data provenance. The approach starts by creating ontologies about data collection and transformation processes. These ontologies, referred to as Workflow-Driven Ontologies, establish a consistent view of the process that is independent of the platform used to carry out the process. Next, software modules are generated, …

Towards Model Fusion In Geophysics: How To Estimate Accuracy Of Different Models, Omar Ochoa, Aaron A. Velasco, Christian Servin

Departmental Technical Reports (CS)

In geophysics, we usually have several Earth models based on different types of data: seismic, gravity, etc. Each of these models captures some aspects of the Earth structure. To get the more description of the Earth, it is desirable to "fuse" these models into a single one. To appropriately fuse the models, we need to know the accuracy of different models. In this paper, we show that the traditional methods cannot be directly used to estimate these accuracies, and we propose a new method for such estimation.

Why ℓ1 Is A Good Approximation To ℓ0: A Geometric Explanation, Carlos Ramirez, Vladik Kreinovich, Miguel Argaez

Departmental Technical Reports (CS)

In practice, we usually have partial information; as a result, we have several different possibilities consistent with the given measurements and the given knowledge. For example, in geosciences, several possible density distributions are consistent with the measurement results. It is reasonable to select the simplest among such distributions. A general solution can be described, e.g., as a linear combination of basic functions. A natural way to define the simplest solution is to select a one for which the number of the non-zero coefficients c_i is the smallest. The corresponding "l₀-optimization" problem is non-convex and therefore, difficult to …

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.

Likert-Scale Fuzzy Uncertainty From A Traditional Decision Making Viewpoint: It Incorporates Both Subjective Probabilities And Utility Information, Joe Lorkowski, Vladik Kreinovich

Departmental Technical Reports (CS)

One of the main methods for eliciting the values of the membership function μ(x) is to use the Likert scales, i.e., to ask the user to mark his or her degree of certainty by an appropriate mark k on a scale from 0 to n and take μ(x)=k/n. In this paper, we show how to describe this process in terms of the traditional decision making. Our conclusion is that the resulting membership degrees incorporate both probability and utility information. It is therefore not surprising that fuzzy techniques often work better than probabilistic techniques -- which only take into account the …