Theory and Algorithms Commons^™

A Survey Of Matrix Completion Methods For Recommendation Systems, Andy Ramlatchan, Mengyun Yang, Quan Liu, Min Li, Jianxin Wang, Yaohang Li

Computer Science Faculty Publications

In recent years, the recommendation systems have become increasingly popular and have been used in a broad variety of applications. Here, we investigate the matrix completion techniques for the recommendation systems that are based on collaborative filtering. The collaborative filtering problem can be viewed as predicting the favorability of a user with respect to new items of commodities. When a rating matrix is constructed with users as rows, items as columns, and entries as ratings, the collaborative filtering problem can then be modeled as a matrix completion problem by filling out the unknown elements in the rating matrix. This article …

Efficient Representative Subset Selection Over Sliding Windows, Yanhao Wang, Yuchen Li, Kian-Lee Tan

Research Collection School Of Computing and Information Systems

Representative subset selection (RSS) is an important tool for users to draw insights from massive datasets. Existing literature models RSS as submodular maximization to capture the "diminishing returns" property of representativeness, but often only has a single constraint, which limits its applications to many real-world problems. To capture the recency issue and support various constraints, we formulate dynamic RSS as maximizing submodular functions subject to general d -knapsack constraints (SMDK) over sliding windows. We propose a KnapWindow framework (KW) for SMDK. KW utilizes KnapStream (KS) for SMDK in append-only streams as a subroutine. It maintains a sequence of checkpoints and …

The Price Of Usability: Designing Operationalizable Strategies For Security Games, Sara Marie Mccarthy, Corine M. Laan, Kai Wang, Phebe Vayanos, Arunesh Sinha, Milind Tambe

Research Collection School Of Computing and Information Systems

We consider the problem of allocating scarce security resources among heterogeneous targets to thwart a possible attack. It is well known that deterministic solutions to this problem being highly predictable are severely suboptimal. To mitigate this predictability, the game-theoretic security game model was proposed which randomizes over pure (deterministic) strategies, causing confusion in the adversary. Unfortunately, such mixed strategies typically involve randomizing over a large number of strategies, requiring security personnel to be familiar with numerous protocols, making them hard to operationalize. Motivated by these practical considerations, we propose an easy to use approach for computing strategies that are easy …

Distributed K-Nearest Neighbor Queries In Metric Spaces, Xin Ding, Yuanliang Zhang, Lu Chen, Yunjun Gao, Baihua Zheng

Research Collection School Of Computing and Information Systems

Metric k nearest neighbor (MkNN) queries have applications in many areas such as multimedia retrieval, computational biology, and location-based services. With the growing volumes of data, a distributed method is required. In this paper, we propose an Asynchronous Metric Distributed System (AMDS), which uniformly partitions the data with the pivot-mapping technique to ensure the load balancing, and employs publish/subscribe communication model to asynchronously process large scale of queries. The employment of asynchronous processing model also improves robustness and efficiency of AMDS. In addition, we develop an efficient estimation based MkNN method using AMDS to improve the query efficiency. Extensive experiments …

Online Active Learning With Expert Advice, Shuji Hao, Peiying Hu, Peilin Zhao, Steven C. H. Hoi, Chunyan Miao

Research Collection School Of Computing and Information Systems

In literature, learning with expert advice methods usually assume that a learner always obtain the true label of every incoming training instance at the end of each trial. However, in many real-world applications, acquiring the true labels of all instances can be both costly and time consuming, especially for large-scale problems. For example, in the social media, data stream usually comes in a high speed and volume, and it is nearly impossible and highly costly to label all of the instances. In this article, we address this problem with active learning with expert advice, where the ground truth of an …

A Bayesian Latent Variable Model Of User Preferences With Item Context, Aghiles Salah, Hady W. Lauw

Research Collection School Of Computing and Information Systems

Personalized recommendation has proven to be very promising in modeling the preference of users over items. However, most existing work in this context focuses primarily on modeling user-item interactions, which tend to be very sparse. We propose to further leverage the item-item relationships that may reflect various aspects of items that guide users’ choices. Intuitively, items that occur within the same “context” (e.g., browsed in the same session, purchased in the same basket) are likely related in some latent aspect. Therefore, accounting for the item’s context would complement the sparse user-item interactions by extending a user’s preference to other items …

The Silencing Power Of Algorithms: How The Facebook News Feed Algorithm Manipulates Users' Perceptions Of Opinion Climates, Callie Jessica Morgan

University Honors Theses

This extended literature review investigates how the architecture and features of the Facebook Newsfeed algorithm, EdgeRank, can inhibit and facilitate the expression of political opinions. This paper will investigate how Elisabeth Noelle-Neumann's theory on public opinion, Spiral of Silence, can be used to assess the Facebook news feed as a political opinion source that actively shapes users' perceptions of minority and majority opinion climates. The feedback loops created by the algorithm's criteria influences users' decisions to self-censor or express their political opinions with interpersonal connections and unfamiliar connections on the site.

Understanding Generalization And Optimization Performance Of Deep Cnns, Pan Zhou, Jiashi Feng

Research Collection School Of Computing and Information Systems

This work aims to provide understandings on the remarkable success of deep convolutional neural networks (CNNs) by theoretically analyzing their generalization performance and establishing optimization guarantees for gradient descent based training algorithms. Specifically, for a CNN model consisting of l convolutional layers and one fully connected layer, we prove that its generalization error is bounded by O( p θ%/n e ) where θ denotes freedom degree of the network parameters and %e = O(log(Ql i=1 bi(ki − si + 1)/p) + log(bl+1)) encapsulates architecture parameters including the kernel size ki , stride si , pooling size p and parameter magnitude …

Development Of A Slab-Based Monte Carlo Proton Dose Algorithm With A Robust Material-Dependent Nuclear Halo Model, John Wesley Chapman Jr

LSU Doctoral Dissertations

Pencil beam algorithms (PBAs) are often utilized for dose calculation in proton therapy treatment planning because they are fast and accurate under most conditions. However, as discussed in Chapman et al (2017), the accuracy of a PBA can be limited under certain conditions because of two major assumptions: (1) the central-axis semi-infinite slab approximation; and, (2) the lack of material dependence in the nuclear halo model. To address these limitations, we transported individual protons using a class II condensed history Monte Carlo and added a novel energy loss method that scaled the nuclear halo equation in water to arbitrary geometry. …

Effects Of Dynamic Goals On Agent Performance, Nathan R. Ball

Theses and Dissertations

Autonomous systems are increasingly being used for complex tasks in dynamic environments. Robust automation needs to be able to establish its current goal and determine when the goal has changed. In human-machine teams autonomous goal detection is an important component of maintaining shared situational awareness between both parties. This research investigates how different categories of goals affect autonomous change detection in a dynamic environment. In order to accomplish this goal, a set of autonomous agents were developed to perform within an environment with multiple possible goals. The agents perform the environmental task while monitoring for goal changes. The experiment tests …

Efficient Phase Retrieval For Off-Axis Point Spread Functions, Salome Esteban Carrasco

Theses and Dissertations

A novel pairing of phase retrieval tools allows for efficient estimation of pupil phase in optical systems from images of point spread functions (PSFs). The phase retrieval algorithm uses correlation of modeled phase in the focal plane to decouple aberrations that are difficult to identify in complex PSFs. The use of a phase kernel that departs from the Fresnel approximation for off-axis PSFs is a more accurate representation of wavefront phase in finite conjugate imaging. The combination of the approximation and phase correlation algorithm can be more efficient and accurate than generic algorithms.

Finding Spanning Trees In Strongly Connected Graphs With Per-Vertex Degree Constraints, Samuel Benjamin Chase

Computer Science and Software Engineering

In this project, I sought to develop and prove new algorithms to create spanning trees on general graphs with per-vertex degree constraints. This means that each vertex in the graph would have some additional value, a degree constraint d. For a spanning tree to be correct, every vertex v_i in the spanning tree must have a degree exactly equal to a degree constraint d_i. This poses an additional constraint on what would otherwise be a trivial spanning tree problem. In this paper, two proofs related to my studies will be discussed and analyzed, leading to my algorithm …

Topographic Maps: Image Processing And Path-Finding, Calin Washington

Master's Theses

Topographic maps are an invaluable tool for planning routes through unfamiliar terrain. However, accurately planning routes on topographic maps is a time- consuming and error-prone task. One factor is the difficulty of interpreting the map itself, which requires prior knowledge and practice. Another factor is the difficulty of making choices between possible routes that have different trade-offs between length and the terrain they traverse.

To alleviate these difficulties, this thesis presents a system to automate the process of finding routes on scanned images of topographic maps. The system allows users to select any two points on a topographic map and …

Funqual: User-Defined, Statically-Checked Call Graph Constraints In C++, Andrew P. Nelson

Master's Theses

Static analysis tools can aid programmers by reporting potential programming mistakes prior to the execution of a program. Funqual is a static analysis tool that reads C++17 code ``in the wild'' and checks that the function call graph follows a set of rules which can be defined by the user. This sort of analysis can help the programmer to avoid errors such as accidentally calling blocking functions in time-sensitive contexts or accidentally allocating memory in heap-sensitive environments. To accomplish this, we create a type system whereby functions can be given user-defined type qualifiers and where users can define their own …

The Effect Of Endgame Tablebases On Modern Chess Engines, Christopher D. Peterson

Computer Engineering

Modern chess engines have the ability to augment their evaluation by using massive tables containing billions of positions and their memorized solutions. This report examines the importance of these tables to better understand the circumstances under which they should be used. The analysis conducted in this paper empirically examines differences in size and speed of memorized positions and their impacts on engine strength. Using this technique, situations where memorized tables improve play (and situations where they do not) are discovered.

Temporal And Spatiotemporal Investigation Of Tourist Attraction Visit Sentiment On Twitter, Jose J. Padilla, Hamdi Kavak, Christopher J. Lynch, Ross J. Gore, Saikou Y. Diallo

VMASC Publications

In this paper, we propose a sentiment-based approach to investigate the temporal and spatiotemporal effects on tourists' emotions when visiting a city's tourist destinations. Our approach consists of four steps: data collection and preprocessing from social media; visitor origin identification; visit sentiment identification; and temporal and spatiotemporal analysis. The temporal and spatiotemporal dimensions include day of the year, season of the year, day of the week, location sentiment progression, enjoyment measure, and multi-location sentiment progression. We apply this approach to the city of Chicago using over eight million tweets. Results show that seasonal weather, as well as special days and …

An Algorithm For Calculating Top-Dimensional Bounding Chains, J. Frederico Carvalho​, Mikael Vejdemo-Johansson, Danica Kragic, Florian T. Pokorny

Publications and Research

We describe the Coefficient-Flow algorithm for calculating the bounding chain of an (n-1)-boundary on an n-manifold-like simplicial complex S. We prove its correctness and show that it has a computational time complexity of O(|S(n−1)|) (where S(n−1) is the set of (n-1)-faces of S). We estimate the big-O coefficient which depends on the dimension of S and the implementation. We present an implementation, experimentally evaluate the complexity of our algorithm, and compare its performance with that of solving the underlying linear system.

An Analysis Of Frenkel Defects And Backgrounds Modeling For Supercdms Dark Matter Searches, Matthew Stein

Physics Theses and Dissertations

Years of astrophysical observations suggest that dark matter comprises more than ~80 % of all matter in the universe. Particle physics theories favor a weakly-interacting particle that could be directly detected in terrestrial experiments. The Super Cryogenic Dark Matter Search (SuperCDMS) Collaboration operates world-leading experiments to directly detect dark matter interacting with ordinary matter. The SuperCDMS Soudan experiment searched for weakly interacting massive particles (WIMPs) via their elastic-scattering interactions with nuclei in low-temperature germanium detectors.

During the operation of the SuperCDMS Soudan experiment, ²¹⁰Pb sources were installed to study background rejection of the Ge detectors. Data from these sources …

Appendix: A Reasonable Bias Approach To Gerrymandering: Using Automated Plan Generation To Evaluate Redistricting Proposals, Bruce E. Cain, Wendy K. Tam Cho, Yan Y. Liu, Emily R. Zhang

William & Mary Law Review Online

Here, we present our findings, analogous to those on the efficiency gap in Part I.B of our Article published in the print edition of the William & Mary Law Review, on the other measures of partisan fairness.

Applications Of Artificial Intelligence In Power Systems, Samin Rastgoufard

LSU New Orleans Theses and Dissertations

Artificial intelligence tools, which are fast, robust and adaptive can overcome the drawbacks of traditional solutions for several power systems problems. In this work, applications of AI techniques have been studied for solving two important problems in power systems.

The first problem is static security evaluation (SSE). The objective of SSE is to identify the contingencies in planning and operations of power systems. Numerical conventional solutions are time-consuming, computationally expensive, and are not suitable for online applications. SSE may be considered as a binary-classification, multi-classification or regression problem. In this work, multi-support vector machine is combined with several evolutionary computation …