OpenRaiser/Intern-Atlas huggingface dataset:
ModSelect: Automatic Modality Selection for Synthetic-to-Real Domain Generalization
Venue: arXiv cs.CV 2022
Year: 2022

Modality selection is an important step when designing multimodal systems, especially in the case of cross-domain activity recognition as certain modalities are more robust to domain shift than others. However, selecting only the modalities which have a positive contribution requires a systematic approach. We tackle this problem by proposing an unsupervised modality selection method (ModSelect), which does not require any ground-truth labels. We determine the correlation between the predictions of multiple unimodal classifiers and the domain discrepancy between their embeddings. Then, we systematically compute modality selection thresholds, which select only modalities with a high correlation and low domain discrepancy. We show in our experiments that our method ModSelect chooses only modalities with positive contributions and consistently improves the performance on a Synthetic-to-Real domain adaptation benchmark, narrowing the domain gap.
Counterexamples expose gaps in the proof of time complexity for cover trees introduced in 2006
Venue: arXiv cs.CG 2022
Year: 2022

This paper is motivated by the k-nearest neighbors search: given an arbitrary metric space, and its finite subsets (a reference set R and a query set Q), design a fast algorithm to find all k-nearest neighbors in R for every point q in Q. In 2006, Beygelzimer, Kakade, and Langford introduced cover trees to justify a near-linear time complexity for the neighbor search in the sizes of Q,R. Section 5.3 of Curtin's PhD (2015) pointed out that the proof of this result was wrong. The key step in the original proof attempted to show that the number of iterations can be estimated by multiplying the length of the longest root-to-leaf path in a cover tree by a constant factor. However, this estimate can miss many potential nodes in several branches of a cover tree, that should be considered during the neighbor search. The same argument was unfortunately repeated in several subsequent papers using cover trees from 2006. This paper explicitly constructs challenging datasets that provide counterexamples to the past proofs of time complexity for the cover tree construction, the k-nearest neighbor search presented at ICML 2006, and the dual-tree search algorithm published in NIPS 2009. The corrected near-linear time complexities with extra parameters are proved in another forthcoming paper by using a new compressed cover tree simplifying the original tree structure.
Sparse Optimization for Unsupervised Extractive Summarization of Long Documents with the Frank-Wolfe Algorithm
Venue: arXiv cs.CL 2022
Year: 2022

We address the problem of unsupervised extractive document summarization, especially for long documents. We model the unsupervised problem as a sparse auto-regression one and approximate the resulting combinatorial problem via a convex, norm-constrained problem. We solve it using a dedicated Frank-Wolfe algorithm. To generate a summary with $k$ sentences, the algorithm only needs to execute $\approx k$ iterations, making it very efficient. We explain how to avoid explicit calculation of the full gradient and how to include sentence embedding information. We evaluate our approach against two other unsupervised methods using both lexical (standard) ROUGE scores, as well as semantic (embedding-based) ones. Our method achieves better results with both datasets and works especially well when combined with embeddings for highly paraphrased summaries.
Recurrent Neural Network-based Anti-jamming Framework for Defense Against Multiple Jamming Policies
Venue: arXiv cs.LG 2022
Year: 2022

Conventional anti-jamming methods mainly focus on preventing single jammer attacks with an invariant jamming policy or jamming attacks from multiple jammers with similar jamming policies. These anti-jamming methods are ineffective against a single jammer following several different jamming policies or multiple jammers with distinct policies. Therefore, this paper proposes an anti-jamming method that can adapt its policy to the current jamming attack. Moreover, for the multiple jammers scenario, an anti-jamming method that estimates the future occupied channels using the jammers' occupied channels in previous time slots is proposed. In both single and multiple jammers scenarios, the interaction between the users and jammers is modeled using recurrent neural networks (RNN)s. The performance of the proposed anti-jamming methods is evaluated by calculating the users' successful transmission rate (STR) and ergodic rate (ER), and compared to a baseline based on Q-learning (DQL). Simulation results show that for the single jammer scenario, all the considered jamming policies are perfectly detected and high STR and ER are maintained. Moreover, when 70 % of the spectrum is under jamming attacks from multiple jammers, the proposed method achieves an STR and ER greater than 75 % and 80 %, respectively. These values rise to 90 % when 30 % of the spectrum is under jamming attacks. In addition, the proposed anti-jamming methods significantly outperform the DQL method for all the considered cases and jamming scenarios.
Meta Learning for High-dimensional Ising Model Selection Using $\ell_1$-regularized Logistic Regression
Venue: arXiv cs.LG 2022
Year: 2022

In this paper, we consider the meta learning problem for estimating the graphs associated with high-dimensional Ising models, using the method of $\ell_1$-regularized logistic regression for neighborhood selection of each node. Our goal is to use the information learned from the auxiliary tasks in the learning of the novel task to reduce its sufficient sample complexity. To this end, we propose a novel generative model as well as an improper estimation method. In our setting, all the tasks are \emph{similar} in their \emph{random} model parameters and supports. By pooling all the samples from the auxiliary tasks to \emph{improperly} estimate a single parameter vector, we can recover the true support union, assumed small in size, with a high probability with a sufficient sample complexity of $Ω(1) $ per task, for $K = Ω(d^3 \log p ) $ tasks of Ising models with $p$ nodes and a maximum neighborhood size $d$. Then, with the support for the novel task restricted to the estimated support union, we prove that consistent neighborhood selection for the novel task can be obtained with a reduced sufficient sample complexity of $Ω(d^3 \log d)$.
Game-Theoretic Algorithms for Conditional Moment Matching
Venue: arXiv cs.GT 2022
Year: 2022

A variety of problems in econometrics and machine learning, including instrumental variable regression and Bellman residual minimization, can be formulated as satisfying a set of conditional moment restrictions (CMR). We derive a general, game-theoretic strategy for satisfying CMR that scales to nonlinear problems, is amenable to gradient-based optimization, and is able to account for finite sample uncertainty. We recover the approaches of Dikkala et al. and Dai et al. as special cases of our general framework before detailing various extensions and how to efficiently solve the game defined by CMR.
Multiple Instance Neuroimage Transformer
Venue: arXiv cs.CV 2022
Year: 2022

For the first time, we propose using a multiple instance learning based convolution-free transformer model, called Multiple Instance Neuroimage Transformer (MINiT), for the classification of T1weighted (T1w) MRIs. We first present several variants of transformer models adopted for neuroimages. These models extract non-overlapping 3D blocks from the input volume and perform multi-headed self-attention on a sequence of their linear projections. MINiT, on the other hand, treats each of the non-overlapping 3D blocks of the input MRI as its own instance, splitting it further into non-overlapping 3D patches, on which multi-headed self-attention is computed. As a proof-of-concept, we evaluate the efficacy of our model by training it to identify sex from T1w-MRIs of two public datasets: Adolescent Brain Cognitive Development (ABCD) and the National Consortium on Alcohol and Neurodevelopment in Adolescence (NCANDA). The learned attention maps highlight voxels contributing to identifying sex differences in brain morphometry. The code is available at https://github.com/singlaayush/MINIT.
Probabilities of Causation with Nonbinary Treatment and Effect
Venue: arXiv cs.AI 2022
Year: 2022

This paper deals with the problem of estimating the probabilities of causation when treatment and effect are not binary. Tian and Pearl derived sharp bounds for the probability of necessity and sufficiency (PNS), the probability of sufficiency (PS), and the probability of necessity (PN) using experimental and observational data. In this paper, we provide theoretical bounds for all types of probabilities of causation to multivalued treatments and effects. We further discuss examples where our bounds guide practical decisions and use simulation studies to evaluate how informative the bounds are for various combinations of data.
Calculus on MDPs: Potential Shaping as a Gradient
Venue: arXiv cs.LG 2022
Year: 2022

In reinforcement learning, different reward functions can be equivalent in terms of the optimal policies they induce. A particularly well-known and important example is potential shaping, a class of functions that can be added to any reward function without changing the optimal policy set under arbitrary transition dynamics. Potential shaping is conceptually similar to potentials, conservative vector fields and gauge transformations in math and physics, but this connection has not previously been formally explored. We develop a formalism for discrete calculus on graphs that abstract a Markov Decision Process, and show how potential shaping can be formally interpreted as a gradient within this framework. This allows us to strengthen results from Ng et al. (1999) describing conditions under which potential shaping is the only additive reward transformation to always preserve optimal policies. As an additional application of our formalism, we define a rule for picking a single unique reward function from each potential shaping equivalence class.
Diffusion Models Beat GANs on Topology Optimization
Venue: arXiv cs.LG 2022
Year: 2022

Structural topology optimization, which aims to find the optimal physical structure that maximizes mechanical performance, is vital in engineering design applications in aerospace, mechanical, and civil engineering. Generative adversarial networks (GANs) have recently emerged as a popular alternative to traditional iterative topology optimization methods. However, these models are often difficult to train, have limited generalizability, and due to their goal of mimicking optimal structures, neglect manufacturability and performance objectives like mechanical compliance. We propose TopoDiff - a conditional diffusion-model-based architecture to perform performance-aware and manufacturability-aware topology optimization that overcomes these issues. Our model introduces a surrogate model-based guidance strategy that actively favors structures with low compliance and good manufacturability. Our method significantly outperforms a state-of-art conditional GAN by reducing the average error on physical performance by a factor of eight and by producing eleven times fewer infeasible samples. By introducing diffusion models to topology optimization, we show that conditional diffusion models have the ability to outperform GANs in engineering design synthesis applications too. Our work also suggests a general framework for engineering optimization problems using diffusion models and external performance with constraint-aware guidance. We publicly share the data, code, and trained models here: https://decode.mit.edu/projects/topodiff/.
Controlling Congestion via In-Network Content Adaptation
Venue: arXiv cs.NI 2022
Year: 2022

Realizing that it is inherently difficult to precisely match the sending rates at the endhost with the available capacity on dynamic cellular links, we build a system, Octopus, that sends real-time data streams over cellular networks using an imprecise controller (that errs on the side of over-estimating network capacity), and then drops appropriate packets in the cellular network buffers to match the actual capacity. We design parameterized primitives for implementing the packet dropping logic, that the applications at the endhost can configure differently to express different content adaptation policies. Octopus transport encodes the app-specified parameters in packet header fields, which the routers parse to execute the desired dropping behavior. Our evaluation shows how real-time applications involving standard and volumetric videos can be designed to exploit Octopus, and achieve 1.5-50 times better performance than state-of-the-art schemes.
An ensemble meta-estimator to predict source code testability
Venue: arXiv cs.SE 2022
Year: 2022

Unlike most other software quality attributes, testability cannot be evaluated solely based on the characteristics of the source code. The effectiveness of the test suite and the budget assigned to the test highly impact the testability of the code under test. The size of a test suite determines the test effort and cost, while the coverage measure indicates the test effectiveness. Therefore, testability can be measured based on the coverage and number of test cases provided by a test suite, considering the test budget. This paper offers a new equation to estimate testability regarding the size and coverage of a given test suite. The equation has been used to label 23,000 classes belonging to 110 Java projects with their testability measure. The labeled classes were vectorized using 262 metrics. The labeled vectors were fed into a family of supervised machine learning algorithms, regression, to predict testability in terms of the source code metrics. Regression models predicted testability with an R2 of 0.68 and a mean squared error of 0.03, suitable in practice. Fifteen software metrics highly affecting testability prediction were identified using a feature importance analysis technique on the learned model. The proposed models have improved mean absolute error by 38% due to utilizing new criteria, metrics, and data compared with the relevant study on predicting branch coverage as a test criterion. As an application of testability prediction, it is demonstrated that automated refactoring of 42 smelly Java classes targeted at improving the 15 influential software metrics could elevate their testability by an average of 86.87%.
Reconfigurable Intelligent Surfaces and Capacity Optimization: A Large System Analysis
Venue: arXiv cs.IT 2022
Year: 2022

Reconfigurable Intelligent Surfaces (RISs), comprising large numbers of low-cost and almost passive metamaterials with tunable reflection properties, have been recently proposed as an enabling technology for programmable wireless propagation environments. In this paper, we present asymptotic closed-form expressions for the mean and variance of the mutual information metric for a multi-antenna transmitter-receiver pair in the presence of multiple RISs, using methods from statistical physics. While nominally valid in the large system limit, we show that the derived Gaussian approximation for the mutual information can be quite accurate, even for modest-sized antenna arrays and metasurfaces. The above results are particularly useful when fast-fading conditions are present, which renders instantaneous channel estimation extremely challenging. We find that, when the channel close to an RIS is correlated, for instance due to small angle spread, which is reasonable for wireless systems with increasing carrier frequencies, the communication link benefits significantly from statistical RIS phase optimization, resulting in gains that are surprisingly higher than the nearly uncorrelated case. Using our novel asymptotic properties of the correlation matrices of the impinging and outgoing signals at the RISs, we can optimize the metasurfaces without brute-force numerical optimization. Furthermore, when the desired reflection from any of the RISs departs significantly from geometrical optics, the metasurfaces can be optimized to provide robust communication links, without significant need for their optimal placement.
Phase Shift-Free Passive Beamforming for Reconfigurable Intelligent Surfaces
Venue: arXiv cs.IT 2022
Year: 2022

Reconfigurable intelligent surface (RIS)-assisted communications recently appeared as a game-changing technology for next-generation wireless communications due to its unprecedented ability to reform the propagation environment. One of the main aspects of using RISs is the exploitation of the so-called passive beamforming (PB), which is carried out by adjusting the reflection coefficients (mainly the phase shifts) of the individual RIS elements. However, practically, this individual phase shift adjustment is associated with many issues in hardware implementation, limiting the RIS achievable gain. In this paper, we propose a low-cost, phase shift-free and novel PB scheme by only optimizing the on/off states of the RIS elements while fixing their phase shifts. The proposed PB scheme is shown to achieve the same scaling law (quadratic growth with the RIS size) for the signal-to-noise ratio as in the classical phase shift-based PB scheme, yet, with far less sensitivity to spatial correlation and phase errors. We provide a unified mathematical analysis that characterizes the performance of the proposed PB scheme and obtain the outage probability for the considered RIS-assisted system. Based on the provided computer simulations, the proposed PB scheme is shown to have a clear superiority over the classical one under different performance metrics.
The computational complexity of some explainable clustering problems
Venue: arXiv cs.LG 2022
Year: 2022

We study the computational complexity of some explainable clustering problems in the framework proposed by [Dasgupta et al., ICML 2020], where explainability is achieved via axis-aligned decision trees. We consider the $k$-means, $k$-medians, $k$-centers and the spacing cost functions. We prove that the first three are hard to optimize while the latter can be optimized in polynomial time.
Trigger-free Event Detection via Derangement Reading Comprehension
Venue: arXiv cs.CL 2022
Year: 2022

Event detection (ED), aiming to detect events from texts and categorize them, is vital to understanding actual happenings in real life. However, mainstream event detection models require high-quality expert human annotations of triggers, which are often costly and thus deter the application of ED to new domains. Therefore, in this paper, we focus on low-resource ED without triggers and aim to tackle the following formidable challenges: multi-label classification, insufficient clues, and imbalanced events distribution. We propose a novel trigger-free ED method via Derangement mechanism on a machine Reading Comprehension (DRC) framework. More specifically, we treat the input text as Context and concatenate it with all event type tokens that are deemed as Answers with an omitted default question. So we can leverage the self-attention in pre-trained language models to absorb semantic relations between input text and the event types. Moreover, we design a simple yet effective event derangement module (EDM) to prevent major events from being excessively learned so as to yield a more balanced training process. The experiment results show that our proposed trigger-free ED model is remarkably competitive to mainstream trigger-based models, showing its strong performance on low-source event detection.
Comparing graph data science libraries for querying and analysing datasets: towards data science queries on graphs
Venue: arXiv cs.DB 2022
Year: 2022

This paper presents an experimental study to compare analysis tools with management systems for querying and analysing graphs. Our experiment compares classic graph navigational operations queries where analytics tools and management systems adopt different execution strategies. Then, our experiment addresses data science pipelines with clustering and prediction models applied to graphs. In this kind of experiment, we underline the interest in combining both approaches and the interest of relying on a parallel execution platform for executing queries.
Dual Space Coupling Model Guided Overlap-Free Scatterplot
Venue: arXiv cs.GR 2022
Year: 2022

The overdraw problem of scatterplots seriously interferes with the visual tasks. Existing methods, such as data sampling, node dispersion, subspace mapping, and visual abstraction, cannot guarantee the correspondence and consistency between the data points that reflect the intrinsic original data distribution and the corresponding visual units that reveal the presented data distribution, thus failing to obtain an overlap-free scatterplot with unbiased and lossless data distribution. A dual space coupling model is proposed in this paper to represent the complex bilateral relationship between data space and visual space theoretically and analytically. Under the guidance of the model, an overlap-free scatterplot method is developed through integration of the following: a geometry-based data transformation algorithm, namely DistributionTranscriptor; an efficient spatial mutual exclusion guided view transformation algorithm, namely PolarPacking; an overlap-free oriented visual encoding configuration model and a radius adjustment tool, namely $f_{r_{draw}}$. Our method can ensure complete and accurate information transfer between the two spaces, maintaining consistency between the newly created scatterplot and the original data distribution on global and local features. Quantitative evaluation proves our remarkable progress on computational efficiency compared with the state-of-the-art methods. Three applications involving pattern enhancement, interaction improvement, and overdraw mitigation of trajectory visualization demonstrate the broad prospects of our method.
FaceOff: A Video-to-Video Face Swapping System
Venue: arXiv cs.CV 2022
Year: 2022

Doubles play an indispensable role in the movie industry. They take the place of the actors in dangerous stunt scenes or scenes where the same actor plays multiple characters. The double's face is later replaced with the actor's face and expressions manually using expensive CGI technology, costing millions of dollars and taking months to complete. An automated, inexpensive, and fast way can be to use face-swapping techniques that aim to swap an identity from a source face video (or an image) to a target face video. However, such methods cannot preserve the source expressions of the actor important for the scene's context. To tackle this challenge, we introduce video-to-video (V2V) face-swapping, a novel task of face-swapping that can preserve (1) the identity and expressions of the source (actor) face video and (2) the background and pose of the target (double) video. We propose FaceOff, a V2V face-swapping system that operates by learning a robust blending operation to merge two face videos following the constraints above. It reduces the videos to a quantized latent space and then blends them in the reduced space. FaceOff is trained in a self-supervised manner and robustly tackles the non-trivial challenges of V2V face-swapping. As shown in the experimental section, FaceOff significantly outperforms alternate approaches qualitatively and quantitatively.