United States

Given a square matrix with noisy dissimilarity measures between pairs of data samples, the metric nearness model computes the best approximation of the matrix from a set of valid distance metrics. Despite its wide applications in machine learning and data processing tasks, the model faces non-trivial computational requirements in seeking the solution due to the large number of metric constraints associated with the feasible region. To tackle the challenge and improve the model&#39;s scalability and applicability, our work designed a practical approach that operates in two stages. The first stage computes a fast yet high-quality approximate solution from a set of isometrically embeddable metrics, which is further improved by an effective heuristic. The second stage refines the approximate solution with the Halpern-Lions-Wittmann-Bauschke projection algorithm, which converges quickly to the optimal solution. In empirical evaluations, the proposed approach runs at least an order of magnitude faster than the state-of-the-art solutions, with significantly improved scalability, complete conformity to constraints, less memory consumption, and other desirable features in real applications.

AAAI 2023

Metric Nearness Made Practical

metric nearness

large-scale learning

convex optimization

The purpose of the AAAI conference is to promote research in artificial intelligence (AI) and scientific exchange among AI researchers, practitioners, scientists, and engineers in affiliated disciplines. 

AAAI 2022

Given a square matrix with noisy dissimilarity measures between pairs of data samples, the metric nearness model computes the best approximation of the matrix from a set of valid distance metrics. Despite its wide applications in machine learning and data processing tasks, the model faces non-trivial computational requirements in seeking the solution due to the large number of metric constraints associated with the feasible region. To tackle the challenge and improve the model's scalability and applicability, our work designed a practical approach that operates in two stages. The first stage computes a fast yet high-quality approximate solution from a set of isometrically embeddable metrics, which is further improved by an effective heuristic. The second stage refines the approximate solution with the Halpern-Lions-Wittmann-Bauschke projection algorithm, which converges quickly to the optimal solution. In empirical evaluations, the proposed approach runs at least an order of magnitude faster than the state-of-the-art solutions, with significantly improved scalability, complete conformity to constraints, less memory consumption, and other desirable features in real applications.

poster

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-23 is the Thirty-Seventh AAAI Conference on Artificial Intelligence. The theme of this conference is to create collaborative bridges within and beyond AI. Like previous AAAI conferences, AAAI-23 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and two new activities: a Bridge Program and a Lab Program. Many of these activities are tailored to the theme of bridges and all are selected according to the highest standards, with additional programs for students and young researchers. 
AAAI is providing you with a conference planner, which you can use to help organize your itinerary of activities. This includes talks to attend in person, talks to attend remotely, breaks with colleagues and your site seeing activities. To access this conference planner, please go to [https://aaai-2023.takemobi.io](https://aaai-2023.takemobi.io).

In order to access this site, you need to register. If you haven't already, please register [here](https://aaai.org/Conferences/AAAI-23/registration/).


The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines.

 We present a novel method for exemplar-based image translation, called matching interleaved diffusion models (MIDMs). Most existing methods for this task were formulated as GAN-based matching-then-generation framework. However, in this framework, matching errors induced by the difficulty of semantic matching across cross-domain, e.g., sketch and photo, can be easily propagated to the generation step, which in turn leads to the degenerated results. Motivated by the recent success of diffusion models, overcoming the shortcomings of GANs, we incorporate the diffusion models to overcome these limitations. Specifically, we formulate a diffusion-based matching-and-generation framework that interleaves cross-domain matching and diffusion steps in the latent space by iteratively feeding the intermediate warp into the noising process and denoising it to generate a translated image. In addition, to improve the reliability of diffusion process, we design confidence-aware process using cycle-consistency to consider only confident regions during translation. Experimental results show that our MIDMs generate more plausible images than state-of-the-art methods.

MIDMs: Matching Interleaved Diffusion Models for Exemplar-based Image Translation

The marginal distribution shift of covariates from training to test phase, named covariate-shift, is prone to make a predictive model with model misspecification perform unstably across agnostic testing data. The recent literature on invariant learning attempts to learn an invariant predictor from heterogeneous environments. However, the performance of the learned predictor depends heavily on the availability and quality of provided environments. In this paper, we propose a simple and effective non-parametric method for generating heterogeneous environments via Random Sample Weighting (RSW). Given the training dataset from a single source environment, we randomly generate a set of covariate-determining sample weights and use each weighted training distribution to simulate an environment. We theoretically show that under appropriate conditions, such random sample weighting can produce sufficient heterogeneity to be exploited by common invariance constraints to find invariant variables for stable prediction under covariate shifts. Extensive experiments on both simulated and real-world datasets clearly validate the effectiveness of our method.

Covariate-Shift Generalization via Random Sample Weighting

Transformer-based autoregressive (AR) methods have achieved appealing performance for varied sequence-to-sequence generation tasks, e.g., neural machine translation, summarization, and code generation, but suffer from low inference efficiency. To speed up the inference stage, many non-autoregressive (NAR) strategies have been proposed in the past few years. Among them, the conditional masked language model (CMLM) is one of the most versatile frameworks, as it can support many different sequence generation scenarios and achieve very competitive performance on these tasks. In this paper, we further introduce a simple yet effective adaptive masking over masking strategy to enhance the refinement capability of the decoder and make the encoder optimization easier. Experiments on \textbf{3} different tasks (neural machine translation, summarization, and code generation) with \textbf{15} datasets in total confirm that our proposed simple method achieves significant performance improvement over the strong CMLM model. Surprisingly, our proposed model yields state-of-the-art performance on neural machine translation (\textbf{34.62} BLEU on WMT16 EN$\to$RO, \textbf{34.82} BLEU on WMT16 RO$\to$EN, and \textbf{34.84} BLEU on IWSLT De$\to$En) and even better performance than the \textbf{AR} Transformer on \textbf{7} benchmark datasets with at least \textbf{2.2$\times$} speedup. Our anonymous code is available at GitHub\footnote{\url{ https://github.com/amom-nar/AMOM}}.

AMOM: Adaptive Masking over Masking for Conditional Masked Language Model

Existing knowledge graph (KG) embedding models have primarily focused on static KGs. However, real-world KGs do not remain static, but rather evolve and grow in tandem with the development of KG applications. Consequently, new facts and previously unseen entities and relations continually emerge, necessitating an embedding model that can quickly learn and transfer new knowledge through growth. Motivated by this, we delve into an expanding field of KG embedding in this paper, i.e., lifelong KG embedding. We consider knowledge transfer and retention of the learning on growing snapshots of a KG without having to learn embeddings from scratch. The proposed model includes a masked KG autoencoder for embedding learning and update, with an embedding transfer strategy to inject the learned knowledge into the new entity and relation embeddings, and an embedding regularization method to avoid catastrophic forgetting. To investigate the impacts of different aspects of KG growth, we construct four datasets to evaluate the performance of lifelong KG embedding. Experimental results show that the proposed model outperforms the state-of-the-art inductive and lifelong embedding baselines.

Lifelong Embedding Learning and Transfer for Growing Knowledge Graphs

The prevalence of region-based urban data has enabled us to explore the correlations of regions for better urban planning and smart-city solutions, in which region embedding plays an important role. However, this is a challenging problem considering the following two factors: different city data for region embedding and the effectiveness for various downstream applications. 
In this paper, we propose a novel framework, named \textbf{HREP} (\textbf{H}eterogeneous \textbf{R}egion \textbf{E}mbedding with \textbf{P}rompt learning), considering both intra-region and inter-region correlations, which includes two major modules, \textbf{H}eterogeneous graph learning for \textbf{R}egion \textbf{E}mbedding (\textbf{HRE}) and prompt learning for different downstream tasks. In the HRE module, we construct a region heterogeneous graph according to three categories of data, capturing inter-region contexts, e.g., human mobility and region geographic neighbors, and intra-region contexts, e.g., POI information. Specially, we design a \textit{relation-aware graph embedding} to learn region embedding and relation embeddings of edge types based on the heterogeneous graph. Then we introduce self-attention to capture the global correlation of regions. Moreover, we develop a \textit{attention-based fusion module} to integrate sharing information among different types of correlations. 
To enable region embedding to be effectively utilized in downstream tasks, we migrate the prompt learning, i.e., continuous prompt
prefix-tuning, which can guide the learning of downstream tasks, leading to better prediction results. Extensive experimental results on real-world datasets show that our model outperforms all state-of-the-art methods dramatically.

Heterogeneous Region Embedding with Prompt Learning

In many applications we want to influence the decisions of independent agents by designing incentives for their actions. We revisit a fundamental problem in this area, called Game Implementation: Given a game in standard form and a set of desired strategies, can we design a set of payment promises such that, if the players take the payment promises into account, then all undominated strategies are desired? Furthermore, we aim to minimize the cost, that is, the worst-case amount of payments.

We study the tractability of computing such payment promises and determine more closely what obstructions we may have to overcome in doing so. We show that Game Implementation is NP-hard even for two players, solving in particular a long open question (Eidenbenz et al. 2011). This suggests more restrictions are necessary to obtain tractability. We thus study the regime in which players have only a small constant number of strategies and obtain the following. First, this case remains NP-hard even if each player's utility depends only on three others. Second, we repair a flawed efficient algorithm for the case of both small number of strategies and small number of players. Among further results, we characterize sets of desired strategies that can be implemented at zero cost as a kind of stable core of the game.

Game Implementation: What are the Obstructions?

Digital advertising constitutes one of the main revenue sources for online platforms. In recent years, some advertisers tend to adopt auto-bidding tools to facilitate advertising performance optimization, making the classical \emph{utility maximizer} model in auction theory not fit well. Some recent studies proposed a new model, called \emph{value maximizer}, for auto-bidding advertisers with return-on-investment (ROI) constraints. However, the model of either utility maximizer or value maximizer could only characterize partial advertisers in real-world advertising platforms. In a mixed environment where utility maximizers and value maximizers coexist, the truthful ad auction design would be challenging since bidders could manipulate both their values and affiliated classes, leading to a multi-parameter mechanism design problem. In this work, we address this issue by proposing a payment rule which combines the corresponding ones in classical VCG and GSP mechanisms in a novel way. Based on this payment rule, we propose a truthful auction mechanism with an approximation ratio of $2$ on social welfare, which is close to the lower bound of at least $\frac{5}{4}$ that we also prove. The designed auction mechanism is a generalization of VCG for utility maximizers and GSP for value maximizers.

Utility Maximizer or Value Maximizer: Mechanism Design for Mixed Bidders in Online Advertising

Time or money? That is a question! In this paper, we consider this dilemma in the pricing regime, in which we try to find the optimal pricing scheme for identical items with heterogenous time-sensitive buyers. We characterize the revenue-optimal solution and propose an efficient algorithm to find it in a Bayesian setting. Our results also demonstrate the tight ratio between the value of wasted time and the seller's revenue, as well as that of two common-used pricing schemes, the $k$-step function and the fixed pricing. To explore the nature of the optimal scheme in the general setting, we present the closed forms over the product distribution and show by examples that positive correlation between the valuation of the item and the cost per unit time could help increase revenue. To the best of our knowledge, it is the first step towards understanding the impact of the time factor as a part of the buyer cost in pricing problems, in the computational view.

Optimal Pricing Schemes for Identical Items with Time-Sensitive Buyers

I will share experiences from working on organ exchanges for the last 18 years, ranging from market designs to new optimization algorithms to large-scale fielding of the techniques and even to computational policy optimization. Originally in kidney exchange, patients with kidney disease obtained compatible donors by swapping their own willing but incompatible donors. I will discuss many modern generalizations of this basic idea. For one, I will discuss never-ending altruist donor chains that have become the main modality of kidney exchanges worldwide and have led to over 10,000 life-saving transplants. Since 2010, our algorithms have been running the national kidney exchange for United Network for Organ Sharing, which has grown to include 80% of the transplant centers in the US. Our algorithms autonomously make the transplant plan each week for that exchange, and have been used by two private exchanges before that. I will summarize the state of the art in algorithms for the batch problem, approaches for the dynamic problem where pairs and altruists arrive and depart, techniques that find the highest-expected-quality solution under the real challenge of unforeseen pre-transplant incompatibilities, algorithms for pre-match compatibility testing, and approaches for striking fairness-efficiency tradeoffs. I will describe the FUTUREMATCH framework that combines these elements and uses data and supercomputing to optimize the policy from high-level human value judgments. The approaches therein may be able to serve as ways of designing policies for many kinds of complex real-world AI systems. I will also discuss the idea of liver lobe exchanges and cross-organ exchanges, and how they have started to emerge for real.

Modern Organ Exchanges: Market Designs, Algorithms, and Opportunities

I share insights on the interaction of humans and AI to jointly solve end-to-end complex problems. The talk is based on my experience with research and engineering of real autonomous mobile service robots, and AI in the finance domain. I will illustrate the integration of perception (data), cognition (reasoning and learning), and action (execution and feedback). And I will focus on several components, including AI to effectively discover and standardize data, for behavior understanding, to simulate and generate synthetic data, to learn from data, principles, and experience, and to provide trustful explanations.

Downloads

Next from AAAI 2023

MIDMs: Matching Interleaved Diffusion Models for Exemplar-based Image Translation

Similar lecture

Subset Approximation of Pareto Regions with Bi-Objective A*