Theory and Algorithms Commons^™

On-Line Portfolio Selection With Moving Average Reversion, Bin Li, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

On-line portfolio selection has attracted increasing interests in machine learning and AI communities recently. Empirical evidences show that stock's high and low prices are temporary and stock price relatives are likely to follow the mean reversion phenomenon. While the existing mean reversion strategies are shown to achieve good empirical performance on many real datasets, they often make the single-period mean reversion assumption, which is not always satisfied in some real datasets, leading to poor performance when the assumption does not hold. To overcome the limitation, this article proposes a multiple-period mean reversion, or so-called Moving Average Reversion (MAR), and a …

Online Kernel Selection: Algorithms And Evaluations, Tianbao Yang, Mehrdad Mahdavi, Rong Jin, Jinfeng Yi, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

Kernel methods have been successfully applied to many machine learning problems. Nevertheless, since the performance of kernel methods depends heavily on the type of kernels being used, identifying good kernels among a set of given kernels is important to the success of kernel methods. A straightforward approach to address this problem is cross-validation by training a separate classifier for each kernel and choosing the best kernel classifier out of them. Another approach is Multiple Kernel Learning (MKL), which aims to learn a single kernel classifier from an optimal combination of multiple kernels. However, both approaches suffer from a high computational …

Fast Bounded Online Gradient Descent Algorithms For Scalable Kernel-Based Online Learning, Peilin Zhao, Jialei Wang, Pengcheng Wu, Rong Jin, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

Kernel-based online learning has often shown state-of-the-art performance for many online learning tasks. It, however, suffers from a major shortcoming, that is, the unbounded number of support vectors, making it non-scalable and unsuitable for applications with large-scale datasets. In this work, we study the problem of bounded kernel-based online learning that aims to constrain the number of support vectors by a predefined budget. Although several algorithms have been proposed in literature, they are neither computationally efficient due to their intensive budget maintenance strategy nor effective due to the use of simple Perceptron algorithm. To overcome these limitations, we propose a …

Exact Soft Confidence-Weighted Learning, Jialei Wang, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

In this paper, we propose a new Soft Confidence-Weighted (SCW) online learning scheme, which enables the conventional confidence-weighted learning method to handle non-separable cases. Unlike the previous confidence-weighted learning algorithms, the proposed soft confidence-weighted learning method enjoys all the four salient properties: (i) large margin training, (ii) confidence weighting, (iii) capability to handle non-separable data, and (iv) adaptive margin. Our experimental results show that the proposed SCW algorithms significantly outperform the original CW algorithm. When comparing with a variety of state-of-the art algorithms (including AROW, NAROW and NHERD), we found that SCW generally achieves better or at least comparable predictive …

Lagrangian Relaxation For Large-Scale Multi-Agent Planning, Geoffrey J. Gordon, Pradeep Varakantham, William Yeoh, Hoong Chuin Lau, Ajay Srinivasan Aravamudhan, Shih-Fen Cheng

LARC Research Publications

Multi-agent planning is a well-studied problem with applications in various areas. Due to computational constraints, existing research typically focuses either on unstructured domains with many agents, where we are content with heuristic solutions, or domains with small numbers of agents or special structure, where we can find provably near-optimal solutions. In contrast, here we focus on provably near-optimal solutions in domains with many agents, by exploiting influence limit. To that end, we make two key contributions: (a) an algorithm, based on Lagrangian relaxation and randomized rounding, for solving multi-agent planning problems represented as large mixed-integer programs; (b) a proof of …

The Intersection Between Science And Computer Science Is Almost Empty, Dick Hamlet

Systems Science Friday Noon Seminar Series

Traditionally, a science such as physics overlaps with mathematics and engineering in a way that has been astonishingly productive. The math provides precise expression for the science, which in turn supplies the engineering with the information it needs to exploit physical phenomena. Computer science naturally wishes to put itself in the center of the traditional picture as a science. Unfortunately, it won't wash. The `science' of programming is pure and simple mathematics, not science. The distinction is more than linguistic, since science and mathematics have quite distinct goals and methods. By making the wrong choice, computer science research has been …

An Evolutionary Search Paradigm That Learns With Past Experiences, Liang Feng, Yew-Soon Ong, Ivor Tsang, Ah-Hwee Tan

Research Collection School Of Computing and Information Systems

A major drawback of evolutionary optimization approaches in the literature is the apparent lack of automated knowledge transfers and reuse across problems. Particularly, evolutionary optimization methods generally start a search from scratch or ground zero state, independent of how similar the given new problem of interest is to those optimized previously. In this paper, we present a study on the transfer of knowledge in the form of useful structured knowledge or latent patterns that are captured from previous experiences of problem-solving to enhance future evolutionary search. The essential contributions of our present study include the meme learning and meme selection …

Distributed Incomplete Pattern Matching Via A Novelweighted Bloom Filter, Siyuan Liu, Lei Kang, Lei Chen, Lionel Ni

Research Collection School Of Computing and Information Systems

In this paper, we first propose a very interesting and practical problem, pattern matching in a distributed mobile environment. Pattern matching is a well-known problem and extensive research has been conducted for performing effective and efficient search. However, previous proposed approaches assume that data are centrally stored, which is not the case in a mobile environment (e.g., mobile phone networks), where one person’s pattern could be separately stored in a number of different stations, and such a local pattern is incomplete compared with the global pattern. A simple solution to pattern matching over a mobile environment is to collect all …

Utilization Of Probabilistic Models In Short Read Assembly From Second-Generation Sequencing, Matthew W. Segar

Honors Theses

With the advent of cheaper and faster DNA sequencing technologies, assembly methods have greatly changed. Instead of outputting reads that are thousands of base pairs long, new sequencers parallelize the task by producing read lengths between 35 and 400 base pairs. Reconstructing an organism’s genome from these millions of reads is a computationally expensive task. Our algorithm solves this problem by organizing and indexing the reads using n-grams, which are short, fixed-length DNA sequences of length n. These n-grams are used to efficiently locate putative read joins, thereby eliminating the need to perform an exhaustive search over all possible read …

Wi-Fi Sensing Algorithms Utilizing Zigbee Rf Reciever For Use In Emergency Communications Mesh, Alexander Nelson

Computer Science and Computer Engineering Undergraduate Honors Theses

This thesis introduces the idea of a low-power Wi-Fi sensing wake-up controller for an emergency communications mesh network, progressively developing a prototype system which could be used in a live environment. Wireless network protocols are reviewed, as well as a limited view of cluster analysis, in order to introduce relevant concepts crucial to understanding this thesis. Algorithms for system implementation are developed, and pseudocode, designed to be configurable and platform independent, is given for each. Design goals for the system are identified with potential approaches are defined in order to optimize for each. An example hardware configuration is given, in …

Efficient Algorithm To Construct Phi Function In Vector Space Secret Sharing Scheme And Application Of Secret Sharing Scheme In Visual Cryptography, Sunny Potay

Masters Theses & Specialist Projects

Secret Sharing refers to a method through which a secret key K can be shared among a group of authorized participants, such that when they come together later, they can figure out the secret key K to decrypt the encrypted message. Any group which is not authorized cannot determine the secret key K. Some of the important secret schemes are Shamir Threshold Scheme, Monotone Circuit Scheme, and Brickell Vector Space Scheme. Brikell’s vector space secret sharing construction requires the existence of a function from a set of participant P in to vector space Zdp, where p is a …

Incorporating The Nsf/Tcpp Curriculum Recommendations In A Liberal Arts Setting, Akshaye Dhawan

Mathematics, Computer Science & Statistics Faculty Publications

This paper examines the integration of the NSF/TCPP Core Curriculum Recommendations in a liberal arts undergraduate setting. We examine how parallel and distributed computing concepts can be incorporated across the breadth of the undergraduate curriculum. As a model of such an integration, changes are proposed to Data Structures and Design and Analysis of Algorithms. These changes were implemented in Design and Analysis of Algorithms and the results were compared to previous iterations of that course taught by the same instructor. The student feedback received shows that the introduction of these topics made the course more engaging and conveyed an adequate …

Error Estimation Techniques To Refine Overlapping Aerial Image Mosaic Processes Via Detected Parameters, William Glenn Bond

Dissertations

In this paper, I propose to demonstrate a means of error estimation preprocessing in the assembly of overlapping aerial image mosaics. The mosaic program automatically assembles several hundred aerial images from a data set by aligning them, via image registration using a pattern search method, onto a GIS grid.

The method presented first locates the images from a data set that it predicts will not align well via the mosaic process, then it uses a correlation function, optimized by a modified Hooke and Jeeves algorithm, to provide a more optimal transformation function input to the mosaic program. Using this improved …

Framework Developmant For Construction Safety Visialization, Kishor Shrestha

College of Engineering: Graduate Celebration Programs

Throughout the history of the construction industry, many fatalities and injuries have occurred in construction sites. One of the major causes of accidents is unsafe site conditions: basically, this is due to inadequate supervision. To improve upon the traditional supervision approach, this study proposes a 'Framework Development for Construction Safety Visualization' approach. In addition to this, a computer vision Edge Detection Algorithm was developed and tested to convert construction site still images into edges of the objects in the images. The framework development of this study uses computer vision, robot vision, image compression, pattern recognition, internet transmission, network communication, and …

Adaptive Image Diffusion In Wavelet Domain, Kumar Mandava

College of Engineering: Graduate Celebration Programs

• Removing noise without sacrificing important structures
• Nonlinear strategies: Wavelet shrinkage and Nonlinear diffusion filtering based on features
• Clustering based wavelet diffusion

Derivation Of Hill's Equation From Scale Invariance, Andres Ortiz^, Vladik Kreinovich*

COURI Symposium Abstracts, Spring 2012

No abstract provided.

How One Trade Could Change The World: High Frequency Trading And The Flash Crash Of 2010, Sarah Perlman

Honors Projects in Finance

Financial markets are controlled directly by a small population of people, but have direct effects on almost every aspect of the global community. Financial markets are now flooded with computerized algorithms that have drastically changed the face of trading. As with any advances in technology, there are always unforeseen events that create new challenges, and adjustments that need to be made. In our increasingly global and technological world, one wrong click of the mouse in New York could affect the stock markets in London, Tokyo, and Brazil. On May 6th, 2010, such a situation occurred and caused the Dow Jones …

Efficient Reinforcement Learning In Multiple-Agent Systems And Its Application In Cognitive Radio Networks, Jing Zhang

Dissertations

The objective of reinforcement learning in multiple-agent systems is to find an efficient learning method for the agents to behave optimally. Finding Nash equilibrium has become the common learning target for the optimality. However, finding Nash equilibrium is a PPAD (Polynomial Parity Arguments on Directed graphs)-complete problem. The conventional methods can find Nash equilibrium for some special types of Markov games.

This dissertation proposes a new reinforcement learning algorithm to improve the search efficiency and effectiveness for multiple-agent systems. This algorithm is based on the definition of Nash equilibrium and utilizes the greedy and rational features of the agents. When …

Random Number Generation: Types And Techniques, David F. Dicarlo

Senior Honors Theses

What does it mean to have random numbers? Without understanding where a group of numbers came from, it is impossible to know if they were randomly generated. However, common sense claims that if the process to generate these numbers is truly understood, then the numbers could not be random. Methods that are able to let their internal workings be known without sacrificing random results are what this paper sets out to describe. Beginning with a study of what it really means for something to be random, this paper dives into the topic of random number generators and summarizes the key …

Context Aware Routing Management Architecture For Airborne Networks, Joan A. Betances

Theses and Dissertations

This thesis advocates the use of Kalman filters in conjunction with network topology information derived from the Air Tasking Order (ATO) during the planning phase for military missions. This approach is the basis for an algorithm that implements network controls that optimize network performance for Mobile Ad hoc Networks (MANET). The trajectories of relevant nodes (airborne platforms) participating in the MANET can be forecasted by parsing key information contained in the ATO. This information is used to develop optimum network routes that can significantly improve MANET performance. Improved MANET performance in the battlefield enables decision makers to access information from …