Computer Engineering Commons^™

Testing Hypotheses On Simulated Data: Why Traditional Hypotheses-Testing Statistics Are Not Always Adequate For Simulated Data, And How To Modify Them, Richard Aló, Vladik Kreinovich, Scott A. Starks

Departmental Technical Reports (CS)

To check whether a new algorithm is better, researchers use traditional statistical techniques for hypotheses testing. In particular, when the results are inconclusive, they run more and more simulations (n2>n1, n3>n2, ..., nm) until the results become conclusive. In this paper, we point out that these results may be misleading. Indeed, in the traditional approach, we select a statistic and then choose a threshold for which the probability of this statistic "accidentally" exceeding this threshold is smaller than, say, 1%. It is very easy to run additional simulations with ever-larger n. The probability of error is still 1% …

Expert System-Type Approach To Voice Disorders: Scheduling Botulinum Toxin Treatment For Adductor Spasmodic Dysphonia, Anthony P. Salvatore, Amitava Biswas, Vladik Kreinovich, Bertha Manriquez, Michael P. Cannito, Robert J. Sinard

Departmental Technical Reports (CS)

One of the most debilitating disorders is adductor spasmodic dysphonia (ADSD), a voice disorder caused by involuntary movements of the muscles of the larynx (voice box). For treating ADSD, botulinum toxin (BT) injections turned out to be very useful. However, the effects of BT are highly variable, so at present, there is no objective criterion of when such a BT treatment is necessary. It is therefore desirable to develop such a criterion.

In this paper, we show that traditional statistical techniques are unable to generate such a criterion, while a natural expert system approach seems to be capable of generating …

Estimating Information Amount Under Interval Uncertainty: Algorithmic Solvability And Computational Complexity, Gang Xiang, Olga Kosheleva, George J. Klir

Departmental Technical Reports (CS)

In most real-life situations, we have uncertainty: we do not know the exact state of the world, there are several (n) different states which are consistent with our knowledge. In such situations, it is desirable to gauge how much information we need to gain to determine the actual state of the world. A natural measure of this amount of information is the average number of "yes"-"no" questions that we need to ask to find the exact state. When we know the probabilities p1,...,pn of different states, then, as Shannon has shown, this number of questions can be determined as S=-p1 …

A Formal Specification In Jml Of The Java Security Package, Poonam Agarwal, Carlos E. Rubio-Medrano, Yoonsik Cheon, Patricia J. Teller

Departmental Technical Reports (CS)

The Java security package allows a programmer to add security features to Java applications. Although the package provides a complex application programming interface (API), its informal description, e.g., Javadoc comments, is often ambiguous or imprecise. Nonetheless, the security of an application can be compromised if the package is used without a concrete understanding of the precise behavior of the API classes and interfaces, which can be attained via formal specification. In this paper, we present our experiences in formally specifying the Java security package in JML, a formal behavior interface specification language for Java. We illustrate portions of our JML …

Fast Computation Of Centroids For Constant-Width Interval-Valued Fuzzy Sets, Jerry M. Mendel, Hongwei Wu, Vladik Kreinovich, Gang Xiang

Departmental Technical Reports (CS)

Interval-valued fuzzy sets provide a more adequate description of uncertainty than traditional fuzzy sets; it is therefore important to use interval-valued fuzzy sets in applications. One of the main applications of fuzzy sets is fuzzy control, and one of the most computationally intensive part of fuzzy control is defuzzification. Since a transition to interval-valued fuzzy sets usually increases the amount of computations, it is vitally important to design faster algorithms for the corresponding defuzzification. In this paper, we provide such an algorithm for a practically important case of constant-width interval-valued fuzzy sets

Topaz: A Firefox Protocol Extension For Gridftp Based On Data Flow Diagrams, Richard Zamudio, Daniel Catarino, Michela Taufer, Brent Stearn, Karan Bhatia

Departmental Technical Reports (CS)

As grid infrastructures mature, an increasing challenge is to provide end-user scientists with intuitive interfaces to computational services, data management capabilities, and visualization tools. The current approach used in a number of cyber-infrastructure projects is to leverage the capabilities of the Mozilla framework to provide rich end-user tools that seamlessly integrate with remote resources such as web/grid services and data repositories.

In this paper we apply rigorous software engineering tools, Data Flow Diagrams or DFDs, to guide the design, implementation, and performance analysis of Topaz, a GridFTP protocol extension to the Firefox browser. GridFTP servers, similar to FTP servers used …

3-D Image Registration Using Fast Fourier Transform, With Potential Applications To Geoinformatics And Bioinformaticsa, Roberto Araiza, Matthew G. Averill, George R. Keller, Scott A. Starks

Departmental Technical Reports (CS)

FFT-based techniques are actively used to register 2-D images, i.e., to find the shift, rotation, and scaling necessary to align one image with the other. It is desirable to extend these techniques to the problem of registering 3-D images. Registration of 3-D images is an important problem in areas such as bioinformatics (e.g., in protein docking) and geoinformatics (e.g., in earth modeling).

Computing Variance Under Interval Uncertainty: A New Algorithm And Its Potential Application To Privacy In Statistical Databases, Richard Aló, Mohsen Beheshti, Gang Xiang

Departmental Technical Reports (CS)

Computation of population mean E=(x1+...+xn)/n and population variance V=(x1^2+...+xn^2)/n -E^2 is an important first step in statistical analysis. In many practical situations, we do not know the exact values of the sample quantities xi, we only know the intervals [Xi-Di, Xi+Di] that contain the actual (unknown) values of xi. Different values of xi from these intervals lead, in general, to different value of population variance. It is therefore desirable to compute the range [V]=[V-,V+] of possible values of V.

This problem of computing population variance under interval uncertainty is, in general, NP-hard. It is known that in some reasonable cases, …

Using Expert Knowledge In Solving The Seismic Inverse Problem, Matthew G. Averill, Kate Miller, George R. Keller, Vladik Kreinovich, Roberto Araiza, Scott A. Starks

Departmental Technical Reports (CS)

For many practical applications, it it important to solve the seismic inverse problem, i.e., to measure seismic travel times and reconstruct velocities at different depths from this data. The existing algorithms for solving the seismic inverse problem often take too long and/or produce un-physical results -- because they do not take into account the knowledge of geophysicist experts. In this paper, we analyze how expert knowledge can be used in solving the seismic inverse problem.

Towards Optimal Use Of Multi-Precision Arithmetic: A Remark, Vladik Kreinovich, Siegfried Rump

Departmental Technical Reports (CS)

If standard-precision computations do not lead to the desired accuracy, then it is reasonable to increase precision until we reach this accuracy. What is the optimal way of increasing precision? One possibility is to choose a constant q>1, so that if the precision which requires the time t did not lead to a success, we select the next precision that requires time q*t. It was shown that among such strategies, the optimal (worst-case) overhead is attained when q=2. In this paper, we show that this "time-doubling" strategy is optimal among all possible strategies, not only among the ones in …

Towards Secure Cyberinfrastructure For Sharing Border Information, Ann Q. Gates, Vladik Kreinovich, Luc Longpre, Paulo Pinheiro Da Silva, Randy G. Keller

Departmental Technical Reports (CS)

In many border-related issues ranging from economic collaboration to border security, it is extremely important that bordering countries share information. One reason why such sharing is difficult is that different countries use different information formats and data structures. It is therefore desirable to design infrastructure to facilitate this information sharing.

UTEP is a lead institution in a similar NSF-sponsored multi-million geoinformatics project, whose goal is to combine diverse and complex geophysical and geographical data stored in different formats and data structures. We describe our experience in using and developing related web service techniques, and we explain how this experience can …

Images With Uncertainty: Efficient Algorithms For Shift, Rotation, Scaling, And Registration, And Their Applications To Geosciences, C. G. Schiek, Roberto Araiza, Jose M. Hurtado, A. A. Velazco, Vladik Kreinovich, V. Sinyanski

Departmental Technical Reports (CS)

In geosciences, we often need to combine two or images of the same area:

in data fusion, we must combine, e.g., data from satellite images with a radar image

in analyzing the effect of an earthquake, we must compare the before and after images, etc.

Compared images are often obtained from slightly different angles, from a slightly different position. Therefore, in order to compare these images, we must register them, i.e., find the shift, rotation, and scaling after which these images match the best, and then apply these transformations to the original images.

There exist efficient algorithms for registration and …

Ellipsoids And Ellipsoid-Shaped Fuzzy Sets As Natural Multi-Variate Generalization Of Intervals And Fuzzy Numbers: How To Elicit Them From Users, And How To Use Them In Data Processing, Vladik Kreinovich, Jan Beck, Hung T. Nguyen

Departmental Technical Reports (CS)

In this paper, we show that ellipsoids are natural multi-variate generalization of intervals and ellipsoid-shaped fuzzy sets are a natural generalization of fuzzy numbers. We explain how to elicit them from users, and how to use them in data processing.

Detecting Outliers Under Interval Uncertainty: A New Algorithm Based On Constraint Satisfaction, Evgeny Dantsin, Alexander Wolpert, Martine Ceberio, Gang Xiang, Vladik Kreinovich

Departmental Technical Reports (CS)

In many application areas, it is important to detect outliers. The traditional engineering approach to outlier detection is that we start with some "normal" values x1,...,xn, compute the sample average E, the sample standard deviation sigma, and then mark a value x as an outlier if x is outside the k0-sigma interval [E-k0*sigma,E+k0*sigma] (for some pre-selected parameter k0). In real life, we often have only interval ranges [xi-,xi+] for the normal values x1,...,xn. In this case, we only have intervals of possible values for the bounds L=E-k0*sigma and U=E+k0*sigma. We can therefore identify outliers as values that are outside all …

The Utep Corpus Of Iraqi Arabic, Nigel Ward, David G. Novick, Salamah I. Salamah

Departmental Technical Reports (CS)

The rules governing turn-taking phenomena are not well understood in general and almost completely undocumented for Arabic. As the first step to modeling these phenomena, we have collected a small corpus of Iraqi Arabic spoken dialogs. The corpus is in three parts. Part A is 110 minutes of unstructured conversations. Parts B1 and B2 are 176 minutes of direction-giving dialogs, most including a greeting phase, a smalltalk phase, a request phase, and a direction-giving phase. Parts A and B1 were recorded with 13 native speakers of Iraqi Arabic, interacting in pairs. In Part B2 the direction-getter is an American with …

Modeling Correlation And Dependence Among Intervals, Scott Ferson, Vladik Kreinovich

Departmental Technical Reports (CS)

This note introduces the notion of dependence among intervals to account for observed or theoretical constraints on the relationships among uncertain inputs in mathematical calculations. We define dependence as any restriction on the possible pairings of values within respective intervals and define nondependence as the degenerate case of no restrictions (which we carefully distinguish from independence in probability theory). Traditional interval calculations assume nondependence, but alternative assumptions are possible, including several which might be practical in engineering settings that would lead to tighter enclosures on arithmetic functions of intervals. We give best possible formulas for addition of intervals under several …

Interval-Based Robust Statistical Techniques For Non-Negative Convex Functions With Application To Timing Analysis Of Computer Chips, Michael Orshansky, Wei-Shen Wang, Gang Xiang, Vladik Kreinovich

Departmental Technical Reports (CS)

In chip design, one of the main objectives is to decrease its clock cycle; however, the existing approaches to timing analysis under uncertainty are based on fundamentally restrictive assumptions. Statistical timing analysis techniques assume that the full probabilistic distribution of timing uncertainty is available; in reality, the complete probabilistic distribution information is often unavailable. Additionally, the existing alternative of treating uncertainty as interval-based, or affine, is limited since it cannot handle probabilistic information in principle. In this paper, a fundamentally new paradigm for timing uncertainty description is proposed as a way to consistently and rigorously handle partially available descriptions of …

On The Functional Form Of Convex Underestimators For Twice Continuously Differentiable Functions, Chirstodoulos A. Floudas, Vladik Kreinovich

Departmental Technical Reports (CS)

The optimal functional form of convex underestimators for general twice continuously differentiable functions is of major importance in deterministic global optimization. In this paper, we provide new theoretical results that address the classes of optimal functional forms for the convex underestimators. These are derived based on the properties of shift-invariance and sign-invariance.

Swarm Intelligence: Theoretical Proof That Empirical Techniques Are Optimal, Dmitry Iourinskiy, Scott A. Starks, Vladik Kreinovich, Stephen F. Smith

Departmental Technical Reports (CS)

A natural way to distribute tasks between autonomous agents is to use swarm intelligence techniques, which simulate the way social insects (such as wasps) distribute tasks between themselves. In this paper, we theoretically prove that the corresponding successful biologically inspired formulas are indeed statistically optimal (in some reasonable sense).

Towards Optimal Techniques For Solving Global Optimization Problems: Symmetry-Based Approach, Chirstodoulos A. Floudas, Vladik Kreinovich

Departmental Technical Reports (CS)

Most techniques for solving global optimization problems have parameters that need to be adjusted to the problem or to the class of problems: for example, in gradient methods, we can select different step sizes. When we have a single parameter (or few parameters) to choose, it is possible to empirically try many values and come up with an (almost) optimal value. Thus, in such situations, we can come up with optimal version of the corresponding technique.

In other approaches, e.g., in methods like convex underestimators, instead of selecting the value of single number-valued parameter, we have select the auxiliary function. …

Interval Finite Element Methods: New Directions, Rafi Muhanna, Vladik Kreinovich, Pavel Solin, Jack Chessa, Roberto Araiza, Gang Xiang

Departmental Technical Reports (CS)

No abstract provided.

Static Timing Analysis Based On Partial Probabilistic Description Of Delay Uncertainty, Wei-Shen Wang, Vladik Kreinovich, Michael Orshansky

Departmental Technical Reports (CS)

No abstract provided.

Monte-Carlo-Type Techniques For Processing Interval Uncertainty, And Their Potential Engineering Applications, Vladik Kreinovich, J. Beck, Carlos M. Ferregut, A. Sanchez, George R. Keller, Matthew G. Averill, Scott A. Starks

Departmental Technical Reports (CS)

In engineering applications, we need to make decisions under uncertainty. Traditionally, in engineering, statistical methods are used, methods assuming that we know the probability distribution of different uncertain parameters. Usually, we can safely linearize the dependence of the desired quantities y (e.g., stress at different structural points) on the uncertain parameters xi - thus enabling sensitivity analysis. Often, the number n of uncertain parameters is huge, so sensitivity analysis leads to a lot of computation time. To speed up the processing, we propose to use special Monte-Carlo-type simulations.

Combining Interval, Probabilistic, And Fuzzy Uncertainty: Foundations, Algorithms, Challenges -- An Overview, Vladik Kreinovich, David J. Berleant, Scott Ferson, Weldon A. Lodwick

Departmental Technical Reports (CS)

Since the 1960s, many algorithms have been designed to deal with interval uncertainty. In the last decade, there has been a lot of progress in extending these algorithms to the case when we have a combination of interval and probabilistic uncertainty. We provide an overview of related algorithms, results, and remaining open problems.

Population Variance Under Interval Uncertainty: A New Algorithm, Evgeny Dantsin, Vladik Kreinovich, Alexander Wolper, Gang Xiang

Departmental Technical Reports (CS)

In statistical analysis of measurement results, it is often beneficial to compute the range [V] of the population variance V when we only know the intervals [Xi-Di,Xi+Di] of possible values of xi. In general, this problem is NP-hard; a polynomial-time algorithm is known for the case when the measurements are sufficiently accurate, i.e., when |Xi-Xj| >= (D_i+D_j)/n for all i =/= j. In this paper, we show that we can efficiently compute [V} under a weaker (and more general) condition |Xi-Xj| >= |D_i-D_j|/n.

Specifying And Checking Method Call Sequences Of Java Programs, Yoonsik Cheon, Ashaveena Perumandla

Departmental Technical Reports (CS)

In a pre and postconditions-style specification, it is difficult to specify the allowed sequences of method calls, referred to as protocols. The protocols are essential properties of reusable object-oriented classes and application frameworks, and the approaches based on the pre and postconditions, such as design by contracts (DBC) and formal behavioral interface specification languages (BISL), are being accepted as a practical and effective tool for describing precise interfaces of (reusable) program modules. We propose a simple extension to the Java Modeling Language (JML), a BISL for Java, to specify protocol properties in an intuitive and concise manner. The key idea …

Optimal Choice Of Granularity In Commonsense Estimation: Why Half-Orders Of Magnitude, Jerry R. Hobbs, Vladik Kreinovich

Departmental Technical Reports (CS)

It has been observed that when people make crude estimates, they feel comfortable choosing between alternatives which differ by a half-order of magnitude (e.g., were there 100, 300, or 1,000 people in the crowd), and less comfortable making a choice on a more detailed scale, with finer granules, or on a coarser scale (like 100 or 1,000). In this paper, we describe two models of choosing granularity in commonsense estimates, and we show that for both models, in the optimal granularity, the next estimate is 3-4 times larger than the previous one. Thus, these two optimization results explain the commonsense …

Computing Mean And Variance Under Dempster-Shafer Uncertainty: Towards Faster Algorithms, Vladik Kreinovich, Gang Xiang, Scott Ferson

Departmental Technical Reports (CS)

In many real-life situations, we only have partial information about the actual probability distribution. For example, under Dempster-Shafer uncertainty, we only know the masses m1,...,mn assigned to different sets S1,...,Sn, but we do not know the distribution within each set Si. Because of this uncertainty, there are many possible probability distributions consistent with our knowledge; different distributions have, in general, different values of standard statistical characteristics such as mean and variance. It is therefore desirable, given a Dempster-Shafer knowledge base, to compute the ranges of possible values of mean E and of variance V.

In their recent paper, A. T. …

Interval-Based Robust Statistical Techniques For Non-Negative Convex Functions, With Application To Timing Analysis Of Computer Chips, Michael Orshansky, Wei-Shen Wang, Martine Ceberio, Gang Xiang

Departmental Technical Reports (CS)

In chip design, one of the main objectives is to decrease its clock cycle. On the design stage, this time is usually estimated by using worst-case (interval) techniques, in which we only use the bounds on the parameters that lead to delays. This analysis does not take into account that the probability of the worst-case values is usually very small; thus, the resulting estimates are over-conservative, leading to unnecessary over-design and under-performance of circuits. If we knew the exact probability distributions of the corresponding parameters, then we could use Monte-Carlo simulations (or the corresponding analytical techniques) to get the desired …

A Fitness Function For Modular Evolutionary Testing Of Object-Oriented Programs, Yoonsik Cheon, Kim Myoung

Departmental Technical Reports (CS)

We show that encapsulation of states in object-oriented programs hinders the search for test data using evolutionary testing. In a well-designed object-oriented program the encapsulated or hidden state is accessible only through exported or public methods. As client code is oblivious to the internal state of a server object, no guidance is available to test the client code using evolutionary testing. In particular, it is difficult to determine the fitness or goodness of test data, as it may depend on the hidden internal state. However, evolutionary testing is a promising new approach whose effectiveness has been shown by several researchers. …