Computer Sciences Commons^™

Hardness Of Sparse Sets And Minimal Circuit Size Problem, Bin Fu

Computer Science Faculty Publications

We study the magnification of hardness of sparse sets in nondeterministic time complexity classes on a randomized streaming model. One of our results shows that if there exists a 2no(1) -sparse set in NDTIME(2no(1)) that does not have any randomized streaming algorithm with no(1) updating time, and no(1) space, then NEXP≠BPP , where a f(n)-sparse set is a language that has at most f(n) strings of length n. We also show that if MCSP is ZPP -hard under polynomial time truth-table reductions, then EXP≠ZPP .

Computational Complexity Characterization Of Protecting Elections From Bribery, Lin Chen, Ahmed Sunny, Lei Xu, Shouhuai Xu, Zhimin Gao, Yang Lu, Weidong Shi, Nolan Shah

Computer Science Faculty Publications

The bribery problem in election has received considerable attention in the literature, upon which various algorithmic and complexity results have been obtained. It is thus natural to ask whether we can protect an election from potential bribery. We assume that the protector can protect a voter with some cost (e.g., by isolating the voter from potential bribers). A protected voter cannot be bribed. Under this setting, we consider the following bi-level decision problem: Is it possible for the protector to protect a proper subset of voters such that no briber with a fixed budget on bribery can alter the election …

Building Patterned Shapes In Robot Swarms With Uniform Control Signals, David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller, Tim Wylie

Computer Science Faculty Publications

This paper investigates a restricted version of robot motion planning, in which particles on a board uniformly respond to global signals that cause them to move one unit distance in a particular direction. We look at the problem of assembling patterns within this model. We first derive upper and lower bounds on the worst-case number of steps needed to reconfigure a general purpose board into a target pattern. We then show that the construction of k-colored patterns of size-n requires Ω(n log k) steps in general, and Ω(n log k + √ k) steps if the constructed shape must always …

Feature Pyramid Transformer, Dong Zhang, Hanwang Zhang, Jinhui Tang, Meng Wang, Xian-Sheng Hua, Qianru Sun

Research Collection School Of Computing and Information Systems

Feature interactions across space and scales underpin modern visual recognition systems because they introduce beneficial visual contexts. Conventionally, spatial contexts are passively hidden in the CNN’s increasing receptive fields or actively encoded by non-local convolution. Yet, the non-local spatial interactions are not across scales, and thus they fail to capture the non-local contexts of objects (or parts) residing in different scales. To this end, we propose a fully active feature interaction across both space and scales, called Feature Pyramid Transformer (FPT). It transforms any feature pyramid into another feature pyramid of the same size but with richer contexts, by using …

An Ensemble Of Epoch-Wise Empirical Bayes For Few-Shot Learning, Yaoyao Liu, Bernt Schiele, Qianru Sun

Research Collection School Of Computing and Information Systems

Few-shot learning aims to train efficient predictive models with a few examples. The lack of training data leads to poor models that perform high-variance or low-confidence predictions. In this paper, we propose to meta-learn the ensemble of epoch-wise empirical Bayes models (E3BM) to achieve robust predictions. “Epoch-wise'' means that each training epoch has a Bayes model whose parameters are specifically learned and deployed. ”Empirical'' means that the hyperparameters, e.g., used for learning and ensembling the epoch-wise models, are generated by hyperprior learners conditional on task-specific data. We introduce four kinds of hyperprior learners by considering inductive vs. transductive, and epoch-dependent …

A Visual Analytics Tool For Personalized Competency Feedback, Joelle Elmaleh, Shankararaman, Venky

Research Collection School Of Computing and Information Systems

In this paper we report our study on the design and implementation of a visual analytics tool, Competency Analytics System (CAS), which provides feedback to instructors on both the cohort and individual student’s competency acquisition rate, as well as provide personalized dashboard to each student on his or her competency acquisition for a specific course. We present the key functionalities of CAS and describe a case study on the implementation of CAS in a first-year programming course. Data from a student survey indicates that the personalized dashboard provided by CAS contributed to enhancing their ability to clearly identify the extent …

Intersentiment: Combining Deep Neural Models On Interaction And Sentiment For Review Rating Prediction, Shi Feng, Kaisong Song, Daling Wang, Wei Gao, Yifei Zhang

Research Collection School Of Computing and Information Systems

Review rating prediction is commonly approached from the perspective of either Collaborative Filtering (CF) or Sentiment Classification (SC). CF-based approach usually resorts to matrix factorization based on user–item interaction, and does not fully utilize the valuable review text features. In contrast, SC-based approach is focused on mining review content, but can just incorporate some user- and product-level features, and fails to capture sufficient interactions between them represented typically in a sparse matrix as CF can do. In this paper, we propose a novel, extensible review rating prediction model called InterSentiment by bridging the user-product interaction model and the sentiment model …

Commanding And Re-Dictation: Developing Eyes-Free Voice-Based Interaction For Editing Dictated Text, Debjyoti Ghosh, Can Liu, Shengdong Zhao, Kotaro Hara

Research Collection School Of Computing and Information Systems

Existing voice-based interfaces have limited support for text editing, especially when seeing the text is difficult, e.g., while walking or cooking. This research develops voice interaction techniques for eyes-free text editing. First, with a Wizard-of-Oz study, we identified two primary user strategies: using commands, e.g., “replace go with goes” and re-dictating over an erroneous portion, e.g., correcting “he go there” by saying “he goes there.” To support these user strategies with an actual system implementation, we developed two eyes-free voice interaction techniques, Commanding and Re-dictation, and evaluated them with a controlled experiment. Results showed that while Re-dictation performs significantly better …

Learning Transferrable Parameters For Long-Tailed Sequential User Behavior Modeling, Jianwen Yin, Chenghao Liu, Weiqing Wang, Jianling Sun, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

Sequential user behavior modeling plays a crucial role in online user-oriented services, such as product purchasing, news feed consumption, and online advertising. The performance of sequential modeling heavily depends on the scale and quality of historical behaviors. However, the number of user behaviors inherently follows a long-tailed distribution, which has been seldom explored. In this work, we argue that focusing on tail users could bring more benefits and address the long tails issue by learning transferrable parameters from both optimization and feature perspectives. Specifically, we propose a gradient alignment optimizer and adopt an adversarial training scheme to facilitate knowledge transfer …

Privacy Preserving Search Services Against Online Attack, Yi Zhao, Jianting Nian, Kaitai Liang, Yanqi Zhao, Liqun Chen, Bo Yang

Research Collection School Of Computing and Information Systems

Searchable functionality is provided in many online services such as mail services or outsourced data storage. To protect users privacy, data in these services is usually stored after being encrypted using searchable encryption. This enables the data user to securely search encrypted data from a remote server without leaking data and query information. Public key encryption with keyword search is one of the research branches of searchable encryption; this provides privacy-preserving searchable functionality for applications such as encrypted email systems. However, it has an inherent vulnerability in that the information of a query may be leaked using a keyword guessing …

Accelerating Exact Constrained Shortest Paths On Gpus, Shengliang Lu, Bingsheng He, Yuchen Li, Hao Fu

Research Collection School Of Computing and Information Systems

The recently emerging applications such as software-defined networks and autonomous vehicles require efficient and exact solutions for constrained shortest paths (CSP), which finds the shortest path in a graph while satisfying some user-defined constraints. Compared with the common shortest path problems without constraints, CSP queries have a significantly larger number of subproblems. The most widely used labeling algorithm becomes prohibitively slow and impractical. Other existing approaches tend to find approximate solutions and build costly indices on graphs for fast query processing, which are not suitable for emerging applications with the requirement of exact solutions. A natural question is whether and …

Aim 2020 Challenge On Video Extreme Super-Resolution: Methods And Results, D. Fuoli, Zhiwu Huang, S. Gu, R. Timofte, A. Raventos, A. Esfandiari, S. Karout, X. Xu, X. Li, X. Xiong, J. Wang, Michelini P. Navarrete, W. Zhang, D. Zhang, H. Zhu, D. Xia, H. Chen, J. Gu, Z. Zhang, T. Zhao

Research Collection School Of Computing and Information Systems

This paper reviews the video extreme super-resolution challenge associated with the AIM 2020 workshop at ECCV 2020. Common scaling factors for learned video super-resolution (VSR) do not go beyond factor 4. Missing information can be restored well in this region, especially in HR videos, where the high-frequency content mostly consists of texture details. The task in this challenge is to upscale videos with an extreme factor of 16, which results in more serious degradations that also affect the structural integrity of the videos. A single pixel in the lowresolution (LR) domain corresponds to 256 pixels in the high-resolution (HR) domain. …

Dual-Dropout Graph Convolutional Network For Predicting Synthetic Lethality In Human Cancers, Ruichu Cai, Xuexin Chen, Yuan Fang, Min Wu, Yuexing Hao

Research Collection School Of Computing and Information Systems

Motivation: Synthetic lethality (SL) is a promising form of gene interaction for cancer therapy, as it is able to identify specific genes to target at cancer cells without disrupting normal cells. As high-throughput wet-lab settings are often costly and face various challenges, computational approaches have become a practical complement. In particular, predicting SLs can be formulated as a link prediction task on a graph of interacting genes. Although matrix factorization techniques have been widely adopted in link prediction, they focus on mapping genes to latent representations in isolation, without aggregating information from neighboring genes. Graph convolutional networks (GCN) can capture …

Meta-Learning On Heterogeneous Information Networks For Cold-Start Recommendation, Yuanfu Lu, Yuan Fang, Chuan Shi

Research Collection School Of Computing and Information Systems

Cold-start recommendation has been a challenging problem due to sparse user-item interactions for new users or items. Existing efforts have alleviated the cold-start issue to some extent, most of which approach the problem at the data level. Earlier methods often incorporate auxiliary data as user or item features, while more recent methods leverage heterogeneous information networks (HIN) to capture richer semantics via higher-order graph structures. On the other hand, recent meta-learning paradigm sheds light on addressing cold-start recommendation at the model level, given its ability to rapidly adapt to new tasks with scarce labeled data, or in the context of …

Social Participation Performance Of Wheelchair Users Using Clustering And Geolocational Sensor's Data, Yukun Yin, Kar Way Tan

Research Collection School Of Computing and Information Systems

For wheelchair users, social participation and physical mobility play a significant part in determining their mental health and quality of life outcomes. However, little is known about how wheelchair users move about and engage in social interactions within their life-spaces. In this project, we investigate the social participation performance of the wheelchair users based on a combination of geolocational and lifestyle survey data collected over a period of three months. This paper adopts a multi-variate approach combining geolocational travel patterns and various factors such as independence, willingness and self-perception to provide multi-faceted analysis to their lifestyles. We provide profiles of …

Measuring Privacy Concerns With Government Surveillance And Right-To-Be-Forgotten In Nomological Net Of Trust And Willingness-To-Share, Gaurav Bansal, Fiona Fui-Hoon Nah

Research Collection School Of Computing and Information Systems

In the post Snowden revelations era, concerns related to government surveillance and oversight have come to the forefront. The ability of the Internet to remember “everything” (or forget anything) also raises a privacy concern associated with the “right to be forgotten”. Hence, in this paper, we propose and examine privacy concerns by extending the Hong and Thong’s (2013) model with the addition of two dimensions: right to be forgotten as well as government surveillance and oversight. We tested two different measurement models using privacy concerns as a second-order and a third-order construct within a nomological net that includes trusting beliefs …

Quantum And Classical Multilevel Algorithms For (Hyper)Graphs, Ruslan Shaydulin

All Dissertations

Combinatorial optimization problems on (hyper)graphs are ubiquitous in science and industry. Because many of these problems are NP-hard, development of sophisticated heuristics is of utmost importance for practical problems. In recent years, the emergence of Noisy Intermediate-Scale Quantum (NISQ) computers has opened up the opportunity to dramaticaly speedup combinatorial optimization. However, the adoption of NISQ devices is impeded by their severe limitations, both in terms of the number of qubits, as well as in their quality. NISQ devices are widely expected to have no more than hundreds to thousands of qubits with very limited error-correction, imposing a strict limit on …

Emergency Department Systems Engineering: Modelling And Event Simulation, O Alharethi Salman Zayed

Student Works (2020-2029)

Emergency department systems are meant to ensure the timely delivery for essential healthcare services through complex systems. (ED) offers various services and have several components in its parts. Examined long previous research on system engineering and quality of healthcare resulting on these are influenced by operational management. Real time data are very helpful for decision making for any systems. Patient output feedback and satisfaction can be ensured with engineered management. EDs have become evident particularly in current scenario when the world is in the grip of the deadly COVID-19. All this implies that analysis is significant for improvement of services …

Through-The-Wall Radar Detection Using Machine Learning, Aihua W. Wood, Ryan Wood, Matthew Charnley

Faculty Publications

This paper explores the through-the-wall inverse scattering problem via machine learning. The reconstruction method seeks to discover the shape, location, and type of hidden objects behind walls, as well as identifying certain material properties of the targets. We simulate RF sources and receivers placed outside the room to generate observation data with objects randomly placed inside the room. We experiment with two types of neural networks and use an 80-20 train-test split for reconstruction and classification.

Visual Saliency Estimation And Its Applications, Fei Xu

All Graduate Theses and Dissertations, Spring 1920 to Summer 2023

The human visual system can automatically emphasize some parts of the image and ignore the other parts when seeing an image or a scene. Visual Saliency Estimation (VSE) aims to imitate this functionality of the human visual system to estimate the degree of human attention attracted by different image regions and locate the salient object. The study of VSE will help us explore the way human visual systems extract objects from an image. It has wide applications, such as robot navigation, video surveillance, object tracking, self-driving, etc.

The current VSE approaches on natural images models generic visual stimuli based on …

Facial Expression Recognition In The Wild Using Convolutional Neural Networks, Amir Hossein Farzaneh

All Graduate Theses and Dissertations, Spring 1920 to Summer 2023

Facial Expression Recognition (FER) is the task of predicting a specific facial expression given a facial image. FER has demonstrated remarkable progress due to the advancement of deep learning. Generally, a FER system as a prediction model is built using two sub-modules: 1. Facial image representation model that learns a mapping from the input 2D facial image to a compact feature representation in the embedding space, and 2. A classifier module that maps the learned features to the label space comprising seven labels of neutral, happy, sad, surprise, anger, fear, or disgust. Ultimately, …

An Analysis Of Syntax Exercises On The Performance Of Cs1 Students, Shelsey B. Sullivan

All Graduate Theses and Dissertations, Spring 1920 to Summer 2023

Students in introductory programming classes (CS1) generally have a difficult time learning the rules of programming. Although the general concepts of programming are relatively easy to learn, it can be difficult to learn what exactly can be typed in what order, which is known as syntax. To attempt to help students overcome this barrier, a study was conducted that introduced exercises into a CS1 class which taught the programming syntax in simple steps. The results of this study were obtained by analyzing the keys the students pressed, the errors of their code, their midterm exam scores, and their responses to …

Automating And Analyzing Whole-Farm Carbon Models, Aditi Maheshwari

All Graduate Theses and Dissertations, Spring 1920 to Summer 2023

The goal of this research is to learn about whole farm carbon models. A whole farm carbon model estimates the emissions of greenhouse gasses (GHGs) based on information for a farm. We analyzed two models, HOLOS whole-farm and COMET-Farm, by running the models on random inputs and building classifiers from the runs. HOLOS estimates GHG emissions for a particular year based on crop and animal agriculture input, while COMET-farm adds past and future farm management practices. Users of the models must manually enter farm data through a graphical user interface (GUI), which is a good method for a single farm, …

Development And Identification Of Metrics To Predict The Impact Of Dimension Reduction Techniques On Classical Machine Learning Algorithms For Still Highway Images, Wasim Akram Khan

All Graduate Theses and Dissertations, Spring 1920 to Summer 2023

We are witnessing an influx of data - images, texts, video, etc. Their high dimensionality and large volume make it challenging to apply machine learning to obtain actionable insight. This thesis explores several aspects pertaining to dimensional reduction: dimension reduction methods, metrics to measure distortion, image preprocessing, etc. Faster training and inference time on reduced data and smaller models which can be deployed on commodity hardware are a critical advantage of dimension reduction. For this study, classical machine learning methods were explored owing to their solid mathematical foundation and interpretability.

The dataset used is a time series of images from …

Machine Learning Enhanced Free-Space And Underwater Oam Optical Communications, Patrick L. Neary

All Graduate Theses and Dissertations, Spring 1920 to Summer 2023

Communications, bandwidth, security, and hardware simplicity are principles of interest to society at large. Recent advances in optics and in understanding properties of light, such as orbital angular momentum (OAM), have provided new potential mediums for communication.

Machine learning has wound its way into a broad range of fascinating areas. An emerging field of research is the use of a unique property of lasers called orbital angular momentum (OAM). With the proper hardware, a laser can go from a Gaussian shaped distribution to a doughnut shaped pattern, where the radius can be changed. Multiple OAM patterns, or modes, can be …

Solar Irradiance Prediction Using Xg-Boost With The Numerical Weather Forecast, Pratyusha Sai Kamarouthu

All Graduate Theses and Dissertations, Spring 1920 to Summer 2023

To defeat global warming, the world expects to look at renewable energy sources. Solar energy is one of the best renewable energy sources which causes no harm to the environment. As solar energy changes with atmospheric parameters like temperature, relative humidity, cloud coverage, dewpoint, sun position, day of the year, etc. It is difficult to understand its nature by science. Predicting solar irradiance which is directly proportional to solar energy using atmospheric parameters is the main goal of this work. Powerful artificial intelligence algorithms that won many coding competitions have been used to predict it. Using these methods and numerical …

Load Forecasting Analysis Using Contextual Data And Integration With Microgrids Used For Off Grid Ev Charging Stations, Ashit Neema

All Graduate Theses and Dissertations, Spring 1920 to Summer 2023

Electricity is an essential component of the smooth working of every sector. If a successful prediction of how much electricity will be required for say the next 24 hours or 48 hours can be made, it will not only help in efficiently planning the activities and operations but also help in minimizing the cost incurred. In this thesis the same is being attempted, first, a model is created that can predict the energy consumption of households using various tools available. To achieve this, historical data of the past 5 years that has been recorded in London has been used. Secondly, …

Application Of Artificial Intelligence And Geographic Information System For Developing Automated Walkability Score, Md Mehedi Hasan

Dissertations

Walking is considered as one of the major modes of active transportation, which contributes to the livability of cities. It is highly important to ensure walk friendly sidewalks to promote human physical activities along roads. Over the last two decades, different walk scores were estimated in respect to walkability measures by applying different methods and approaches. However, in the era of big data and machine learning revolution, there is still a gap to measure the composite walkability score in an automated way by applying and quantifying the activityfriendliness of walkable streets. In this study, a street-level automated walkability score was …

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

McKelvey School of Engineering Graduate Student 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 and …

Predictive Insights For Improving The Resilience Of Global Food Security Using Artificial Intelligence, Meng Leong How, Yong Jiet Chan, Sin Mei Cheah

Research Collection Lee Kong Chian School Of Business

Unabated pressures on food systems affect food security on a global scale. A human-centric artificial intelligence-based probabilistic approach is used in this paper to perform a unified analysis of data from the Global Food Security Index (GFSI). The significance of this intuitive probabilistic reasoning approach for predictive forecasting lies in its simplicity and user-friendliness to people who may not be trained in classical computer science or in software programming. In this approach, predictive modeling using a counterfactual probabilistic reasoning analysis of the GFSI dataset can be utilized to reveal the interplay and tensions between the variables that underlie food affordability, …