Engineering Commons^™

Detecting Filled Pauses In Tutorial Dialogs, Gaurav Garg, Nigel Ward

Departmental Technical Reports (CS)

As dialog systems become more capable, users tend to talk more spontaneously and less formally. Spontaneous speech includes features which convey information about the user's state. In particular, filled pauses, such as `um' and `uh', can indicate that the user is having trouble, wants more time, wants to hold the floor, or is uncertain. In this paper we present a first study of the acoustic characteristics of filled pauses in tutorial dialogs. We show that in this domain, as in other domains, filled pauses typically have flat pitch and fairly constant energy. We present a simple algorithm based on these …

Fast Computation Of Exact Ranges Of Symmetric Convex And Concave Functions Under Interval Uncertainty, Gang Xiang

Departmental Technical Reports (CS)

Many statistical characteristics y=f(x1,...,xn) are continuous, symmetric, and either concave or convex; examples include population variance V=(1/n)*(x1^2+...+xn^2)-E^2 (where E=(1/n)*(x1+...+xn), Shannon's entropy S=-p1*log(p1)-..-pn*log(pn), and many other characteristics. In practice, often, we often only know the intervals Xi=[xi-,xi+] that contain the (unknown) actual inputs xi. Since different values xi from Xi lead, in general, to different values of f(x1,...,xn), we need to find the range Y={f(x1,...,xn):x1 in X1,...,xn in Xn}, i.e., the maximum and the minimum of f(x1,...,xn) over the box X1 x ... x Xn. It is known that for convex functions, there exists a feasible (polynomial-time) algorithm for computing its …

The Effectiveness Of Threshold-Based Scheduling Policies On Boinc Projects, Trilce Estrada, David A. Flores, Michela Taufer, Patricia J. Teller, Andre Kerstens, David P. Anderson

Departmental Technical Reports (CS)

Several scientific projects use BOINC (Berkeley Open Infrastructure for Network Computing) to perform large-scale simulations using volunteers� computers (workers) across the Internet. In general, the scheduling of tasks in BOINC uses a First-Come-First-Serve policy and no attention is paid to workers� past performance, such as whether they have tended to perform tasks promptly and correctly. In this paper we use SimBA, a discrete-event simulator of BOINC applications, to study new threshold-based scheduling strategies for BOINC projects that use availability and reliability metrics to classify workers and distribute tasks according to this classification. We show that if availability and reliability thresholds …

For Complex Intervals, Exact Range Computation Is Np-Hard Even For Single Use Expressions (Even For The Product), Martine Ceberio, Vladik Kreinovich, Guenter Mayer

Departmental Technical Reports (CS)

One of the main problems of interval computations is to compute the range Y of the given function f(x1,...,xn) under interval uncertainty. Interval computations started with the invention of straightforward interval computations, when we simply replace each elementary arithmetic operation in the code for f with the corresponding operation from interval arithmetic. In general, this technique only leads to an enclosure for the desired range, but in the important case of single use expressions (SUE), in which each variable occurs only once, we get the exact range. Thus, for SUE expressions, there exists a feasible (polynomial-time) algorithm for computing the …

Measuring Privacy Loss In Statistical Databases, Vinod Chirayath, Luc Longpre, Vladik Kreinovich

Departmental Technical Reports (CS)

Protection of privacy in databases has become of increasing importance. While a number of techniques have been proposed to query databases while preserving privacy of individual records in the database, very little is done to define a measure on how much privacy is lost after statistical releases. We suggest a definition based on information theory. Intuitively, the privacy loss is proportional to how much the descriptional complexity of a record decreases relative to the statistical release. There are some problems with this basic definition and we suggest ways to address these problems.

Unimodality, Independence Lead To Np-Hardness Of Interval Probability Problems, Daniel J. Berleant, Olga Kosheleva, Vladik Kreinovich, Hung T. Nguyen

Departmental Technical Reports (CS)

In many real-life situations, we only have partial information about probabilities. This information is usually described by bounds on moments, on probabilities of certain events, etc. -- i.e., by characteristics c(p) which are linear in terms of the unknown probabilities pj. If we know interval bounds on some such characteristics ai <= ci(p) <= Ai, and we are interested in a characteristic c(p), then we can find the bounds on c(p) by solving a linear programming problem.

In some situations, we also have additional conditions on the probability distribution -- e.g., we may know that the two variables x1 and x2 are independent, or that the distribution of x1 and x2 is unimodal. We show that adding each of these conditions makes the corresponding interval probability …

How To Measure Loss Of Privacy, Luc Longpre, Vladik Kreinovich

Departmental Technical Reports (CS)

To compare different schemes for preserving privacy, it is important to be able to gauge loss of privacy. Since loss of privacy means that we gain new information about a person, it seems natural to measure the loss of privacy by the amount of information that we gained. However, this seemingly natural definition is not perfect: when we originally know that a person's salary is between $10,000 and $20,000 and later learn that the salary is between $10,000 and $15,000, we gained exactly as much information (one bit) as when we learn that the salary is an even number -- …

Statistical Data Processing Under Interval Uncertainty: Algorithms And Computational Complexity, Vladik Kreinovich

Departmental Technical Reports (CS)

No abstract provided.

Automatic Labeling Of Back Channels, Udit Sajjanhar, Nigel Ward

Departmental Technical Reports (CS)

In dialog, the proper production of back-channels is an important way for listeners to cooperate with speakers. Developing quantitative models of this process is important both for improving spoken dialog systems and for teaching second language learners. An essential step for the development of such models is labeling all back-channels in corpora of human-human dialogs. Currently this is done by hand. This report describes a method for automatically identifying back-channels in conversation corpora, using only the patterns of speech and silence by the speaker and the listener in the local context. Tested on Arabic, Spanish, and English, this method identifies …

Economics Of Engineering Design Under Interval (And Fuzzy) Uncertainty: Case Study Of Building Design, Carlos M. Ferregut, Jan Beck, Araceli Sanchez, Vladik Kreinovich

Departmental Technical Reports (CS)

One of the main objectives of engineering design is to find a design that is the cheapest among all designs that satisfy given constraints. Most of the constraints must be satisfied under all possible values within certain ranges. Checking all possible combinations of values is often very time-consuming. In this paper, we propose a faster algorithm for checking such constraints.

Growth Rates Under Interval Uncertainty, Janos Hajagos, Vladik Kreinovich

Departmental Technical Reports (CS)

For many real-life systems ranging from financial to population-related to medical, dynamics is described by a system of linear equations. For such systems, the growth rate lambda can be determined as the largest eigenvalue of the corresponding matrix A. In many practical situations, we only know the components of the matrix A with interval (or fuzzy) uncertainty. In such situations, it is desirable to find the range of possible values of lambda. In this paper, we propose an efficient algorithm for computing lambda for a practically important case when all the components of the matrix A are non-negative.

Interval And Fuzzy Techniques In Business-Related Computer Security: Intrusion Detection, Privacy Protection, Mohsen Beheshti, Jianchao Han, Luc Longpre, Scott A. Starks, J. Ivan Vargas, Gang Xiang

Departmental Technical Reports (CS)

E-commerce plays an increasingly large role in business. As a result, business-related computer security becomes more and more important. In this talk, we describe how interval and fuzzy techniques can help in solving related computer security problems.

Bilinear Models From System Approach Justified For Classification, With Potential Applications To Bioinformatics, Richard Aló, Francois Modave, Vladik Kreinovich, David Herrera, Xiaojing Wang

Departmental Technical Reports (CS)

When we do not know the dynamics of a complex system, it is natural to use common sense to get a reasonable first approximation -- which turns out to be a bilinear dynamics. Surprisingly, for classification problems, a similar bilinear approximation turns out to be unexpectedly accurate. In this paper, we provide an explanation for this accuracy.

Helping Students To Become Researchers: What We Can Gain From Russian Experience, Vladik Kreinovich, Ann Q. Gates, Olga Kosheleva

Departmental Technical Reports (CS)

The fact that many internationally renowned scientists have been educated in the former Soviet Union shows that many features of its education system were good. In this session, we briefly describe the features that we believe to have been good. Some of these features have already been successfully implemented (with appropriate adjustments) in affinity research groups at the Department of Computer Science of the The University of Texas at El Paso (UTEP).

Optimized Sampling Frequencies For Weld Reliability Assessments Of Long Pipeline Segments, Cesar J. Carrasco, Vladik Kreinovich

Departmental Technical Reports (CS)

In this paper, we describe new faster algorithms that design an optimal testing strategy for long pipeline segments.

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 …

Interview No. 1655, Newton P. Matthews

Combined Interviews

Newton P. Matthews was born in North Carolina, in January of 1941; grew up in Goldsboro, NC, site of Seymour Johnson Air Base; he graduated college at Wake Forest University in Winston- Salem, NC in 1962; he describes the cold war tension in the early 1960s, he joined the U.S. Air Force to avoid being drafted into the Army; he says he was selected for Officer Training School as a navigator, he wanted to be a pilot but at the time needed 20/20 vision; he mentions being in training during the Cuban Missile Crisis; he recalls navigator bombardier training and …