Theory and Algorithms Commons^™

Gradient Estimation For Attractor Networks, Thomas Flynn

Dissertations, Theses, and Capstone Projects

It has been hypothesized that neural network models with cyclic connectivity may be more powerful than their feed-forward counterparts. This thesis investigates this hypothesis in several ways. We study the gradient estimation and optimization procedures for several variants of these networks. We show how the convergence of the gradient estimation procedures are related to the properties of the networks. Then we consider how to tune the relative rates of gradient estimation and parameter adaptation to ensure successful optimization in these models. We also derive new gradient estimators for stochastic models. First, we port the forward sensitivity analysis method to the …

Big Networks: Analysis And Optimal Control, Hung The Nguyen

Theses and Dissertations

The study of networks has seen a tremendous breed of researches due to the explosive spectrum of practical problems that involve networks as the access point. Those problems widely range from detecting functionally correlated proteins in biology to finding people to give discounts and gain maximum popularity of a product in economics. Thus, understanding and further being able to manipulate/control the development and evolution of the networks become critical tasks for network scientists. Despite the vast research effort putting towards these studies, the present state-of-the-arts largely either lack of high quality solutions or require excessive amount of time in real-world …

Resource Optimization In Wireless Sensor Networks For An Improved Field Coverage And Cooperative Target Tracking, Husam Sweidan

Dissertations, Master's Theses and Master's Reports

There are various challenges that face a wireless sensor network (WSN) that mainly originate from the limited resources a sensor node usually has. A sensor node often relies on a battery as a power supply which, due to its limited capacity, tends to shorten the life-time of the node and the network as a whole. Other challenges arise from the limited capabilities of the sensors/actuators a node is equipped with, leading to complication like a poor coverage of the event, or limited mobility in the environment. This dissertation deals with the coverage problem as well as the limited power and …

Offline And Online Density Estimation For Large High-Dimensional Data, Aref Majdara

Dissertations, Master's Theses and Master's Reports

Density estimation has wide applications in machine learning and data analysis techniques including clustering, classification, multimodality analysis, bump hunting and anomaly detection. In high-dimensional space, sparsity of data in local neighborhood makes many of parametric and nonparametric density estimation methods mostly inefficient.

This work presents development of computationally efficient algorithms for high-dimensional density estimation, based on Bayesian sequential partitioning (BSP). Copula transform is used to separate the estimation of marginal and joint densities, with the purpose of reducing the computational complexity and estimation error. Using this separation, a parallel implementation of the density estimation algorithm on a 4-core CPU is …

Process Models Discovery And Traces Classification: A Fuzzy-Bpmn Mining Approach., Kingsley Okoye Dr, Usman Naeem Dr, Syed Islam Dr, Abdel-Rahman H. Tawil Dr, Elyes Lamine Dr

Journal of International Technology and Information Management

The discovery of useful or worthwhile process models must be performed with due regards to the transformation that needs to be achieved. The blend of the data representations (i.e data mining) and process modelling methods, often allied to the field of Process Mining (PM), has proven to be effective in the process analysis of the event logs readily available in many organisations information systems. Moreover, the Process Discovery has been lately seen as the most important and most visible intellectual challenge related to the process mining. The method involves automatic construction of process models from event logs about any domain …

Ethics And Bias In Machine Learning: A Technical Study Of What Makes Us “Good”, Ashley Nicole Shadowen

Student Theses

The topic of machine ethics is growing in recognition and energy, but bias in machine learning algorithms outpaces it to date. Bias is a complicated term with good and bad connotations in the field of algorithmic prediction making. Especially in circumstances with legal and ethical consequences, we must study the results of these machines to ensure fairness. This paper attempts to address ethics at the algorithmic level of autonomous machines. There is no one solution to solving machine bias, it depends on the context of the given system and the most reasonable way to avoid biased decisions while maintaining the …

Ancr—An Adaptive Network Coding Routing Scheme For Wsns With Different-Success-Rate Links †, Xiang Ji, Anwen Wang, Chunyu Li, Chun Ma, Yao Peng, Dajin Wang, Qingyi Hua, Feng Chen, Dingyi Fang

Department of Computer Science Faculty Scholarship and Creative Works

As the underlying infrastructure of the Internet of Things (IoT), wireless sensor networks (WSNs) have been widely used in many applications. Network coding is a technique in WSNs to combine multiple channels of data in one transmission, wherever possible, to save node’s energy as well as increase the network throughput. So far most works on network coding are based on two assumptions to determine coding opportunities: (1) All the links in the network have the same transmission success rate; (2) Each link is bidirectional, and has the same transmission success rate on both ways. However, these assumptions may not be …

Investigating Genetic Algorithm Optimization Techniques In Video Games, Nathan Ambuehl

Undergraduate Honors Theses

Immersion is essential for player experience in video games. Artificial Intelligence serves as an agent that can generate human-like responses and intelligence to reinforce a player’s immersion into their environment. The most common strategy involved in video game AI is using decision trees to guide chosen actions. However, decision trees result in repetitive and robotic actions that reflect an unrealistic interaction. This experiment applies a genetic algorithm that explores selection, crossover, and mutation functions for genetic algorithm implementation in an isolated Super Mario Bros. pathfinding environment. An optimized pathfinding AI can be created by combining an elitist selection strategy with …

Online Multitask Relative Similarity Learning, Shuji Hao, Peilin Zhao, Yong Liu, Steven C. H. Hoi, Chunyan Miao

Research Collection School Of Computing and Information Systems

Relative similarity learning (RSL) aims to learn similarity functions from data with relative constraints. Most previous algorithms developed for RSL are batch-based learning approaches which suffer from poor scalability when dealing with real world data arriving sequentially. These methods are often designed to learn a single similarity function for a specific task. Therefore, they may be sub-optimal to solve multiple task learning problems. To overcome these limitations, we propose a scalable RSL framework named OMTRSL (Online Multi-Task Relative Similarity Learning). Specifically, we first develop a simple yet effective online learning algorithm for multi-task relative similarity learning. Then, we also propose …

An Analysis Of The Application Of Simplified Silhouette To The Evaluation Of K-Means Clustering Validity, Fei Wang, Hector-Hugo Franco-Penya, John D. Kelleher, John Pugh, Robert J. Ross

Conference papers

Silhouette is one of the most popular and effective internal measures for the evaluation of clustering validity. Simplified Silhouette is a computationally simplified version of Silhouette. However, to date Simplified Silhouette has not been systematically analysed in a specific clustering algorithm. This paper analyses the application of Simplified Silhouette to the evaluation of k-means clustering validity and compares it with the k-means Cost Function and the original Silhouette from both theoretical and empirical perspectives. The theoretical analysis shows that Simplified Silhouette has a mathematical relationship with both the k-means Cost Function and the original Silhouette, while empirically, we show that …

Solving Algorithmic Problems In Finitely Presented Groups Via Machine Learning, Jonathan Gryak

Dissertations, Theses, and Capstone Projects

Machine learning and pattern recognition techniques have been successfully applied to algorithmic problems in free groups. In this dissertation, we seek to extend these techniques to finitely presented non-free groups, in particular to polycyclic and metabelian groups that are of interest to non-commutative cryptography.

As a prototypical example, we utilize supervised learning methods to construct classifiers that can solve the conjugacy decision problem, i.e., determine whether or not a pair of elements from a specified group are conjugate. The accuracies of classifiers created using decision trees, random forests, and N-tuple neural network models are evaluated for several non-free groups. …

Neural Network Ai For Fightingice, Alan D. Robison

Computer Engineering

Game AI in the fighting game genre, along the lines of Street Fighter, Mortal Kombat and Tekken, is traditionally script-based, with hard-coded reactions to various situations. Though this approach is often easy to understand and tweak, it requires substantial time and understanding of the game to implement in a way that is challenging and satisfying for the player due to the very large possibility space. This paper explores the use of neural networks as an alternative approach by implementing and training a network to select an action to take each frame based on the game state.

Local Gaussian Processes For Efficient Fine-Grained Traffic Speed Prediction, Truc Viet Le, Richard Oentaryo, Siyuan Liu, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

Traffic speed is a key indicator for the efficiency of an urban transportation system. Accurate modeling of the spatiotemporally varying traffic speed thus plays a crucial role in urban planning and development. This paper addresses the problem of efficient fine-grained traffic speed prediction using big traffic data obtained from static sensors. Gaussian processes (GPs) have been previously used to model various traffic phenomena, including flow and speed. However, GPs do not scale with big traffic data due to their cubic time complexity. In this work, we address their efficiency issues by proposing localGPs to learn from and make predictions for …

Tackling Large-Scale Home Health Care Delivery Problem With Uncertainty, Cen Chen, Zachary Rubinstein, Stephen Smith, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

In this work, we investigate a multi-period Home HealthCare Scheduling Problem (HHCSP) under stochastic serviceand travel times. We first model the deterministic problemas an integer linear programming model that incorporatesreal-world requirements, such as time windows, continuityof care, workload fairness, inter-visit temporal dependencies.We then extend the model to cope with uncertainty in durations,by introducing chance constraints into the formulation.We propose efficient solution approaches, which providequantifiable near-optimal solutions and further handlethe uncertainties by employing a sampling-based strategy. Wedemonstrate the effectiveness of our proposed approaches oninstances synthetically generated by real-world dataset forboth deterministic and stochastic scenarios.

Sampling Based Approaches For Minimizing Regret In Uncertain Markov Decision Problems (Mdps), Asrar Ahmed, Pradeep Varakantham, Meghna Lowalekar, Yossiri Adulyasak, Patrick Jaillet

Research Collection School Of Computing and Information Systems

Markov Decision Processes (MDPs) are an effective model to represent decision processes in the presence of transitional uncertainty and reward tradeoffs. However, due to the difficulty in exactly specifying the transition and reward functions in MDPs, researchers have proposed uncertain MDP models and robustness objectives in solving those models. Most approaches for computing robust policies have focused on the computation of maximin policies which maximize the value in the worst case amongst all realisations of uncertainty. Given the overly conservative nature of maximin policies, recent work has proposed minimax regret as an ideal alternative to the maximin objective for robust …

An Improved Algorithm For Learning To Perform Exception-Tolerant Abduction, Mengxue Zhang

McKelvey School of Engineering Graduate Student Theses & Dissertations

Abstract

Inference from an observed or hypothesized condition to a plausible cause or explanation for this condition is known as abduction. For many tasks, the acquisition of the necessary knowledge by machine learning has been widely found to be highly effective. However, the semantics of learned knowledge are weaker than the usual classical semantics, and this necessitates new formulations of many tasks. We focus on a recently introduced formulation of the abductive inference task that is thus adapted to the semantics of machine learning. A key problem is that we cannot expect that our causes or explanations will be perfect, …

Music Feature Matching Using Computer Vision Algorithms, Mason Hollis

Computer Science and Computer Engineering Undergraduate Honors Theses

This paper seeks to establish the validity and potential benefits of using existing computer vision techniques on audio samples rather than traditional images in order to consistently and accurately identify a song of origin from a short audio clip of potentially noisy sound. To do this, the audio sample is first converted to a spectrogram image, which is used to generate SURF features. These features are compared against a database of features, which have been previously generated in a similar fashion, in order to find the best match. This algorithm has been implemented in a system that can run as …

Stop Nuclear Smuggling Through Efficient Container Inspection, Xinrun Wang, Qingyu Guo, Bo An

Research Collection School Of Computing and Information Systems

Since 2003, the U.S. government has spent $850 million on the Megaport Initiative which aims at stopping the nuclear smuggling in international container shipping through advanced inspection facilities including Non-Intrusive Inspection (NII) and Mobile Radiation Detection and Identification System (MRDIS). Unfortunately, it remains a significant challenge to efficiently inspect more than 11.7 million containers imported to the U.S. due to the limited inspection resources. Moreover, existing work in container inspection neglects the sophisticated behavior of the smuggler who can surveil the inspector’s strategy and decide the optimal (sequential) smuggling plan. This paper is the first to tackle this challenging container …

A Parallelized Method For Solving Large Scale Integer Linear Optimization Problems Using Cut-And-Solve With Applications To Cgwas, John Brandenburg

Theses

The commercial solver CPLEX has been one of the top solvers of mixed-integer and purely integer linear problems for some time. Its method of solving, Branch-and-Cut, has been shown to be highly effective, but has its limits in terms of input sizes which are tractable, and cannot be effectively parallelized beyond a small number. Here we present a different method of solution, Cut-and-Solve, which utilizes the power of CPLEX to effectively parallelize any mixed-integer or integer linear problem. We have utilized Cut-and-Solve in a novel way to offer optimal solution guarantees more quickly. We will show comparisons of Cut-and-Solve to …

An Efficient Approach To Model-Based Hierarchical Reinforcement Learning, Zhuoru Li, Akshay Narayan, Tze-Yun Leong

Research Collection School Of Computing and Information Systems

We propose a model-based approach to hierarchical reinforcement learning that exploits shared knowledge and selective execution at different levels of abstraction, to efficiently solve large, complex problems. Our framework adopts a new transition dynamics learning algorithm that identifies the common action-feature combinations of the subtasks, and evaluates the subtask execution choices through simulation. The framework is sample efficient, and tolerates uncertain and incomplete problem characterization of the subtasks. We test the framework on common benchmark problems and complex simulated robotic environments. It compares favorably against the stateof-the-art algorithms, and scales well in very large problems.

Xic Clustering By Baseyian Network, Kyle J. Handy

Graduate Student Theses, Dissertations, & Professional Papers

No abstract provided.

An Introduction To The Theory And Applications Of Bayesian Networks, Anant Jaitha

CMC Senior Theses

Bayesian networks are a means to study data. A Bayesian network gives structure to data by creating a graphical system to model the data. It then develops probability distributions over these variables. It explores variables in the problem space and examines the probability distributions related to those variables. It conducts statistical inference over those probability distributions to draw meaning from them. They are good means to explore a large set of data efficiently to make inferences. There are a number of real world applications that already exist and are being actively researched. This paper discusses the theory and applications of …

Scalable Greedy Algorithms For Task/Resource Constrained Multi-Agent Stochastic Planning, Pritee Agrawal, Pradeep Varakantham, William Yeoh

Research Collection School Of Computing and Information Systems

Synergistic interactions between task/resource allocation and stochastic planning exist in many environments such as transportation and logistics, UAV task assignment and disaster rescue. Existing research in exploiting these synergistic interactions between the two problems have either only considered domains where tasks/resources are completely independent of each other or have focussed on approaches with limited scalability. In this paper, we address these two limitations by introducing a generic model for task/resource constrained multi-agent stochastic planning, referred to as TasC-MDPs. We provide two scalable greedy algorithms, one of which provides posterior quality guarantees. Finally, we illustrate the high scalability and solution performance …

Optimizing The Mix Of Games And Their Locations On The Casino Floor, Jason D. Fiege, Anastasia D. Baran

International Conference on Gambling & Risk Taking

We present a mathematical framework and computational approach that aims to optimize the mix and locations of slot machine types and denominations, plus other games to maximize the overall performance of the gaming floor. This problem belongs to a larger class of spatial resource optimization problems, concerned with optimizing the allocation and spatial distribution of finite resources, subject to various constraints. We introduce a powerful multi-objective evolutionary optimization and data-modelling platform, developed by the presenter since 2002, and show how this software can be used for casino floor optimization. We begin by extending a linear formulation of the casino floor …

Stationary And Time-Dependent Optimization Of The Casino Floor Slot Machine Mix, Anastasia D. Baran, Jason D. Fiege

International Conference on Gambling & Risk Taking

Modeling and optimizing the performance of a mix of slot machines on a gaming floor can be addressed at various levels of coarseness, and may or may not consider time-dependent trends. For example, a model might consider only time-averaged, aggregate data for all machines of a given type; time-dependent aggregate data; time-averaged data for individual machines; or fully time dependent data for individual machines. Fine-grained, time-dependent data for individual machines offers the most potential for detailed analysis and improvements to the casino floor performance, but also suffers the greatest amount of statistical noise. We present a theoretical analysis of single …

Designing And Comparing Multiple Portfolios Of Parameter Configurations For Online Algorithm Selection, Aldy Gunawan, Hoong Chuin Lau, Mustafa Misir

Research Collection School Of Computing and Information Systems

Algorithm portfolios seek to determine an effective set of algorithms that can be used within an algorithm selection framework to solve problems. A limited number of these portfolio studies focus on generating different versions of a target algorithm using different parameter configurations. In this paper, we employ a Design of Experiments (DOE) approach to determine a promising range of values for each parameter of an algorithm. These ranges are further processed to determine a portfolio of parameter configurations, which would be used within two online Algorithm Selection approaches for solving different instances of a given combinatorial optimization problem effectively. We …

Ant Colony Optimization For Continuous Spaces, Rachel Findley

Computer Science and Computer Engineering Undergraduate Honors Theses

Ant Colony Optimization (ACO) is an optimization algorithm designed to find semi-optimal solutions to Combinatorial Optimization Problems. The challenge of modifying this algorithm to effectively optimize over a continuous domain is one that has been tackled by several researchers. In this paper, ACO has been modified to use several variations of the algorithm for continuous spaces. An aspect of ACO which is crucial to its success when optimizing over a continuous space is choosing the appropriate object (solution component) out of an infinite set to add to the ant's path. This step is highly important in shaping good solutions. Important …

A Study Of Android Malware Detection Techniques And Machine Learning, Balaji Baskaran, Anca Ralescu

MAICS: The Modern Artificial Intelligence and Cognitive Science Conference

Android OS is one of the widely used mobile Operating Systems. The number of malicious applications and adwares are increasing constantly on par with the number of mobile devices. A great number of commercial signature based tools are available on the market which prevent to an extent the penetration and distribution of malicious applications. Numerous researches have been conducted which claims that traditional signature based detection system work well up to certain level and malware authors use numerous techniques to evade these tools. So given this state of affairs, there is an increasing need for an alternative, really tough malware …

Extended Pixel Representation For Image Segmentation, Deeptha Girish, Vineeta Singh, Anca Ralescu

MAICS: The Modern Artificial Intelligence and Cognitive Science Conference

We explore the use of extended pixel representation for color based image segmentation using the K-means clustering algorithm. Various extended pixel representations have been implemented in this paper and their results have been compared. By extending the representation of pixels an image is mapped to a higher dimensional space. Unlike other approaches, where data is mapped into an implicit features space of higher dimension (kernel methods), in the approach considered here, the higher dimensions are defined explicitly. Preliminary experimental results which illustrate the proposed approach are promising.

An Autonomic Computing System Based On A Rule-Based Policy Engine And Artificial Immune Systems, Rahmira Rufus, William Nick, Joseph Shelton, Albert Esterline

MAICS: The Modern Artificial Intelligence and Cognitive Science Conference

Autonomic computing systems arose from the notion that complex computing systems should have properties like those of the autonomic nervous system, which coordinates bodily functions and allows attention to be directed to more pressing needs. An autonomic system allows the system administrator to specify high-level policies, which the system maintains without administrator assistance. Policy enforcement can be done with a rule based system such as Jess (a java expert system shell). An autonomic system must be able to monitor itself, and this is often a limiting factor. We are developing an automatic system that has a policy engine and uses …