Computer Sciences Commons^™

Feasible Algorithms For Lattice And Directed Subspaces, Jennifer (Hamlyn) Del Valle, Vladik Kreinovich, Piotr Wojciechowski

Departmental Technical Reports (CS)

In some practical situations (e.g., in econometrics), it is important to check whether a given linear subspace of a space R^m with component-wise order is a lattice -- and if it is not, whether it is at least a directed ordered space. Because of the practical importance, it is desirable to have feasible algorithms for solving these problems -- which in Computer Science is usually interpreted as algorithms whose computation time does not exceed a polynomial of the length of the input. No such algorithms were previously known. In this paper, we present feasible algorithms for solving both problems.

Approximate Nature Of Traditional Fuzzy Methodology Naturally Leads To Complex-Valued Fuzzy Degrees, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

In the traditional fuzzy logic, the experts' degrees of confidence in their statements is described by numbers from the interval [0,1]. These degree have a clear intuitive meaning. Somewhat surprisingly, in some applications, it turns out to be useful to also consider different numerical degrees -- e.g., complex-valued degrees. While these complex-valued degrees are helpful in solving practical problems, their intuitive meaning is not clear. In this paper, we provide a possible explanation for the success of complex-valued degrees which makes their use more intuitively understandable -- namely, we show that these degrees naturally appear due to the approximate nature …

Knowledge Geometry Is Similar To General Relativity: Both Mass And Knowledge Curve The Corresponding Spaces, Francisco Zapata, Vladik Kreinovich

Departmental Technical Reports (CS)

In this paper, we explain and explore the idea that knowledge is similar to mass in physics: similarly to how mass curves space-time, knowledge curves the corresponding knowledge space.

Finding Specifications Of While Statements Using Patterns, Aditi Barua, Yoonsik Cheon

Departmental Technical Reports (CS)

A formal correctness proof of code containing loops such as while statements typically uses the technique of proof-by-induction, and often the most difficult part of carrying out an inductive proof is formulating a correct induction hypothesis, a specification for a loop statement. An incorrect induction hypothesis will surely lead to a proof failure. In this paper we propose a systematic way for identifying specifications of while statements. The key idea of our approach is to categorize and document common patterns of while statements along with their specifications. This is based on our observation that similarly-structured while statements frequently have similarly-structured …

Picture Fuzzy Sets - A New Concept For Computational Intelligence Problems, Bui Cong Cuong, Vladik Kreinovich

Departmental Technical Reports (CS)

Since Zadeh introduced fuzzy sets in 1965, a lot of new theories treating imprecision and uncertainty have been introduced. Some of these theories are extensions of fuzzy set theory, other try to handle imprecision and uncertainty in different way. In this paper, we introduce a new notion of picture fuzzy sets (PFS), which are directly extensions of fuzzy sets and of intuitonistic fuzzy sets (Atanassov). Then some operations on picture fuzzy sets are defined and some properties of these operations are considered. Here the basic preliminaries of PFS theory are presented.

Studying Volatility And Dependency Of Chinese Outbound Tourism Demand In Singapore, Malaysia, And Thailand: A Vine Copula Approach, Jianxu Liu, Songsak Sriboonchitta, Hung T. Nguyen, Vladik Kreinovich

Departmental Technical Reports (CS)

This paper investigates the volatility and dependence of Chinese tourism demand for Singapore, Malaysia, and Thailand (SMT) destinations, using the vine copula based auto regression moving average-generalized autoregressive conditional heteroskedasticity (ARMA-GARCH) model. It is found that a jolt to the tourist flow can have long-standing ramifications for the SMT countries. The estimation of the vine copulas among SMT show that the Survival Gumbel, Frank, and Gaussian copulas are the best copulas for Canonical vine (C-vine) or Drawable vine (D-vine) among the possible pair-copulas. In addition, this paper illustrates the making of time-varying Frank copulas for vine copulas. Finally, there is …

From Urysohn's Universal Metric Space To A Universal Space-Time, A. G. Aksoy, Z. Glassman, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

A known Urysohn's result shows that there exists a universal} metric space, i.e., a metric space into every other (separable) metric space can be isomorphically embedded. Moreover, this universal metric space can be selected to be ultra-homogeneous -- every isomorphism of its two finite subsets can be extended to the isomorphism of the whole space.

Starting with Einstein's theories of Special and General relativity, space-times are described by a different type of structure -- a set (of events) equipped with the proper time t(a,b) between points a and b; such spaces are known as space-times with kinematic metric, or k-space-times. …

Algebraic Product Is The Only T-Norm For Which Optimization Under Fuzzy Constraints Is Scale-Invariant, Juan Carlos Figueroa Garcia, Martine Ceberio, Vladik Kreinovich

Departmental Technical Reports (CS)

In many practical situations, we need to optimize under fuzzy constraints. There is a known Bellman-Zadeh approach for solving such problems, but the resulting solution, in general, depends on the choice of a not well-defined constant M. We show that this dependence disappears if we use an algebraic t-norm (and-operation) a * b, and we also prove that the algebraic product is the only t-norm for which the corresponding solution is independent on M.

A Vine Copula Approach For Analyzing Financial Risk And Co-Movement Of The Indonesian, Philippine And Thailand Stock Markets, Songsak Sriboonchitta, Jianxu Liu, Vladik Kreinovich, Hung T. Nguyen

Departmental Technical Reports (CS)

This paper aims at analyzing the financial risk and co-movement of stock markets in three countries: Indonesia, Philippine and Thailand. It consists of analyzing the conditional volatility and test the leverage effect in the stock markets of the three countries. To capture the pairwise and conditional dependence between the variables, we use the method of vine copulas. In addition, we illustrate the computations of the value at risk and the expected shortfall using Monte Carlo simulation with copula based GJR-GARCH model. The empirical evidence shows that all the leverage effects add much to the capacity for explanation of the three …

Data Collection For The Similar Segments In Social Speech Task, Nigel G. Ward, Steven D. Werner

Departmental Technical Reports (CS)

Information retrieval systems rely heavily on models of similarity, but for spoken dialog such models currently use mostly standard textual-content similarity. As part of the MediaEval Benchmarking Initiative, we have created a new corpus to support development of similarity models for spoken dialog. This corpus includes 26 casual dialogs among members of two semi-cohesive groups, totaling about 5 hours, with 1889 labeled regions associated into 227 sets which annotators judged to be similar enough to share a tag. This technical report brings together information about this corpus and its intended uses.

Similarity Approach To Defining Basic Level Of Concepts Explained From The Utility Viewpoint, Joe Lorkowski, Martin Trnecka

Departmental Technical Reports (CS)

In many practical situations, it is necessary to describe an image in words. From the purely logical viewpoint, to describe the same object, we can use concepts of different levels of abstraction: e.g., when the image includes a dog, we can say that it is a dog, or that it is a mammal, or that it is a German Shepherd. In such situations, humans usually select a concept which, to them, in the most natural; this concept is called the basic level concept. However, the notion of a basic level concept is difficult to describe in precise terms; as a …

Complete Description Of Idempotent Hedges In Fuzzy Logic, Jaime Nava

Departmental Technical Reports (CS)

In describing expert knowledge, it is often important to properly take into account hedges} like "very", "somewhat", etc. In particular, fuzzy logic provides a consistent way of describing hedges. For some of the hedges, a repetition changes the meaning: e.g., "very very small" is smaller than "very small". However, other hedges -- like "somewhat" -- are idempotent, in the sense that repeating this hedge twice does not change the meaning. In this paper, we provide a complete description of such idempotent hedges.

On Early Stages Of Idea Propagation, The Number Of Adopters Grows As N(T) ~ C * Ta: Theoretical Explanation Of The Empirical Observation, L. Octavio Lerma, Deana Pennington, Vladik Kreinovich

Departmental Technical Reports (CS)

New good ideas sometimes propagate too slowly. To speed up their propagation, we need to have a quantitative understanding of how ideas propagate. An intuitive understanding of ideas propagation has led to several reasonable first-approximation mathematical models. These models provide a good description of idea propagation on the later stages, when the ideas have already been adopted by a reasonably large number of people. However, at the critically important early stages, these models are not perfect: these models predict a linear growth with time, while empirical growth data is often better described by a power law. In this paper, we …

Vine Copulas As A Way To Describe And Analyze Multi-Variate Dependence In Econometrics: Computational Motivation And Comparison With Bayesian Networks And Fuzzy Approaches, Songsak Sriboonchitta, Jianxu Liu, Vladik Kreinovich, Hung T. Nguyen

Departmental Technical Reports (CS)

In the last decade, vine copulas emerged as a new efficient techniques for describing and analyzing multi-variate dependence in econometrics. Our experience has shown, however, that while these techniques have been successfully applied to many practical problems of econometrics, there is still a lot of confusion and misunderstanding related to vine copulas. In this paper, we provide a motivation for this new technique from the computational viewpoint. We show that other techniques used to described dependence -- Bayesian networks and fuzzy techniques -- can be viewed as a particular case of vine copulas.

How To Distinguish True Dependence From Varying Independence?, Marketa Krmelova, Martin Trnecka, Vladik Kreinovich, Berlin Wu

Departmental Technical Reports (CS)

A usual statistical criterion for the quantities X and Y to be independent is that the corresponding distribution function F(x,y) is equal to the product of the corresponding marginal distribution functions. If this equality is violated, this is usually taken to mean that X and Y are dependent. In practice, however, the inequality may be caused by the fact that we have a mixture of several populations, in each of which X and Y are independent. In this paper, we show how we can distinguish true dependence from such varying independence. This can also lead to new measures to degree …

How To Faster Test A Device For Different Combinations Of Parameters, Francisco Zapata, Luis C. Gutierrez, Vladik Kreinovich

Departmental Technical Reports (CS)

A device has to function properly under all possible conditions: e.g., for all temperatures within a given range, for all possible humidity values within a given range, etc. Ideally, it would be nice to be able to test a device for all possible combinations of these parameters, but the number of such combinations is often so huge that such an exhaustive testing is not possible. Instead, it is reasonable to check the device for all possible values of each parameter, for each possible pairs of values of two parameters, and, in general, for all possible combinations of values of k …

Why Trapezoidal And Triangular Membership Functions Work So Well: Towards A Theoretical Explanation, Aditi Barua, Lalitha Snigdha Mudunuri, Olga Kosheleva

Departmental Technical Reports (CS)

In fuzzy logic, an imprecise ("fuzzy") property is described by its membership function μ(x), i.e., by a function which describes, for each real number x, to what degree this real number satisfies the desired property. In principle, membership functions can be of different shape, but in practice, trapezoidal and triangular membership functions are most frequently used. In this paper, we provide an interval-based theoretical explanation for this empirical fact.

Note On Fair Price Under Interval Uncertainty, Joshua Mckee, Joe Lorkowski, Thavatchai Ngamsantivong

Departmental Technical Reports (CS)

Often, in decision making situations, we do not know the exact value of a gain resulting from making each decision, we only know the bounds on this gain. To make a reasonable decision under such interval uncertainty, it makes sense to estimate the fair price of each alternative, and then to select the alternative with the highest price. In this paper, we show that the value of the fair price can be uniquely determined from some reasonable requirements: e.g., the additivity requirement, that the fair price of two objects together should be equal to the sum of the fair prices …

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 …