Theory and Algorithms Commons^™

Target Detection Using Convolutional Neural Networks, Robert P. Loibl

Theses and Dissertations

This research explores the use of Convolutional Neural Networks (CNNs) to classify targets of interest within satellite imagery. Methods were specifically devised for the classification of airports within Landsat-8 scenes. A novel automated dataset generation technique was developed to create labeled datasets from satellite imagery using only coordinate metadata. Using this approach a very large dataset of over 132,000 labeled images was created without human input. This dataset was used to evaluate the effects of color and resolution on airport classification accuracy. Two experiments were run with the first experiment classifying large airports with 96.8% accuracy, and the second classifying …

Cross-Language Learning For Program Classification Using Bilateral Tree-Based Convolutional Neural Networks, Duy Quoc Nghi Bui, Lingxiao Jiang, Yijun Yu

Research Collection School Of Computing and Information Systems

Towards the vision of translating code that implements an algorithm from one programming language into another, this paper proposes an approach for automated program classification using bilateral tree-based convolutional neural networks (BiTBCNNs). It is layered on top of two tree-based convolutional neural networks (TBCNNs), each of which recognizes the algorithm of code written in an individual programming language. The combination layer of the networks recognizes the similarities and differences among code in different programming languages. The BiTBCNNs are trained using the source code in different languages but known to implement the same algorithms and/or functionalities. For a preliminary evaluation, we …

Sparse Passive-Aggressive Learning For Bounded Online Kernel Methods, Jing Lu, Doyen Sahoo, Peilin Zhao, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

One critical deficiency of traditional online kernel learning methods is their unbounded and growing number of support vectors in the online learning process, making them inefficient and non-scalable for large-scale applications. Recent studies on scalable online kernel learning have attempted to overcome this shortcoming, e.g., by imposing a constant budget on the number of support vectors. Although they attempt to bound the number of support vectors at each online learning iteration, most of them fail to bound the number of support vectors for the final output hypothesis, which is often obtained by averaging the series of hypotheses over all the …

R3: Reinforced Ranker-Reader For Open-Domain Question Answering, Shuohang Wang, Mo Yu, Xiaoxiao Guo, Zhiguo Wang, Tim Klinger, Wei Zhang, Shiyu Chang, Gerald Tesauro, Bowen Zhou, Jing Jiang

Research Collection School Of Computing and Information Systems

In recent years researchers have achieved considerable success applying neural network methods to question answering (QA). These approaches have achieved state of the art results in simplified closed-domain settings such as the SQuAD (Rajpurkar et al. 2016) dataset, which provides a pre-selected passage, from which the answer to a given question may be extracted. More recently, researchers have begun to tackle open-domain QA, in which the model is given a question and access to a large corpus (e.g., wikipedia) instead of a pre-selected passage (Chen et al. 2017a). This setting is more complex as it requires large-scale search for relevant …

Gradient Estimation For Attractor Networks, Thomas Flynn

Dissertations, Theses, and Capstone Projects

It has been hypothesized that neural network models with cyclic connectivity may be more powerful than their feed-forward counterparts. This thesis investigates this hypothesis in several ways. We study the gradient estimation and optimization procedures for several variants of these networks. We show how the convergence of the gradient estimation procedures are related to the properties of the networks. Then we consider how to tune the relative rates of gradient estimation and parameter adaptation to ensure successful optimization in these models. We also derive new gradient estimators for stochastic models. First, we port the forward sensitivity analysis method to the …

Cryptosystems Using Subgroup Distortion, Indira Chatterji, Delaram Kahrobaei, Ni Yen Lu

Publications and Research

In this paper we propose cryptosystems based on subgroup distortion in hyperbolic groups. We also include concrete examples of hyperbolic groups as possible platforms.

Relating Justification Logic Modality And Type Theory In Curry–Howard Fashion, Konstantinos Pouliasis

Dissertations, Theses, and Capstone Projects

This dissertation is a work in the intersection of Justification Logic and Curry--Howard Isomorphism. Justification logic is an umbrella of modal logics of knowledge with explicit evidence. Justification logics have been used to tackle traditional problems in proof theory (in relation to Godel's provability) and philosophy (Gettier examples, Russel's barn paradox). The Curry--Howard Isomorphism or proofs-as-programs is an understanding of logic that places logical studies in conjunction with type theory and -- in current developments -- category theory. The point being that understanding a system as a logic, a typed calculus and, a language of a class of categories constitutes …

Two Birds With One Stone: Classifying Positive And Unlabeled Examples On Uncertain Data Streams, Donghong Han, Shuoru Li, Fulin Wei, Yuying Tang, Feida Zhu, Guoren Wang

Research Collection School Of Computing and Information Systems

An important feature characteristic of the data streams in many of today's big data applications is the intrinsic uncertainty, which could happen for both item occurrence and attribute value. While this has already posed great challenges for fundamental data mining tasks such as classification, things are made even more complicated by the fact that completely-labeled examples are usually unavailable in such settings, leaving researchers the only option to learn classifiers on partially-labeled examples on uncertain data streams. Furthermore, there will be concept drift on evolving data streams. To address these challenges, this paper therefore focuses on the study of learning …

Models As Weapons: Review Of Weapons Of Math Destruction: How Big Data Increases Inequality And Threatens Democracy By Cathy O’Neil (2016), Samuel L. Tunstall

Numeracy

Cathy O’Neil. 2016. Weapons of Math Destruction: How Big Data Increases Inequality and Threatens Democracy (New York, NY: Crown) 272 pp. ISBN 978-0553418811.

Accessible to a wide readership, Cathy O’Neil’s Weapons of Math Destruction: How Big Data Increases Inequality and Threatens Democracy provides a lucid yet alarming account of the extensive reach of mathematical models in influencing all of our lives. With a particular eye towards social justice, O’Neil not only warns modelers to be cognizant of the effects of their work on real people—especially vulnerable groups who have less power to fight back—but also encourages laypersons to take initiative …

Efficient Randomized Algorithms For The Fixed Precision Low Rank Matrix Approximation, Wenjian Yu, Yu Gu, Yaohang Li

Computer Science Faculty Publications

Randomized algorithms for low-rank matrix approximation are investigated, with the emphasis on the fixed-precision problem and computational efficiency for handling large matrices. The algorithms are based on the so-called QB factorization, where Q is an orthonormal matrix. First, a mechanism for calculating the approximation error in the Frobenius norm is proposed, which enables efficient adaptive rank determination for a large and/or sparse matrix. It can be combined with any QB-form factorization algorithm in which B's rows are incrementally generated. Based on the blocked randQB algorithm by Martinsson and Voronin, this results in an algorithm called randQB_EI. Then, we further revise …

Big Networks: Analysis And Optimal Control, Hung The Nguyen

Theses and Dissertations

The study of networks has seen a tremendous breed of researches due to the explosive spectrum of practical problems that involve networks as the access point. Those problems widely range from detecting functionally correlated proteins in biology to finding people to give discounts and gain maximum popularity of a product in economics. Thus, understanding and further being able to manipulate/control the development and evolution of the networks become critical tasks for network scientists. Despite the vast research effort putting towards these studies, the present state-of-the-arts largely either lack of high quality solutions or require excessive amount of time in real-world …

Estimating The Respiratory Lung Motion Model Using Tensor Decomposition On Displacement Vector Field, Kingston Kang

Theses and Dissertations

Modern big data often emerge as tensors. Standard statistical methods are inadequate to deal with datasets of large volume, high dimensionality, and complex structure. Therefore, it is important to develop algorithms such as low-rank tensor decomposition for data compression, dimensionality reduction, and approximation.

With the advancement in technology, high-dimensional images are becoming ubiquitous in the medical field. In lung radiation therapy, the respiratory motion of the lung introduces variabilities during treatment as the tumor inside the lung is moving, which brings challenges to the precise delivery of radiation to the tumor. Several approaches to quantifying this uncertainty propose using a …

A Parallel Mesh Generator In 3d/4d, Kirill Voronin

Portland Institute for Computational Science Publications

In the report a parallel mesh generator in 3d/4d is presented. The mesh generator was developed as a part of the research project on space-time discretizations for partial differential equations in the least-squares setting. The generator is capable of constructing meshes for space-time cylinders built on an arbitrary 3d space mesh in parallel. The parallel implementation was created in the form of an extension of the finite element software MFEM. The code is publicly available in the Github repository

Glyph Based Segmentation Of Chinese Calligraphy Characters In The "Collected Characters" Stele., David A. Mcinnis

EWU Masters Thesis Collection

Text character segmentation is the process of detecting the bounding box position of individual characters within a written text document image. The character segmentation problem remains extremely difficult for ancient Chinese calligraphy documents. This paper examines a glyph-based segmentation technique for segmenting Chinese Calligraphy characters in the "Collected Characters". The glyph-based character segmentation pipeline utilizes a combination of well-understood image processing techniques in a novel pipeline which is able to detect Chinese calligraphy characters from ink-blots with a good reliability.

A Practical And Efficient Algorithm For The K-Mismatch Shortest Unique Substring Finding Problem, Daniel Robert Allen

EWU Masters Thesis Collection

This thesis revisits the k-mismatch shortest unique substring (SUS) finding problem and demonstrates that a technique recently presented in the context of solving the k-mismatch average common substring problem can be adapted and combined with parts of the existing solution, resulting in a new algorithm which has expected time complexity of O(n log^k n), while maintaining a practical space complexity at O(kn), where n is the string length. When k > 0, which is the hard case, the new proposal significantly improves the any-case O(n²) time complexity of the prior best method for k-mismatch SUS finding. Experimental study …

Algorithmic Issues In Some Disjoint Clustering Problems In Combinatorial Circuits, Zola Nailah Donovan

Graduate Theses, Dissertations, and Problem Reports (ETD)

As the modern integrated circuit continues to grow in complexity, the design of very large-scale integrated (VLSI) circuits involves massive teams employing state-of-the-art computer-aided design (CAD) tools. An old, yet significant CAD problem for VLSI circuits is physical design automation. In this problem, one needs to compute the best physical layout of millions to billions of circuit components on a tiny silicon surface. The process of mapping an electronic design to a chip involves several physical design stages, one of which is clustering. Even for combinatorial circuits, there exist several models for the clustering problem. In particular, we consider the …

Extensions Of The Morse-Hedlund Theorem, Eben Blaisdell

Honors Theses

Bi-infinite words are sequences of characters that are infinite forwards and backwards; for example "...ababababab...". The Morse-Hedlund theorem says that a bi-infinite word f repeats itself, in at most n letters, if and only if the number of distinct subwords of length n is at most n. Using the example, "...ababababab...", there are 2 subwords of length 3, namely "aba" and "bab". Since 2 is less than 3, we must have that "...ababababab..." repeats itself after at most 3 letters. In fact it does repeat itself every two letters. …

Bi-Objective Optimization Of Kidney Exchanges, Siyao Xu

Theses and Dissertations--Computer Science

Matching people to their preferences is an algorithmic topic with real world applications. One such application is the kidney exchange. The best "cure" for patients whose kidneys are failing is to replace it with a healthy one. Unfortunately, biological factors (e.g., blood type) constrain the number of possible replacements. Kidney exchanges seek to alleviate some of this pressure by allowing donors to give their kidney to a patient besides the one they most care about and in turn the donor for that patient gives her kidney to the patient that this first donor most cares about. Roth et al.~first discussed …

Ultra-Fast And Memory-Efficient Lookups For Cloud, Networked Systems, And Massive Data Management, Ye Yu

Theses and Dissertations--Computer Science

Systems that process big data (e.g., high-traffic networks and large-scale storage) prefer data structures and algorithms with small memory and fast processing speed. Efficient and fast algorithms play an essential role in system design, despite the improvement of hardware. This dissertation is organized around a novel algorithm called Othello Hashing. Othello Hashing supports ultra-fast and memory-efficient key-value lookup, and it fits the requirements of the core algorithms of many large-scale systems and big data applications. Using Othello hashing, combined with domain expertise in cloud, computer networks, big data, and bioinformatics, I developed the following applications that resolve several major …

Implementing Write Compression In Flash Memory Using Zeckendorf Two-Round Rewriting Codes, Vincent T. Druschke

Dissertations, Master's Theses and Master's Reports

Flash memory has become increasingly popular as the underlying storage technology for high-performance nonvolatile storage devices. However, while flash offers several benefits over alternative storage media, a number of limitations still exist within the current technology. One such limitation is that programming (altering a bit from its default value) and erasing (returning a bit to its default value) are asymmetric operations in flash memory devices: a flash memory can be programmed arbitrarily, but can only be erased in relatively large batches of storage bits called blocks, with block sizes ranging from 512K up to several megabytes. This creates a situation …

Logic -> Proof -> Rest, Maxwell Taylor

Senior Independent Study Theses

REST is a common architecture for networked applications. Applications that adhere to the REST constraints enjoy significant scaling advantages over other architectures. But REST is not a panacea for the task of building correct software. Algebraic models of computation, particularly CSP, prove useful to describe the composition of applications using REST. CSP enables us to describe and verify the behavior of RESTful systems. The descriptions of each component can be used independently to verify that a system behaves as expected. This thesis demonstrates and develops CSP methodology to verify the behavior of RESTful applications.

Applying Machine Learning To Advance Cyber Security: Network Based Intrusion Detection Systems, Hassan Hadi Latheeth Al-Maksousy

Computer Science Theses & Dissertations

Many new devices, such as phones and tablets as well as traditional computer systems, rely on wireless connections to the Internet and are susceptible to attacks. Two important types of attacks are the use of malware and exploiting Internet protocol vulnerabilities in devices and network systems. These attacks form a threat on many levels and therefore any approach to dealing with these nefarious attacks will take several methods to counter. In this research, we utilize machine learning to detect and classify malware, visualize, detect and classify worms, as well as detect deauthentication attacks, a form of Denial of Service (DoS). …

Fast Identification Of High Utility Itemsets From Candidates, Jun-Feng Qu, Mengchi Liu, Chunsheng Xin, Zhongbo Wu

Electrical & Computer Engineering Faculty Publications

High utility itemsets (HUIs) are sets of items with high utility, like profit, in a database. Efficient mining of high utility itemsets is an important problem in the data mining area. Many mining algorithms adopt a two-phase framework. They first generate a set of candidate itemsets by roughly overestimating the utilities of all itemsets in a database, and subsequently compute the exact utility of each candidate to identify HUIs. Therefore, the major costs in these algorithms come from candidate generation and utility computation. Previous works mainly focus on how to reduce the number of candidates, without dedicating much attention to …

An Iterated Local Search Algorithm For The Team Orienteering Problem With Variable Profits, Aldy Gunawan, Kien Ming Ng, Graham Kendall, Junhan Lai

Research Collection School Of Computing and Information Systems

The orienteering problem (OP) is a routing problem that has numerous applications in various domains such as logistics and tourism. The objective is to determine a subset of vertices to visit for a vehicle so that the total collected score is maximized and a given time budget is not exceeded. The extensive application of the OP has led to many different variants, including the team orienteering problem (TOP) and the team orienteering problem with time windows. The TOP extends the OP by considering multiple vehicles. In this article, the team orienteering problem with variable profits (TOPVP) is studied. The main …

Intersection Of Art And Science Ii, Petronio Bendito, Tim Korb

Lawson Building Exhibitions on the Intersection of Art and Science

The Intersection of Art and Science exhibition is an interdisciplinary educational project that examines a wide range of expressive approaches explored by international artists working at the intersection of art, mathematics, computer science, and technology. It is a joint collaboration between the Department of Computer Science and the Patti and Rusty Rueff School of Visual and Performing Arts at Purdue University. Featured artists: Manuel Baez, Sarah Berube, Robert Bosch, Sage Jenson, Jean-Marc Castera, Marc Chamberland, Marion Chamberland, Laura De Decker, Bathsheba Grossman, Colin Liotta, Vincent J. Matsko, Kerry Mitchell, Janna Schimka, Rolf Schmuck, and Markus Schwehm. The exhibition was curated …

Evaluating A Cluster Of Low-Power Arm64 Single-Board Computers With Mapreduce, Daniel Mcdermott

EWU Masters Thesis Collection

With the meteoric rise of enormous data collection in science, industry, and the cloud, methods for processing massive datasets have become more crucial than ever. MapReduce is a restricted programing model for expressing parallel computations as simple serial functions, and an execution framework for distributing those computations over large datasets residing on clusters of commodity hardware. MapReduce abstracts away the challenging low-level synchronization and scalability details which parallel and distributed computing often necessitate, reducing the concept burden on programmers and scientists who require data processing at-scale. Typically, MapReduce clusters are implemented using inexpensive commodity hardware, emphasizing quantity over quality due …

Smartphone User Privacy Preserving Through Crowdsourcing, Bahman Rashidi

Theses and Dissertations

In current Android architecture, users have to decide whether an app is safe to use or not. Expert users can make savvy decisions to avoid unnecessary private data breach. However, the majority of regular users are not technically capable or do not care to consider privacy implications to make safe decisions. To assist the technically incapable crowd, we propose a permission control framework based on crowdsourcing. At its core, our framework runs new apps under probation mode without granting their permission requests up-front. It provides recommendations on whether to accept or not the permission requests based on decisions from peer …

High-Order Integral Equation Methods For Quasi-Magnetostatic And Corrosion-Related Field Analysis With Maritime Applications, Robert Pfeiffer

Theses and Dissertations--Electrical and Computer Engineering

This dissertation presents techniques for high-order simulation of electromagnetic fields, particularly for problems involving ships with ferromagnetic hulls and active corrosion-protection systems.

A set of numerically constrained hexahedral basis functions for volume integral equation discretization is presented in a method-of-moments context. Test simulations demonstrate the accuracy achievable with these functions as well as the improvement brought about in system conditioning when compared to other basis sets.

A general method for converting between a locally-corrected Nyström discretization of an integral equation and a method-of-moments discretization is presented next. Several problems involving conducting and magnetic-conducting materials are solved to verify the accuracy …

Mechanism Design, Matching Theory And The Stable Roommates Problem, Yashaswi Mohanty

Honors Theses

This thesis consists of two independent albeit related chapters. The first chapter introduces concepts from mechanism design and matching theory, and discusses potential applications of this theory, particularly in relation to dorm allocations in colleges. The second chapter investigates a subset of the dorm allocation problem, namely that of matching roommates. In particular, the paper looks at the probability of solvability of random instances of the stable roommates game under the condition that preferences are not completely random and exogenous but endogenously determined through a dependence on room choice. These probabilities are estimated using Monte-Carlo simulations and then compared with …

Gpu Accelerated Risk Quantification, Forrest L. Ireland

EWU Masters Thesis Collection

Factor Analysis of Information Risk (FAIR) is a standard model for quantitatively estimating cybersecurity risks and has been implemented as a sequential Monte Carlo simulation in the RiskLens and FAIR-U applications. Monte Carlo simulations employ random sampling techniques to model certain systems through the course of many iterations. Due to their sequential nature, FAIR simulations in these applications are limited in the number of iterations they can perform in a reasonable amount of time. One method that has been extensively used to speed up Monte Carlo simulations is to implement them to take advantage of the massive parallelization available when …