Computer Engineering Commons^™

Extracting Trust Network Information From Scientific Web Portals, Alejandro Castaneda, Paulo Pinheiro Da Silva

Departmental Technical Reports (CS)

An increased exchange of (scientific) information across organizations and disciplines is one of the long-term goals of the semantic web. In any such exchange of information, it is not difficult to identify one or more (scientific) communities responsible for the measurement, gathering and processing of scientific information. More challenging, however, is to understand the trust relations between members of these communities, whether the members are organizations or people. With a better understanding of trust relations, one may be able to compute trust recommendations for scientific information exchange, increasing in this way the acceptance of information by scientists. In this paper, …

Intermediate Degrees Are Needed For The World To Be Cognizable: Towards A New Justification For Fuzzy Logic Ideas, Hung T. Nguyen, Vladik Kreinovich, J. Esteban Gamez, Francois Modave, Olga Kosheleva

Departmental Technical Reports (CS)

Most traditional examples of fuzziness come from the analysis of commonsense reasoning. When we reason, we use words from natural language like "young", "well". In many practical situations, these words do not have a precise true-or-false meaning, they are fuzzy. One may therefore be left with an impression that fuzziness is a subjective characteristic, it is caused by the specific way our brains work.

However, the fact that that we are the result of billions of years of successful adjusting-to-the-environment evolution makes us conclude that everything about us humans is not accidental. In particular, the way we reason is not …

Toward Formalizing Non-Monotonic Reasoning In Physics: The Use Of Kolmogorov Complexity, Vladik Kreinovich

Departmental Technical Reports (CS)

When a physicist writes down equations, or formulates a theory in any other terms, he usually means not only that these equations are true for the real world, but also that the model corresponding to the real world is "typical" among all the solutions of these equations. This type of argument is used when physicists conclude that some property is true by showing that it is true for "almost all" cases. There are formalisms that partially capture this type of reasoning, e.g., techniques based on the Kolmogorov-Martin-Lof definition of a random sequence. The existing formalisms, however, have difficulty formalizing, e.g., …

Testing The Value Of A Time-Based Language Model For Speech Recognition, Nisha Kiran, Nigel Ward

Departmental Technical Reports (CS)

Speech recognition relies on the language model in order to decode an utterance, and in general a better language model improves the performance of a speech recognizer. We have recently found that a time-based language model can improve on a standard trigram language model in terms of perplexity. This technical report presents the evaluation of this new language model in the context of speech recognition. First, a basic speech recognizer was built using the HTK tool. Then the recognizer was run using the standard language model and using the time-based one. On a testset of 39,147 words from the Switchboard …

Trade-Off Between Sample Size And Accuracy: Case Of Measurements Under Interval Uncertainty, Hung T. Nguyen, Olga Kosheleva, Vladik Kreinovich, Scott Ferson

Departmental Technical Reports (CS)

In many practical situations, we are not satisfied with the accuracy of the existing measurements. There are two possible ways to improve the measurement accuracy:

first, instead of a single measurement, we can make repeated measurements; the additional information coming from these additional measurements can improve the accuracy of the result of this series of measurements;

second, we can replace the current measuring instrument with a more accurate one; correspondingly, we can use a more accurate (and more expensive) measurement procedure provided by a measuring lab -- e.g., a procedure that includes the use of a higher quality reagent.

In …

Application-Motivated Combinations Of Fuzzy, Interval, And Probability Approaches, And Their Use In Geoinformatics, Bioinformatics, And Engineering, Vladik Kreinovich

Departmental Technical Reports (CS)

Most data processing techniques traditionally used in scientific and engineering practice are statistical. These techniques are based on the assumption that we know the probability distributions of measurement errors etc. In practice, often, we do not know the distributions, we only know the bound D on the measurement accuracy - hence, after the get the measurement result X, the only information that we have about the actual (unknown) value x of the measured quantity is that x belongs to the interval [X - D, X + D]. Techniques for data processing under such interval uncertainty are called interval computations; these …

Sloth-Nfs And The Possibility Of Using Fuzzy Control To Optimize Cache Management, Ryan C. Spring, Eric Freudenthal

Departmental Technical Reports (CS)

Modern software systems are complex and increasingly vulnerable to malicious attack. In order to apply bug fixes and protect against security weaknesses, workstation administrators must continuously patch operating system and application program installations. To simplify this process, administrators generally configure systems into clusters with common installations of operating systems and application programs in a manner that patches and other routine maintenance can be applied en masse. Two widely used approaches offer complementary advantages: Installations and updates are particularly convenient when all data including operating system and programs is served by traditional centralized network-connected file servers (networked file systems) because administrators …

Asymmetric Paternalism: Description Of The Phenomenon, Explanation Based On Decisions Under Uncertainty, And Possible Applications To Education, Olga Kosheleva, Francois Modave

Departmental Technical Reports (CS)

In general, human being are rational decision makers, but in many situations, they exhibit unexplained "inertia", reluctance to switch to a better decision. In this paper, we show that this seemingly irrational behavior can be explained if we take uncertainty into account; we also explain how this phenomenon can be utilized in education.

Impact Of Checkpoint Latency On The Optimal Checkpoint Interval And Execution Time, Sarala Arunagiri, Seetharami Seelam, Ron A. Oldfield, Maria Ruiz, Patricia J. Teller, Rolf Riesen

Departmental Technical Reports (CS)

The massive scale of current and next-generation massively parallel processing (MPP) systems presents significant challenges related to fault tolerance. In particular, the standard approach to fault tolerance, application-directed checkpointing, puts an incredible strain on the storage system and the interconnection network. This results in overheads on the appliation that severely impact performance and scalability. The checkpoint overhead can be reduced by decreasing the checkpoint latency, which is the time to write a checkpoint file, or by increasing the checkpoint interval, which is the compute time between writing checkpoint files. However, increasing the checkpoint interval may increase execution time in the …

Program Synthesis From Workflow-Driven Ontologies, Leonardo Salayandia, Steve Roach, Ann Q. Gates

Departmental Technical Reports (CS)

An approach that results in the development of Workflow-Driven Ontologies (WDO) (called the WDO approach) allows domain scientists to capture process knowledge in the form of concepts as well as relations between concepts. Program synthesis techniques can be employed to generate algorithmic solutions by transforming the process knowledge expressed in the WDO as concepts and relations to variables and functions and computing unknown variables from known ones based on the process knowledge documented by the domain scientist. Furthermore, the algorithmic solutions that are generated by program synthesis potentially can support the composition of services, which result in the creation of …

Opportunistic Checkpoint Intervals To Improve System Performance, Sarala Arunagiri, John T. Daly, Patricia J. Teller, Seetharami Seelam, Ron A. Oldfield, Maria Ruiz Varela, Rolf Riesen

Departmental Technical Reports (CS)

The massive scale of current and next-generation massively parallel processing (MPP) systems presents significant challenges related to fault tolerance. For applications that perform periodic checkpoints, the choice of the checkpoint interval, the period between checkpoints, can have a significant impact on the execution time of the application. Finding the optimal checkpoint interval that minimizes the wall clock execution time, has been a subject of research over the last decade. In an environment where there are concurrent applications competing for access to the network and storage resources, in addition to application execution times, contention at these shared resources need to be …

Fast Algorithms For Uncertainty Propagation, And Their Applications To Structural Integrity, Andrzej Pownuk, Jakub Cerveny, Jerald Brady

Departmental Technical Reports (CS)

In many practical situations, we need to know how uncertainty propagates through data processing algorithms, i.e., how the uncertainty in the inputs affects the results of data processing. This problem is important for all types of uncertainty: probabilistic, interval, and fuzzy. From the computational viewpoint, however, this problem is much more complex for interval and fuzzy uncertainty. Therefore, for these types of uncertainty, it is desirable to design faster algorithms.

In this paper, we describe faster algorithms for two practically important situations:

linearization situations, when the approximation errors are small and therefore, the data processing algorithms can be replaced by …

Everything Is A Matter Of Degree: A New Theoretical Justification Of Zadeh's Principle, Hung T. Nguyen, Vladik Kreinovich

Departmental Technical Reports (CS)

One of the main ideas behind fuzzy logic and its applications is that everything is a matter of degree. We are often accustomed to think that every statement about a physical world is true or false -- that an object is either a particle or a wave, that a person is either young or not, either well or ill -- but in reality, we sometimes encounter intermediate situations. In this paper, we show that the existence of such intermediate situations can be theoretically explained -- by a natural assumption that the real world is cognizable.

Towards An Optimal Algorithm For Computing Fixed Points: Dynamical Systems Approach, With Applications To Transportation Engineering, Ruey L. Cheu, Gang Xiang, Vladik Kreinovich

Departmental Technical Reports (CS)

In many practical problems, it is desirable to find an equilibrium. For example, equilibria are important in transportation engineering.

Many urban areas suffer from traffic congestion. Intuitively, it may seem that a road expansion (e.g., the opening of a new road) should always improve the traffic conditions. However, in reality, a new road can actually worsen traffic congestion. It is therefore extremely important that before we start a road expansion project, we first predict the effect of this project on traffic congestion.

When a new road is built, some traffic moves to this road to avoid congestion on the other …

How To Reconcile Physical Theories With The Idea Of Free Will: From Analysis Of A Simple Model To Interval And Fuzzy Approaches, Julio C. Urenda, Olga Kosheleva

Departmental Technical Reports (CS)

Most modern physical theories are formulated in terms of differential equations. As a result, if we know exactly the current state of the world, then this state uniquely determines all the future events -- including our own future behavior. This determination seems to contradict the intuitive notion of a free will, according to which we are free to make decisions -- decisions which cannot be determined based on the past locations and velocities of the elementary particles. In quantum physics, the situation is somewhat better in the sense that we cannot determine the exact behavior, but we can still determine …

Towards More Adequate Representation Of Uncertainty: From Intervals To Set Intervals, With The Possible Addition Of Probabilities And Certainty Degrees, J. T. Yao, Y. Y. Yao, Vladik Kreinovich, Paulo Pinheiro Da Silva, Scott A. Starks, Gang Xiang, H. T. Nguyen

Departmental Technical Reports (CS)

In the ideal case of complete knowledge, for each property Pi (such as "high fever", "headache", etc.), we know the exact set Si of all the objects that satisfy this property. In practice, we usually only have partial knowledge. In this case, we only know the set Si- of all the objects about which we know that Pi holds and the set Si+ about which we know that Pi may hold (i.e., equivalently, that we have not yet excluded the possibility of Pi). This pair of sets is called a set interval.

Based on the knowledge of the original properties, …

Estimating Variance Under Interval And Fuzzy Uncertainty: Parallel Algorithms, Karen Villaverde, Gang Xiang

Departmental Technical Reports (CS)

Traditional data processing in science and engineering starts with computing the basic statistical characteristics such as the population mean E and population variance V. In computing these characteristics, it is usually assumed that the corresponding data values x1,...,xn are known exactly. In many practical situations, we only know intervals [xi-,xi+] that contain the actual (unknown) values of xi or, more generally, a fuzzy number that describes xi. In this case, different possible values of xi lead, in general, to different values of E and V. In such situations, we are interested in producing the intervals of possible values of E …

How To Measure A Degree Of Mismatch Between Probability Models, P-Boxes, Etc.: A Decision-Theory-Motivated Utility-Based Approach, Luc Longpre, Scott Ferson, W. Troy Tucker

Departmental Technical Reports (CS)

Different models can be used to describe real-life phenomena: deterministic, probabilistic, fuzzy, models in which we have interval-valued or fuzzy-valued probabilities, etc. Models are usually not absolutely accurate. It is therefore important to know how accurate is a given model. In other words, it is important to be able to measure a mismatch between the model and the empirical data. In this paper, we describe an approach of measuring this mismatch which is based on the notion of utility, the central notion of utility theory.

We also show that a similar approach can be used to measure the loss of …

Relations Between Interval Computing And Soft Computing, Vladik Kreinovich

Departmental Technical Reports (CS)

This paper starts with a brief reminder of why data processing and knowledge processing are needed in the first place, why interval and fuzzy methods are needed for data and knowledge processing, and which of the possible data and knowledge processing techniques we should use. Then, we explain how these reasonable soft computing techniques are naturally related with interval computing. Finally, we explain the need for interval-valued fuzzy techniques -- techniques which will be used a lot in our future applications -- and how the transition to such techniques is also related to interval computing.

Towards Fast Algorithms For Processing Type-2 Fuzzy Data: Extending Mendel's Algorithms From Interval-Valued To A More General Case, Vladik Kreinovich, Gang Xiang

Departmental Technical Reports (CS)

It is known that processing of data under general type-1 fuzzy uncertainty can be reduced to the simplest case -- of interval uncertainty: namely, Zadeh's extension principle is equivalent to level-by-level interval computations applied to alpha-cuts of the corresponding fuzzy numbers.

However, type-1 fuzzy numbers may not be the most adequate way of describing uncertainty, because they require that an expert can describe his or her degree of confidence in a statement by an exact value. In practice, it is more reasonable to expect that the expert estimates his or her degree by using imprecise words from natural language -- …

Cahsi Year 2 Evaluation Report: Recruiting, Retaining, And Advancing Hispanics In Computing, Heather Thiry, Sarah Hug, Lecia Barker

Departmental Technical Reports (CS)

No abstract provided.

Applications Of 1-D Versions Of Image Referencing Techniques To Hydrology And To Patient Rehabilitation, Roberto Araiza, Martine Ceberio, Naga Suman Kanagala, Vladik Kreinovich, Gang Xiang

Departmental Technical Reports (CS)

In this paper, we consider two seemingly unrelated problems: the hydrology problem of relation between groundwater and surface water, and a problem of identification of human gait in neuro-rehabilitation. It turns out that in both problems, we can efficiently use soft computing-motivated algorithms originally developed for image referencing.

Beyond Intervals: Phase Transitions Lead To More General Ranges, Karen Villaverde, Gilbert Ornelas

Departmental Technical Reports (CS)

One of the main tasks of science and engineering is to use the current values of the physical quantities for predicting the future values of the desired quantities. Due to the (inevitable) measurement inaccuracy, we usually know the current values of the physical quantities with interval uncertainty. Traditionally, it is assumed that all the processes are continuous; as a result, the range of possible values of the future quantities is also known with interval uncertainty. However, in many practical situations (such as phase transitions), the dependence of the future values on the current ones becomes discontinuous. We show that in …

Selecting The Most Representative Sample Is Np-Hard: Need For Expert (Fuzzy) Knowledge, J. Esteban Gamez, Francois Modave, Olga Kosheleva

Departmental Technical Reports (CS)

One of the main applications of fuzzy techniques is to formalize the notions of "typical", "representative", etc.

The main idea behind fuzzy techniques is that they formalize expert knowledge expressed by words from natural language.

In this paper, we show that if we do not use this knowledge, i.e., if we only use the data, then selecting the most representative sample becomes a computationally difficult (NP-hard) problem. Thus, the need to find such samples in reasonable time justifies the use of fuzzy techniques.

Extracting Computable Bounds (And Algorithms) From Classical Existence Proofs: Girard Domains Enable Us To Go Beyond Local Compactness, Vladik Kreinovich, Karen Villaverde

Departmental Technical Reports (CS)

In classical mathematics, the existence of a solution is often proven indirectly, non-constructively, without an efficient method for constructing the corresponding object. In many cases, we can extract an algorithm from a classical proof: e.g., when an object is (non-constructively) proven to be unique in a locally compact space (or when there are two such objects with a known lower bound on the distance between them). In many other practical situations, a (seemingly) natural formalization of the corresponding practical problem leads to a non-compact set. In this paper, we show that often, in such situations, we can extract efficient algorithms …

Identification Of Human Gait In Neuro-Rehabilitation: Towards Efficient Algorithms, Naga Suman Kanagala, Martine Ceberio, Thompson Sarkodie-Gyan, Vladik Kreinovich, Roberto Araiza

Departmental Technical Reports (CS)

Many neurological diseases such as stroke, traumatic body injury, spinal cord injury drastically decrease the patient's ability to walk without physical assistance. To re-establish normal gait, patients undergo extensive rehabilitation. At present, rehabilitation requires gait assessment by highly qualified experienced clinicians. To make rehabilitations easier to access and to decrease the rehabilitation cost, it is desirable to automate gait assessment. In precise terms, gait assessment means comparing the recorded patient's gait with a standard (average) gait of healthy people of the same body measurements. One of the problems in this comparison is that patients walk slower; so, to properly compare …

Integrating Random Testing With Constraints For Improved Efficiency And Diversity, Yoonsik Cheon, Antonio Cortes, Martine Ceberio, Gary T. Leavens

Departmental Technical Reports (CS)

Random testing can be fully automated, eliminates subjectiveness in constructing test cases, and increases the diversity of test data. However, randomly generated tests may not satisfy program's assumptions (e.g., method preconditions). While constraint solving can satisfy such assumptions, it does not necessarily generate diverse tests and is hard to apply to large programs. We blend these techniques by extending random testing with constraint solving, improving the efficiency of generating valid test data while preserving diversity. For domains such as objects, we generate input values randomly; however, for values of finite domains such as integers, we represent test data generation as …

A Library-Based Approach To Translating Ocl Constraints To Jml Assertions For Runtime Checking, Carmen Avila, Guillermo Flores, Jr., Yoonsik Cheon

Departmental Technical Reports (CS)

OCL is a formal notation to specify constraints on UML models that cannot otherwise be expressed by diagrammatic notations such as class diagrams. Using OCL one can document detailed design decisions and choices along with the behavior, e.g., class invariants and method pre and postconditions. However, OCL constraints cannot be directly executed and checked at runtime by an implementation, thus constraint violations may not be detected or noticed, causing many potential development and maintenance problems. In this paper we propose an approach to checking OCL constraints at runtime by translating them to executable JML assertions. The key components of our …

Identifying And Explaining Map Quality Through Provenance: A User Study, Nicholas Ricky Del Rio, Paulo Pinheiro Da Silva

Departmental Technical Reports (CS)

Applications deployed on cyber-infrastructures often rely on multiple data sources and distributed compute resources to access, process, and derive results. When application results are maps, it is possible that non-intentional imperfections can get introduced into the map generation processes because of several reasons including the use of low quality datasets, use of data filtering techniques incompatible for the kind of map to be generated, or even the use of inappropriate mapping parameters, e.g., low-resolution gridding parameters. Without some means for accessing and visualizing the provenance associated with map generation processes, i.e., metadata about information sources and methods used to derive …

Equidecomposability (Scissors Congruence) Of Polyhedra In R^3 And R^4 Is Algorithmically Decidable: Hilbert's 3rd Problem Revisited, Vladik Kreinovich

Departmental Technical Reports (CS)

No abstract provided.