OpenRaiser/Intern-Atlas huggingface dataset:
Event Collapse in Contrast Maximization Frameworks
Venue: arXiv cs.CV 2022
Year: 2022

Contrast maximization (CMax) is a framework that provides state-of-the-art results on several event-based computer vision tasks, such as ego-motion or optical flow estimation. However, it may suffer from a problem called event collapse, which is an undesired solution where events are warped into too few pixels. As prior works have largely ignored the issue or proposed workarounds, it is imperative to analyze this phenomenon in detail. Our work demonstrates event collapse in its simplest form and proposes collapse metrics by using first principles of space-time deformation based on differential geometry and physics. We experimentally show on publicly available datasets that the proposed metrics mitigate event collapse and do not harm well-posed warps. To the best of our knowledge, regularizers based on the proposed metrics are the only effective solution against event collapse in the experimental settings considered, compared with other methods. We hope that this work inspires further research to tackle more complex warp models.
MACFE: A Meta-learning and Causality Based Feature Engineering Framework
Venue: arXiv cs.LG 2022
Year: 2022

Feature engineering has become one of the most important steps to improve model prediction performance, and to produce quality datasets. However, this process requires non-trivial domain-knowledge which involves a time-consuming process. Thereby, automating such process has become an active area of research and of interest in industrial applications. In this paper, a novel method, called Meta-learning and Causality Based Feature Engineering (MACFE), is proposed; our method is based on the use of meta-learning, feature distribution encoding, and causality feature selection. In MACFE, meta-learning is used to find the best transformations, then the search is accelerated by pre-selecting "original" features given their causal relevance. Experimental evaluations on popular classification datasets show that MACFE can improve the prediction performance across eight classifiers, outperforms the current state-of-the-art methods in average by at least 6.54%, and obtains an improvement of 2.71% over the best previous works.
Online Learning in Supply-Chain Games
Venue: arXiv cs.GT 2022
Year: 2022

We study a repeated game between a supplier and a retailer who want to maximize their respective profits without full knowledge of the problem parameters. After characterizing the uniqueness of the Stackelberg equilibrium of the stage game with complete information, we show that even with partial knowledge of the joint distribution of demand and production costs, natural learning dynamics guarantee convergence of the joint strategy profile of supplier and retailer to the Stackelberg equilibrium of the stage game. We also prove finite-time bounds on the supplier's regret and asymptotic bounds on the retailer's regret, where the specific rates depend on the type of knowledge preliminarily available to the players. In the special case when the supplier is not strategic (vertical integration), we prove optimal finite-time regret bounds on the retailer's regret (or, equivalently, the social welfare) when costs and demand are adversarially generated and the demand is censored.
ReFinED: An Efficient Zero-shot-capable Approach to End-to-End Entity Linking
Venue: arXiv cs.CL 2022
Year: 2022

We introduce ReFinED, an efficient end-to-end entity linking model which uses fine-grained entity types and entity descriptions to perform linking. The model performs mention detection, fine-grained entity typing, and entity disambiguation for all mentions within a document in a single forward pass, making it more than 60 times faster than competitive existing approaches. ReFinED also surpasses state-of-the-art performance on standard entity linking datasets by an average of 3.7 F1. The model is capable of generalising to large-scale knowledge bases such as Wikidata (which has 15 times more entities than Wikipedia) and of zero-shot entity linking. The combination of speed, accuracy and scale makes ReFinED an effective and cost-efficient system for extracting entities from web-scale datasets, for which the model has been successfully deployed. Our code and pre-trained models are available at https://github.com/alexa/ReFinED
Seasonal Encoder-Decoder Architecture for Forecasting
Venue: arXiv cs.LG 2022
Year: 2022

Deep learning (DL) in general and Recurrent neural networks (RNNs) in particular have seen high success levels in sequence based applications. This paper pertains to RNNs for time series modelling and forecasting. We propose a novel RNN architecture capturing (stochastic) seasonal correlations intelligently while capable of accurate multi-step forecasting. It is motivated from the well-known encoder-decoder (ED) architecture and multiplicative seasonal auto-regressive model. It incorporates multi-step (multi-target) learning even in the presence (or absence) of exogenous inputs. It can be employed on single or multiple sequence data. For the multiple sequence case, we also propose a novel greedy recursive procedure to build (one or more) predictive models across sequences when per-sequence data is less. We demonstrate via extensive experiments the utility of our proposed architecture both in single sequence and multiple sequence scenarios.
Vertex Sparsifiers for Hyperedge Connectivity
Venue: arXiv cs.DS 2022
Year: 2022

Recently, Chalermsook et al. [SODA'21(arXiv:2007.07862)] introduces a notion of vertex sparsifiers for $c$-edge connectivity, which has found applications in parameterized algorithms for network design and also led to exciting dynamic algorithms for $c$-edge st-connectivity [Jin and Sun FOCS'21(arXiv:2004.07650)]. We study a natural extension called vertex sparsifiers for $c$-hyperedge connectivity and construct a sparsifier whose size matches the state-of-the-art for normal graphs. More specifically, we show that, given a hypergraph $G=(V,E)$ with $n$ vertices and $m$ hyperedges with $k$ terminal vertices and a parameter $c$, there exists a hypergraph $H$ containing only $O(kc^{3})$ hyperedges that preserves all minimum cuts (up to value $c$) between all subset of terminals. This matches the best bound of $O(kc^{3})$ edges for normal graphs by [Liu'20(arXiv:2011.15101)]. Moreover, $H$ can be constructed in almost-linear $O(p^{1+o(1)} + n(rc\log n)^{O(rc)}\log m)$ time where $r=\max_{e\in E}|e|$ is the rank of $G$ and $p=\sum_{e\in E}|e|$ is the total size of $G$, or in $\text{poly}(m, n)$ time if we slightly relax the size to $O(kc^{3}\log^{1.5}(kc))$ hyperedges.
Sudowoodo: Contrastive Self-supervised Learning for Multi-purpose Data Integration and Preparation
Venue: arXiv cs.DB 2022
Year: 2022

Machine learning (ML) is playing an increasingly important role in data management tasks, particularly in Data Integration and Preparation (DI&P). The success of ML-based approaches, however, heavily relies on the availability of large-scale, high-quality labeled datasets for different tasks. Moreover, the wide variety of DI&P tasks and pipelines oftentimes requires customizing ML solutions which can incur a significant cost for model engineering and experimentation. These factors inevitably hold back the adoption of ML-based approaches to new domains and tasks. In this paper, we propose Sudowoodo, a multi-purpose DI&P framework based on contrastive representation learning. Sudowoodo features a unified, matching-based problem definition capturing a wide range of DI&P tasks including Entity Matching (EM) in data integration, error correction in data cleaning, semantic type detection in data discovery, and more. Contrastive learning enables Sudowoodo to learn similarity-aware data representations from a large corpus of data items (e.g., entity entries, table columns) without using any labels. The learned representations can later be either directly used or facilitate fine-tuning with only a few labels to support different DI&P tasks. Our experiment results show that Sudowoodo achieves multiple state-of-the-art results on different levels of supervision and outperforms previous best specialized blocking or matching solutions for EM. Sudowoodo also achieves promising results in data cleaning and semantic type detection tasks showing its versatility in DI&P applications.
Modeling and Predicting Transistor Aging under Workload Dependency using Machine Learning
Venue: arXiv cs.LG 2022
Year: 2022

The pivotal issue of reliability is one of colossal concern for circuit designers. The driving force is transistor aging, dependent on operating voltage and workload. At the design time, it is difficult to estimate close-to-the-edge guardbands that keep aging effects during the lifetime at bay. This is because the foundry does not share its calibrated physics-based models, comprised of highly confidential technology and material parameters. However, the unmonitored yet necessary overestimation of degradation amounts to a performance decline, which could be preventable. Furthermore, these physics-based models are exceptionally computationally complex. The costs of modeling millions of individual transistors at design time can be evidently exorbitant. We propose the revolutionizing prospect of a machine learning model trained to replicate the physics-based model, such that no confidential parameters are disclosed. This effectual workaround is fully accessible to circuit designers for the purposes of design optimization. We demonstrate the models' ability to generalize by training on data from one circuit and applying it successfully to a benchmark circuit. The mean relative error is as low as 1.7%, with a speedup of up to 20X. Circuit designers, for the first time ever, will have ease of access to a high-precision aging model, which is paramount for efficient designs. This work is a promising step in the direction of bridging the wide gulf between the foundry and circuit designers.
CompoSuite: A Compositional Reinforcement Learning Benchmark
Venue: arXiv cs.LG 2022
Year: 2022

We present CompoSuite, an open-source simulated robotic manipulation benchmark for compositional multi-task reinforcement learning (RL). Each CompoSuite task requires a particular robot arm to manipulate one individual object to achieve a task objective while avoiding an obstacle. This compositional definition of the tasks endows CompoSuite with two remarkable properties. First, varying the robot/object/objective/obstacle elements leads to hundreds of RL tasks, each of which requires a meaningfully different behavior. Second, RL approaches can be evaluated specifically for their ability to learn the compositional structure of the tasks. This latter capability to functionally decompose problems would enable intelligent agents to identify and exploit commonalities between learning tasks to handle large varieties of highly diverse problems. We benchmark existing single-task, multi-task, and compositional learning algorithms on various training settings, and assess their capability to compositionally generalize to unseen tasks. Our evaluation exposes the shortcomings of existing RL approaches with respect to compositionality and opens new avenues for investigation.
Strong Anonymity for Mesh Messaging
Venue: arXiv cs.CR 2022
Year: 2022

Messaging systems built on mesh networks consisting of smartphones communicating over Bluetooth have been used by protesters around the world after governments have disrupted Internet connectivity. Unfortunately, existing systems have been shown to be insecure; most concerningly by not adequately hiding metadata. This is further complicated by the fact that wireless communication such as Bluetooth is inherently a broadcasting medium. In this paper, we present a new threat model that captures the security requirements of protesters in this setting. We then provide a solution that satisfies the required security properties, hides all relevant metadata, scales to moderately sized protests, and supports group messaging. This is achieved by broadcasting all messages in a way that limits the overhead of duplicate messages, ensuring that ciphertexts do not leak metadata, and limiting what can be learned by observing user behavior. We also build a model of our system and numerically evaluate it to support our claims and analyze how many users it supports. Finally, we discuss further extensions that remove potential bottlenecks in scaling and support substantially more users.
A Systematic Review and Thematic Analysis of Community-Collaborative Approaches to Computing Research
Venue: arXiv cs.HC 2022
Year: 2022

HCI researchers have been gradually shifting attention from individual users to communities when engaging in research, design, and system development. However, our field has yet to establish a cohesive, systematic understanding of the challenges, benefits, and commitments of community-collaborative approaches to research. We conducted a systematic review and thematic analysis of 47 computing research papers discussing participatory research with communities for the development of technological artifacts and systems, published over the last two decades. From this review, we identified seven themes associated with the evolution of a project: from establishing community partnerships to sustaining results. Our findings suggest that several tensions characterize these projects, many of which relate to the power and position of researchers, and the computing research environment, relative to community partners. We discuss the implications of our findings and offer methodological proposals to guide HCI, and computing research more broadly, towards practices that center communities.
Auction for Double-Wide Ads
Venue: arXiv cs.GT 2022
Year: 2022

We propose an auction for online advertising where each ad occupies either one square or two horizontally-adjacent squares of a grid of squares. Our primary application are ads for products shown on retail websites such as Instacart or Amazon where the products are naturally organized into a grid. We propose efficient algorithms for computing the optimal layout of the ads and pricing of the ads. The auction is a generalization of the generalized second-price (GSP) auction used by internet search engines (e.g. Google, Microsoft Bing, Yahoo!).
Explainable Legal Case Matching via Inverse Optimal Transport-based Rationale Extraction
Venue: arXiv cs.IR 2022
Year: 2022

As an essential operation of legal retrieval, legal case matching plays a central role in intelligent legal systems. This task has a high demand on the explainability of matching results because of its critical impacts on downstream applications -- the matched legal cases may provide supportive evidence for the judgments of target cases and thus influence the fairness and justice of legal decisions. Focusing on this challenging task, we propose a novel and explainable method, namely \textit{IOT-Match}, with the help of computational optimal transport, which formulates the legal case matching problem as an inverse optimal transport (IOT) problem. Different from most existing methods, which merely focus on the sentence-level semantic similarity between legal cases, our IOT-Match learns to extract rationales from paired legal cases based on both semantics and legal characteristics of their sentences. The extracted rationales are further applied to generate faithful explanations and conduct matching. Moreover, the proposed IOT-Match is robust to the alignment label insufficiency issue commonly in practical legal case matching tasks, which is suitable for both supervised and semi-supervised learning paradigms. To demonstrate the superiority of our IOT-Match method and construct a benchmark of explainable legal case matching task, we not only extend the well-known Challenge of AI in Law (CAIL) dataset but also build a new Explainable Legal cAse Matching (ELAM) dataset, which contains lots of legal cases with detailed and explainable annotations. Experiments on these two datasets show that our IOT-Match outperforms state-of-the-art methods consistently on matching prediction, rationale extraction, and explanation generation.
SCouT: Synthetic Counterfactuals via Spatiotemporal Transformers for Actionable Healthcare
Venue: arXiv cs.AI 2022
Year: 2022

The Synthetic Control method has pioneered a class of powerful data-driven techniques to estimate the counterfactual reality of a unit from donor units. At its core, the technique involves a linear model fitted on the pre-intervention period that combines donor outcomes to yield the counterfactual. However, linearly combining spatial information at each time instance using time-agnostic weights fails to capture important inter-unit and intra-unit temporal contexts and complex nonlinear dynamics of real data. We instead propose an approach to use local spatiotemporal information before the onset of the intervention as a promising way to estimate the counterfactual sequence. To this end, we suggest a Transformer model that leverages particular positional embeddings, a modified decoder attention mask, and a novel pre-training task to perform spatiotemporal sequence-to-sequence modeling. Our experiments on synthetic data demonstrate the efficacy of our method in the typical small donor pool setting and its robustness against noise. We also generate actionable healthcare insights at the population and patient levels by simulating a state-wide public health policy to evaluate its effectiveness, an in silico trial for asthma medications to support randomized controlled trials, and a medical intervention for patients with Friedreich's ataxia to improve clinical decision-making and promote personalized therapy.
Delayed Impact of Interdisciplinary Research
Venue: arXiv cs.DL 2022
Year: 2022

Interdisciplinary research increasingly fuels innovation, and is considered to be a key to tomorrow breakthrough. Yet little is known about whether interdisciplinary research manifests delayed impact. Here, we use the time to reach the citation peak to quantify the highest impact time and citation dynamics, and examine its relationship with interdisciplinarity. Using large scale publication datasets, our results suggest that interdisciplinary papers show significant delayed impact both microscopically per paper and macroscopically collectively, as it takes longer time for interdisciplinary papers to reach their citation peak. Furthermore, we study the underlying forces of such delayed impact, finding that the effect goes beyond the Matthew effect (i.e., the rich-get-richer effect). Finally, we find that team size and content conventionality only partly account for this effect. Overall, our results suggest that governments, research administrators, funding agencies should be aware of this general feature of interdisciplinary science, which may have broad policy implications.
TensorIR: An Abstraction for Automatic Tensorized Program Optimization
Venue: arXiv cs.LG 2022
Year: 2022

Deploying deep learning models on various devices has become an important topic. The wave of hardware specialization brings a diverse set of acceleration primitives for multi-dimensional tensor computations. These new acceleration primitives, along with the emerging machine learning models, bring tremendous engineering challenges. In this paper, we present TensorIR, a compiler abstraction for optimizing programs with these tensor computation primitives. TensorIR generalizes the loop nest representation used in existing machine learning compilers to bring tensor computation as the first-class citizen. Finally, we build an end-to-end framework on top of our abstraction to automatically optimize deep learning models for given tensor computation primitives. Experimental results show that TensorIR compilation automatically uses the tensor computation primitives for given hardware backends and delivers performance that is competitive to state-of-art hand-optimized systems across platforms.
Adversarial Framework with Certified Robustness for Time-Series Domain via Statistical Features
Venue: arXiv cs.LG 2022
Year: 2022

Time-series data arises in many real-world applications (e.g., mobile health) and deep neural networks (DNNs) have shown great success in solving them. Despite their success, little is known about their robustness to adversarial attacks. In this paper, we propose a novel adversarial framework referred to as Time-Series Attacks via STATistical Features (TSA-STAT)}. To address the unique challenges of time-series domain, TSA-STAT employs constraints on statistical features of the time-series data to construct adversarial examples. Optimized polynomial transformations are used to create attacks that are more effective (in terms of successfully fooling DNNs) than those based on additive perturbations. We also provide certified bounds on the norm of the statistical features for constructing adversarial examples. Our experiments on diverse real-world benchmark datasets show the effectiveness of TSA-STAT in fooling DNNs for time-series domain and in improving their robustness. The source code of TSA-STAT algorithms is available at https://github.com/tahabelkhouja/Time-Series-Attacks-via-STATistical-Features
Dynamic Time Warping based Adversarial Framework for Time-Series Domain
Venue: arXiv cs.LG 2022
Year: 2022

Despite the rapid progress on research in adversarial robustness of deep neural networks (DNNs), there is little principled work for the time-series domain. Since time-series data arises in diverse applications including mobile health, finance, and smart grid, it is important to verify and improve the robustness of DNNs for the time-series domain. In this paper, we propose a novel framework for the time-series domain referred as {\em Dynamic Time Warping for Adversarial Robustness (DTW-AR)} using the dynamic time warping measure. Theoretical and empirical evidence is provided to demonstrate the effectiveness of DTW over the standard Euclidean distance metric employed in prior methods for the image domain. We develop a principled algorithm justified by theoretical analysis to efficiently create diverse adversarial examples using random alignment paths. Experiments on diverse real-world benchmarks show the effectiveness of DTW-AR to fool DNNs for time-series data and to improve their robustness using adversarial training. The source code of DTW-AR algorithms is available at https://github.com/tahabelkhouja/DTW-AR
QKVA grid: Attention in Image Perspective and Stacked DETR
Venue: arXiv cs.CV 2022
Year: 2022

We present a new model named Stacked-DETR(SDETR), which inherits the main ideas in canonical DETR. We improve DETR in two directions: simplifying the cost of training and introducing the stacked architecture to enhance the performance. To the former, we focus on the inside of the Attention block and propose the QKVA grid, a new perspective to describe the process of attention. By this, we can step further on how Attention works for image problems and the effect of multi-head. These two ideas contribute the design of single-head encoder-layer. To the latter, SDETR reaches better performance(+0.6AP, +2.7APs) to DETR. Especially to the performance on small objects, SDETR achieves better results to the optimized Faster R-CNN baseline, which was a shortcoming in DETR. Our changes are based on the code of DETR. Training code and pretrained models are available at https://github.com/shengwenyuan/sdetr.
Abstract Processes in the Absence of Conflicts in General Place/Transition Systems
Venue: arXiv cs.LO 2022
Year: 2022

Goltz and Reisig generalised Petri's concept of processes of one-safe Petri nets to general nets where places carry multiple tokens. BD-processes are equivalence classes of Goltz-Reisig processes connected through the swapping transformation of Best and Devillers; they can be considered as an alternative representation of runs of nets. Here we present an order respecting bijection between the BD-processes and the FS-processes of a countable net, the latter being defined -- in an analogous way -- as equivalence classes of firing sequences. Using this, we show that a countable net without binary conflicts has a (unique) largest BD-process.