Theory and Algorithms Commons^™

Opinion Question Answering By Sentiment Clip Localization, Lei Pang, Chong-Wah Ngo

Research Collection School Of Computing and Information Systems

This article considers multimedia question answering beyond factoid and how-to questions. We are interested in searching videos for answering opinion-oriented questions that are controversial and hotly debated. Examples of questions include "Should Edward Snowden be pardoned?" and "Obamacare-unconstitutional or not?". These questions often invoke emotional response, either positively or negatively, hence are likely to be better answered by videos than texts, due to the vivid display of emotional signals visible through facial expression and speaking tone. Nevertheless, a potential answer of duration 60s may be embedded in a video of 10min, resulting in degraded user experience compared to reading the …

Negative Factor: Improving Regular-Expression Matching In Strings, Xiaochun Yang, Tao Qiu, Bin Wang, Baihua Zheng, Yaoshu Wang, Chen Li

Research Collection School Of Computing and Information Systems

The problem of finding matches of a regular expression (RE) on a string exists in many applications such as text editing, biosequence search, and shell commands. Existing techniques first identify candidates using substrings in the RE, then verify each of them using an automaton. These techniques become inefficient when there are many candidate occurrences that need to be verified. In this paper we propose a novel technique that prunes false negatives by utilizing negative factors, which are substrings that cannot appear in an answer. A main advantage of the technique is that it can be integrated with many existing algorithms …

Online Learning Of Arima For Time Series Prediction, Chenghao Liu, Hoi, Steven C. H., Peilin Zhao, Jianling Sun

Research Collection School Of Computing and Information Systems

Autoregressive integrated moving average (ARIMA) is one of the most popular linear models for time series forecasting due to its nice statistical properties and great flexibility. However, its parameters are estimated in a batch manner and its noise terms are often assumed to be strictly bounded, which restricts its applications and makes it inefficient for handling large-scale real data. In this paper, we propose online learning algorithms for estimating ARIMA models under relaxed assumptions on the noise terms, which is suitable to a wider range of applications and enjoys high computational efficiency. The idea of our ARIMA method is to …

Multiagent Based Algorithmic Approach For Fast Response In Railway Disaster Handling, Poulami Dalapati, Arambam James Singh, Animesh Dutta

Research Collection School Of Computing and Information Systems

Disaster management in railway network is an important issue. It requires to minimize negative impact and also fast, efficient recovery from the disturbances. The main challenge here is that, the effect of inconvenience spreads out very fast in time and space. It takes noticeable amount of time to get back everything in the previous situation. This paper proposes a multi agent based algorithmic approach for disaster handling in Railway Network. This takes care of fast response to get total number of affected trains in a fast and efficient manner. We propose few algorithms to handle this situation and simulate it …

Shortest Path Based Decision Making Using Probabilistic Inference, Akshat Kumar

Research Collection School Of Computing and Information Systems

We present a new perspective on the classical shortest path routing (SPR) problem in graphs. We show that the SPR problem can be recast to that of probabilistic inference in a mixture of simple Bayesian networks. Maximizing the likelihood in this mixture becomes equivalent to solving the SPR problem. We develop the well known Expectation-Maximization (EM) algorithm for the SPR problem that maximizes the likelihood, and show that it does not get stuck in a locally optimal solution. Using the same probabilistic framework, we then address an NP-Hard network design problem where the goal is to repair a network of …

Solving Risk-Sensitive Pomdps With And Without Cost Observations, Ping Hou, William Yeoh, Pradeep Varakantham

Research Collection School Of Computing and Information Systems

Partially Observable Markov Decision Processes (POMDPs) are often used to model planning problems under uncertainty. The goal in Risk-Sensitive POMDPs (RS-POMDPs) is to find a policy that maximizes the probability that the cumulative cost is within some user-defined cost threshold. In this paper, unlike existing POMDP literature, we distinguish between the two cases of whether costs can or cannot be observed and show the empirical impact of cost observations. We also introduce a new search-based algorithm to solve RS-POMDPs and show that it is faster and more scalable than existing approaches in two synthetic domains and a taxi domain generated …

Hpcnmf: A High-Performance Toolbox For Non-Negative Matrix Factorization, Karthik Devarajan, Guoli Wang

COBRA Preprint Series

Non-negative matrix factorization (NMF) is a widely used machine learning algorithm for dimension reduction of large-scale data. It has found successful applications in a variety of fields such as computational biology, neuroscience, natural language processing, information retrieval, image processing and speech recognition. In bioinformatics, for example, it has been used to extract patterns and profiles from genomic and text-mining data as well as in protein sequence and structure analysis. While the scientific performance of NMF is very promising in dealing with high dimensional data sets and complex data structures, its computational cost is high and sometimes could be critical for …

Signal Flow Graph Approach To Efficient Dst I-Iv Algorithms, Sirani M. Perera

Publications

In this paper, fast and efficient discrete sine transformation (DST) algorithms are presented based on the factorization of sparse, scaled orthogonal, rotation, rotation-reflection, and butterfly matrices. These algorithms are completely recursive and solely based on DST I-IV. The presented algorithms have low arithmetic cost compared to the known fast DST algorithms. Furthermore, the language of signal flow graph representation of digital structures is used to describe these efficient and recursive DST algorithms having (n�1) points signal flow graph for DST-I and n points signal flow graphs for DST II-IV.

Improved Egt-Based Robustness Analysis Of Negotiation Strategies In Multiagent Systems Via Model Checking, Songzheng Song, Jianye Hao, Yang Liu, Jun Sun, Ho-Fung Leung, Jie Zhang

Research Collection School Of Computing and Information Systems

Automated negotiations play an important role in various domains modeled as multiagent systems, where agents represent human users and adopt different negotiation strategies. Generally, given a multiagent system, a negotiation strategy should be robust in the sense that most agents in the system have the incentive to choose it rather than other strategies. Empirical game-theoretic (EGT) analysis is a game-theoretic analysis approach to investigate the robustness of different strategies based on a set of empirical results. In this study, we propose that model-checking techniques can be adopted to improve EGT analysis for negotiation strategies. The dynamics of strategy profiles can …

Enhancements To Hierarchical Pathfinding Algorithms, Xin Li

Electronic Theses and Dissertations

In this thesis we study the problem of pathfinding in static grid-based maps. We apply the approach of abstraction and refinement. We abstract the grid map into a graph representation, and use the classic A* algorithm to search for a path in the abstract space, and then refine it into low-level path.

We started with a 2013 entry program to the Grid-based Path Planning Competition, and implemented several enhancements to experiment with the tradeoff between memory usage and search speed. Our program returns the refined low-level path incrementally, therefore reduces the first-move lag in large maps. We cache the low-level …

Modeling, Learning And Reasoning About Preference Trees Over Combinatorial Domains, Xudong Liu

Theses and Dissertations--Computer Science

In my Ph.D. dissertation, I have studied problems arising in various aspects of preferences: preference modeling, preference learning, and preference reasoning, when preferences concern outcomes ranging over combinatorial domains. Preferences is a major research component in artificial intelligence (AI) and decision theory, and is closely related to the social choice theory considered by economists and political scientists. In my dissertation, I have exploited emerging connections between preferences in AI and social choice theory. Most of my research is on qualitative preference representations that extend and combine existing formalisms such as conditional preference nets, lexicographic preference trees, answer-set optimization programs, possibilistic …

Chillisource Game Engine Particle System Study, Angela Gross

Graduate Student Theses, Dissertations, & Professional Papers

The majority of modern game engines utilize intricate objects called particle systems which are a collection of many particles that together represent an object without well-defined surfaces. This thesis discusses the results of studying and stressing particle systems within ChilliSource, an open-source game engine written in C++, with the goal of understanding a complex system and exploring possible optimizations that could be made to it. The studies performed were driven by metrics generated with custom profiling classes that kept track of things like the number of particles rendered, how long the engine spent rendering particles, or even how long a …

Using Genetic Algorithms To Evolve Artificial Neural Networks, William T. Kearney

Honors Theses

This paper demonstrates that neuroevolution is an effective method to determine an optimal neural network topology. I provide an overview of the NeuroEvolution of Augmenting Topologies (NEAT) algorithm, and describe how unique characteristics of this algorithm solve various problem inherent to neuroevolution (namely the competing conventions problem and the challenges associated with protecting topological innovation). Parallelization is shown to greatly speed up efficiency, further reinforcing neuroevolution as a potential alternative to traditional backpropagation. I also demonstrate that appropriate parameter selection is critical in order to efficiently converge to an optimal topology. Lastly, I produce an example solution to a medical …

Algorithmic Foundations Of Heuristic Search Using Higher-Order Polygon Inequalities, Newton Henry Campbell Jr.

CCAC Theses and Dissertations

The shortest path problem in graphs is both a classic combinatorial optimization problem and a practical problem that admits many applications. Techniques for preprocessing a graph are useful for reducing shortest path query times. This dissertation studies the foundations of a class of algorithms that use preprocessed landmark information and the triangle inequality to guide A* search in graphs. A new heuristic is presented for solving shortest path queries that enables the use of higher order polygon inequalities. We demonstrate this capability by leveraging distance information from two landmarks when visiting a vertex as opposed to the common single landmark …

Aspect Mining Using Multiobjective Genetic Clustering Algorithms, David G. Bethelmy

CCAC Theses and Dissertations

In legacy software, non-functional concerns tend to cut across the system and manifest themselves as tangled or scattered code. If these crosscutting concerns could be modularized and the system refactored, then the system would become easier to understand, modify, and maintain. Modularized crosscutting concerns are known as aspects and the process of identifying aspect candidates in legacy software is called aspect mining.

One of the techniques used in aspect mining is clustering and there are many clustering algorithms. Current aspect mining clustering algorithms attempt to form clusters by optimizing one objective function. However, the objective function to be optimized tends …

Performance Based Contracting For The Manufacturing Industry By Using Integrated Platform And Dynamic Pricing Model, Lindawati, Aldy Gunawan

Research Collection Lee Kong Chian School Of Business

Although Performance Based Contracting (PBC) concept is not totally new, the PBC adaptation in Industrial Machinery and Components (IMC) manufacturing, which produces high-value and long life machineries, is rather slow and it is done with extra caution. Three main concerns for manufacturers to implement PBC are the investment cost, the maintenance cost and possible revenue loss. To handle these concerns and accelerate the PBC implementation, we propose an integrated platform that consists of three components: dynamic pricing, sensor data feeding and machinery monitoring. We model the dynamic pricing as an optimization problem and propose Genetic Algorithm to solve the problem. …

Topics On Register Synthesis Problems, Weihua Liu

Theses and Dissertations--Computer Science

Pseudo-random sequences are ubiquitous in modern electronics and information technology. High speed generators of such sequences play essential roles in various engineering applications, such as stream ciphers, radar systems, multiple access systems, and quasi-Monte-Carlo simulation. Given a short prefix of a sequence, it is undesirable to have an efficient algorithm that can synthesize a generator which can predict the whole sequence. Otherwise, a cryptanalytic attack can be launched against the system based on that given sequence.

Linear feedback shift registers (LFSRs) are the most widely studied pseudorandom sequence generators. The LFSR synthesis problem can be solved by the Berlekamp-Massey algorithm, …

Dynamically Parallel Camshift: Gpu Accelerated Object Tracking In Digital Video, Matthew J. Perry

EWU Masters Thesis Collection

"The CAMSHIFT algorithm is widely used for tracking dynamically sized and positioned objects in real-time applications. In spite of its extensive study on the platform of sequential CPU, its research on massively parallel Graphical Processing Unit (GPU) platform is quite limited. In this work, we designed and implemented two different parallel algorithms for CAMSHIFT using CUDA. The first design performs calculations on the GPU, but requires iterative data transfers back to the host CPU for condition checking, which bottlenecks the entire program. In the second design, we propose an enhanced parallel reduction-based CAMSHIFT using dynamic parallelism to reduce overhead of …

K-D Tree-Segmented Block Truncation Coding For Image Compression, Proceso L. Fernandez Jr, Ryan Rey M. Daga

Department of Information Systems & Computer Science Faculty Publications

Block truncation coding (BTC) is a class of image compression algorithms whose main technique is the partitioning of an image into pixel blocks that are then each encoded using a representative set of pixel values. It is commonly used because of its simplicity and low computational complexity. The Quadtree-segmented BTC (QTS-BTC), which utilizes a dynamic hierarchical segmentation technique, is among the most efficient in the BTC class. In this study, we propose a new BTC variant that introduces two ideas: (1) the use of a k-d tree for segmentation and (2) the use of a Mean Squared Error (MSE) threshold …

Evaluating And Improving The Efficiency Of Software And Algorithms For Sequence Data Analysis, Hugh L. Eaves

Theses and Dissertations

With the ever-growing size of sequence data sets, data processing and analysis are an increasingly large portion of the time and money spent on nucleic acid sequencing projects. Correspondingly, the performance of the software and algorithms used to perform that analysis has a direct effect on the time and expense involved. Although the analytical methods are widely varied, certain types of software and algorithms are applicable to a number of areas. Targeting improvements to these common elements has the potential for wide reaching rewards. This dissertation research consisted of several projects to characterize and improve upon the efficiency of several …