USC at AAAI ’21: Algorithmic Fairness, Electoral College Strategy, De-Biasing Machine Learning

| February 4, 2021

Notable research includes work on algorithmic fairness for pressing social issues and resource allocation in presidential campaigns.

USC researchers present 21 papers at AAAI 2021. Image/iStock.

USC researchers present 21 papers at AAAI 2021. Image/iStock.

At the 35th AAAI Conference on Artificial Intelligence, held virtually on Feb. 2-9, USC researchers will present 24 papers spanning a variety of topics including multi-agent pathfinding, generative models, algorithmic fairness, computational analyses of the electoral college and more.

Run by the largest professional organization in the field, the AAAI conference aims to promote research in artificial intelligence and scientific exchange among AI researchers, practitioners, scientists, and engineers in affiliated disciplines.

Professors Yan Liu and Sven Koenig.

AAAI 2021 received a record-high 9034 submissions compared to last year’s 8800. More than 7911 papers went to review and a total of 1692 papers were accepted at a rate of 21%, just 0.4 percent higher than last year’s 20.6%.

This year, USC computer science professors Yan Liu and Sven Koenig both serve in key leadership positions, as associate program committee chair and conference committee chair, respectively.

“The annual meeting of the Association for the Advancement of Artificial Intelligence (AAAI) is one of the world’s leading conferences in artificial intelligence,” said Liu. “USC’s strong presence at AAAI-21 highlights the high-quality AI research work conducted at the university.”

Adds Koenig: “The AAAI conference is—together with IJCAI—the top conference that covers all areas of artificial intelligence. USC has traditionally been very strong in artificial intelligence, both in terms of the number of researchers in different areas of artificial intelligence and the quality of their research, which is reflected in the papers that will be presented at AAAI 2021.”

USC Research Professor Yolanda Gil is also past president of AAAI and awards committee chair. At this year’s conference, Gil will award a new $1 million prize for AI for the benefit of humanity, honoring individuals whose work in the field has had a transformative impact on society. In addition to the numerous papers presented at this year’s conference, USC Research Professor Pedro Szekely will co-organize a workshop on commonsense knowledge in AI.

Research Spotlights, AAAI 2021

GAN-Generated Super Mario Levels

Generative adversarial network (GAN) models can automatically generate content, for instance images or video game levels, in a given style or aesthetic. But these models are typically notoriously hard to control. “For example, while we can generate levels that look similar to some human-authored examples, it is challenging to generate levels that have a desired number of enemies, or a number of ‘sky’ tiles,” said Stefanos Nikolaidis, an assistant professor of computer science.

In this paper, Nikolaidis and his co-authors show that a recent class of algorithms, named “quality diversity algorithms,” can be used to simultaneously generate video game levels in the Super Mario Games Series that are stylistically similar to human-authored examples, while having diverse features of interest. This content can be useful in many domains beyond video games, for example, to generate different walking gaits for robots in varied terrain.

Below: Playthrough of an automatically generated level, featuring 93 upper tiles and 3 enemies. 

 

Algorithmic Fairness for Public Health 

PhD student Aida Rahmattalabi.

Several behavioral, social, and public health interventions—such as suicide- and HIV-prevention, or preparing for natural disasters—leverage social network information to maximize outreach. The idea is to select a few key people to train, so that they share this information with the rest of the community.

Algorithms can help choose “peer leaders” or “influencers” for such interventions. But traditional algorithms for “influence maximization” have not been designed with these interventions in mind. As a result, they may disproportionately exclude minority communities from the intervention’s benefits. Making them fairer, however, can can lead to significant loss in efficiency, which is one of the major drawbacks of existing methods.

To address shortcomings in “fair influence maximization,” PhD computer science student Aida Rahmattalabi and her co-authors describe the properties that this kind of algorithm should satisfy, and develop an efficient algorithm for influencer choices. Extensive experiments on synthetic and real-world datasets, including a case study on landslide risk management, demonstrate the efficacy of the proposed framework.

Electoral College Strategy

Shang-Hua Teng.

The recent fiercely-fought US presidential elections have drawn attention to both the democratic fairness and strategic challenges of the Electoral College. A paper co-authored by Professor Shang-Hua Teng focuses on the latter aspect through a computational and game-theoretical lens. Teng is a University Professor of computer science and mathematics and Seeley G. Mudd Professor of Engineering.

Presidential campaigns are a competition across multiple political battlegrounds, one in each state. During this process, each candidate’s team must strategically allocate resources, such as campaign budgets, candidate’s time, on-the-ground staff and policy decisions. The ultimate goal: to maximize the total number of the electoral votes on election day.

In this paper, Teng and his colleagues aim to understand the difficulty of competition over multiple battlegrounds, involving allocation of complex, multifaceted resources, and to develop efficient algorithms for finding best possible solutions. “By formulating multi-state campaign as a two-player game, rather than merely as a one-player strategic allocation, the research also hopes to capture the outcome of the game, which could be important for election prediction,” said Teng. “We hope in theory, the work could lead to something useful for future candidates.”

De-Biasing Machine Learning

Machine learning is increasingly ubiquitous in daily life, affecting small things like what websites and products you see online, to big things like who is approved for a loan or gets hired. Machine learning relies on training data, which may be biased, producing unfair decisions and favoring one group over the other.

“In the job hiring process, you could hide all the candidates’ information and choose with a coin flip,” said the paper’s lead author Umang Gupta, a PhD student advised by Research Associate Professor Greg Ver Steeg. “But, while fair, this seems counter-productive because we end up discarding all the signals that could help pick the best person for the job.”

Instead, the researchers, propose an automated machine learning approach for controlling which information is useful for a task, while limiting the amount of information that could be used to discriminate against a particular group in the wrong hands.

“For instance, if we know that a candidate went to Wellesley (a liberal arts college for women), one may use this information to discriminate against female candidates,” said Gupta. “On the other hand, we can restrict the information to ‘attended a well-regarded liberal arts university’ This makes it easier to select more skilled employees for the job while only giving a small hint about the gender of the applicant (because more women than men go to college).”

Below: PhD student Umang Gupta presents a one-minute explainer video for his paper on fairness in information theory. 

 

Multi-Agent Pathfinding

Multi-Agent Path Finding (MAPF) is the problem of computing collision-free paths for a team of agents from their current locations to given destinations. MAPF is a core part of a number of autonomous systems, like driverless vehicles, drone swarms, and even video game character AI. Several researchers are presenting work in this area, including three papers co-authored by Sven Koenig, who has been working on this topic for several years, Nora Ayanian and Bistra Dilkina.

“We designed an algorithm selector called MAPFAST using deep learning techniques to help people choose the best pathfinding algorithm to use depending on different problems,” said Jingyao Ren, a PhD student advised by Nora Ayanian.

“It can be applied to multi-robot pathfinding applications and improve the overall solving speed. For example, Amazon uses robots in their warehouses to deliver items which requires to calculate collision free paths for these robots, MAPFAST will help to choose the fastest and best algorithm to use.”

View the list of accepted papers below:

EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding
Jiaoyang Li (University of Southern California); Wheeler Ruml (University of New Hampshire); Sven Koenig (University of Southern California)

Lifelong Multi-Agent Path Finding in Large-Scale Warehouses
Jiaoyang Li (University of Southern California); Andrew Tinka (Amazon Robotics); Scott Kiesel (Amazon Robotics); Joseph W Durham (Amazon Robotics); T. K. Satish Kumar (University of Southern California); Sven Koenig (University of Southern California)

Knowledge-driven Self-supervision for Zero-shot Commonsense Question Answering
Kaixin Ma (CMU); Filip Ilievski (University of Southern California/ISI); Jonathan M Francis (Carnegie Mellon University; Bosch Research Pittsburgh); Yonatan Bisk; Eric Nyberg (CMU); Alessandro Oltramari (Bosch Research Pittsburgh)

Subtype-aware Dynamic Unsupervised Domain Adaptation
Xiaofeng Liu (CMU); Xiongchang Liu (Harvard); Wenxuan Ji (Nankai); Bo Hu (Harvard); Fangxu Xing (Harvard); Jun Lu (BIDMC); Jane You (HK); C.-C. Jay Kuo (University of Southern California); Georges El Fakhri (Massachusetts General Hospital / Harvard Medical School); Jonghye Woo (Massachusetts General Hospital / Harvard Medical School)

Learning to Resolve Conflicts for Multi-Agent Path Finding with Conflict-Based Search
Taoan Huang (University of Southern California); Sven Koenig (University of Southern California); Bistra Dilkina (University of Southern California)

f-Aware Conflict Prioritization & Improved Heuristics For Conflict-Based Search
Eli Boyarski (Ben-Gurion University of the Negev); Ariel Felner (BGU); Pierre Le Bodic (Monash University); Daniel Harabor (Monash University); Peter Stuckey (Monash University); Sven Koenig (University of Southern California)

Scalable and Safe Multi-Agent Motion Planning with Nonlinear Dynamics and Bounded Disturbances
Jingkai Chen (MIT); Jiaoyang Li (University of Southern California); Chuchu Fan (MIT); Brian C Williams (Massachusetts Institute of Technology)

Unsupervised Model Adaptation for Continual Semantic Segmentation
Serban Stan (University of Southern California); Mohammad Rostami (University of Southern California)

A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraints
Krishna C Kalagarla (University of Southern California); Rahul Jain (University of Southern California); Pierluigi Nuzzo (University of Southern California)

Exacerbating Algorithmic Bias through Fairness Attacks
Ninareh Mehrabi (University of Southern California/ISI); Muhammad Naveed (University of Southern California); Fred Morstatter (University of Southern California/ISI); Aram Galstyan (University of Southern California/ISI)

A Hybrid Probabilistic Approach for Table Understanding
Kexuan Sun (University of Southern California); Harsha Rayudu (University of Southern California); Jay Pujara (University of Southern California)

Learning from History: Modeling Temporal Knowledge Graphs with Sequential Copy-Generation Networks
Cunchao Zhu (National University of Defense Technology); Muhao Chen (University of Southern California/UPenn); Changjun Fan (National University of Defense Technology); Guangquan Cheng (National University of Defense Technology); Yan Zhang (EPITA)

Symmetry Breaking for k-Robust Multi-Agent Path Finding
Zhe Chen (Monash University); Daniel Harabor (Monash University); Jiaoyang Li (University of Southern California); Peter Stuckey (Monash University)

Illuminating Mario Scenes in the Latent Space of a Generative Adversarial Network
Matthew Fontaine (University of Southern California); Ruilin Liu (University of Southern California); Ahmed Khalifa (New York University); Jignesh Modi (University of Southern California); Julian Togelius (New York University); Amy K. Hoover (New Jersey Institute of Technology); Stefanos Nikolaidis (University of Southern California)

Document-Level Relation Extraction with Adaptive Thresholding and Localized Context Pooling
Wenxuan Zhou (University of Southern California); Kevin Huang (JD AI Research); Tengyu Ma (Stanford); Jing Huang (JD.COM)

IsoBN: Fine-Tuning BERT with Isotropic Batch Normalization
Wenxuan Zhou (University of Southern California); Bill Yuchen Lin (University of Southern California); Xiang Ren (University of Southern California)

Classification with Strategically Withheld Data
Anilesh K Krishnaswamy (Duke University); Haoming Li (University of Southern California); David Rein (Duke); Hanrui Zhang (Duke University); Vincent Conitzer (Duke)

Controllable Guarantees for Fair Outcomes via Contrastive Information Estimation
Umang Gupta (University of Southern California/ISI); Aaron M Ferber (University of Southern California); Bistra Dilkina (University of Southern California); Greg Ver Steeg (University of Southern California/ISI)

DeepPseudo: Pseudo value based deep learning models for competing risk analysis
Md Mahmudur Rahman (University of Maryland Baltimore County); Koji Matsuo (University of Southern California); Shinya Matsuzaki (Osaka University); Sanjay Purushotham (University of Maryland, Baltimore County)

Computational Analyses of the Electoral College: Campaigning Is Hard But Approximately Manageable
Sina Dehghani (IPM); Hamed Saleh (University of Maryland); Saeed Seddighin (Toyota Technological Institute); Shanghua Teng (University of Southern California)

Visual Pivoting for (Unsupervised) Entity Alignment
Fangyu Liu (University of Cambridge); Muhao Chen (University of Southern California/UPenn); Dan Roth (UPenn); Nigel Collier (University of Cambridge)

Clinical Temporal Relation Extraction with Probabilistic Soft Logic Regularization and Global Inference
Yichao Zhou (UCLA); Yu Yan (UCLA); Rujun Han (University of Southern California); J. Harry Caufield (University of California, Los Angeles); Kai-Wei Chang (kwchang@cs.ucla.edu); Yizhou Sun (UCLA); Peipei Ping (University of California, Los Angeles); Wei Wang (UCLA)

MELINDA: A Multimodal Dataset for Biomedical Experiment Method Classification
Te-Lin Wu (University of California, Los Angeles (UCLA); Shikhar Singh (University of Southern California); Sayan Paul (Intuit); Gully A Burns (Chan Zuckerberg Initiative); Nanyun Peng

Fair Influence Maximization: a Welfare Optimization Approach
Aida Rahmattalabi (University of Southern California); Shahin Jabbari (Harvard University); Himabindu Lakkaraju (Harvard); Phebe Vayanos (University of Southern California); Max Izenberg (Pardee RAND Graduate School); Ryan Brown (RAND Corporation); Eric Rice (University of Southern California); Milind Tambe (Harvard University)

MAPFAST: A Deep Algorithm Selector for Multi-Agent Path Finding using Shortest Path Embedding (Poster)
Jingyao Ren (University of Southern California), Vikraman Sathiyanarayanan (University of Southern California), Eric Ewing (University of Southern California), Baskin Senbaslar (University of Southern California), Nora Ayanian (University of Southern California)

Learning-Based Travel Prediction in Urban Road Network Resilience Optimization (Workshop paper)
Guancheng Qiu (University of Southern California), Amrita Gupta (University of Southern California), Caleb Robinson (University of Southern California), Shuo Feng (University of Southern California) and Bistra Dilkina (University of Southern California)

Clinical trial of an AI-augmented intervention for HIV prevention in youth experiencing homelessness (Workshop paper)
Bryan Wilder (Harvard University), Laura Onasch-Vera (University of Southern California), Graham Diguiseppi (University of Southern California), Robin Petering (Lens Co), Chyna Hill (University of Southern California), Amulya Yadav (Pennsylvania State University), Eric Rice (University of Southern California), Milind Tambe (Harvard University)

 

Share This Story