Computer Sciences Commons^™

Algebraic Solutions To Overdefined Systems With Applications To Cryptanalysis, Eric Crockett

Mathematical Sciences Technical Reports (MSTR)

Cryptographic algorithms are based on a wide variety of difficult problems in mathematics. One of these problems is finding a solution to a system of multivariate quadratic equations (MQ). A generalization of this problem is to find a solution to a system of higher order non-linear equations. Both of these problems are NP-hard over any field. Many cryptosystems such as AES, Serpent, Toyocrypt, and others can be reduced to some form of the MQ problem. In this paper we analyze the relinearization and XL algorithms for solving overdetermined systems of non-linear equations, as well as two variations of the XL …

Cloud Shadow Detection And Removal From Aerial Photo Mosaics Using Light Detection And Ranging (Lidar) Reflectance Images, Glover Eugene George

Dissertations

The process of creating aerial photo mosaics can be severely affected by clouds and the shadows they create. In the CZMIL project discussed in this work, the aerial survey aircraft flies below the clouds, but the shadows cast from clouds above the aircraft cause the resultant mosaic image to have sub-optimal results. Large intensity variations, caused both from the cloud shadow within a single image and the juxtaposition of areas of cloud shadow and no cloud shadow during the image stitching process, create an image that may not be as useful to the concerned research scientist. Ideally, we would like …

Double Updating Online Learning, Peilin Zhao, Steven C. H. Hoi, Rong Jin

Research Collection School Of Computing and Information Systems

In most kernel based online learning algorithms, when an incoming instance is misclassified, it will be added into the pool of support vectors and assigned with a weight, which often remains unchanged during the rest of the learning process. This is clearly insufficient since when a new support vector is added, we generally expect the weights of the other existing support vectors to be updated in order to reflect the influence of the added support vector. In this paper, we propose a new online learning method, termed Double Updating Online Learning, or DUOL for short, that explicitly addresses this problem. …

Adaptive Decision Support For Structured Organizations: A Case For Orgpomdps, Pradeep Reddy Varakantham, Nathan Schurr, Alan Carlin, Christopher Amato

Research Collection School Of Computing and Information Systems

In today's world, organizations are faced with increasingly large and complex problems that require decision-making under uncertainty. Current methods for optimizing such decisions fall short of handling the problem scale and time constraints. We argue that this is due to existing methods not exploiting the inherent structure of the organizations which solve these problems. We propose a new model called the OrgPOMDP (Organizational POMDP), which is based on the partially observable Markov decision process (POMDP). This new model combines two powerful representations for modeling large scale problems: hierarchical modeling and factored representations. In this paper we make three key contributions: …

Topic Detection And Tracking Using Hidden Markov Models, Aditya S. Tatavarty

UNLV Theses, Dissertations, Professional Papers, and Capstones

There is a continuous progress in automatic recording of broadcast speech using speech recognition. With the increasing use of this technology, a new source of data is added to the pool of information available over web. This has increased the need to categorize the resulting text, based on their topic for the purpose of information retrieval.

In this thesis we present an approach to automatically assign a topic or track a change of topic in a stream of input data. Our approach is based on the use of Hidden Markov Models and language processing techniques. We consider input text as …

Shop Problems In Scheduling, James Andro-Vasko

UNLV Theses, Dissertations, Professional Papers, and Capstones

The shop problems in scheduling will be discussed in this thesis. The ones I'll be discussing will be the flow shop, open shop, and job shop. The general idea of shop problems is that you're given a set of jobs and a set of machines. Each job is predeterminely broken into parts and there are rules to how each part is executed on a machine. In this thesis, several shop problems and their algorithms will be introduced that I have researched. There are several examples and counter examples that I have constructed. Also I will discuss how an arbitrary problem …

Sharp Feature Identification In A Polygon, Joseph P. Scanlan

UNLV Theses, Dissertations, Professional Papers, and Capstones

This thesis presents an efficient algorithm for recognizing and extracting sharp-features from polygonal shapes. As used here, a sharp-feature is a distinct portion of a polygon that is long and skinny. The algorithm executes in O(n^2) time, where n is the number of vertices in the polygon. Experimental results from a Java implementation of the algorithm are also presented.

Finding Acronyms And Their Definitions Using Hmm, Lakshmi Vyas

UNLV Theses, Dissertations, Professional Papers, and Capstones

In this thesis, we report on design and implementation of a Hidden Markov Model (HMM) to extract acronyms and their expansions. We also report on the training of this HMM with Maximum Likelihood Estimation (MLE) algorithm using a set of examples.

Finally, we report on our testing using standard recall and precision. The HMM achieves a recall and precision of 98% and 92% respectively.

Implementation Of Hidden Semi-Markov Models, Nagendra Abhinav Dasu

UNLV Theses, Dissertations, Professional Papers, and Capstones

One of the most frequently used concepts applied to a variety of engineering and scientific studies over the recent years is that of a Hidden Markov Model (HMM). The Hidden semi-Markov model (HsMM) is contrived in such a way that it does not make any premise of constant or geometric distributions of a state duration. In other words, it allows the stochastic process to be a semi-Markov chain. Each state can have a collection of observations and the duration of each state is a variable. This allows the HsMM to be used extensively over a range of applications. Some of …

Using Smoothing Techniques To Improve The Performance Of Hidden Markov’S Model, Sweatha Boodidhi

UNLV Theses, Dissertations, Professional Papers, and Capstones

The result of training a HMM using supervised training is estimated probabilities for emissions and transitions. There are two difficulties with this approach Firstly, sparse training data causes poor probability estimates. Secondly, unseen probabilities have emission probability of zero. In this thesis, we report on different smoothing techniques and their implementations. We further report on our experimental results using standard precision and recall for various smoothing techniques.

Implementation Of Numerically Stable Hidden Markov Model, Usha Ramya Tatavarty

UNLV Theses, Dissertations, Professional Papers, and Capstones

A Hidden Markov model (HMM) is a statistical Markov model in which the system being modeled is assumed to be a Markov process with unobserved (hidden) states. HMM is an extremely flexible tool and has been successfully applied to a wide variety of stochastic modeling tasks. One of the first applications of HMM is speech recognition. Later they came to be known for their applicability in handwriting recognition, part-of-speech tagging and bio-informatics.

In this thesis, we will explain the mathematics involved in HMMs and how to efficiently perform HMM computations using dynamic programming (DP) which makes it easy to implement …

Information Extraction In An Optical Character Recognition Context, Ramon Pereda

UNLV Theses, Dissertations, Professional Papers, and Capstones

In this dissertation, we investigate the effectiveness of information extraction in the presence of Optical Character Recognition (OCR). It is well known that the OCR errors have no effects on general retrieval tasks. This is mainly due to the redundancy of information in textual documents. Our work shows that information extraction task is significantly influenced by OCR errors. Intuitively, this is due to the fact that extraction algorithms rely on a small window of text surrounding the objects to be extracted.

We show that extraction methodologies based on the Hidden Markov Models are not robust enough to deal with extraction …

Higher-Level Application Of Adaptive Dynamic Programming/Reinforcement Learning – A Next Phase For Controls And System Identification?, George G. Lendaris

Systems Science Friday Noon Seminar Series

Humans have the ability to make use of experience while performing system identification and selecting control actions for changing situations. In contrast to current technological implementations that slow down as more knowledge is stored, as more experience is gained, human processing speeds up and has enhanced effectiveness. An emerging experience-based (“higher level”) approach promises to endow our technology with enhanced efficiency and effectiveness.

The notions of context and context discernment are important to understanding this human ability. These are defined as appropriate to controls and system-identification. Some general background on controls, Dynamic Programming, and Adaptive Critic leading to Adaptive Dynamic …

Dynamic Decision Making And Race Games, Shipra De

Calvert Undergraduate Research Awards

Frequent criticism in dynamic decision making research pertains to the overly complex nature of the decision tasks used in experimentation. To address such concerns we study dynamic decision making with respect to the simple race game Hog, which has a computable optimal decision strategy. In the two-player game of Hog, individuals compete to be the first to reach a designated threshold of points. Players alternate rolling a desired quantity of dice. If the number one appears on any of the dice, the player receives no points for his turn; otherwise, the sum of the numbers appearing on the dice is …

Fusion Of Visual And Thermal Images Using Genetic Algorithms, Sertan Erkanli

Electrical & Computer Engineering Theses & Dissertations

Demands for reliable person identification systems have increased significantly due to highly security risks in our daily life. Recently, person identification systems are built upon the biometrics techniques such as face recognition. Although face recognition systems have reached a certain level of maturity, their accomplishments in practical applications are restricted by some challenges, such as illumination variations. Current visual face recognition systems perform relatively well under controlled illumination conditions while thermal face recognition systems are more advantageous for detecting disguised faces or when there is no illumination control. A hybrid system utilizing both visual and thermal images for face recognition …

Unmanned Aerial Vehicles Collision Avoidance From Moving Obstacles, Atila Ozdemir

Electrical & Computer Engineering Theses & Dissertations

The usage of the unmanned aerial vehicles (UAV) is becoming more diverse day by day in both military and civil applications. Specifically in military applications, they are becoming a "must-have" component in every arsenal. Low cost, and especially the importance of human life, makes these vehicles desired in any military situation. But in order to take advantage of the UAVs, these vehicles should be able to navigate safely and not collide with other air vehicles, especially ones that are manned and carry personnel. As a result, the importance of a collision avoidance system of the UA V arises and begins …

Video Stabilization Based On Speeded-Up Robust Features, Minqi Zhou

Electrical & Computer Engineering Theses & Dissertations

With the advancement of science and technology, portable devices using video cameras are becoming more popular. Videos captured by ordinary commercial cameras always suffer from undesired motion which results from human hand shaking and mobile platform vibration. The undesired motion would not only blur the image degrading the image quality leading to inaccurate results in automatic object recognition and tracking, but also make it difficult for people to focus on specific object regions. It is also a possibility that one may feel dizzy while watching shaky video for a long time. Many hardware and software methodologies have been developed by …

A Probabilistic Analysis Of Misparking In Reservation Based Parking Garages, Vikas G. Ashok

Computer Science Theses & Dissertations

Parking in major cities is an expensive and annoying affair, the reason ascribed to the limited availability of parking space. Modern parking garages provide parking reservation facility, thereby ensuring availability to prospective customers. Misparking in such reservation based parking garages creates confusion and aggravates driver frustration. The general conception about misparking is that it tends to completely cripple the normal functioning of the system leading to chaos and confusion. A single mispark tends to have a ripple effect and therefore spawns a chain of misparks. The chain terminates when the last mispark occurs at the parking slot reserved by the …

Two-Layer Multiple Kernel Learning, Jinfeng Zhuang, Ivor W. Tsang, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

Multiple Kernel Learning (MKL) aims to learn kernel machines for solving a real machine learning problem (e.g. classification) by exploring the combinations of multiple kernels. The traditional MKL approach is in general “shallow” in the sense that the target kernel is simply a linear (or convex) combination of some base kernels. In this paper, we investigate a framework of Multi-Layer Multiple Kernel Learning (MLMKL) that aims to learn “deep” kernel machines by exploring the combinations of multiple kernels in a multi-layer structure, which goes beyond the conventional MKL approach. Through a multiple layer mapping, the proposed MLMKL framework offers higher …

Decompiler For Pseudo Code Generation, Ankit Patel

Master's Projects

Decompiling is an area of interest for researchers in the field of software reverse engineering. When the source code from a high-level programming language is compiled, it loses a great deal of information, including code structure, syntax, and punctuation.
The purpose of this research is to develop an algorithm that can efficiently decompile assembly language into pseudo C code. There are tools available that claim to extract high-level code from an executable file, but the results of these tools tend to be inaccurate and unreadable.
Our proposed algorithm can decompile assembly code to recover many basic high-level programming structures, including …

A Family Of Simple Non-Parametric Kernel Learning Algorithms From Pairwise Constraints, Jinfeng Zhuang, Ivor W. Tsang, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

Previous studies of Non-Parametric Kernel Learning (NPKL) usually formulate the learning task as a Semi-Definite Programming (SDP) problem that is often solved by some general purpose SDP solvers. However, for N data examples, the time complexity of NPKL using a standard interior-point SDP solver could be as high as O(N6.5), which prohibits NPKL methods applicable to real applications, even for data sets of moderate size. In this paper, we present a family of efficient NPKL algorithms, termed "SimpleNPKL", which can learn non-parametric kernels from a large set of pairwise constraints efficiently. In particular, we propose two efficient SimpleNPKL algorithms. One …

Recognition Situations Using Extended Dempster-Shafer Theory, Susan Mckeever

Other resources

Weiser’s [111] vision of pervasive computing describes a world where technology seamlessly integrates into the environment, automatically responding to peoples’ needs. Underpinning this vision is the ability of systems to automatically track the situation of a person. The task of situation recognition is critical and complex: noisy and unreliable sensor data, dynamic situations, unpredictable human behaviour and changes in the environment all contribute to the complexity. No single recognition technique is suitable in all environments. Factors such as availability of training data, ability to deal with uncertain information and transparency to the user will determine which technique to use in …

Multi-Objective Zone Mapping In Large-Scale Distributed Virtual Environments, Nguyen Binh Duong Ta, Suiping Zhou, Wentong Cai, Xueyan Tang, Rassul Avani

Research Collection School Of Computing and Information Systems

In large-scale distributed virtual environments (DVEs), the NP-hard zone mapping problem concerns how to assign distinct zones of the virtual world to a number of distributed servers to improve overall interactivity. Previously, this problem has been formulated as a single-objective optimization problem, in which the objective is to minimize the total number of clients that are without QoS. This approach may cause considerable network traffic and processing overhead, as a large number of zones may need to be migrated across servers. In this paper, we introduce a multi-objective approach to the zone mapping problem, in which both the total number …

Minimax And Maximin Fitting Of Geometric Objects To Sets Of Points, Yan B. Mayster

Electronic Theses and Dissertations

This thesis addresses several problems in the facility location sub-area of computational geometry. Let S be a set of n points in the plane. We derive algorithms for approximating S by a step function curve of size k < n, i.e., by an x-monotone orthogonal polyline ℜ with k < n horizontal segments. We use the vertical distance to measure the quality of the approximation, i.e., the maximum distance from a point in S to the horizontal segment directly above or below it. We consider two types of problems: min-ε, where the goal is to minimize the error for a …

Flipping The Winner Of A Poset Game, Adam O. Kalinich '12

Student Publications & Research

Partially-ordered set games, also called poset games, are a class of two-player combinatorial games. The playing field consists of a set of elements, some of which are greater than other elements. Two players take turns removing an element and all elements greater than it, and whoever takes the last element wins. Examples of poset games include Nim and Chomp. We investigate the complexity of computing which player of a poset game has a winning strategy. We give an inductive procedure that modifies poset games to change the nim-value which informally captures the winning strategies in the game. For a generic …

On The Applications Of Deterministic Chaos For Encrypting Data On The Cloud, Jonathan Blackledge, Nikolai Ptitsyn

Conference papers

Cloud computing is expected to grow considerably in the future because it has so many advantages with regard to sale and cost, change management, next generation architectures, choice and agility. However, one of the principal concerns for users of the Cloud is lack of control and above all, data security. This paper considers an approach to encrypting information before it is ‘placed’ on the Cloud where each user has access to their own encryption algorithm, an algorithm that is based on a set of iterated function systems that outputs a chaotic number stream, designed to produce a cryptographically secure cipher. …

Shared Memory, Message Passing, And Hybrid Merge Sorts For Standalone And Clustered Smps, Atanas Radenski

Mathematics, Physics, and Computer Science Faculty Books and Book Chapters

While merge sort is well-understood in parallel algorithms theory, relatively little is known of how to implement parallel merge sort with mainstream parallel programming platforms, such as OpenMP and MPI, and run it on mainstream SMP-based systems, such as multi-core computers and multi-core clusters. This is misfortunate because merge sort is not only a fast and stable sort algorithm, but it is also an easy to understand and popular representative of the rich class of divide-and-conquer methods; hence better understanding of merge sort parallelization can contribute to better understanding of divide-and-conquer parallelization in general. In this paper, we investigate three …

In-Degree Dynamics Of Large-Scale P2p Systems, Zhongmei Yao, Daren B. H. Cline, Dmitri Loguinov

Computer Science Faculty Publications

This paper builds a complete modeling framework for understanding user churn and in-degree dynamics in unstructured P2P systems in which each user can be viewed as a stationary alternating renewal process. While the classical Poisson result on the superposition of n stationary renewal processes for n→∞ requires that each point process become sparser as n increases, it is often difficult to rigorously show this condition in practice. In this paper, we first prove that despite user heterogeneity and non-Poisson arrival dynamics, a superposition of edge-arrival processes to a live user under uniform selection converges to a Poisson process when …

Enhancement Technique For Aerial Images, Sertan Erkanli, Ahmet Gungor Pakfiliz, Jiang Li

Electrical & Computer Engineering Faculty Publications

Recently, we proposed an enhancement technique for uniformly and non-uniformly illuminated dark images that provides high color accuracy and better balance between the luminance and the contrast in images to improve the visual representations of digital images. In this paper we define an improved version of the proposed algorithm to enhance aerial images in order to reduce the gap between direct observation of a scene and its recorded image.

Fine-Tuning Algorithm Parameters Using The Design Of Experiments Approach, Aldy Gunawan, Hoong Chuin Lau, Linda Lindawati

Research Collection School Of Computing and Information Systems

Optimizing parameter settings is an important task in algorithm design. Several automated parameter tuning procedures/configurators have been proposed in the literature, most of which work effectively when given a good initial range for the parameter values. In the Design of Experiments (DOE), a good initial range is known to lead to an optimum parameter setting. In this paper, we present a framework based on DOE to find a good initial range of parameter values for automated tuning. We use a factorial experiment design to first screen and rank all the parameters thereby allowing us to then focus on the parameter …