Theory and Algorithms Commons^™

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 …

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 …

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 …

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 …

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

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 …

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

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 …

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

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 …

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.

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 …

Computational Studies Of Carbon Nanocluster Solidification, Chathuri C. Silva

Dissertations

A subset of micron-size meteoritic carbon particles formed in red giant atmospheres show a core-rim structure, likely condensed from a vapor phase into super-cooled carbon droplets that nucleated graphene sheets (~40Å) on randomly oriented 5-atom loops during solidification, followed by coating with a graphite rim. Similar particles form during slow cooling of carbon vapor in the lab.

Here we investigate the nucleation and growth of carbon rings and graphene sheets using density functional theory (DFT). Our objectives: (1). explore different computational techniques in DFT-VASP for various carbon structures and compare the results with literature, (2). investigate the nucleation and growth …

On Communication For Distributed Babai Point Computation, Maiara F. Bollauf, Vinay A. Vaishampayan, Sueli I.R. Costa

Publications and Research

We present a communication-efficient distributed protocol for computing the Babai point, an approximate nearest point for a random vector X∈Rn in a given lattice. We show that the protocol is optimal in the sense that it minimizes the sum rate when the components of X are mutually independent. We then investigate the error probability, i.e. the probability that the Babai point does not coincide with the nearest lattice point, motivated by the fact that for some cases, a distributed algorithm for finding the Babai point is sufficient for finding the nearest lattice point itself. Two different probability models for X …

Representation Of Nonlinear Pseudo-Random Generators Using State-Space Equations, Raghad K. Salih

Emirates Journal for Engineering Research

The idea of research is a representation of the nonlinear pseudo-random generators using state-space equations that is not based on the usual description as shift register synthesis but in terms of matrices. Different types of nonlinear pseudo-random generators with their algorithms have been applied in order to investigate the output pseudo-random sequences. Moreover, two examples are given for conciliated the results of this representation.

Decoding Clinical Biomarker Space Of Covid-19: Exploring Matrix Factorization-Based Feature Selection Methods, Farshad Saberi-Movahed, Mahyar Mohammadifard, Adel Mehrpooya, Mohammad Rezaei-Ravari, Kamal Berahmand, Mehrdad Rostami, Saeed Karami, Mohammad Najafzadeh, Davood Hajinezhad, Mina Jamshidi, Farshid Abedi, Mahtab Mohammadifard, Elnaz Farbod, Farinaz Safavi, Mohammadreza Dorvash, Shahrzad Vahedi, Mahdi Eftekhari, Farid Saberi-Movahed, Iman Tavassoly

Publications and Research

One of the most critical challenges in managing complex diseases like COVID-19 is to establish an intelligent triage system that can optimize the clinical decision-making at the time of a global pandemic. The clinical presentation and patients’ characteristics are usually utilized to identify those patients who need more critical care. However, the clinical evidence shows an unmet need to determine more accurate and optimal clinical biomarkers to triage patients under a condition like the COVID-19 crisis. Here we have presented a machine learning approach to find a group of clinical indicators from the blood tests of a set of COVID-19 …

On The Use Of Minimum Penalties In Statistical Learning, Ben Sherwood, Bradley S. Price

Faculty & Staff Scholarship

Modern multivariate machine learning and statistical methodologies estimate parameters of interest while leveraging prior knowledge of the association between outcome variables. The methods that do allow for estimation of relationships do so typically through an error covariance matrix in multivariate regression which does not scale to other types of models. In this article we proposed the MinPEN framework to simultaneously estimate regression coefficients associated with the multivariate regression model and the relationships between outcome variables using mild assumptions. The MinPen framework utilizes a novel penalty based on the minimum function to exploit detected relationships between responses. An iterative algorithm that …

Design And Development Of Techniques To Ensure Integrity In Fog Computing Based Databases, Abdulwahab Fahad S. Alazeb

Graduate Theses and Dissertations

The advancement of information technology in coming years will bring significant changes to the way sensitive data is processed. But the volume of generated data is rapidly growing worldwide. Technologies such as cloud computing, fog computing, and the Internet of things (IoT) will offer business service providers and consumers opportunities to obtain effective and efficient services as well as enhance their experiences and services; increased availability and higher-quality services via real-time data processing augment the potential for technology to add value to everyday experiences. This improves human life quality and easiness. As promising as these technological innovations, they are prone …

Electricity Market Operations With Massive Renewable Integration: New Designs, Shengfei Yin

Electrical Engineering Theses and Dissertations

Electricity market has been transitioning from a conventional and deterministic operation to a stochastic operation under the increasing penetration of renewable energy. Industry-level solutions toward the future electricity market operation ask for both accuracy and efficiency while maintaining model interpretability. Hence, reliable stochastic optimization techniques come to the first place for such a complex and dynamic problem.

This work starts at proposing a solution strategy for the uncertainty-based power system planning problem, which acts as a preliminary and instructs the electricity market operation. Considering 100% renewable penetration in the future, it analyzes the cost-effectiveness of renewable energy from a long-term …

Mmconv: An Environment For Multimodal Conversational Search Across Multiple Domains, Lizi Liao, Le Hong Long, Zheng Zhang, Minlie Huang, Tat-Seng Chua

Research Collection School Of Computing and Information Systems

Although conversational search has become a hot topic in both dialogue research and IR community, the real breakthrough has been limited by the scale and quality of datasets available. To address this fundamental obstacle, we introduce the Multimodal Multi-domain Conversational dataset (MMConv), a fully annotated collection of human-to-human role-playing dialogues spanning over multiple domains and tasks. The contribution is two-fold. First, beyond the task-oriented multimodal dialogues among user and agent pairs, dialogues are fully annotated with dialogue belief states and dialogue acts. More importantly, we create a relatively comprehensive environment for conducting multimodal conversational search with real user settings, structured …

Promoting Diversity In Academic Research Communities Through Multivariate Expert Recommendation, Omar Salman

Graduate Theses and Dissertations

Expert recommendation is the process of identifying individuals who have the appropriate knowledge and skills to achieve a specific task. It has been widely used in the educational environment mainly in the hiring process, paper-reviewer assignment, and assembling conference program committees. In this research, we highlight the problem of diversity and fair representation of underrepresented groups in expertise recommendation, factors that current expertise recommendation systems rarely consider. We introduce a novel way to model experts in academia by considering demographic attributes in addition to skills. We use the h-index score to quantify skills for a researcher and we identify five …

An Adaptive Large Neighborhood Search For The Green Mixed Fleet Vehicle Routing Problem With Realistic Energy Consumption And Partial Recharges, Vincent F. Yu, Panca Jodiawan, Aldy Gunawan

Research Collection School Of Computing and Information Systems

This study addresses a variant of the Electric Vehicle Routing Problem with Mixed Fleet, named as the Green Mixed Fleet Vehicle Routing Problem with Realistic Energy Consumption and Partial Recharges. This problem contains three important characteristics — realistic energy consumption, partial recharging policy, and carbon emissions. An adaptive Large Neighborhood Search heuristic is developed for the problem. Experimental results show that the proposed ALNS finds optimal solutions for most small-scale benchmark instances in a significantly faster computational time compared to the performance of CPLEX solver. Moreover, it obtains high quality solutions for all medium- and large-scale instances under a reasonable …

The Multi-Vehicle Cycle Inventory Routing Problem: Formulation And A Metaheuristic Approach, Vincent F. Yu, Audrey Tedja Widjaja, Aldy Gunawan, Pieter Vansteenwegen

Research Collection School Of Computing and Information Systems

This paper presents a new variant of the Multi-Vehicle Cyclic Inventory Routing Problem (MV-CIRP) which aims to determine a subset of customers to be visited, the appropriate number of vehicles used, and the corresponding cycle time and route sequence, such that the total cost (e.g. transportation, inventory, and rewards) is minimized. The MV-CIRP is formulated as a mixed-integer nonlinear programming model. We propose a Simulated Annealing (SA) based algorithm to solve the problem. SA is first tested on the available benchmark Single-Vehicle CIRP (SV-CIRP) instances and compared to the state-of-the-art algorithms. SA is then tested on the benchmark MV-CIRP instances …

Task Similarity Aware Meta Learning: Theory-Inspired Improvement On Maml, Pan Zhou, Yingtian Zpu, Xiaotong Yuan, Jiashi Feng, Caiming Xiong, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

Few-shot learning ability is heavily desired for machine intelligence. By meta-learning a model initialization from training tasks with fast adaptation ability to new tasks, model-agnostic meta-learning (MAML) has achieved remarkable success in a number of few-shot learning applications. However, theoretical understandings on the learning ability of MAML remain absent yet, hindering developing new and more advanced meta learning methods in a principled way. In this work, we solve this problem by theoretically justifying the fast adaptation capability of MAML when applied to new tasks. Specifically, we prove that the learnt meta-initialization can benefit the fast adaptation to new tasks with …

An Efficient Transformer-Based Model For Vietnamese Punctuation Prediction, Hieu Tran, Cuong V. Dinh, Hong Quang Pham, Binh T. Nguyen

Research Collection School Of Computing and Information Systems

In both formal and informal texts, missing punctuation marks make the texts confusing and challenging to read. This paper aims to conduct exhaustive experiments to investigate the benefits of the pre-trained Transformer-based models on two Vietnamese punctuation datasets. The experimental results show our models can achieve encouraging results, and adding Bi-LSTM or/and CRF layers on top of the proposed models can also boost model performance. Finally, our best model can significantly bypass state-of-the-art approaches on both the novel and news datasets for the Vietnamese language. It can gain the corresponding performance up to 21.45%21.45% and 18.27%18.27% in the overall F1-scores.