Computer Sciences Commons^™

Reverse Mathematics Is Computable For Interval Computations, Martine Ceberio, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

For systems of equations and/or inequalities under interval uncertainty, interval computations usually provide us with a box whose all points satisfy this system. Reverse mathematics means finding necessary and sufficient conditions, i.e., in this case, describing the set of {\it all} the points that satisfy the given system. In this paper, we show that while we cannot always exactly describe this set, it is possible to have a general algorithm that, given ε > 0, provides an ε-approximation to the desired solution set.

Optimization Of Quadratic Forms And T-Norm Forms On Interval Domain And Computational Complexity, Milan Hladik, Michal Čerńy, Vladik Kreinovich

Departmental Technical Reports (CS)

We consider the problem of maximization of a quadratic form over a box. We identify the NP-hardness boundary for sparse quadratic forms: the problem is polynomially solvable for O(log n) nonzero entries, but it is NP-hard if the number of nonzero entries is of the order n^ε for an arbitrarily small ε > 0. Then we inspect further polynomially solvable cases. We define a sunflower graph over the quadratic form and study efficiently solvable cases according to the shape of this graph (e.g. the case with small sunflower leaves or the case with a restricted number of negative entries). Finally, …

Which T-Norm Is Most Appropriate For Bellman-Zadeh Optimization, Vladik Kreinovich, Olga Kosheleva, Shahnaz Shahbazova

Departmental Technical Reports (CS)

In 1970, Richard Bellman and Lotfi Zadeh proposed a method for finding the maximum of a function under fuzzy constraints. The problem with this method is that it requires the knowledge of the minimum and the maximum of the objective function over the corresponding crisp set, and minor changes in this crisp set can lead to a drastic change in the resulting maximum. It is known that if we use a product "and"-operation (t-norm), the dependence on the maximum disappears. Natural questions are: what if we use other t-norms? Can we eliminate the dependence on the minimum? What if we …

When Is Data Processing Under Interval And Fuzzy Uncertainty Feasible: What If Few Inputs Interact? Does Feasibility Depend On How We Describe Interaction?, Milan Hladík, Michal Čerńy, Vladik Kreinovich

Departmental Technical Reports (CS)

It is known that, in general, data processing under interval and fuzzy uncertainty is NP-hard -- which means that, unless P = NP, no feasible algorithm is possible for computing the accuracy of the result of data processing. It is also known that the corresponding problem becomes feasible if the inputs do not interact with each other, i.e., if the data processing algorithm computes the sum of n functions, each depending on only one of the $n$ inputs. In general, inputs x_i and x_j interact. If we take into account all possible interactions, and we use bilinear functions …

Why Skew Normal: A Simple Pedagogical Explanation, José Guadalupe Flores Muñiz, Vyacheslav Kalashnikov, Nataliya Kalashnykova, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

In many practical situations, we only know a few first moments of a random variable, and out of all probability distributions which are consistent with this information, we need to select one. When we know the first two moments, we can use the Maximum Entropy approach and get normal distribution. However, when we know the first three moments, the Maximum Entropy approach doe snot work. In such situations, a very efficient selection is a so-called skew normal distribution. However, it is not clear why this particular distribution should be selected. In this paper, we provide an explanation for this selection.

Why 70/30 Or 80/20 Relation Between Training And Testing Sets: A Pedagogical Explanation, Afshin Gholamy, Vladik Kreinovich, Olga Kosheleva

Departmental Technical Reports (CS)

When learning a dependence from data, to avoid overfitting, it is important to divide the data into the training set and the testing set. We first train our model on the training set, and then we use the data from the testing set to gauge the accuracy of the resulting model. Empirical studies show that the best results are obtained if we use 20-30% of the data for testing, and the remaining 70-80% of the data for training. In this paper, we provide a possible explanation for this empirical result.

Why Burgers Equation: Symmetry-Based Approach, Leobardo Valera, Martine Ceberio, Vladik Kreinovich

Departmental Technical Reports (CS)

In many application areas ranging from shock waves to acoustics, we encounter the same partial differential equation known as the Burgers' equation. The fact that the same equation appears in different application domains, with different physics, makes us conjecture that it can be derived from the fundamental principles. Indeed, in this paper, we show that this equation can be uniquely determined by the corresponding symmetries.

Lotfi Zadeh: A Pioneer In Ai, A Pioneer In Statistical Analysis, A Pioneer In Foundations Of Mathematics, And A True Citizen Of The World, Vladik Kreinovich

Departmental Technical Reports (CS)

Everyone knows Lotfi Zadeh as the Father of Fuzzy Logic. There have been -- and will be -- many papers on this important topic. What I want to emphasize in this paper is that his ideas go way beyond fuzzy logic:

• he was a pioneer in AI;
• he was a pioneer in statistical analysis; and
• he was a pioneer in foundations of mathematics.

My goal is to explain these ideas to non-fuzzy folks. I also want to emphasize that he was a true Citizen of the World.

An Uncertainty-Aware Workflow For Keyhole Surgery Planning Using Hierarchical Image Semantics, Christina Gillmann, Robin G.C. Maack, Tobias Post, Thomas Wischgoll, Hans Hagen

Computer Science and Engineering Faculty Publications

Keyhole surgeries become increasingly important in clinical daily routine as they help minimizing the damage of a patient's healthy tissue. The planning of keyhole surgeries is based on medical imaging and an important factor that influences the surgeries' success. Due to the image reconstruction process, medical image data contains uncertainty that exacerbates the planning of a keyhole surgery. In this paper we present a visual workfiow that helps clinicians to examine and compare different surgery paths as well as visualizing the patients' affected tissue. The analysis is based on the concept of hierarchical image semantics, that segment the underlying image …

From Traditional Neural Networks To Deep Learning: Towards Mathematical Foundations Of Empirical Successes, Vladik Kreinovich

Departmental Technical Reports (CS)

How do we make computers think? To make machines that fly, it is reasonable to look at the creatures that know how to fly: the birds. To make computers think, it is reasonable to analyze how we think -- this is the main origin of neural networks. At first, one of the main motivations was speed -- since even with slow biological neurons, we often process information fast. The need for speed motivated traditional 3-layer neural networks. At present, computer speed is rarely a problem, but accuracy is -- this motivated deep learning. In this paper, we concentrate on the …

Italian Folk Multiplication Algorithm Is Indeed Better: It Is More Parallelizable, Martine Ceberio, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

Traditionally, many ethnic groups had their own versions of arithmetic algorithms. Nowadays, most of these algorithms are studied mostly as pedagogical curiosities, as an interesting way to make arithmetic more exciting to the kids: by applying to their patriotic feelings -- if they are studying the algorithms traditionally used by their ethic group -- or simply to their sense of curiosity. Somewhat surprisingly, we show that one of these algorithms -- a traditional Italian multiplication algorithm -- is actually in some reasonable sense better than the algorithm that we all normally use -- namely, it is easier to parallelize.

A New Kalman Filter Model For Nonlinear Systems Based On Ellipsoidal Bounding, Ligang Sun, Hamza Alkhatib, Boris Kargoll, Vladik Kreinovich, Ingo Neumann

Departmental Technical Reports (CS)

In this paper, a new filter model called set-membership Kalman filter for nonlinear state estimation problems was designed, where both random and unknown but bounded uncertainties were considered simultaneously in the discrete-time system. The main loop of this algorithm includes one prediction step and one correction step with measurement information, and the key part in each loop is to solve an optimization problem. The solution of the optimization problem produces the optimal estimation for the state, which is bounded by ellipsoids. The new filter was applied on a highly nonlinear benchmark example and a two-dimensional simulated trajectory estimation problem, in …

Why Learning Has Aha-Moments And Why We Should Also Reward Effort, Not Just Results, Gerargo Uranga, Vladik Kreinovich, Olga Kosheleva

Departmental Technical Reports (CS)

Traditionally, in machine learning, the quality of the result improves steadily with time (usually slowly but still steadily). However, as we start applying reinforcement learning techniques to solve complex tasks -- such as teaching a computer to play a complex game like Go -- we often encounter a situation in which for a long time, then is no improvement, and then suddenly, the system's efficiency jumps almost to its maximum. A similar phenomenon occurs in human learning, where it is known as the aha-moment. In this paper, we provide a possible explanation for this phenomenon, and show that this explanation …

When Good Components Go Bad: Formally Secure Compilation Despite Dynamic Compromise, Guglielmo Fachini, CăTăLin Hriţcu, Marco Stronati, Arthur Azevedo De Amorim, Carmine Abate, Roberto Blanco, Théo Laurent, Benjamin C. Pierce, Andrew Tolmach

Computer Science Faculty Publications and Presentations

We propose a new formal criterion for secure compilation, giving strong end-to-end security guarantees for software components written in unsafe, low-level languages with C-style undefined behavior. Our criterion is the first to model dynamic compromise in a system of mutually distrustful components running with least privilege. Each component is protected from all the others—in particular, from components that have encountered undefined behavior and become compromised. Each component receives secure compilation guarantees up to the point when it becomes compromised, after which an attacker can take complete control over the component and use any of its privileges to attack the remaining …

Does The Test Work? Evaluating A Web-Based Language Placement Test, Avizia Long, Sun-Young Shin, Kimberly Geeslin, Erik Willis

Faculty Publications

In response to the need for examples of test validation from which everyday language programs can benefit, this paper reports on a study that used Bachman’s (2005) assessment use argument (AUA) framework to examine evidence to support claims made about the intended interpretations and uses of scores based on a new web-based Spanish language placement test. The test, which consisted of 100 items distributed across five item types (sound discrimination, grammar, listening comprehension, reading comprehension, and vocabulary), was tested with 2,201 incoming first-year and transfer students at a large, Midwestern public university. Analyses of internal consistency and validity revealed the …

Auditing Snomed Ct Hierarchical Relations Based On Lexical Features Of Concepts In Non-Lattice Subgraphs, Licong Cui, Olivier Bodenreider, Jay Shi, Guo-Qiang Zhang

Computer Science Faculty Publications

Objective—We introduce a structural-lexical approach for auditing SNOMED CT using a combination of non-lattice subgraphs of the underlying hierarchical relations and enriched lexical attributes of fully specified concept names. Our goal is to develop a scalable and effective approach that automatically identifies missing hierarchical IS-A relations.

Methods—Our approach involves 3 stages. In stage 1, all non-lattice subgraphs of SNOMED CT’s IS-A hierarchical relations are extracted. In stage 2, lexical attributes of fully-specified concept names in such non-lattice subgraphs are extracted. For each concept in a non-lattice subgraph, we enrich its set of attributes with attributes from its ancestor …

On The Use Of Semantic-Based Aig To Automatically Generate Programming Exercises, Laura Zavala, Benito Mendoza

Publications and Research

In introductory programming courses, proficiency is typically achieved through substantial practice in the form of relatively small assignments and quizzes. Unfortunately, creating programming assignments and quizzes is both, time-consuming and error-prone. We use Automatic Item Generation (AIG) in order to address the problem of creating numerous programming exercises that can be used for assignments or quizzes in introductory programming courses. AIG is based on the use of test-item templates with embedded variables and formulas which are resolved by a computer program with actual values to generate test-items. Thus, hundreds or even thousands of test-items can be generated with a single …

A Jpeg Corner Artifact From Directed Rounding Of Dct Coefficients, Shruti Agarwal, Hany Farid

Computer Science Technical Reports

JPEG compression introduces a number of well known artifacts including blocking and ringing. We describe a lesser known or understood artifact consisting of a slightly darker or lighter pixel in the corner of 8 x 8 pixel blocks. This artifact is introduced by the directed rounding of DCT coefficients. In particular, we show that DCT coefficients that are uniformly rounded down or up (but not to the nearest neighbor) give rise to this artifact. An analysis of thousands of different camera models reveals that this artifact is present in approximately 61% of cameras. We also propose a simple filtering technique …

Internet Of Underground Things: Sensing And Communications On The Field For Precision Agriculture, Mehmet C. Vuran, Abdul Salam, Rigoberto Wong, Suat Irmak

School of Computing: Conference and Workshop Papers

The projected increases in World population and need for food have recently motivated adoption of information technology solutions in crop fields within precision agriculture approaches. Internet of underground things (IOUT), which consists of sensors and communication devices, partly or completely buried underground for real-time soil sensing and monitoring, emerge from this need. This new paradigm facilitates seamless integration of underground sensors, machinery, and irrigation systems with the complex social network of growers, agronomists, crop consultants, and advisors. In this paper, state-of-the-art communication architectures are reviewed, and underlying sensing technology and communication mechanisms for IOUT are presented. Recent advances in the …

Scheduling In Mapreduce Clusters, Chen He

School of Computing: Dissertations, Theses, and Student Research

MapReduce is a framework proposed by Google for processing huge amounts of data in a distributed environment. The simplicity of the programming model and the fault-tolerance feature of the framework make it very popular in Big Data processing.

As MapReduce clusters get popular, their scheduling becomes increasingly important. On one hand, many MapReduce applications have high performance requirements, for example, on response time and/or throughput. On the other hand, with the increasing size of MapReduce clusters, the energy-efficient scheduling of MapReduce clusters becomes inevitable. These scheduling challenges, however, have not been systematically studied.

The objective of this dissertation is to …

Statistical Analysis Of Network Change, Teresa D. Schmidt, Martin Zwick

Complex Systems Faculty Publications and Presentations

Networks are rarely subjected to hypothesis tests for difference, but when they are inferred from datasets of independent observations statistical testing is feasible. To demonstrate, a healthcare provider network is tested for significant change after an intervention using Medicaid claims data. First, the network is inferred for each time period with (1) partial least squares (PLS) regression and (2) reconstructability analysis (RA). Second, network distance (i.e., change between time periods) is measured as the mean absolute difference in (1) coefficient matrices for PLS and (2) calculated probability distributions for RA. Third, the network distance is compared against a reference distribution …

Vt-Revolution: Interactive Programming Video Tutorial Authoring And Watching System, Lingfeng Bao, Zhenchang Xing, Xin Xia, David Lo

Research Collection School Of Computing and Information Systems

Procedural knowledge describes actions and manipulations that are carried out to complete programming tasks. An effective way to document procedural knowledge is programming video tutorials. Existing solutions to adding interactive workflow and elements to programming videos have a dilemma between the level of desired interaction and the efforts required for authoring tutorials. In this work, we tackle this dilemma by designing and building a programming video tutorial authoring system that leverages operating system level instrumentation to log workflow history while tutorial authors are creating programming videos, and the corresponding tutorial watching system that enhances the learning experience of video tutorials …

Summary Of The Special Issue “Neutrosophic Information Theory And Applications” At “Information” Journal, Florentin Smarandache, Jun Ye

Branch Mathematics and Statistics Faculty and Staff Publications

Over a period of seven months (August 2017–February 2018), the Special Issue dedicated to “Neutrosophic Information Theory and Applications” by the “Information” journal (ISSN 2078-2489), located in Basel, Switzerland, was a success. The Guest Editors, Prof. Dr. Florentin Smarandache from the University of New Mexico (USA) and Prof. Dr. Jun Ye from the Shaoxing University (China), were happy to select—helped by a team of neutrosophic reviewers from around the world, and by the “Information” journal editors themselves—and publish twelve important neutrosophic papers, authored by 27 authors and coauthors. There were a variety of neutrosophic topics studied and used by the …

Relating Justification Logic Modality And Type Theory In Curry–Howard Fashion, Konstantinos Pouliasis

Dissertations, Theses, and Capstone Projects

This dissertation is a work in the intersection of Justification Logic and Curry--Howard Isomorphism. Justification logic is an umbrella of modal logics of knowledge with explicit evidence. Justification logics have been used to tackle traditional problems in proof theory (in relation to Godel's provability) and philosophy (Gettier examples, Russel's barn paradox). The Curry--Howard Isomorphism or proofs-as-programs is an understanding of logic that places logical studies in conjunction with type theory and -- in current developments -- category theory. The point being that understanding a system as a logic, a typed calculus and, a language of a class of categories constitutes …

Vision-Based Assistive Indoor Localization, Feng Hu

Dissertations, Theses, and Capstone Projects

An indoor localization system is of significant importance to the visually impaired in their daily lives by helping them localize themselves and further navigate an indoor environment. In this thesis, a vision-based indoor localization solution is proposed and studied with algorithms and their implementations by maximizing the usage of the visual information surrounding the users for an optimal localization from multiple stages. The contributions of the work include the following: (1) Novel combinations of a daily-used smart phone with a low-cost lens (GoPano) are used to provide an economic, portable, and robust indoor localization service for visually impaired people. (2) …

Multimodal Sensing And Data Processing For Speaker And Emotion Recognition Using Deep Learning Models With Audio, Video And Biomedical Sensors, Farnaz Abtahi

Dissertations, Theses, and Capstone Projects

The focus of the thesis is on Deep Learning methods and their applications on multimodal data, with a potential to explore the associations between modalities and replace missing and corrupt ones if necessary. We have chosen two important real-world applications that need to deal with multimodal data: 1) Speaker recognition and identification; 2) Facial expression recognition and emotion detection.

The first part of our work assesses the effectiveness of speech-related sensory data modalities and their combinations in speaker recognition using deep learning models. First, the role of electromyography (EMG) is highlighted as a unique biometric sensor in improving audio-visual speaker …

Object Localization, Segmentation, And Classification In 3d Images, Allan Zelener

Dissertations, Theses, and Capstone Projects

We address the problem of identifying objects of interest in 3D images as a set of related tasks involving localization of objects within a scene, segmentation of observed object instances from other scene elements, classifying detected objects into semantic categories, and estimating the 3D pose of detected objects within the scene. The increasing availability of 3D sensors motivates us to leverage large amounts of 3D data to train machine learning models to address these tasks in 3D images. Leveraging recent advances in deep learning has allowed us to develop models capable of addressing these tasks and optimizing these tasks jointly …

Word Co-Occurrence Regularized Non-Negative Matrix Tri-Factorization For Text Data Co-Clustering, Aghiles Salah, Melissa Ailem, Mohamed Nadif

Research Collection School Of Computing and Information Systems

Text data co-clustering is the process of partitioning the documents and words simultaneously. This approach has proven to be more useful than traditional one-sided clustering when dealing with sparsity. Among the wide range of co-clustering approaches, Non-Negative Matrix Tri-Factorization (NMTF) is recognized for its high performance, flexibility and theoretical foundations. One important aspect when dealing with text data, is to capture the semantic relationships between words since documents that are about the same topic may not necessarily use exactly the same vocabulary. However, this aspect has been overlooked by previous co-clustering models, including NMTF. To address this issue, we rely …

Sparse Passive-Aggressive Learning For Bounded Online Kernel Methods, Jing Lu, Doyen Sahoo, Peilin Zhao, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

One critical deficiency of traditional online kernel learning methods is their unbounded and growing number of support vectors in the online learning process, making them inefficient and non-scalable for large-scale applications. Recent studies on scalable online kernel learning have attempted to overcome this shortcoming, e.g., by imposing a constant budget on the number of support vectors. Although they attempt to bound the number of support vectors at each online learning iteration, most of them fail to bound the number of support vectors for the final output hypothesis, which is often obtained by averaging the series of hypotheses over all the …

Unified Locally Linear Classifiers With Diversity-Promoting Anchor Points, Chenghao Liu, Teng Zhang, Peilin Zhao, Jianling Sun, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

Locally Linear Support Vector Machine (LLSVM) has been actively used in classification tasks due to its capability of classifying nonlinear patterns. However, existing LLSVM suffers from two drawbacks: (1) a particular and appropriate regularization for LLSVM has not yet been addressed; (2) it usually adopts a three-stage learning scheme composed of learning anchor points by clustering, learning local coding coordinates by a predefined coding scheme, and finally learning for training classifiers. We argue that this decoupled approaches oversimplifies the original optimization problem, resulting in a large deviation due to the disparate purpose of each step. To address the first issue, …