Computer Engineering Commons^™

Studies In The Use Of Time Into Utterance As A Predictive Feature For Language Modeling, Nigel Ward, Alejandro Vega

Departmental Technical Reports (CS)

In (Ward and Vega 2008) we examined how how word probabilities vary with time into utterance, and proposed a method for using this information to improve a language model. In this report we examine some ancillary issues in the modeling and exploitation of these regularities.

Functional Specification And Verification Of Object-Oriented Programs, Yoonsik Cheon

Departmental Technical Reports (CS)

One weakness of Hoare-style verification techniques based on first-order predicate logic is that reasoning is backward from postconditions to preconditions. A natural, forward reasoning is possible by viewing a program as a mathematical function that maps one program state to another. This functional program verification technique requires a minimal mathematical background as it uses equational reasoning based on sets and functions. Thus, it can be easily taught and used in practice. In this paper, we formalize a functional program specification and verification technique and extend it for object-oriented programs. Our approach allows one to formally specify and verify the behavior …

Why Ellipsoid Constraints, Ellipsoid Clusters, And Riemannian Space-Time: Dvoretzky's Theorem Revisited, Karen Villaverde, Olga Kosheleva, Martine Ceberio

Departmental Technical Reports (CS)

In many practical applications, we encounter ellipsoid constraints, ellipsoid-shaped clusters, etc. A usual justification for this ellipsoid shape comes from the fact that many real-life quantities are normally distributed, and for a multi-variate normal distribution, a natural confidence set (containing the vast majority of the objects) is an ellipsoid. However, ellipsoid appear more frequently than normal distributions (which occur in about half of the cases). In this paper, we provide a new justification for ellipsoids based on a known mathematical result -- Dvoretzky's Theorem.

Towards An Efficient Bisection Of Ellipsoids, Paden Portillo, Martine Ceberio, Vladik Kreinovich

Departmental Technical Reports (CS)

Constraints are often represented as ellipsoids. One of the main advantages of such constrains is that, in contrast to boxes, over which optimization of even quadratic functions is NP-hard, optimization of a quadratic function over an ellipsoid is feasible. Sometimes, the area described by constrains is too large, so it is reasonable to bisect this area (one or several times) and solve the optimization problem for all the sub-areas. Bisecting a box, we still get a box, but bisecting an ellipsoid, we do not get an ellipsoid. Usually, this problem is solved by enclosing the half-ellipsoid in a larger ellipsoid, …

From Computing Sets Of Optima, Pareto Sets, And Sets Of Nash Equilibria To General Decision-Related Set Computations, Vladik Kreinovich

Departmental Technical Reports (CS)

Several algorithms have been proposed to compute sets of optima, Pareto sets, sets of Nash equilibria. In this paper, we present a general algorithm for decision-related set computations that includes all these algorithms as particular cases.

To make our algorithm understandable to people working in optimization and in game theory, we also provide motivations and explanations for our formalizations of the corresponding problems and for the related notions of computable mathematics.

Minimum Description Length (Mdl) Principle As A Possible Approach To Arc Detection, Jan Beck, David Nemir, Vladik Kreinovich

Departmental Technical Reports (CS)

Detecting arcing faults is an important but difficult-to-solve practical problem. In this paper, we show how the Minimum Description Length (MDL) Principle can help in solving this problem.

Optimal Prices In The Presence Of Discounts: A New Economic Application Of Choquet Integrals, Hung T. Nguyen, Vladik Kreinovich

Departmental Technical Reports (CS)

In many real-life situations, there are ``package deals'', when customers who buy two or more different items get a special discount. For example, when planning a trip, a deal including airfare and hotel costs less than the airfare and hotel on their own; there are often also special deals when we combine airfare with car rental, and deals that cover all three items plus tickets to local tourist attractions, etc.

Usually, there are several such deals with different combinations and different discounts. What if we plan to buy several different copies of each item: e.g., we plan a group tour …

Spatial Resolution For Processing Seismic Data: Type-2 Methods For Finding The Relevant Granular Structure, Vladik Kreinovich, Jaime Nava, Rodrigo Romero, Julio Olaya, Aaron A. Velasco, Kate C. Miller

Departmental Technical Reports (CS)

One of the main methods of determining the Earth structure is the analysis of the seismic data. Based on the seismic data, we produce a 3-D map describing the density at different locations on different depths. Due to incomplete coverage and measurement uncertainty, this map provides only an approximate description of the actual density distribution. For example, based on the seismic data, it is impossible to distinguish between the densities at two nearby points. In other words, what we actually reconstruct is not a function of 3 variables, but rather values determined on the appropriate spatial granules. Because of this …

How To Describe Spatial Resolution: An Approach Similar To The Central Limit Theorem, Omar Ochoa, Martine Ceberio, Vladik Kreinovich

Departmental Technical Reports (CS)

For spatially distributed quantities v(x), there are two main reasons why the measured value is different from the actual value. First, the sensors are imprecise, so the measured value is slightly different from the actual one. Second, sensors have a finite {\it spatial resolution}: they do not simply measure the value at a single point, they are "blurred", i.e., affected by the values of the nearby points as well. It is known that uncertainty can be often described by the Gaussian distribution. This possibility comes from the Central Limit Theorem, according to which the sum of many independent small measurement …

Toward Computing An Optimal Trajectory For An Environment-Oriented Unmanned Aerial Vehicle (Uav) Under Uncertainty, Jerald Brady, Octavio Lerma, Vladik Kreinovich, Craig Tweedie

Departmental Technical Reports (CS)

Over the past decade a few but increasing number of researchers have begun using Unmanned Aerial Vehicles (UAVs) to expand and improve upon existing remote sensing capabilities in the Arctic. Due to the limited flight time, it is important to make sure that the UAV follows an optimal trajectory -- in which it cover all the points from a given area within the smallest possible trajectory length. Under the usual assumptions that we cover a rectangular area and that each on-board sensor covers all the points with a given radius r, we describe the optimal trajectory. A more complex optimal …

Towards A More Adequate Defuzzification Of Interval-Valued Fuzzy Sets, Vladik Kreinovich, Van Nam Huynh, Yoshiteru Nakamori

Departmental Technical Reports (CS)

It is known that interval-valued fuzzy sets [m(x)] provide a more adequate description of expert uncertainty than the more traditional "type-1" (number-valued) fuzzy techniques. Specifically, an interval-valued fuzzy set can be viewed as a class of possible fuzzy sets m(x) from [m(x)]. In this case, as a result of defuzzification, it is natural to return the range [u] of all possible values u(m) that can be obtained by defuzzifying membership functions m(x) from this class. In practice, it is reasonable to restrict ourselves only to fuzzy numbers m(x), i.e., to "unimodal" fuzzy sets. Under this restriction, in general, we get …

How To Define A Confidence Set For Functions: A New Justification Of The Area Method, Vladik Kreinovich, Gang Xiang, Michael Oberguggenberger

Departmental Technical Reports (CS)

Due to uncertainty, in many problems, we only know the probability of different values. In such situations, we need to make decisions based on these probabilities: e.g., we must tell the user which values are possible and which are not. Often -- e.g., for a normal distribution -- the probability density is everywhere positive, so, theoretically, all real values are possible. In practice, it is usually safe to assume that values whose probability is very small are not possible. For a single variable, this idea is described by a confidence interval C, the interval for which the probability to be …

Femprof: Advancing Females To The Professoriate In Computing, Nestor J. Rodriguez, Richard A. Alo, Sarah Hug, Sangeeta Gad, Nayda Santiago, Gladys O. Ducodray

Departmental Technical Reports (CS)

Considering both the percentage of science and engineering PhDs awarded to women in the twenty year period 1974-2004 and the data from the National Science 2006 Survey of Earned Doctorates 1974-2004, the U.S. National Academies noted that women in 2004 have attained equality with men in their representation in the Social Sciences and Life Sciences but are still lagging in Physical and Computing Sciences and Engineering. In the top 50 engineering departments in the U.S., women earn one-fourth of the PhDs granted in Chemical Engineering and 15% in engineering overall (Handelsman et al, 2005). Although women constitute about half of …

How To Relate Fuzzy And Owa Estimates, Tanja Magoc, Vladik Kreinovich

Departmental Technical Reports (CS)

In many practical situations, we have several estimates x1, ..., xn of the same quantity x, i.e., estimates for which x1 ~ x, x2 ~ x, ..., and xn ~ x. It is desirable to combine (fuse) these estimates into a single estimate for x. From the fuzzy viewpoint, a natural way to combine these estimates is: (1) to describe, for each x and for each i, the degree mu(xi - x) to which x is close to xi, (2) to use a t-norm ("and"-operation) to combine these degrees into a degree to which x is consistent with all n …

Efficient Algorithms For Heavy-Tail Analysis Under Interval Uncertainty, Vladik Kreinovich, Monchaya Chiangpradit, Wararit Panichkitkosolkul

Departmental Technical Reports (CS)

Most applications of statistics to science and engineering are based on the assumption that the corresponding random variables are normally distributed, i.e., distributed according to Gaussian law in which the probability density function d(x) exponentially decreases with x: d(x) ~ exp(-k * x^2). Normal distributions indeed frequently occur in practice. However, there are also many practical situations, including situations from mathematical finance, in which we encounter heavy-tailed distributions, i.e., distributions in which d(x) decreases as d(x) ~ x^(-a). To properly take this uncertainty into account when making decisions, it is necessary to estimate the parameters of such distributions based on …

Metrization Theorem For Space-Times: From Urysohn's Problem Towards Physically Useful Constructive Mathematics, Vladik Kreinovich

Departmental Technical Reports (CS)

In the early 1920s, Pavel Urysohn proved his famous lemma (sometimes referred to as "first non-trivial result of point set topology"). Among other applications, this lemma was instrumental in proving that under reasonable conditions, every topological space can be metrized.

A few years before that, in 1919, a complex mathematical theory was experimentally proven to be extremely useful in the description of real world phenomena: namely, during a solar eclipse, General Relativity theory -- that uses pseudo-Riemann spaces to describe space-time -- has been (spectacularly) experimentally confirmed. Motivated by this success, Urysohn started working on an extension of his lemma …

Extending Maximum Entropy Techniques To Entropy Constraints, Gang Xiang, Vladik Kreinovich

Departmental Technical Reports (CS)

In many practical situations, we have only partial information about the probabilities. In some cases, we have {\em crisp} (interval) bounds on the probabilities and/or on the related statistical characteristics. In other situations, we have {\em fuzzy} bounds, i.e., different interval bounds with different degrees of certainty.

In a situation with uncertainty, we do not know the exact value of the desired characteristic. In such situations, it is desirable to find its worst possible value, its best possible value, and its "typical" value -- corresponding to the "most probable" probability distribution. Usually, as such a "typical" distribution, we select the …

Towards A Natural Proof Of Metrization Theorem For Space-Times, Vladik Kreinovich, Olga Kosheleva

Departmental Technical Reports (CS)

In the early 1920s, Pavel Urysohn proved his famous lemma (sometimes referred to as "first non-trivial result of point set topology"). Among other applications, this lemma was instrumental in proving that under reasonable conditions, every topological space can be metrized.

A few years before that, in 1919, a complex mathematical theory was experimentally proven to be extremely useful in the description of real world phenomena: namely, during a solar eclipse, General Relativity theory -- that uses pseudo-Riemann spaces to describe space-time -- has been (spectacularly) experimentally confirmed. Motivated by this success, Urysohn started working on an extension of his lemma …

Selecting The Best Location For A Meteorological Tower: A Case Study Of Multi-Objective Constraint Optimization, Aline James, Craig Tweedie, Tanja Magoc, Vladik Kreinovich, Martine Ceberio

Departmental Technical Reports (CS)

Using the problem of selecting the best location for a meteorological tower as an example, we show that in multi-objective optimization under constraints, the traditional weighted average approach is often inadequate. We also show that natural invariance requirements lead to a more adequate approach -- a generalization of Nash's bargaining solution.

How To Relate Spectral Risk Measures And Utilities, Songsak Sriboonchitta, Hung T. Nguyen, Vladik Kreinovich

Departmental Technical Reports (CS)

Traditional decision theory describes human behavior and human preferences in terms of utility functions. In the last decades, it was shown that in many economic situations, a reasonable description of the actual decisions can be found if we use a different approach -- of spectral risk measures. In each of these approaches, we first need to empirically find the corresponding function: utility function in the traditional approach and the weighting function for spectral risk measures. Since both approaches provide a reasonable description of the same actual behavior (in particular, of the same actual economic behavior), it is desirable to be …

Why Polynomial Formulas In Soft Computing, Decision Making, Etc.?, Olga Kosheleva, Martine Ceberio, Vladik Kreinovich

Departmental Technical Reports (CS)

We show that in many application areas including soft constraints reasonable requirements of scale-invariance lead to polynomial formulas for combining degrees (of certainty, of preference, etc.)

Towards Improved Trapezoidal Approximation To Intersection (Fusion) Of Trapezoidal Fuzzy Numbers: Specific Procedure And General Non-Associativity Theorem, Gang Xiang, Vladik Kreinovich

Departmental Technical Reports (CS)

In some cases, our uncertainty about a quantity can be described by an interval of its possible values. If we have two or more pieces of interval information about the same quantity, then we can conclude that the actual value belongs to the intersection of these intervals.

In general, we may need a fuzzy number to represent our partial knowledge. A fuzzy number can be viewed as a collection of intervals (alpha-cuts) corresponding to different degrees alpha from [0,1]. In practice, we can only store finitely many alpha-cuts. Usually, we only store the lower and upper alpha-cuts (corresponding to alpha …

Access Control Contracts For Java Program Modules, Carlos E. Rubio-Medrano, Yoonsik Cheon

Departmental Technical Reports (CS)

Application-level security has become an issue in recent years; for example, errors, discrepancies and omissions in the specification of access control constraints of security-sensitive software components are recognized as an important source for security vulnerabilities. We propose to formally specify access control assumptions or constraints of a program module and enforce them at run-time. We call such specifications access control contracts. To realize access control contracts, we extended the JML language, a formal interface specification language for Java, and developed a prototype support tool that translates access control contracts to runtime checks. The access control contract reduces the vulnerability that …

A New Eclipse-Based Jml Compiler Built Using Ast Merging, Amritam Sarcar, Yoonsik Cheon

Departmental Technical Reports (CS)

The Java Modeling Language (JML) is a formal interface specification language to document the behavior of Java program modules and has been used in many research and industrial projects. However, its inability to support Java 5 features such as generics is reducing its user base significantly. Besides, the JML compiler is on average 8.5 times slower than the javac Java compiler. In this paper, we present a new JML compiler built on the Eclipse Java compiler to support Java 5 features. We used a technique called AST merging to implement coarse-grained incremental compilation. In our experiments we observed a significant …

Runtime Constraint Checking Approaches For Ocl, A Critical Comparison, Carmen Avila, Amritam Sarcar, Yoonsik Cheon, Cesar Yeep

Departmental Technical Reports (CS)

There are many benefits of checking design constraints at runtime---for example, automatic detection of design drift or corrosion. However, there is no comparative analysis of different approaches although such an analysis could provide a sound basis for determining the appropriateness of one approach over the others. In this paper we conduct a comparative analysis and evaluation of different constraint checking approaches possible for the Object Constraint Language (OCL). We compare several approaches including (1) direct translation to implementation languages, (2) use of executable assertion languages, and (3) use of aspect-oriented programming languages. Our comparison includes both quantitative metrics such as …

Runtime Assertion Checking For Jml On The Eclipse Platform Using Ast Merging, Amritam Sarcar

Departmental Technical Reports (CS)

The Java Modeling Language (JML) is a formal behavioral interface specification language for Java. It is used for detailed design documentation of Java program modules such as classes and interfaces. JML has been used extensively by many researchers across various projects and has a large and varied spectrum of tool support. It extends from runtime assertion checking (RAC) to theorem proving.

Amongst these tools, RAC and ESC/Java has been used as a common tool for many research projects. RAC for JML is a tool that checks at runtime for possible violations of any specifications. However, lately there has been a …

Estimating Information Amount Under Uncertainty: Algorithmic Solvability And Computational Complexity, Vladik Kreinovich, Gang Xiang

Departmental Technical Reports (CS)

Measurement results (and, more generally, estimates) are never absolutely accurate: there is always an uncertainty, the actual value x is, in general, different from the estimate X. Sometimes, we know the probability of different values of the estimation error dx=X-x, sometimes, we only know the interval of possible values of dx, sometimes, we have interval bounds on the cdf of dx. To compare different measuring instruments, it is desirable to know which of them brings more information - i.e., it is desirable to gauge the amount of information. For probabilistic uncertainty, this amount of information is described by Shannon's entropy; …

Optimal Sensor Placement In Environmental Research: Designing A Sensor Network Under Uncertainty, Aline James, Craig Tweedie, Tanja Magoc, Vladik Kreinovich, Martine Ceberio

Departmental Technical Reports (CS)

One of our main challenges in meteorology and environment research is that in many important remote areas, sensor coverage is sparse, leaving us with numerous blind spots. Placement and maintenance of sensors in these areas are expensive. It is therefore desirable to find out how, within a given budget, we can design a sensor network are important activities was developing reasonable techniques for sensor that would provide us with the largest amount of useful information while minimizing the size of the "blind spot" areas which is not covered by the sensors.

This problem is very difficult even to formulate in …

Symmetries: A General Approach To Integrated Uncertainty Management, Vladik Kreinovich, Hung T. Nguyen, Songsak Sriboonchitta

Departmental Technical Reports (CS)

We propose to use symmetries as a general approach to maintaining different types of uncertainty, and we show how the symmetry approach can help, especially in in economics-related applications.

Discrete Taylor Series As A Simple Way To Predict Properties Of Chemical Substances Like Benzenes And Cubanes, Jaime Nava, Vladik Kreinovich, Guillermo Restrepo, Douglas J. Klein

Departmental Technical Reports (CS)

In many applications, we have numerous molecules that are obtained from a "template" molecule like benzene C6H6 or cubane C8H8 by replacing some of its hydrogen atoms with other atoms or atom groups (called ligands). Depending on how many original atoms are replaced and which ones are replaced, we obtain a large number of different chemical substances. It is desirable to be able, based on the measurements performed on a small number of such substances, to accurately predict the characteristics (such as energy) of all similar substances.

Such predictions are very important, since, e.g. cubanes, while kinetically stable, are highly …