Open Access. Powered by Scholars. Published by Universities.®

Theory and Algorithms Commons

Open Access. Powered by Scholars. Published by Universities.®

1,570 Full-Text Articles 2,199 Authors 340,189 Downloads 127 Institutions

All Articles in Theory and Algorithms

Faceted Search

1,570 full-text articles. Page 1 of 58.

A Near-Optimal Change-Detection Based Algorithm For Piecewise-Stationary Combinatorial Semi-Bandits, Huozhi ZHOU, Lingda WANG, Lav N. VARSHNEY, Ee Peng LIM 2020 Singapore Management University

A Near-Optimal Change-Detection Based Algorithm For Piecewise-Stationary Combinatorial Semi-Bandits, Huozhi Zhou, Lingda Wang, Lav N. Varshney, Ee Peng Lim

Research Collection School Of Information Systems

We investigate the piecewise-stationary combinatorial semi-bandit problem. Compared to the original combinatorial semi-bandit problem, our setting assumes the reward distributions of base arms may change in a piecewise-stationary manner at unknown time steps. We propose an algorithm, GLR-CUCB, which incorporates an efficient combinatorial semi-bandit algorithm, CUCB, with an almost parameter-free change-point detector, the Generalized Likelihood Ratio Test (GLRT). Our analysis shows that the regret of GLR-CUCB is upper bounded by O(√NKT logT), where N is the number of piecewise-stationary segments, K is the number of base arms, and T is the number of time steps. As a complement, we ...


Unclonable Secret Keys, Marios Georgiou 2020 The Graduate Center, City University of New York

Unclonable Secret Keys, Marios Georgiou

Dissertations, Theses, and Capstone Projects

We propose a novel concept of securing cryptographic keys which we call “Unclonable Secret Keys,” where any cryptographic object is modified so that its secret key is an unclonable quantum bit-string whereas all other parameters such as messages, public keys, ciphertexts, signatures, etc., remain classical. We study this model in the authentication and encryption setting giving a plethora of definitions and positive results as well as several applications that are impossible in a purely classical setting.

In the authentication setting, we define the notion of one-shot signatures, a fundamental element in building unclonable keys, where the signing key not only ...


An Effective Method For Attribute Subset Selection, Considering The Resource In Pattern Recognition, Bakhtiyorjon Bakirovich Akbaraliev 2020 Tashkent University of Information Technologies named after Muhammad al-Khwarizimi Address: Amir Temur st., 1002000, Tashkent city, Republic of Uzbekistan E-mail:b.akbaraliev@gmail.com; b.akbaraliev@tuit.uz, Phone:+998-93-376-54-00.

An Effective Method For Attribute Subset Selection, Considering The Resource In Pattern Recognition, Bakhtiyorjon Bakirovich Akbaraliev

Chemical Technology, Control and Management

An analytical method for determining informative sets of features (INP) is developed, taking into account the resource for criteria based on the use of a measure of dispersion of classified objects. The areas of existence of the solution are defined. The statements and properties for the Fischer-type information criterion are proved, using which the proposed analytical method for determining the INP guarantees optimal results in the sense of maximizing the selected functional. The appropriateness of choosing this type of informative criterion is justified. A method for transforming attributes is proposed. The universality of the method in relation to the type ...


Fast Streaming K-Means Clustering With Coreset Caching, Yu Zhang, Kanat Tangwongsan, Srikanta Tirthapura 2020 Iowa State University

Fast Streaming K-Means Clustering With Coreset Caching, Yu Zhang, Kanat Tangwongsan, Srikanta Tirthapura

Electrical and Computer Engineering Publications

We present new algorithms for k-means clustering on a data stream with a focus on providing fast responses to clustering queries. Compared to the state-of-the-art, our algorithms provide substantial improvements in the query time for cluster centers while retaining the desirable properties of provably small approximation error and low space usage. Our proposed clustering algorithms systematically reuse the "coresets" (summaries of data) computed for recent queries in answering the current clustering query, a novel technique which we refer to as coreset caching. We also present an algorithm called OnlineCC that integrates the coreset caching idea with a simple sequential streaming ...


Investigating Single Precision Floating General Matrix Multiply In Heterogeneous Hardware, Steven Harris 2020 Washington University in St. Louis

Investigating Single Precision Floating General Matrix Multiply In Heterogeneous Hardware, Steven Harris

Engineering and Applied Science Theses & Dissertations

The fundamental operation of matrix multiplication is ubiquitous across a myriad of disciplines. Yet, the identification of new optimizations for matrix multiplication remains relevant for emerging hardware architectures and heterogeneous systems. Frameworks such as OpenCL enable computation orchestration on existing systems, and its availability using the Intel High Level Synthesis compiler allows users to architect new designs for reconfigurable hardware using C/C++. Using the HARPv2 as a vehicle for exploration, we investigate the utility of several of the most notable matrix multiplication optimizations to better understand the performance portability of OpenCL and the implications for such optimizations on this ...


Querying Recurrent Convoys Over Trajectory Data, Munkh-Erdene YADAMJAV, Zhifeng BAO, Baihua ZHENG, Farhana M. CHOUDHURY, Hanan SAMET 2020 Singapore Management University

Querying Recurrent Convoys Over Trajectory Data, Munkh-Erdene Yadamjav, Zhifeng Bao, Baihua Zheng, Farhana M. Choudhury, Hanan Samet

Research Collection School Of Information Systems

Moving objects equipped with location-positioning devices continuously generate a large amount of spatio-temporal trajectory data. An interesting finding over a trajectory stream is a group of objects that are travelling together for a certain period of time. Existing studies on mining co-moving objects do not consider an important correlation between co-moving objects, which is the reoccurrence of the movement pattern. In this study, we define a problem of finding recurrent pattern of co-moving objects from streaming trajectories and propose an efficient solution that enables us to discover recent co-moving object patterns repeated within a given time period. Experimental results on ...


An Exact Algorithm For Agile Earth Observation Satellite Scheduling With Time-Dependent Profits, Guansheng PENG, Guopeng SONG, Lining XING, Aldy GUNAWAN, Pieter VANSTEENWEGEN 2020 Singapore Management University

An Exact Algorithm For Agile Earth Observation Satellite Scheduling With Time-Dependent Profits, Guansheng Peng, Guopeng Song, Lining Xing, Aldy Gunawan, Pieter Vansteenwegen

Research Collection School Of Information Systems

The scheduling of an Agile Earth Observation Satellite (AEOS) consists of selecting and scheduling a subset of possible targets for observation in order to maximize the collected profit related to the images while satisfying its operational constraints. In this problem, a set of candidate targets for observation is given, each with a time-dependent profit and a visible time window. The exact profit of a target depends on the start time of its observation, reaching its maximum at the midpoint of its visible time window. This time dependency stems from the fact that the image quality is determined by the look ...


Adaptive Task Sampling For Meta-Learning, Chenghao LIU, Zhihao WANG, Doyen SAHOO, Yuan FANG, Kun ZHANG, Steven C. H. HOI 2020 Singapore Management University

Adaptive Task Sampling For Meta-Learning, Chenghao Liu, Zhihao Wang, Doyen Sahoo, Yuan Fang, Kun Zhang, Steven C. H. Hoi

Research Collection School Of Information Systems

Meta-learning methods have been extensively studied and applied in computer vision, especially for few-shot classification tasks. The key idea of meta-learning for few-shot classification is to mimic the few-shot situations faced at test time by randomly sampling classes in meta-training data to construct fewshot tasks for episodic training. While a rich line of work focuses solely on how to extract meta-knowledge across tasks, we exploit the complementary problem on how to generate informative tasks. We argue that the randomly sampled tasks could be sub-optimal and uninformative (e.g., the task of classifying “dog” from “laptop” is often trivial) to the ...


Mapping The Modern History Of The Philosophy Of Religion With Machine Learning, Jackson C. Foster 2020 The University of Alabama

Mapping The Modern History Of The Philosophy Of Religion With Machine Learning, Jackson C. Foster

The Macksey Journal

A current debate in the philosophy of religion (PoR) is about future routes for scholarship. While many scholars have assessed where the subfield could expand, few have consulted the discipline’s modern history in their evaluations. Thus the aim of “Mapping the Modern History of the Philosophy of Religion” is to propose a computationally-based history of PoR as a foundation for future growth. To that end, this research processes over three-thousand articles from three journals in PoR with latent Dirichlet allocation (LDA), a machine-learning algorithm. LDA creates groups of related terms, exhibiting the most historically significant topics in the philosophy ...


Atmospheric Contrail Detection With A Deep Learning Algorithm, Nasir Siddiqui 2020 University of Minnesota Morris Digital Well

Atmospheric Contrail Detection With A Deep Learning Algorithm, Nasir Siddiqui

Scholarly Horizons: University of Minnesota, Morris Undergraduate Journal

Aircraft contrail emission is widely believed to be a contributing factor to global climate change. We have used machine learning techniques on images containing contrails in hopes of being able to identify those which contain contrails and those that do not. The developed algorithm processes data on contrail characteristics as captured by long-term image records. Images collected by the United States Department of Energy’s Atmospheric Radiation Management user facility(ARM) were used to train a deep convolutional neural network for the purpose of this contrail classification. The neural network model was trained with 1600 images taken by the Total ...


Lulling Waters: A Poetry Reading For Real-Time Music Generation Through Emotion Mapping, Ashley Muniz, Toshihisa Tsuruoka 2020 New York University

Lulling Waters: A Poetry Reading For Real-Time Music Generation Through Emotion Mapping, Ashley Muniz, Toshihisa Tsuruoka

Electronic Literature Organization Conference 2020

Through a poetic narrative, “Lulling Waters” tells the story of a whale overcoming the loss of his mother, who passed away from ingesting plastic, as he attempts to escape from the polluted oceanic world. The live performance of this poem utilizes a software system called Soundwriter, which was developed with the goal of enriching the oral storytelling experience through music. This video demonstrates how Soundwriter’s real-time hybrid system was able to analyze “Lulling Waters” through its lexical and auditory features. Emotionally salient words were given ratings based on arousal, valence, and dominance while the emotionally charged prosodic features of ...


Probabilistic Value Selection For Space Efficient Model, Gunarto Sindoro NGOO, Baihua ZHENG, Kuo-Wei HSU, Wen-Chih PENG 2020 Singapore Management University

Probabilistic Value Selection For Space Efficient Model, Gunarto Sindoro Ngoo, Baihua Zheng, Kuo-Wei Hsu, Wen-Chih Peng

Research Collection School Of Information Systems

An alternative to current mainstream preprocessing methods is proposed: Value Selection (VS). Unlike the existing methods such as feature selection that removes features and instance selection that eliminates instances, value selection eliminates the values (with respect to each feature) in the dataset with two purposes: reducing the model size and preserving its accuracy. Two probabilistic methods based on information theory's metric are proposed: PVS and P + VS. Extensive experiments on the benchmark datasets with various sizes are elaborated. Those results are compared with the existing preprocessing methods such as feature selection, feature transformation, and instance selection methods. Experiment results ...


Query Graph Generation For Answering Multi-Hop Complex Questions From Knowledge Bases, Yunshi LAN, Jing JIANG 2020 Singapore Management University

Query Graph Generation For Answering Multi-Hop Complex Questions From Knowledge Bases, Yunshi Lan, Jing Jiang

Research Collection School Of Information Systems

Previous work on answering complex questions from knowledge bases usually separately addresses two types of complexity: questions with constraints and questions with multiple hops of relations. In this paper, we handle both types of complexity at the same time. Motivated by the observation that early incorporation of constraints into query graphs can more effectively prune the search space, we propose a modified staged query graph generation method with more flexible ways to generate query graphs. Our experiments clearly show that our method achieves the state of the art on three benchmark KBQA datasets.


Improving Multimodal Named Entity Recognition Via Entity Span Detection With Unified Multimodal Transformer, Jianfei YU, Jing JIANG, Li YANG, Rui XIA 2020 Singapore Management University

Improving Multimodal Named Entity Recognition Via Entity Span Detection With Unified Multimodal Transformer, Jianfei Yu, Jing Jiang, Li Yang, Rui Xia

Research Collection School Of Information Systems

In this paper, we study Multimodal Named Entity Recognition (MNER) for social media posts. Existing approaches for MNER mainly suffer from two drawbacks: (1) despite generating word-aware visual representations, their word representations are insensitive to the visual context; (2) most of them ignore the bias brought by the visual context. To tackle the first issue, we propose a multimodal interaction module to obtain both image-aware word representations and word-aware visual representations. To alleviate the visual bias, we further propose to leverage purely text-based entity span detection as an auxiliary module, and design a Unified Multimodal Transformer to guide the final ...


Translating Counting Problems Into Computable Language Expressions, Zach Prescott 2020 University of Missouri-St. Louis

Translating Counting Problems Into Computable Language Expressions, Zach Prescott

Theses

The realm of automated problem solving is a relatively new field, even in the context of natural language processing. One area where this is often demonstrated is that of creating a program that can solve word problems. The program must understand the problem, perform some processing, and then convey this information to a user in a way that is accessible and understandable. There has been quite a lot of progress in this area with simpler problems. However, when it comes to understanding problems that involve a level of NLP, the results are not conclusive. In this paper, we would like ...


Assessing Evidence Relevance By Disallowing Assessment, John Licato, Michael Cooper 2020 University of South Florida

Assessing Evidence Relevance By Disallowing Assessment, John Licato, Michael Cooper

OSSA Conference Archive

Guidelines for assessing whether potential evidence is relevant to some argument tend to rely on criteria that are subject to well-known biasing effects. We describe a framework for argumentation that does not allow participants to directly decide whether evidence is potentially relevant to an argument---instead, evidence must prove its relevance through demonstration. This framework, called WG-A, is designed to translate into a dialogical game playable by minimally trained participants.


Towards Distributed Node Similarity Search On Graphs, Tianming ZHANG, Yunjun GAO, Baihua ZHENG, Lu CHEN, Shiting WEN, Wei GUO 2020 Singapore Management University

Towards Distributed Node Similarity Search On Graphs, Tianming Zhang, Yunjun Gao, Baihua Zheng, Lu Chen, Shiting Wen, Wei Guo

Research Collection School Of Information Systems

Node similarity search on graphs has wide applications in recommendation, link prediction, to name just a few. However, existing studies are insufficient due to two reasons: (i) the scale of the real-world graph is growing rapidly, and (ii) vertices are always associated with complex attributes. In this paper, we propose an efficiently distributed framework to support node similarity search on massive graphs, which considers both graph structure correlation and node attribute similarity in metric spaces. The framework consists of preprocessing stage and query stage. In the preprocessing stage, a parallel KD-tree construction (KDC) algorithm is developed to form a newly ...


Design And Implementation Of A Deterministic And Nondeterministic Finite Automaton Simulator, Camron C. Dennler 2020 California Polytechnic State University, San Luis Obispo

Design And Implementation Of A Deterministic And Nondeterministic Finite Automaton Simulator, Camron C. Dennler

Computer Science and Software Engineering

The purpose of this project is to assist students in visualizing and understanding the structure and operation of deterministic and nondeterministic finite automata. This software achieves this purpose by providing students with the ability to build, modify, and test automata in an intuitive environment. This enables a simple and efficient avenue for experimentation, which upholds the Cal Poly ideal of Learning by Doing.

Readers of this report should be familiar with basic concepts in the theory of finite state machines; a general understanding of object-oriented programming is also necessary.


Quantum Random Walk Search And Grover's Algorithm - An Introduction And Neutral-Atom Approach, Anna Maria Houk 2020 California Polytechnic State University, San Luis Obispo

Quantum Random Walk Search And Grover's Algorithm - An Introduction And Neutral-Atom Approach, Anna Maria Houk

Physics

In the sub-field of quantum algorithms, physicists and computer scientist take classical computing algorithms and principles and see if there is a more efficient or faster approach implementable on a quantum computer, i.e. a ”quantum advantage”. We take random walks, a widely applicable group of classical algorithms, and move them into the quantum computing paradigm. Additionally, an introduction to a popular quantum search algorithm called Grover’s search is included to guide the reader to the development of a quantum search algorithm using quantum random walks. To close the gap between algorithm and hardware, we will look at using ...


Evaluating Driving Performance Of A Novel Behavior Planning Model On Connected Autonomous Vehicles, Keyur Shah 2020 University of Connecticut

Evaluating Driving Performance Of A Novel Behavior Planning Model On Connected Autonomous Vehicles, Keyur Shah

Honors Scholar Theses

Many current algorithms and approaches in autonomous driving attempt to solve the "trajectory generation" or "trajectory following” problems: given a target behavior (e.g. stay in the current lane at the speed limit or change lane), what trajectory should the vehicle follow, and what inputs should the driving agent apply to the throttle and brake to achieve this trajectory? In this work, we instead focus on the “behavior planning” problem—specifically, should an autonomous vehicle change lane or keep lane given the current state of the system?

In addition, current theory mainly focuses on single-vehicle systems, where vehicles do not ...


Digital Commons powered by bepress