Theory and Algorithms Commons^™

Vertex Weighted Spectral Clustering, Mohammad Masum

Electronic Theses and Dissertations

Spectral clustering is often used to partition a data set into a specified number of clusters. Both the unweighted and the vertex-weighted approaches use eigenvectors of the Laplacian matrix of a graph. Our focus is on using vertex-weighted methods to refine clustering of observations. An eigenvector corresponding with the second smallest eigenvalue of the Laplacian matrix of a graph is called a Fiedler vector. Coefficients of a Fiedler vector are used to partition vertices of a given graph into two clusters. A vertex of a graph is classified as unassociated if the Fiedler coefficient of the vertex is close to …

Large-Scale Online Feature Selection For Ultra-High Dimensional Sparse Data, Yue Wu, Steven C. H. Hoi, Tao Mei, Nenghai Yu

Research Collection School Of Computing and Information Systems

Feature selection (FS) is an important technique in machine learning and data mining, especially for large scale high-dimensional data. Most existing studies have been restricted to batch learning, which is often inefficient and poorly scalable when handling big data in real world. As real data may arrive sequentially and continuously, batch learning has to retrain the model for the new coming data, which is very computationally intensive. Online feature selection (OFS) is a promising new paradigm that is more efficient and scalable than batch learning algorithms. However, existing online algorithms usually fall short in their inferior efficacy. In this article, …

Modeling Trajectories With Recurrent Neural Networks, Hao Wu, Ziyang Chen, Weiwei Sun, Baihua Zheng, Wei Wang

Research Collection School Of Computing and Information Systems

Modeling trajectory data is a building block for many smart-mobility initiatives. Existing approaches apply shallow models such as Markov chain and inverse reinforcement learning to model trajectories, which cannot capture the long-term dependencies. On the other hand, deep models such as Recurrent Neura lNetwork (RNN) have demonstrated their strength of modeling variable length sequences. However, directly adopting RNN to model trajectories is not appropriate because of the unique topological constraints faced by trajectories. Motivated by these findings, we design two RNN-based models which can make full advantage of the strength of RNN to capture variable length sequence and meanwhile to …

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 …

A Decidable Fragment In Separation Logic With Inductive Predicates And Arithmetic, Quang Loc Le, Makoto Tatsuta, Jun Sun, Wei-Ngan Chin

Research Collection School Of Computing and Information Systems

We consider the satisfiability problem for a fragment of separation logic including inductive predicates with shape and arithmetic properties. We show that the fragment is decidable if the arithmetic properties can be represented as semilinear sets. Our decision procedure is based on a novel algorithm to infer a finite representation for each inductive predicate which precisely characterises its satisfiability. Our analysis shows that the proposed algorithm runs in exponential time in the worst case. We have implemented our decision procedure and integrated it into an existing verification system. Our experiment on benchmarks shows that our procedure helps to verify the …

A Weighted Maximum Matching Algorithm For Influence Maximization And Structural Controllability, Giorgio Sartor, Yeow Khiang Chia, Laura Wynter, Justin Ruths

Research Collection School Of Computing and Information Systems

Structural control and influence maximization on networks both admit the problem of selecting a particular subset of nodes. In structural control, the subset of nodes should guarantee the controllability of the network (in the usual sense) for almost any combination of weights. In influence maximization, given a diffusion process over the network, the chosen subset of nodes (of a given cardinality) should produce the greatest diffusive influence over the rest of the network. While structural control exploits only the structure of the network, influence maximization depends both on the structure and the weights of the edges. We modify an algorithm …

Educational Magic Tricks Based On Error-Detection Schemes, Ronald I. Greenberg

Computer Science: Faculty Publications and Other Works

Magic tricks based on computer science concepts help grab student attention and can motivate them to delve more deeply. Error detection ideas long used by computer scientists provide a rich basis for working magic; probably the most well known trick of this type is one included in the CS Unplugged activities. This paper shows that much more powerful variations of the trick can be performed, some in an unplugged environment and some with computer assistance. Some of the tricks also show off additional concepts in computer science and discrete mathematics.

Game Specific Approaches To Monte Carlo Tree Search For Dots And Boxes, Jared Prince

Mahurin Honors College Capstone Experience/Thesis Projects

In this project, a Monte Carlo tree search player was designed and implemented for the child’s game dots and boxes, the computational burden of which has left traditional artificial intelligence approaches like minimax ineffective. Two potential improvements to this player were implemented using game-specific information about dots and boxes: the lack of information for decision-making provided by the net score and the inherent symmetry in many states. The results of these two approaches are presented, along with details about the design of the Monte Carlo tree search player. The first improvement, removing net score from the state information, was proven …

Encryption Backdoors: A Discussion Of Feasibility, Ethics, And The Future Of Cryptography, Jennifer A. Martin

Honors Projects

In the age of technological advancement and the digitization of information, privacy seems to be all but an illusion. Encryption is supposed to be the white knight that keeps our information and communications safe from unwanted eyes, but how secure are the encryption algorithms that we use? Do we put too much trust in those that are charged with implementing our everyday encryption systems? This paper addresses the concept of backdoors in encryption: ways that encryption systems can be implemented so that the security can be bypassed by those that know about its existence. Many governments around the world are …

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.

Scalable And Fully Distributed Localization In Large-Scale Sensor Networks, Miao Jin, Su Xia, Hongyi Wu, Xianfeng David Gu

Electrical & Computer Engineering Faculty Publications

This work proposes a novel connectivity-based localization algorithm, well suitable for large-scale sensor networks with complex shapes and a non-uniform nodal distribution. In contrast to current state-of-the-art connectivity-based localization methods, the proposed algorithm is highly scalable with linear computation and communication costs with respect to the size of the network; and fully distributed where each node only needs the information of its neighbors without cumbersome partitioning and merging process. The algorithm is theoretically guaranteed and numerically stable. Moreover, the algorithm can be readily extended to the localization of networks with a one-hop transmission range distance measurement, and the propagation of …

Cataloging Github Repositories, Abhishek Sharma, Ferdian Thung, Pavneet Singh Kochhar, Agus Sulistya, David Lo

Research Collection School Of Computing and Information Systems

GitHub is one of the largest and most popular repository hosting service today, having about 14 million users and more than 54 million repositories as of March 2017. This makes it an excellent platform to find projects that developers are interested in exploring. GitHub showcases its most popular projects by cataloging them manually into categories such as DevOps tools, web application frameworks, and game engines. We propose that such cataloging should not be limited only to popular projects. We explore the possibility of developing such cataloging system by automatically extracting functionality descriptive text segments from readme files of GitHub repositories. …

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 …

Compress: A Comprehensive Framework Of Trajectory Compression In Road Networks, Yunheng Han, Weiwei Sun, Baihua Zheng

Research Collection School Of Computing and Information Systems

More and more advanced technologies have become available to collect and integrate an unprecedented amount of data from multiple sources, including GPS trajectories about the traces of moving objects. Given the fact that GPS trajectories are vast in size while the information carried by the trajectories could be redundant, we focus on trajectory compression in this article. As a systematic solution, we propose a comprehensive framework, namely, COMPRESS (Comprehensive Paralleled Road-Network-Based Trajectory Compression), to compress GPS trajectory data in an urban road network. In the preprocessing step, COMPRESS decomposes trajectories into spatial paths and temporal sequences, with a thorough justification …

Community Detection In Social Networks, Ketki Kulkarni

Master's Projects

The rise of the Internet has brought people closer. The number of interactions between people across the globe has gone substantially up due to social awareness, the advancements of the technology, and digital interaction. Social networking sites have built societies, communities virtually. Often these societies are displayed as a network of nodes depicting people and edges depicting relationships, links. This is a good and e cient way to store, model and represent systems which have a complex and rich information. Towards that goal we need to nd e ective, quick methods to analyze social networks. One of the possible solution …

Influence Detection And Spread Estimation In Social Networks, Madhura Kaple

Master's Projects

A social network is an online platform, where people communicate and share information with each other. Popular social network features, which make them di erent from traditional communication platforms, are: following a user, re-tweeting a post, liking and commenting on a post etc. Many companies use various social networking platforms extensively as a medium for marketing their products. A xed amount of budget is alloted by the companies to maximize the positive in uence of their product. Every social network consists of a set of users (people) with connections between them. Each user has the potential to extend its in …

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, …

Algorithmic Factorization Of Polynomials Over Number Fields, Christian Schulz

Mathematical Sciences Technical Reports (MSTR)

The problem of exact polynomial factorization, in other words expressing a polynomial as a product of irreducible polynomials over some field, has applications in algebraic number theory. Although some algorithms for factorization over algebraic number fields are known, few are taught such general algorithms, as their use is mainly as part of the code of various computer algebra systems. This thesis provides a summary of one such algorithm, which the author has also fully implemented at https://github.com/Whirligig231/number-field-factorization, along with an analysis of the runtime of this algorithm. Let k be the product of the degrees of the adjoined elements used …

Unsupervised Machine Learning In Agent-Based Modeling, Luke D. Robinson

Celebration of Learning

Agent-based models (ABMs) are used by researchers in a variety of fields to model natural phenomena. In an ABM, a wide range of behaviors and outcomes can be observed based on the parameters of the model. In many cases, these behaviors can be categorized into discrete outcomes identifiable by human observers. Our goal was to use clustering algorithms to identify those outcomes from model output data. For this project, we used data from the NetLogo Wolf Sheep Predation model to explore and evaluate three clustering algorithms from Python's scikit-learn package. If this task can be completed reliably by a computer, …

Network Modeling Of Infectious Disease: Transmission, Control And Prevention, Christina M. Chandler

Honors College Theses

Many factors come into play when it comes to the transmission of infectious diseases. In disease control and prevention, it is inevitable to consider the general population and the relationships between individuals as a whole, which calls for advanced mathematical modeling approaches.

We will use the concept of network flow and the modified Ford-Fulkerson algorithm to demonstrate the transmission of infectious diseases over a given period of time. Through our model one can observe what possible measures should be taken or improved upon in the case of an epidemic. We identify key nodes and edges in the resulted network, which …

Optimized Forecasting Of Dominant U.S. Stock Market Equities Using Univariate And Multivariate Time Series Analysis Methods, Michael Schwartz

Computational and Data Sciences Theses

This dissertation documents an investigation into forecasting U.S. stock market equities via two very different time series analysis techniques: 1) autoregressive integrated moving average (ARIMA), and 2) singular spectrum analysis (SSA). Approximately 40% of the S&P 500 stocks are analyzed. Forecasts are generated for one and five days ahead using daily closing prices. Univariate and multivariate structures are applied and results are compared. One objective is to explore the hypothesis that a multivariate model produces superior performance over a univariate configuration. Another objective is to compare the forecasting performance of ARIMA to SSA, as SSA is a relatively recent development …

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 …

Electrodynamical Modeling For Light Transport Simulation, Michael G. Saunders

Undergraduate Honors Theses

Modernity in the computer graphics community is characterized by a burgeoning interest in physically based rendering techniques. That is to say that mathematical reasoning from first principles is widely preferred to ad hoc, approximate reasoning in blind pursuit of photorealism. Thereby, the purpose of our research is to investigate the efficacy of explicit electrodynamical modeling by means of the generalized Jones vector given by Azzam [1] and the generalized Jones matrix given by Ortega-Quijano & Arce-Diego [2] in the context of stochastic light transport simulation for computer graphics. To augment the status quo path tracing framework with such a modeling …

A Trivium-Inspired Pseudorandom Number Generator With A Statistical Comparison To The Randomness Of Securerandom And Trivium, Latoya Niesha Jackson

Theses and Dissertations

A pseudorandom number generator (PRNG) is an algorithm that produces a sequence of numbers which emulates the characteristics of a random sequence. In comparison to its genuine counterpart, PRNGs are considered more suitable for computing devices in that they do not consume a lot of resources (in terms of memory) and their portability; they can also be used on a wide range of devices. Cryptographically Secure PRNGs (CSPRNGs) are the only type of PRNGs suitable for cryptographic applications. They are specially designed to withstand security attacks. In this thesis, we provide descriptions of two CSPRNGs: Trivium, a hardware-based stream cipher …

A Comparative Study Of Cognitive Systems For Learning, Praneetha Mandava

Theses and Dissertations

Learning is the modification of a behavioral tendency by experience. Memory and reasoning are the most important aspects for learning in humans; information is temporarily stored in the short-term memory and processed, compared with existing memories and stored in long-term memory, and can be re-used when needed. One way to describe an organized pattern of thought or behavior and the categories of information along with their relationships is by using schemas. A cognitive script is one form of a schema that evolves over multiple exposures to the same set of stimuli and/or repeated enactment of a particular behavior. This research …

Robust Object Tracking Via Locality Sensitive Histograms, Shengfeng He, Rynson W.H Lau, Qingxiong Yang, Jiang Wang, Ming-Hsuan Yang

Research Collection School Of Computing and Information Systems

This paper presents a novel locality sensitive histogram (LSH) algorithm for visual tracking. Unlike the conventional image histogram that counts the frequency of occurrence of each intensity value by adding ones to the corresponding bin, an LSH is computed at each pixel location, and a floating-point value is added to the corresponding bin for each occurrence of an intensity value. The floating-point value exponentially reduces with respect to the distance to the pixel location where the histogram is computed. An efficient algorithm is proposed that enables the LSHs to be computed in time linear in the image size and the …

Determining Feasibility Resilience: Set Based Design Iteration Evaluation Through Permutation Stability Analysis, James E. Ross

Dissertations

The goal of robust design is to select a design that will still perform satisfactorily even with unexpected variation in design parameters. A resilient design will accommodate unanticipated future system requirements. Through studying the variations of system parameters through the use of multi objective optimization, a designer hopes to locate a robustly resilient design, which performs current mission well even with varying system parameters and is able to be easily repurposed to new missions. This ability to withstand changes is critical because it is common for the product of a design to undergo changes throughout its life cycle. This subject …