Select a calendar:
Filter April Events by Event Type:
SUNMONTUEWEDTHUFRISAT
University Calendar
Events for April
-
Nam Ma (USC), PhD Defense
Tue, Apr 09, 2013 @ 10:00 AM - 12:00 PM
Thomas Lord Department of Computer Science
University Calendar
Committee:
Aiichiro Nakano
Viktor K. Prasanna (Chairman)
Cauligi S. Raghavendra
Title: Scalable Exact Inference in Probabilistic Graphical Models on Multi-core Platforms
Abstract:
The recent switch to multi-core computing and the emergence of machine learning applications offer many opportunities for parallelization. A fundamental challenge is how to achieve scalability with the increasing number of cores. It is especially challenging for machine learning problems that have graph computational structure.
This thesis explores parallelism for exact inference in probabilistic graphical models to achieve scalable performance on multi-core platforms. Exact inference is widely used in probabilistic reasoning and machine learning. It also represents a large class of graph computations that have sophisticated computational patterns with large data sets. We propose parallel techniques to extract and exploit parallelism efficiently at multiple levels in the input graph.
• We first exploit parallelism available from the input graph using multithreading and task scheduling. At the node level, we explore data parallelism for the computational operations within a node. Data layout and data parallel algorithms are proposed for such node level computations. At the graph level, task parallelism is explored using directed acyclic graph (DAG) model. DAG scheduling is employed to efficiently map the tasks in the DAG to the hardware cores.
• In many cases, the input graph provides insufficient parallelism. To expose more parallelism, we study a relationship called 'weak dependency' between the tasks in a DAG. A novel DAG scheduling scheme is developed to exploit weak dependency for parallelism. In addition, pointer jumping technique is employed for exact inference when the input graph offers very limited parallelism due to its chain-like structure. With such explorations, a given fixed-size problem can still achieve high scalability with the increasing number of cores.
• In order to avoid the implementation complexity of many parallel techniques, we study the use of MapReduce as a high level programming model for exact inference. Our MapReduce-based algorithms for exact inference can also be applied for a class of graph computations with data dependency.
We implement and evaluate our techniques on state-of-the-art multi-core systems and demonstrate their scalability for a variety of input graphs.Location: Ronald Tutor Hall of Engineering (RTH) - 324
Audiences: Everyone Is Invited
Contact: Assistant to CS chair
-
PhD Defense - Jason Tsai
Tue, Apr 30, 2013 @ 12:00 AM - 02:00 PM
Thomas Lord Department of Computer Science
University Calendar
Date: April 30, 2013
Venue: RTH 526
Time: 12:00pm
PhD Candidate: Jason Tsai
Title: Protecting Networks Against Diffusive Attacks: Game-Theoretic Resource Allocation for Contagion Mitigation
Committee:
Milind Tambe (chair)
Stacy Marsella
Bhaskar Krishnamachari
Sha Yang
Matthew McCubbins (outside member)
Emma Bowring
Abstract:
Many real-world situations involve attempts to spread influence through a social network. For example, viral marketing is when a marketer selects a few people to receive some initial advertisement in the hopes that these `seeds' will spread the news. Even peacekeeping operations in one area have been shown to have a contagious effect on the neighboring vicinity. Each of these domains also features multiple parties seeking to maximize or mitigate a contagious effect by spreading its own influence among a select few seeds, naturally yielding an adversarial resource allocation problem. My work models the interconnected network of people as a graph and develops algorithms to optimize resource allocation in these networked competitive contagion scenarios.
Game-theoretic resource allocation in the past has not considered domains with both a networked structure and contagion effects, rendering them unusable in critical domains such as rumor control, counterinsurgency, and crowd management. Networked domains without contagion effects already present computational challenges due to the large scale of the action space. To address this issue, my first contribution proposed efficient game-theoretic allocation algorithms for the graph-based urban road network domain. This work still provides the only polynomial-time algorithm for allocating vehicle checkpoints through a city, giving law enforcement officers an efficient tool to combat terrorists making their way to potential points of attack. Second, I have provided the first game-theoretic treatment for contagion mitigation in social networks and given practitioners the first principled techniques for such vital concerns as rumor control and counterinsurgency. Finally, I extended my work on game-theoretic contagion mitigation to address uncertainty about the network structure to find that, contrary to what evidence and intuition suggest, heuristic sampling approaches provide near-optimal solutions across a wide range of generative graph models and uncertainty models. Thus, despite extreme practical challenges in attaining accurate social network information, my techniques remain near-optimal across numerous forms of uncertainty in multiple synthetic and real-world graph structures.
Beyond optimization of resource allocation, I have further studied contagion effects to understand the effectiveness of such resources. First, I created an evacuation simulation, ESCAPES, to explore the interaction of pedestrian fear contagion and authority fear mitigation during an evacuation. Second, using this simulator, I have advanced the frontier in contagion modeling by developing empirical evaluation methods for comparing and calibrating computational contagion models that are critical in crowd simulations and evacuation modeling. Finally, I have also conducted an examination of agent-human emotional contagion to inform the rising use of simulations for personnel training in emotionally-charged situations.
Location: Ronald Tutor Hall of Engineering (RTH) - 526
Audiences: Everyone Is Invited
Contact: Lizsl De Leon
