Theory and Algorithms Commons^™

Tradao: A Visual Analytics System For Trading Algorithm Optimization, Ka Wing Tsang, Haotian Li, Fuk Ming Lam, Yifan Mu, Yong Wang, Huamin Qu

Research Collection School Of Computing and Information Systems

With the wide applications of algorithmic trading, it has become critical for traders to build a winning trading algorithm to beat the market. However, due to the lack of efficient tools, traders mainly rely on their memory to manually compare the algorithm instances of a trading algorithm and further select the best trading algorithm instance for the real trading deployment. We work closely with industry practitioners to discover and consolidate user requirements and develop an interactive visual analytics system for trading algorithm optimization. Structured expert interviews are conducted to evaluateTradAOand a representative case study is documented for illustrating the system …

Quantum-Inspired Algorithm For Vehicle Sharing Problem, Whei Yeap Suen, Chun Yat Lee, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

Recent hardware developments in quantum technologies have inspired a myriad of special-purpose hardware devices tasked to solve optimization problems. In this paper, we explore the application of Fujitsu’s quantum-inspired CMOS-based Digital Annealer (DA) in solving constrained routing problems arising in transportation and logistics. More precisely in this paper, we study the vehicle sharing problem and show that the DA as a QUBO solver can potentially fill the gap between two common methods: exact solvers like Cplex and heuristics. We benchmark the scalability and quality of solutions obtained by DA with Cplex and with a greedy heuristic. Our results show that …

Novel Theorems And Algorithms Relating To The Collatz Conjecture, Michael R. Schwob, Peter Shiue, Rama Venkat

Mathematical Sciences Faculty Research

Proposed in 1937, the Collatz conjecture has remained in the spotlight for mathematicians and computer scientists alike due to its simple proposal, yet intractable proof. In this paper, we propose several novel theorems, corollaries, and algorithms that explore relationships and properties between the natural numbers, their peak values, and the conjecture. These contributions primarily analyze the number of Collatz iterations it takes for a given integer to reach 1 or a number less than itself, or the relationship between a starting number and its peak value.

Solving Multiple Inference In Graphical Models, Cong Chen

Dissertations, Theses, and Capstone Projects

For inference problems in graphical models, much effort has been directed at algorithms for obtaining one single optimal prediction. In practice, the data is often noisy or incomplete, which makes one single optimal solution unreliable. To address this problem, multiple Inference is proposed to find several best solutions, M-Best, where multiple hypotheses are preferred for advanced reasoning. People use oracle accuracy as an evaluation criterion expecting one of the solutions has high accuracy with the ground truth. It has been shown that it is beneficial for the top solutions to be diverse. Approaches for solving diverse multiple inference are proposed …

Quantum Computing For Supply Chain Finance, Paul R. Griffin, Ritesh Sampat

Research Collection School Of Computing and Information Systems

Applying quantum computing to real world applications to assess the potential efficacy is a daunting task for non-quantum specialists. This paper shows an implementation of two quantum optimization algorithms applied to portfolios of trade finance portfolios and compares the selections to those chosen by experienced underwriters and a classical optimizer. The method used is to map the financial risk and returns for a trade finance portfolio to an optimization function of a quantum algorithm developed in a Qiskit tutorial. The results show that whilst there is no advantage seen by using the quantum algorithms, the performance of the quantum algorithms …

Unified And Incremental Simrank: Index-Free Approximation With Scheduled Principle, Fanwei Zhu, Yuan Fang, Kai Zhang, Kevin C.-C. Chang, Hongtai Cao, Zhen Jiang, Minghui Wu

Research Collection School Of Computing and Information Systems

SimRank is a popular link-based similarity measure on graphs. It enables a variety of applications with different modes of querying (e.g., single-pair, single-source and all-pair modes). In this paper, we propose UISim, a unified and incremental framework for all SimRank modes based on a scheduled approximation principle. UISim processes queries with incremental and prioritized exploration of the entire computation space, and thus allows flexible tradeoff of time and accuracy. On the other hand, it creates and shares common “building blocks” for online computation without relying on indexes, and thus is efficient to handle both static and dynamic graphs. Our experiments …

Routing Policy Choice Prediction In A Stochastic Network: Recursive Model And Solution Algorithm, Tien Mai, Xinlian Yu, Song Gao, Emma Frejinger

Research Collection School Of Computing and Information Systems

We propose a Recursive Logit (STD-RL) model for routing policy choice in a stochastic time-dependent (STD) network, where a routing policy is a mapping from states to actions on which link to take next, and a state is defined by node, time and information. A routing policy encapsulates travelers’ adaptation to revealed traffic conditions when making route choices. The STD-RL model circumvents choice set generation, a procedure with known issues related to estimation and prediction. In a given state, travelers make their link choice maximizing the sum of the utility of the outgoing link and the expected maximum utility until …

Molecular Vibrations Of Symmetric Molecules: Raman Scattering Driven Molecular Dynamics Method, Martina Kaledin, Dominick Pierre-Jacques, Ciara Tyler, Jason Dyke

Symposium of Student Scholars

This project focuses on developing a novel computational technique to study molecular vibrations through infrared (IR) and Raman scattering Driven Molecular Dynamics (DMD) method. While the main criterion for IR absorption is a net change in the dipole moment in a molecule as it vibrates, presently we wish to predict and analyze vibrational spectra to study symmetric vibrational modes that are IR inactive or weakly active while strongly Raman active. A newly developed method was tested on CO₂, H₂O, CH₄, and C₂₀ molecules. Students optimized the molecular structures, obtained vibrational frequencies, and IR …

Teaching Machine Learning For The Physical Sciences: A Summary Of Lessons Learned And Challenges, Viviana Acquaviva

Publications and Research

This paper summarizes some challenges encountered and best practices established in several years of teaching Machine Learning for the Physical Sciences at the undergraduate and graduate level. I discuss motivations for teaching ML to physicists, desirable properties of pedagogical materials, such as accessibility, relevance, and likeness to real-world research problems, and give examples of components of teaching units.

An Adaptive Cryptosystem On A Finite Field, Awnon Bhowmik, Unnikrishnan Menon

Publications and Research

Owing to mathematical theory and computational power evolution, modern cryptosystems demand ingenious trapdoor functions as their foundation to extend the gap between an enthusiastic interceptor and sensitive information. This paper introduces an adaptive block encryption scheme. This system is based on product, exponent, and modulo operation on a finite field. At the heart of this algorithm lies an innovative and robust trapdoor function that operates in the Galois Field and is responsible for the superior speed and security offered by it. Prime number theorem plays a fundamental role in this system, to keep unwelcome adversaries at bay. This is a …

Quantum Grover's Oracles With Symmetry Boolean Functions, Peng Gao

Dissertations and Theses

Quantum computing has become an important research field of computer science and engineering. Among many quantum algorithms, Grover's algorithm is one of the most famous ones. Designing an effective quantum oracle poses a challenging conundrum in circuit and system-level design for practical application realization of Grover's algorithm.

In this dissertation, we present a new method to build quantum oracles for Grover's algorithm to solve graph theory problems. We explore generalized Boolean symmetric functions with lattice diagrams to develop a low quantum cost and area efficient quantum oracle. We study two graph theory problems: cycle detection of undirected graphs and generalized …

Ensemble Data Fitting For Bathymetric Models Informed By Nominal Data, Samantha Zambo

Dissertations

Due to the difficulty and expense of collecting bathymetric data, modeling is the primary tool to produce detailed maps of the ocean floor. Current modeling practices typically utilize only one interpolator; the industry standard is splines-in-tension.

In this dissertation we introduce a new nominal-informed ensemble interpolator designed to improve modeling accuracy in regions of sparse data. The method is guided by a priori domain knowledge provided by artificially intelligent classifiers. We recast such geomorphological classifications, such as ‘seamount’ or ‘ridge’, as nominal data which we utilize as foundational shapes in an expanded ordinary least squares regression-based algorithm. To our knowledge …

Multilateration Index., Chip Lynch

Electronic Theses and Dissertations

We present an alternative method for pre-processing and storing point data, particularly for Geospatial points, by storing multilateration distances to fixed points rather than coordinates such as Latitude and Longitude. We explore the use of this data to improve query performance for some distance related queries such as nearest neighbor and query-within-radius (i.e. “find all points in a set P within distance d of query point q”). Further, we discuss the problem of “Network Adequacy” common to medical and communications businesses, to analyze questions such as “are at least 90% of patients living within 50 miles of a covered emergency …

Desktop Application For The Puzzle Board Game “Rush Hour”, Huanqing Nong

Electronic Theses, Projects, and Dissertations

Rush Hour is a sliding block puzzle board game. This game comes with a board of 6 x 6 grid simulating a parking lot with an exit at the right end of the third row and some vehicle models of size 1 x 2 or 1 x 3 which can slide along the grooves of the grid forward or backward. The goal of the game is to clear the path by moving the vehicles on the board in a certain way for the target car, which lies on the third row of the grid, to merge out the “parking lot” …

Neural Regret-Matching For Distributed Constraint Optimization Problems, Yanchen Deng, Runshen Yu, Xinrun Wang, Bo An

Research Collection School Of Computing and Information Systems

Distributed constraint optimization problems (DCOPs) are a powerful model for multi-agent coordination and optimization, where information and controls are distributed among multiple agents by nature. Sampling-based algorithms are important incomplete techniques for solving medium-scale DCOPs. However, they use tables to exactly store all the information (e.g., costs, confidence bounds) to facilitate sampling, which limits their scalability. This paper tackles the limitation by incorporating deep neural networks in solving DCOPs for the first time and presents a neural-based sampling scheme built upon regret-matching. In the algorithm, each agent trains a neural network to approximate the regret related to its local problem …

Boundary Detection With Bert For Span-Level Emotion Cause Analysis, Xiangju Li, Wei Gao, Shi Feng, Yifei Zhang, Daling Wang

Research Collection School Of Computing and Information Systems

Emotion cause analysis (ECA) has been anemerging topic in natural language processing,which aims to identify the reasons behind acertain emotion expressed in the text. MostECA methods intend to identify the clausewhich contains the cause of a given emotion,but such clause-level ECA (CECA) can be ambiguous and imprecise. In this paper, we aimat span-level ECA (SECA) by detecting theprecise boundaries of text spans conveying accurate emotion causes from the given context.We formulate this task as sequence labelingand position identification problems and design two neural methods to solve them. Experiments on two benchmark ECA datasets showthat the proposed methods substantially outperform the …

Bidding Mechanisms In Graph Games, Guy Avni, Thomas A. Henzinger, Dorde Zikelic

Research Collection School Of Computing and Information Systems

A graph game proceeds as follows: two players move a token through a graph to produce a finite or infinite path, which determines the payoff of the game. We study bidding games in which in each turn, an auction determines which player moves the token. Bidding games were largely studied in combination with two variants of first-price auctions called “Richman” and “poorman” bidding. We study taxman bidding, which span the spectrum between the two. The game is parameterized by a constant τ∈[0,1]: portion τ of the winning bid is paid to the other player, and portion 1−τ to the bank. …

Cfr-Mix: Solving Imperfect Information Extensive-Form Games With Combinatorial Action Space, Shuxin Li, Youzhi Zhang, Xinrun Wang, Wanqi Xue, Bo An

Research Collection School Of Computing and Information Systems

In many real-world scenarios, a team of agents must coordinate with each other to compete against an opponent. The challenge of solving this type of game is that the team's joint action space grows exponentially with the number of agents, which results in the inefficiency of the existing algorithms, e.g., Counterfactual Regret Minimization (CFR). To address this problem, we propose a new framework of CFR: CFR-MIX. Firstly, we propose a new strategy representation that represents a joint action strategy using individual strategies of all agents and a consistency relationship to maintain the cooperation between agents. To compute the equilibrium with …

Solving Large-Scale Extensive-Form Network Security Games Via Neural Fictitious Self-Play, Wanqi Xue, Youzhi Zhang, Shuxin Li, Xinrun Wang, Bo An, Chai Kiat Yeo

Research Collection School Of Computing and Information Systems

Securing networked infrastructures is important in the real world. The problem of deploying security resources to protect against an attacker in networked domains can be modeled as Network Security Games (NSGs). Unfortunately, existing approaches, including the deep learning-based approaches, are inefficient to solve large-scale extensive-form NSGs. In this paper, we propose a novel learning paradigm, NSG-NFSP, to solve large-scale extensive-form NSGs based on Neural Fictitious Self-Play (NFSP). Our main contributions include: i) reforming the best response (BR) policy network in NFSP to be a mapping from action-state pair to action-value, to make the calculation of BR possible in NSGs; ii) …

Reproducibility Companion Paper: Knowledge Enhanced Neural Fashion Trend Forecasting, Yunshan Ma, Yujuan Ding, Xun Yang, Lizi Liao, Wai Keung Wong, Tat-Seng Chua, Jinyoung Moon, Hong-Han Shuai

Research Collection School Of Computing and Information Systems

This companion paper supports the replication of the fashion trend forecasting experiments with the KERN (Knowledge Enhanced Recurrent Network) method that we presented in the ICMR 2020. We provide an artifact that allows the replication of the experiments using a Python implementation. The artifact is easy to deploy with simple installation, training and evaluation. We reproduce the experiments conducted in the original paper and obtain similar performance as previously reported. The replication results of the experiments support the main claims in the original paper.