Computer Sciences Commons^™

Creative Discussions Or Memorization? Maybe Both? (On The Example Of Teaching Computer Science), Vladik Kreinovich, Olga Kosheleva

Departmental Technical Reports (CS)

We all strive to be creative in our teaching, but there is often not enough time to make all the topics creative fun. So sometimes, we teach memorization first, understanding later. We do it, but we often do it without seriously analyzing which topics to "sacrifice" to memorization. In this talk, we use simple mathematical models of learning to come up with relevant recommendations: Namely, all the topics form a dependency graph, and if we do not have enough time to allow students to treat all topics with equal creativity, then the most reasonable topics for memorization first are the …

Why Sugeno Lambda-Measures, Hung T. Nguyen, Vladik Kreinovich, Joe Lorkowski, Saiful Abu

Departmental Technical Reports (CS)

To describe expert uncertainty, it is often useful to go beyond additive probability measures and use non-additive (fuzzy) measures. One of the most widely and successfully used class of such measures is the class of Sugeno lambda-measures. Their success is somewhat paradoxical, since from the purely mathematical viewpoint, these measures are -- in some reasonable sense -- equivalent to probability measures. In this paper, we explain this success by showing that while mathematically, it is possible to reduce Sugeno measures to probability measures, from the computational viewpoint, using Sugeno measures is much more efficient. We also show that among all …

Optimizing Pred(25) Is Np-Hard, Martine Ceberio, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

Usually, in data processing, to find the parameters of the models that best fits the data, people use the Least Squares method. One of the advantages of this method is that for linear models, it leads to an easy-to-solve system of linear equations. A limitation of this method is that even a single outlier can ruin the corresponding estimates; thus, more robust methods are needed. In particular, in software engineering, often, a more robust pred(25) method is used, in which we maximize the number of cases in which the model's prediction is within the 25% range of the observations. In …

How To Test Hypotheses When Exact Values Are Replaced By Intervals To Protect Privacy: Case Of T-Tests, Vladik Kreinovich, Christian Servin

Departmental Technical Reports (CS)

Researchers continuously look for possible relations between relevant quantities, e.g., relations which may help in preventing and curing diseases. Once a hypothesis is made about such a relation, it is necessary to test whether it is confirmed by the data. For such hypothesis testing, t-tests are most widely used. For example, a t-test can check, based on two samples, whether it is possible that they come from distributions with the same mean -- e.g., whether the average blood pressure after a proposed treatment is the same as before or it is provably smaller -- meaning that the tested treatment works. …

Inverse Problems In Theory And Practice Of Measurements And Metrology, Konstantin K. Semenov, Gennadi N. Solopchenko, Vladik Kreinovich

Departmental Technical Reports (CS)

In this paper, we consider the role of inverse problems in metrology. We describe general methods of solving inverse problems which are useful in measurements practice. We also discuss how to modify these methods in situations in which there is a need for real-time data processing.

Fuzzy Intervals As Foundation Of Metrological Support For Computations With Inaccurate Data, Konstantin K. Semenov, Gennady N. Solopchenko, Vladik Kreinovich

Departmental Technical Reports (CS)

In this paper, we discuss the possibility of using the formalism of fuzzy intervals as a basis for computational metrology. We consider advantages of using fuzzy intervals instead of the traditional intervals as a characteristic of uncertainty of the results of computations with inaccurate data.

A Catalog Of While Loop Specification Patterns, Aditi Barua, Yoonsik Cheon

Departmental Technical Reports (CS)

This document provides a catalog of while loop patterns along with their skeletal specifications. The specifications are written in a functional form known as intended functions. The catalog can be used to derive specifications of while loops by first matching the loops to the cataloged patterns and then instantiating the skeletal specifications of the matched patterns. Once their specifications are formulated and written, the correctness of while loops can be proved rigorously or formally using the functional program verification technique in which a program is viewed as a mathematical function from one program state to another.

Construction Of Shear Wave Models By Applying Multi-Objective Optimization To Multiple Geophysical Data Sets, Lennox Thompson, Aaron A. Velasco, Vladik Kreinovich

Departmental Technical Reports (CS)

For this work, our main purpose is to obtain a better understanding of the Earth's tectonic processes in the Texas region, which requires us to analyze the Earth structure. We expand on a constrained optimization approach for a joint inversion least-squares (LSQ) algorithm to characterize a one-dimensional Earth's structure of Texas with the use of multiple geophysical data sets. We employed a joint inversion scheme using multiple geophysical datasets for the sole purpose of obtaining a three-dimensional velocity structure of Texas in order to identify an ancient rift system within Texas. In particular, we use data from the USArray, which …

What If We Only Have Approximate Stochastic Dominance?, Vladik Kreinovich, Hung T. Nguyen, Songsak Sriboonchitta

Departmental Technical Reports (CS)

In many practical situations, we need to select one of the two alternatives, and we do not know the exact form of the user's utility function -- e.g., we only know that it is increasing. In this case, stochastic dominance result says that if the cumulative distribution function (cdf) corresponding to the first alternative is always smaller than or equal than the cdf corresponding to the second alternative, then the first alternative is better. This criterion works well in many practical situations, but often, we have situations when for most points, the first cdf is smaller but at some points, …

How To Assign Weights To Different Factors In Vulnerability Analysis: Towards A Justification Of A Heuristic Technique, Beverly Rivera, Irbis Gallegos, Vladik Kreinovich

Departmental Technical Reports (CS)

The main objective of vulnerability analysis is to select the alternative which is the least vulnerable. To make this selection, we must describe the vulnerability of each alternative by a single number -- then we will select the alternative with the smallest value of this vulnerability index. Usually, there are many aspects of vulnerability: vulnerability of a certain asset to a storm, to a terrorist attack, to hackers' attack, etc. For each aspect, we can usually gauge the corresponding vulnerability, the difficulty is how to combine these partial vulnerabilities into a single weighted value. In our previous research, we proposed …

Dealing With Uncertainties In Computing: From Probabilistic And Interval Uncertainty To Combination Of Different Types Of Uncertainty, Vladik Kreinovich

Departmental Technical Reports (CS)

To predict values of future quantities, we apply algorithms to the current and past measurement results. Because of the measurement errors and model inaccuracy, the resulting estimates are, in general, different from the desired values of the corresponding quantities. There exist methods for estimating this difference, but these methods have been mainly developed for the two extreme cases: the case when we know the exact probability distributions of all the measurement errors and the interval case, when we only know the bounds on the measurement errors. In practice, we often have some partial information about the probability distributions which goes …

R-Bounded Fuzzy Measures Are Equivalent To Epsilon-Possibility Measures, Karen A. Richart-Ruiz, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

Traditional probabilistic description of uncertainty is based on additive probability measures. To describe non-probabilistic uncertainty, it is therefore reasonable to consider non-additive measures. An important class of non-additive measures are possibility measures, for which m(A union B) = max(m(A), m(B)). In this paper, we show that possibility measures are, in some sense, universal approximators: for every epsilon > 0, every non-additive measure which satisfies a certain reasonable boundedness property is equivalent to a measure which is epsilon-close to a possibility measure.

How To Estimate Relative Spatial Resolution Of Different Maps Or Images Of The Same Area?, Christian Servin, A A. Velasco, Vladik Kreinovich

Departmental Technical Reports (CS)

In this paper, we describe how to estimate relative spatial resolution of different maps or images of the same area under uncertainty. We consider probabilistic and fuzzy approaches and we show that both approaches lead to the same estimates -- which makes us more confident that this joint result is reasonable.

A Simple Probabilistic Explanation Of Term Frequency-Inverse Document Frequency (Tf-Idf) Heuristic (And Variations Motivated By This Explanation), Lukas Havrlant, Vladik Kreinovich

Departmental Technical Reports (CS)

In document analysis, an important task is to automatically find keywords which best describe the subject of the document. One of the most widely used techniques for keyword detection is a technique based on the term frequency-inverse document frequency (tf-idf) heuristic. This techniques has some explanations, but these explanations are somewhat too complex to be fully convincing. In this paper, we provide a simple probabilistic explanation for the tf-idf heuristic. We also show that the ideas behind explanation can help us come up with more complex formulas which will hopefully lead to a more adequate detection of keywords.

Wiener's Conjecture About Transformation Groups Helps Predict Which Fuzzy Techniques Work Better, Francisco Zapata, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

Often, application success only comes when we select specific fuzzy techniques (t-norm, membership function, etc.) -- and in different applications, different techniques are the best. How to find the best technique? Exhaustive search of all techniques is not an option: there are too many of them. We need to come up with a narrow class of promising techniques, so that trying them all is realistic. In this paper, we show that such a narrowing can be obtained from transformation groups techniques motivated by N. Wiener's conjecture -- which was, in its turn, motivated by observations about human vision.

Towards Efficient Algorithms For Approximating A Fuzzy Relation By Fuzzy Rules: Case When "And"- And "Or"-Operation Are Distributive, Christian Servin, Vladik Kreinovich

Departmental Technical Reports (CS)

A generic fuzzy relation often requires too many parameters to represent -- especially when we have a relation between many different quantities x1, ..., xn. There is, however, a class of relations which require much fewer parameters to describe - namely, relations which come from fuzzy rules. It is therefore reasonable to approximate a given relation by fuzzy rules. In this paper, we explain how this can be done in an important case when "and"- and "or"-operation are distributive -- and we also explain why this case is important.

Interval And Symmetry Approaches To Uncertainty -- Pioneered By Wiener -- Helps Explain Many Seemingly Irrational Human Behaviors: A Case Study, Joe Lorkowski, Vladik Kreinovich

Departmental Technical Reports (CS)

It has been observed that in many cases, when we present a user with three selections od different price (and, correspondingly, different quality), then the user selects the middle selection. This empirical fact -- known as a compromise effect -- seems to contradicts common sense. Indeed, when a rational decision-maker selects one of the two alternatives, and then we add an additional option, then the user will either keep the previous selection or switch to a new option, but he/she will not select a previously rejected option. However, this is exactly what happens under the compromise effect. If we present …

Writing Self-Testing Java Classes With Selftest, Yoonsik Cheon

Departmental Technical Reports (CS)

This document provides a tutorial introduction to Java annotations called SelfTest. The SelfTest annotations allow one to annotate Java classes with test data, and the SelfTest annotation processor generates executable JUnit test classes from annotated Java classes by translating test cases to executable JUnit tests. The SelfTest annotations not only automate unit testing of Java classes significantly but also provides a step toward writing self-testing Java classes by embedding test data in source code for both compile and runtime processing.

Simpler-To-Describe Cases Are Often More Difficult To Prove: A Possible Explanation, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

In many areas of mathematics, simpler-to-describe cases are often more difficult to prove. In this paper, we provide examples of such phenomena (Bieberbach's Conjecture, Poincar\'e Conjecture, Fermat's Last Theorem), and we provide a possible explanation for this empirical fact.

Logic Of Scientific Discovery: How Physical Induction Affects What Is Computable, Vladik Kreinovich, Olga Kosheleva

Departmental Technical Reports (CS)

Most of our knowledge about a physical world comes from physical induction: if a hypothesis is confirmed by a sufficient number of observations, we conclude that this hypothesis is universally true. We show that a natural formalization of this property affects what is computable when processing measurement and observation results, and we explain how this formalization is related to Kolmogorov complexity and randomness. We also consider computational consequences of an alternative idea also coming form physics: that no physical law is absolutely true, that every physical law will sooner or later need to be corrected. It turns out that this …

Roadmap For Graduating Students With Expertise In The Analysis And Development Of Secure Cyber-Systems, Ann Q. Gates, Salamah Salamah, Luc Longpre

Departmental Technical Reports (CS)

Modern society is intensely and irreversibly dependent on software systems of extraordinary size and complexity. This includes software systems in domain areas such as defense, energy, communication, transportation, and manufacturing. Due to the rapid expansion and reliance on the global Internet for day-to-day functions of individuals, organizations, governments, and industry around the world, cyber-security has emerged as an essential component of computing curricula. To address regional and national needs, the Computer Science Department has defined a roadmap for educating and preparing students who have expertise in the analysis and development of secure cyber-systems. Toward that vision, the department has set …

Fuzzy Logic Ideas Can Help In Explaining Kahneman And Tversky's Empirical Decision Weights, Joe Lorkowski, Vladik Kreinovich

Departmental Technical Reports (CS)

Analyzing how people actually make decisions, the Nobelist Daniel Kahneman and his co-author Amos Tversky found out that instead of maximizing the expected gain, people maximize a weighted gain, with weights determined by the corresponding probabilities. The corresponding empirical weights can be explained qualitatively, but quantitatively, these weights remains largely unexplained. In this paper, we show that with a surprisingly high accuracy, these weights can be explained by fuzzy logic ideas.

From Interval-Valued Probabilities To Interval-Valued Possibilities: Case Studies Of Interval Computation Under Constraints, Luis C. Gutierrez, Martine Ceberio, Vladik Kreinovich, Rebekah L. Gruver, Mariana Peña, Mathew J. Rister, Abraham Saldaña, John Vasquez, Janelle Ybarra, Salem Benferhat

Departmental Technical Reports (CS)

In many engineering situations, we need to make decisions under uncertainty. In some cases, we know the probabilities p_i of different situations i; these probabilities should add up to 1. In other cases, we only have expert estimates of the degree of possibility μ_ii of different situations; in accordance with the possibility theories, the largest of these degrees should be equal to 1.

In practice, we often only know these degrees p_i and μ_ii with uncertainty. Usually, we know the upper bound and the lower bound on each of these values. In other words, …

Decision Making Under Interval Uncertainty: What Can And What Cannot Be Computed In Linear Time And In Real Time, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

In engineering, we constantly need to make decisions: which design to select, which parameters to select for this design, etc.

The traditional approach to decision making is based on the assumption that we know all possible consequences of each alternative, and we know the probability of each such consequence. Under this assumption, we can describe a rational decision-making process: to each possible consequence, we assign a numerical values called its utility, and we select the alternative for which the expected value of the utility is the largest.

An important advantage of this approach is that it can be performed in …

Extending Ocl To Better Express Uml Qualified Associations, Alla Dove, Aditi Barua, Yoonsik Cheon

Departmental Technical Reports (CS)

A qualified association in the Unified Modeling Language (UML) is an association that allows one to restrict the objects referred in an association using a key called a qualifier. A qualified association can appear in a constraint written in the Object Constraint Language (OCL) to specify a precise UML model. However, the OCL notation fails to provide appropriate support for expressing certain types of constraints written using qualified associations. In this paper we first describe a deficiency of OCL in expressing qualified associations and then propose a small extension to OCL to make it more expressive. The key idea of …

How To Understand Connections Based On Big Data: From Cliques To Flexible Granules, Ali Jalal-Kamali, M. Shahriar Hossain, Vladik Kreinovich

Departmental Technical Reports (CS)

One of the main objectives of science and engineering is to predict the future state of the world -- and to come up with actions which will lead to the most favorable outcome. To be able to do that, we need to have a quantitative model describing how the values of the desired quantities change -- and for that, we need to know which factors influence this change. Usually, these factors are selected by using traditional statistical techniques, but with the current drastic increase in the amount of available data -- known as the advent of {\it big data} -- …

Towards Decision Making Under Interval, Set-Valued, Fuzzy, And Z-Number Uncertainty: A Fair Price Approach, Joe Lorkowski, Vladik Kreinovich, Rafik Aliev

Departmental Technical Reports (CS)

In this paper, we explore one of the possible ways to make decisions under uncertainty: namely, we explain how to define a fair price for a participation in such a decision, and then select an alternative for which the corresponding fair price is the largest. This idea is explained on the examples of interval uncertainty, set-valued, fuzzy, and Z-number uncertainty.

Fitts's Law: Towards A Geometric Explanation, Olga Kosheleva, Vladik Kreinovich, Octavio Lerma

Departmental Technical Reports (CS)

In designing human-computer interfaces, designers use an empirical Fitts's Law, according to which the average time T of accessing an icon of size w at a distance d from the center of the screen is proportional to the logarithm of the ratio w/d. There exist explanations for this law, but these explanations have gaps. In this paper, we show that these gaps can be explained if we analyze this problem from the geometric viewpoint. Thus, we get a geometric explanation of the Fitts's Law.

How To Compare Different Range Estimations: A Symmetry-Based Approach, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

How to compare different range estimators for multivariate functions under uncertainty? To answer this question, we analyze which utility functions can be used for this task. Specifically, we: (1) introduce various invariance assumptions, (2) describe the class of all utility functions which satisfy these assumptions, and (3) show how the resulting utility functions can be used to compare different range estimators.

Range Estimation Under Constraints Is Computable Unless There Is A Discontinuity, Martine Ceberio, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

One of the main problems of interval computations is computing the range of a given function over given intervals. It is known that there is a general algorithm for computing the range of computable functions over computable intervals. However, if we take into account that often in practice, not all possible combinations of the inputs are possible (i.e., that there are constraints), then it becomes impossible to have an algorithm which would always compute this range. In this paper, we explain that the main reason why range estimation under constraints is not always computable is that constraints may introduce discontinuity …