SCS Honors Senior Thesis 2020 (Pittsburgh)

Take a look at the senior honors thesis research done by our undergraduates this semester. Click on the title link to view a pdf of the associated poster (if available). If you have questions about a student's work, feel free to email them using the indicated andrew ID (andrewID@andrew.cmu.edu).

Also feel free to attend their presentations on Wednesday, May 6. All times are Eastern Daylight Time.
Registration for event: https://cmu.zoom.us/meeting/register/tJIldOygqT4pE9LqIvCRYzInJT9dbk-iCy3O

11:30AM	Jennifer Lee	Reasoning By Instruction Using COMmonsEnse Transformers
11:50AM	Simin Li	Chunking in Neural Networks
12:10PM	Joshua Zhanson	Investigating and Robustifying Proximal Policy Optimization
12:30PM	Wenxin Ding	On the Privacy-Utility Tradeoff in Peer-Review Data Analysis
12:50PM	Peter Wu	Multimodal Representation Learning
BREAK
2:00PM	Rishabh Chatterjee	Design and Evaluation of Automated Interventions to Increase Usage     of a Phone-Based Literacy Technology in Rural Africa
2:20PM	Zachary Sussman	Outlier-Robust Linear and ReLU Regression
2:40PM	Minji Kim	Detecting the End of Speaking Turns to Enhance Social Robots' Participation     in Group Conversation
3:00PM	Yue Wu	Posterior Regulation GAN
3:20PM	Jake Olkin	Developing Simulation Environments and Applying Deep Reinforcement Learning Algorithms     for the SoftGym Project
3:40PM	Vaidehi Srinivas	Simpler Approximations for the Network Steiner-Tree Problem

  

Rishabh Chatterjee
rishabhc
Advisor(s): Amy Ogan, Michael Madaio
Title: Design and Evaluation of Automated Interventions to Increase Usage of a Phone-Based Literacy Technology in Rural Africa
Presentation Time: 2:00PM
Abstract: Despite an overall rise in global literacy rates, formal education in many low-resource contexts may be insufficient to foster early literacy. Educational technologies may help provide accessible, out-of-school literacy instruction, but children may not persist in voluntarily using such systems to learn. Prior research has developed methods for predicting learner dropout from formal courses and Massive Open Online Courses (MOOCs), often for adults, but not for children's voluntary EdTech usage. Similarly, research in healthcare has shown that automated interventions (like SMS reminders) are positively correlated with voluntary medical adherence, but there is a gap in EdTech literature regarding the effect of such interventions on system usage.To support early literacy in rural contexts, a phone-based literacy technology was deployed with families in rural communities in Côte d'Ivoire in two longitudinal studies. In this thesis, we first investigate the feasibility of using system log data to predict gaps in mobile education system usage in rural communities. We use a time-series classification approach, and we compare the performance of multiple models, identify the most important features, and evaluate our approach on a replication study of the same system in the same context. We then investigate the efficacy of automated, rule-based SMS reminders in increasing voluntary system usage by comparing children’s usage statistics pre and post intervention, and suggest methods to implement preemptive interventions to promote system usage. We contribute insights and design implications for (1) predicting learners' voluntary usage, (2) implementing preemptive interventions, and (3) the effect of automated interventions on system usage on out-of-school mobile learning applications in rural contexts.

Wenxin (Freda) Ding
wenxind
Advisor(s): Nihar Shah, Weina Wang
Title: On the Privacy-Utility Tradeoff in Peer-Review Data Analysis
Presentation Time: 12:30PM
Abstract: Peer review is a critical part of scientific research, however, the design of fair and efficient review processes is a major challenge. In order to enable more research on this important topic, it behooves to release more peer-review data. The major concern with doing so, however, is that peer-review data is private (i.e., the identities of reviewers are not known to authors). In this work we design techniques to release peer-review data in a differentially private manner, with an emphasis on having as high an accuracy of the released data while also preserving privacy.
Our contributions span conceptual, theoretical, and applied aspects of this problem, and our main contributions are as follows.
On the conceptual front, we first identify unavailability of data as a key problem in research on peer review. We design a framework that encompasses several kinds of data that we identify as key for research on various aspects of peer review (such as miscalibration and subjectivity biases). We formulate the goal of releasing peer review data in a privacy-preserving manner. We show that projecting the (noisy) private output on any convex set containing all possible ``true'' values of the data enjoys appealing properties in terms of the utility (accuracy) of the data.
On the theoretical front, we first prove that the obvious approach of projecting on the set of all true values can, surprisingly, lead to a reduction in the accuracy. We then argue for the judiciousness of projecting on the convex hull of all true values, and we then prove that unfortunately doing such a projection is NP-hard. Our third theoretical contribution is to design a polynomial-time algorithm that projects the data into a small convex set containing all true values. We show that this set is indeed reasonably small via an axiomatic approach.
Finally, on the applied front, we evaluate our algorithm on real-world peer review data and also conduct an in-depth study via extensive synthetic simulations. Our evaluations reveal that our algorithm leads to up to orders of magnitude improvements in accuracy, thereby strongly demonstrating the utility of our proposed algorithm in practice.
The paper reviewing process is a critical part of scientific research, however, the design of fair and efficient review processes is a major challenge. In order to enable more research on this important topic, it behooves to release more peer review data. The major concern with doing so, however, is that peer review data is private (i.e., the identities of reviewers are not known to authors). In this work we design techniques to release peer review data in a differentially private manner, with an emphasis on having as high an accuracy of the released data while also preserving privacy.

Manuel Fernandez
manuelf
Advisor(s): David Woodruff
Title: Graph Spanners in the Message-Passing Model
Presented: December 2019
Abstract: Graph spanners are sparse subgraphs which approximately preserve all pairwise shortest-path distances in an input graph. The notion of approximation can be additive, multiplicative, or both, and many variants of this problem have been extensively studied. We study the problem of computing a graph spanner when the edges of the input graph are distributed across two or more sites in an arbitrary, possibly worst-case partition, and the goal is for the sites to minimize the communication used to output a spanner. We assume the message-passing model of communication, for which there is a point-to-point link between all pairs of sites as well as a coordinator who is responsible for producing the output. We stress that the subset of edges that each site has is not related to the network topology, which is fixed to be point-to-point. While this model has been extensively studied for related problems such as graph connectivity, it has not been systematically studied for graph spanners. We present the first tradeoffs for total communication versus the quality of the spanners computed, for two or more sites, as well as for additive and multiplicative notions of distortion. We show separations in the communication complexity when edges are allowed to occur on multiple sites, versus when each edge occurs on at most one site. We obtain nearly tight bounds (up to polylog factors) for the communication of additive 2-spanners in both the with and without duplication models, multiplicative (2k−1)-spanners in the with duplication model, and multiplicative 3 and 5-spanners in the without duplication model. Our lower bound for multiplicative 3-spanners employs biregular bipartite graphs rather than the usual Erd ̋os girth conjecture graphs and may be of wider interest.

Minji Kim
minjik2
Advisor(s): Henny Admoni
Title: Detecting the End of Speaking Turns to Enhance Social Robots' Participation in Group Conversation
Presentation Time: 2:40PM
Abstract: Human-Robot Interaction research investigates how robots can support the functions of groups of people, for example by encouraging equal participation in group conversations. To be effective at balancing the participation across members of a group, these robots need to be able to detect when people in the group have ended their speaking turn. In this research project, I will construct a deep learning model that uses acoustic features to detect the end of speaking turns in real time, and then test the model’s effectiveness in group conversation. The accuracy and latency of end-of-turn detection will be used as metrics to determine the success of the model. The model will be trained and tested on in-person recordings of groups of 3 people performing the desert survival task. To support group conversation studies done over video, it will also be trained and tested on video recordings of groups of 3 people performing the desert survival task. To further study the robustness of the model, cross performance of the model where it will be trained on in-person data when tested on video data and trained on video data when tested on in-person data will also be observed in this study.

Varsha Kumar
varshak
Advisor(s): Red Whittaker
Title: Resource-Limited Exploration Autonomy for Planetary Rovers
In Progress: Expected Completion Spring 2021
Abstract: Robot functionality in truly uncontrolled environments is thwarted by the debility of current autonomy software. Carnegie Mellon’s ice-finding lunar micro-rover will be humanity’s first real moonshot that compels ambitious autonomy from minimal computing and sensing in an unpredictable and highly uncontrolled environment. MoonRanger design constraints, such as limited compute power and limited sensing, compel unprecedented autonomous functionality that will rely on algorithms for determining location, orientation, and maps of surrounding terrain. These elements of autonomy are keystones in MoonRanger’s overarching architecture, which, by necessity, encompasses both software and hardware considerations. This research details the foundations of a robust pose estimation under these limitations. The investigation evinces how preliminary algorithm application on experimental data is informing decisions as to the validity of design. The poster projects future research and speculates MoonRanger’s impact of shattering the boundaries of autonomous robotics.

Jennifer Lee
jennife4
Advisor(s): Tom Mitchell
Title: Reasoning By Instruction Using COMmonsEnse Transformers
Presentation Time: 11:30AM
Abstract: LIA, Learning by Instruction Agent, is a ML paradigm in which humans teach the machine a new task through verbal instructions and demonstrations. For example, the user can ask LIA to wake them up if it snows by giving an if-then command, “if it snows tonight then wake me up early”. While these machines are successful at understanding these types of commands, humans often underspecify the preconditions of their statements. If we go back to our example, if the user’s goal is to account for traffic slowdown due to snow, then they probably meant to say, “if it’s a working day and there is enough snow to cause traffic, then wake me up early”. Consequently, we look at if-then-because statements, where the because indicates the user’s goal, to help find these underspecified pre-conditions. For my senior thesis, I developed methods for LIA to more easily find multi-hop reasoning chains in order to understand how the action indicated in the ‘then’ clause helps the user achieve the goal indicated in the ‘because’ clause. Using an external knowledge base called COMET that outputs commonsense knowledge given an input statement, the computer is able to query for the pre-conditions of the ‘because’ goal and the post-conditions of the ‘if’ and ‘then’ clauses to generate a reasoning chain. In addition, we were able to uncover different logic patterns in the commands, which we refer to as logic templates, that help the machine make a more informed query into COMET. As a result, we augment LIA’s ability to interpret user instructions, which helps her infer details that were underspecified by the user. In this thesis, I show that for some general if-then-because commands, LIA can query COMET and use logic templates to help generate reasoning chains, and for more sophisticated commands, LIA uses user instruction in order to complete these reasoning chains.

Simin Li
siminl
Advisor(s): Tai-Sing Lee
Title: Chunking in Neural Networks
Presentation Time: 11:50AM
Abstract: Chunking is the combination of lower level concepts to form higher level concepts in human memory systems. In this talk, a similar property of information representation, namely chunking in both neural networks and human cognition will be presented. We will attempt to answer the questions: is a neural network a good model of the brain in terms of neural representation of chunks? How are chunks represented in neural networks? In specific, I will show results of replication of a human study related to chunking theory done with neural networks.

Jake Olkin
jolkin
Advisor(s): David Held and Xingyu Lin
Title: Developing Simulation Environments and Applying Deep Reinforcement Learning Algorithms for the SoftGym Project
Presentation Time: 3:20PM
Abstract: When measuring the effectiveness of an approach to learning how to manipulate deformable objects, it is important to have a set of tasks to measure the approach’s performance. Currently, researchers design their own tasks to test their approaches. The tasks vary from researcher to researcher in objective, underlying simulator, and representation of the task. This makes the comparison of algorithms difficult, because they are usually tested in different circumstances. This project seeks to create a standard set of tasks for researchers to use when evaluating their approaches to manipulating deformable objects. These tasks will cover a large variety of manipulation challenges. Additionally, we will benchmark a number of state-of-the-art algorithms to create a baseline to measure the progress made in the field. Environments were developed relating to the manipulation of cloth, a deformable object. The TD3 reinforcement learning algorithm was applied on these environments. Initial attempts resulted in action saturation and poor learning results. This problem was alleviated by introducing weight decay to the stochastic gradient descent optimization. A comparison of reinforcement learning results from training with the TD3 algorithm using different parameters and observation spaces will be presented.

Vaidehi Srinivas
vaidehis
Advisor(s): Anupam Gupta
Title: Simpler Approximations for the Network Steiner-Tree Problem
Presentation Time: 3:40PM
Abstract: The Network Steiner-Tree problem is a well-known problem in combinatorial optimization. The input is an undirected graph G = (V, E) with non-negative edge weights, and a set of terminals, S ⊆ V . The goal is to output a minimum cost tree T ⊆ G, that spans all of S. In general, this problem is known to be NP-complete, so we study polynomial-time approximation algorithms. Some polynomial-time approximation results for this problem include an 11/6-approximation, found by Zelikovsky in 1993. In 2005, Robins and Zelikovsky found an algorithm that achieves a ≈ 1.55-approximation. These algorithms use greedy strategies to make a set of incremental improvements to the result. We investigate whether the algorithms can be simplified by reducing to submodular function optimization under knapsack constraints, and applying Sviridenko’s 2004 cost-benefit greedy algorithm, which is known to give a 1 − 1/e approximation.

Zachary Sussman
zsussman
Advisor(s): Pravesh Kothari
Title: Outlier-Robust Linear and ReLU Regression
Presentation Time: 2:20PM
Abstract: The field of robust estimation is concerned with the estimation of statistical quantities from datasets where a certain fraction of the points has been corrupted by an adversary. Recently, there have been some breakthroughs in the field of robust estimation using methods like sum-of-squares and adaptive thresholding. An important desirable property of statistical estimators is consistency: that the estimation error converges to 0 as the number of samples tends to infinity. When the outliers are allowed to be fully adversarial, any estimator has to necessarily incur an error that remains non-zero even in the infinite sample limit. In this thesis, we investigate a previously studied restriction on the outliers to be "oblivious" that allows consistent estimation to be statistically possible. Prior works have shown efficient estimators for robust linear regression in this setting. In this work, we show a simplified algorithm and extend it to more expressive and practically important classes such as Rectified Linear Units.

Peter Wu
peterw1
Advisor(s): Louis-Philippe Morency
Title: Multimodal Representation Learning
Presentation Time: 12:50PM
Abstract: Data that humans perceive in the world are inherently composed of multiple modalities, for example vision, audio, and natural language. Machine learning (ML) models thus should be able to interpret data from multiple modalities in order to make full use of available data in the world. In this work, we investigate how to enable ML models to effectively handle complex multimodal data by creating solutions for two challenging tasks: synthesizing speech from text and classifying data from an unseen modality. We draw on novel meta learning and representation learning techniques to devise algorithms that can leverage information from other modalities to improve model performance.

Yue (Holmes) Wu
ywu5
Advisor(s): Eric Xing and Zhiting Hu
Title: Posterior Regulation GAN
Presentation Time: 3:00PM
Abstract: Generative Adversarial Networks (GANs) have been extensively studied from a variety of perspectives, such as the game-theoretic viewpoint, energy-based modeling, and minimizing Wasserstein distance. Despite great success in the vision domain, GANs still suffer from training instability. The instability and inefficiency of GAN training is most significant in text generation due to its discrete nature. To promote training stability, we develop a new perspective of GANs based on the connections with posterior regularization. The proposed viewpoint naturally results in two novel revisions to the previous GANs formulations, including: 1) in the phase of discriminator learning, a more effective sampling mechanism for re-weighting fake samples, and 2) in the phase of generator learning, a relative entropy regularization for stabilizing the updates. We show the new formulation is compatible with the latest theoretical guarantees on informative gradients. Empirical studies show our approach achieves state-of-the-art performance in both text manipulation and image generation.

Joshua Zhanson
jzhanson
Advisor(s): Ruslan Salakhutdinov
Title: Investigating and Robustifying Proximal Policy Optimization
Presentation Time: 12:10PM
Abstract: Policy gradient optimization algorithms such as Proximal Policy Optimization (PPO) in deep reinforcement learning suffer from high variance and poor sample efficiency. We show that PPO gradient samples exhibit a fundamental distributional property, "heavy-tailedness", which enables the use of estimation techniques from robust statistics to improve learning speed and stability.