OpenRaiser/Intern-Atlas huggingface dataset:
Efficiently Trained Low-Resource Mongolian Text-to-Speech System Based On FullConv-TTS
Venue: arXiv cs.CL 2023
Year: 2023

Recurrent Neural Networks (RNNs) have become the standard modeling technique for sequence data, and are used in a number of novel text-to-speech models. However, training a TTS model including RNN components has certain requirements for GPU performance and takes a long time. In contrast, studies have shown that CNN-based sequence synthesis technology can greatly reduce training time in text-to-speech models while ensuring a certain performance due to its high parallelism. We propose a new text-to-speech system based on deep convolutional neural networks that does not employ any RNN components (recurrent units). At the same time, we improve the generality and robustness of our model through a series of data augmentation methods such as Time Warping, Frequency Mask, and Time Mask. The final experimental results show that the TTS model using only the CNN component can reduce the training time compared to the classic TTS models such as Tacotron while ensuring the quality of the synthesized speech.
Connected k-Center and k-Diameter Clustering
Venue: arXiv cs.DS 2023
Year: 2023

Motivated by an application from geodesy, we introduce a novel clustering problem which is a $k$-center (or k-diameter) problem with a side constraint. For the side constraint, we are given an undirected connectivity graph $G$ on the input points, and a clustering is now only feasible if every cluster induces a connected subgraph in $G$. We call the resulting problems the connected $k$-center problem and the connected $k$-diameter problem. We prove several results on the complexity and approximability of these problems. Our main result is an $O(\log^2{k})$-approximation algorithm for the connected $k$-center and the connected $k$-diameter problem. For Euclidean metrics and metrics with constant doubling dimension, the approximation factor of this algorithm improves to $O(1)$. We also consider the special cases that the connectivity graph is a line or a tree. For the line we give optimal polynomial-time algorithms and for the case that the connectivity graph is a tree, we either give an optimal polynomial-time algorithm or a $2$-approximation algorithm for all variants of our model. We complement our upper bounds by several lower bounds.
Emergent Quantized Communication
Venue: arXiv cs.AI 2023
Year: 2023

The field of emergent communication aims to understand the characteristics of communication as it emerges from artificial agents solving tasks that require information exchange. Communication with discrete messages is considered a desired characteristic, for both scientific and applied reasons. However, training a multi-agent system with discrete communication is not straightforward, requiring either reinforcement learning algorithms or relaxing the discreteness requirement via a continuous approximation such as the Gumbel-softmax. Both these solutions result in poor performance compared to fully continuous communication. In this work, we propose an alternative approach to achieve discrete communication -- quantization of communicated messages. Using message quantization allows us to train the model end-to-end, achieving superior performance in multiple setups. Moreover, quantization is a natural framework that runs the gamut from continuous to discrete communication. Thus, it sets the ground for a broader view of multi-agent communication in the deep learning era.
Geometry-Complete Perceptron Networks for 3D Molecular Graphs
Venue: arXiv cs.LG 2023
Year: 2023

The field of geometric deep learning has had a profound impact on the development of innovative and powerful graph neural network architectures. Disciplines such as computer vision and computational biology have benefited significantly from such methodological advances, which has led to breakthroughs in scientific domains such as protein structure prediction and design. In this work, we introduce GCPNet, a new geometry-complete, SE(3)-equivariant graph neural network designed for 3D molecular graph representation learning. Rigorous experiments across four distinct geometric tasks demonstrate that GCPNet's predictions (1) for protein-ligand binding affinity achieve a statistically significant correlation of 0.608, more than 5% greater than current state-of-the-art methods; (2) for protein structure ranking achieve statistically significant target-local and dataset-global correlations of 0.616 and 0.871, respectively; (3) for Newtownian many-body systems modeling achieve a task-averaged mean squared error less than 0.01, more than 15% better than current methods; and (4) for molecular chirality recognition achieve a state-of-the-art prediction accuracy of 98.7%, better than any other machine learning method to date. The source code, data, and instructions to train new models or reproduce our results are freely available at https://github.com/BioinfoMachineLearning/GCPNet.
A Transformer-Based Substitute Recommendation Model Incorporating Weakly Supervised Customer Behavior Data
Venue: arXiv cs.IR 2023
Year: 2023

The substitute-based recommendation is widely used in E-commerce to provide better alternatives to customers. However, existing research typically uses the customer behavior signals like co-view and view-but-purchase-another to capture the substitute relationship. Despite its intuitive soundness, we find that such an approach might ignore the functionality and characteristics of products. In this paper, we adapt substitute recommendation into language matching problem by taking product title description as model input to consider product functionality. We design a new transformation method to de-noise the signals derived from production data. In addition, we consider multilingual support from the engineering point of view. Our proposed end-to-end transformer-based model achieves both successes from offline and online experiments. The proposed model has been deployed in a large-scale E-commerce website for 11 marketplaces in 6 languages. Our proposed model is demonstrated to increase revenue by 19% based on an online A/B experiment.
Embracing Off-the-Grid Samples
Venue: arXiv cs.IT 2023
Year: 2023

Many empirical studies suggest that samples of continuous-time signals taken at locations randomly deviated from an equispaced grid (i.e., off-the-grid) can benefit signal acquisition, e.g., undersampling and anti-aliasing. However, explicit statements of such advantages and their respective conditions are scarce in the literature. This paper provides some insight on this topic when the sampling positions are known, with grid deviations generated i.i.d. from a variety of distributions. By solving a square-root LASSO decoder with an interpolation kernel we demonstrate the capabilities of nonuniform samples for compressive sampling, an effective paradigm for undersampling and anti-aliasing. For functions in the Wiener algebra that admit a discrete $s$-sparse representation in some transform domain, we show that $\mathcal{O}(s\log N)$ random off-the-grid samples are sufficient to recover an accurate $\frac{N}{2}$-bandlimited approximation of the signal. For sparse signals (i.e., $s \ll N$), this sampling complexity is a great reduction in comparison to equispaced sampling where $\mathcal{O}(N)$ measurements are needed for the same quality of reconstruction (Nyquist-Shannon sampling theorem). We further consider noise attenuation via oversampling (relative to a desired bandwidth), a standard technique with limited theoretical understanding when the sampling positions are non-equispaced. By solving a least squares problem, we show that $\mathcal{O}(N\log N)$ i.i.d. randomly deviated samples provide an accurate $\frac{N}{2}$-bandlimited approximation of the signal with suppression of the noise energy by a factor $\sim\frac{1}{\sqrt{\log N}}$.
Prototypical quadruplet for few-shot class incremental learning
Venue: arXiv cs.CV 2023
Year: 2023

Scarcity of data and incremental learning of new tasks pose two major bottlenecks for many modern computer vision algorithms. The phenomenon of catastrophic forgetting, i.e., the model's inability to classify previously learned data after training with new batches of data, is a major challenge. Conventional methods address catastrophic forgetting while compromising the current session's training. Generative replay-based approaches, such as generative adversarial networks (GANs), have been proposed to mitigate catastrophic forgetting, but training GANs with few samples may lead to instability. To address these challenges, we propose a novel method that improves classification robustness by identifying a better embedding space using an improved contrasting loss. Our approach retains previously acquired knowledge in the embedding space, even when trained with new classes, by updating previous session class prototypes to represent the true class mean, which is crucial for our nearest class mean classification strategy. We demonstrate the effectiveness of our method by showing that the embedding space remains intact after training the model with new classes and outperforms existing state-of-the-art algorithms in terms of accuracy across different sessions.
Bringing Online Egocentric Action Recognition into the wild
Venue: arXiv cs.CV 2023
Year: 2023

To enable a safe and effective human-robot cooperation, it is crucial to develop models for the identification of human activities. Egocentric vision seems to be a viable solution to solve this problem, and therefore many works provide deep learning solutions to infer human actions from first person videos. However, although very promising, most of these do not consider the major challenges that comes with a realistic deployment, such as the portability of the model, the need for real-time inference, and the robustness with respect to the novel domains (i.e., new spaces, users, tasks). With this paper, we set the boundaries that egocentric vision models should consider for realistic applications, defining a novel setting of egocentric action recognition in the wild, which encourages researchers to develop novel, applications-aware solutions. We also present a new model-agnostic technique that enables the rapid repurposing of existing architectures in this new context, demonstrating the feasibility to deploy a model on a tiny device (Jetson Nano) and to perform the task directly on the edge with very low energy consumption (2.4W on average at 50 fps). The code is publicly available at: https://github.com/EgocentricVision/EgoWild.
Integration-free Learning of Flow Maps
Venue: arXiv cs.GR 2023
Year: 2023

We present a method for learning neural representations of flow maps from time-varying vector field data. The flow map is pervasive within the area of flow visualization, as it is foundational to numerous visualization techniques, e.g. integral curve computation for pathlines or streaklines, as well as computing separation/attraction structures within the flow field. Yet bottlenecks in flow map computation, namely the numerical integration of vector fields, can easily inhibit their use within interactive visualization settings. In response, in our work we seek neural representations of flow maps that are efficient to evaluate, while remaining scalable to optimize, both in computation cost and data requirements. A key aspect of our approach is that we can frame the process of representation learning not in optimizing for samples of the flow map, but rather, a self-consistency criterion on flow map derivatives that eliminates the need for flow map samples, and thus numerical integration, altogether. Central to realizing this is a novel neural network design for flow maps, coupled with an optimization scheme, wherein our representation only requires the time-varying vector field for learning, encoded as instantaneous velocity. We show the benefits of our method over prior works in terms of accuracy and efficiency across a range of 2D and 3D time-varying vector fields, while showing how our neural representation of flow maps can benefit unsteady flow visualization techniques such as streaklines, and the finite-time Lyapunov exponent.
Optimal Scoring Rules for Multi-dimensional Effort
Venue: arXiv cs.GT 2023
Year: 2023

This paper develops a framework for the design of scoring rules to optimally incentivize an agent to exert a multi-dimensional effort. This framework is a generalization to strategic agents of the classical knapsack problem (cf. Briest, Krysta, and Vöcking, 2005, Singer, 2010) and it is foundational to applying algorithmic mechanism design to the classroom. The paper identifies two simple families of scoring rules that guarantee constant approximations to the optimal scoring rule. The truncated separate scoring rule is the sum of single dimensional scoring rules that is truncated to the bounded range of feasible scores. The threshold scoring rule gives the maximum score if reports exceed a threshold and zero otherwise. Approximate optimality of one or the other of these rules is similar to the bundling or selling separately result of Babaioff, Immorlica, Lucier, and Weinberg (2014). Finally, we show that the approximate optimality of the best of those two simple scoring rules is robust when the agent's choice of effort is made sequentially.
Implicit Graphon Neural Representation
Venue: arXiv cs.LG 2023
Year: 2023

Graphons are general and powerful models for generating graphs of varying size. In this paper, we propose to directly model graphons using neural networks, obtaining Implicit Graphon Neural Representation (IGNR). Existing work in modeling and reconstructing graphons often approximates a target graphon by a fixed resolution piece-wise constant representation. Our IGNR has the benefit that it can represent graphons up to arbitrary resolutions, and enables natural and efficient generation of arbitrary sized graphs with desired structure once the model is learned. Furthermore, we allow the input graph data to be unaligned and have different sizes by leveraging the Gromov-Wasserstein distance. We first demonstrate the effectiveness of our model by showing its superior performance on a graphon learning task. We then propose an extension of IGNR that can be incorporated into an auto-encoder framework, and demonstrate its good performance under a more general setting of graphon learning. We also show that our model is suitable for graph representation learning and graph generation.
A tight upper bound on the number of non-zero weights of a quasi-cyclic code
Venue: arXiv cs.IT 2023
Year: 2023

Let $\mathcal{C}$ be a quasi-cyclic code of index $l(l\geq2)$. Let $G$ be the subgroup of the automorphism group of $\mathcal{C}$ generated by $ρ^l$ and the scalar multiplications of $\mathcal{C}$, where $ρ$ denotes the standard cyclic shift. In this paper, we find an explicit formula of orbits of $G$ on $\mathcal{C}\setminus \{\mathbf{0}\}$. Consequently, an explicit upper bound on the number of nonzero weights of $\mathcal{C}$ is immediately derived and a necessary and sufficient condition for codes meeting the bound is exhibited. If $\mathcal{C}$ is a one-generator quasi-cyclic code, a tighter upper bound on the number of nonzero weights of $\mathcal{C}$ is obtained by considering a larger automorphism subgroup which is generated by the multiplier, $ρ^l$ and the scalar multiplications of $\mathcal{C}$. In particular, we list some examples to show the bounds are tight. Our main result improves and generalizes some of the results in \cite{M2}.
Modulo-Counting First-Order Logic on Bounded Expansion Classes
Venue: arXiv cs.LO 2023
Year: 2023

We prove that, on bounded expansion classes, every first-order formula with modulo counting is equivalent, in a linear-time computable monadic expansion, to an existential first-order formula. As a consequence, we derive, on bounded expansion classes, that first-order transductions with modulo counting have the same encoding power as existential first-order transductions. Also, modulo-counting first-order model checking and computation of the size of sets definable in modulo-counting first-order logic can be achieved in linear time on bounded expansion classes. As an application, we prove that a class has structurally bounded expansion if and only if it is a class of bounded depth vertex-minors of graphs in a bounded expansion class. We also show how our results can be used to implement fast matrix calculus on bounded expansion matrices over a finite field.
TAP-Vid: A Benchmark for Tracking Any Point in a Video
Venue: arXiv cs.CV 2023
Year: 2023

Generic motion understanding from video involves not only tracking objects, but also perceiving how their surfaces deform and move. This information is useful to make inferences about 3D shape, physical properties and object interactions. While the problem of tracking arbitrary physical points on surfaces over longer video clips has received some attention, no dataset or benchmark for evaluation existed, until now. In this paper, we first formalize the problem, naming it tracking any point (TAP). We introduce a companion benchmark, TAP-Vid, which is composed of both real-world videos with accurate human annotations of point tracks, and synthetic videos with perfect ground-truth point tracks. Central to the construction of our benchmark is a novel semi-automatic crowdsourced pipeline which uses optical flow estimates to compensate for easier, short-term motion like camera shake, allowing annotators to focus on harder sections of video. We validate our pipeline on synthetic data and propose a simple end-to-end point tracking model TAP-Net, showing that it outperforms all prior methods on our benchmark when trained on synthetic data.
EEG-Fest: Few-shot based Attention Network for Driver's Vigilance Estimation with EEG Signals
Venue: arXiv cs.LG 2023
Year: 2023

A lack of driver's vigilance is the main cause of most vehicle crashes. Electroencephalography(EEG) has been reliable and efficient tool for drivers' drowsiness estimation. Even though previous studies have developed accurate and robust driver's vigilance detection algorithms, these methods are still facing challenges on following areas: (a) small sample size training, (b) anomaly signal detection, and (c) subject-independent classification. In this paper, we propose a generalized few-shot model, namely EEG-Fest, to improve aforementioned drawbacks. The EEG-Fest model can (a) classify the query sample's drowsiness with a few samples, (b) identify whether a query sample is anomaly signals or not, and (c) achieve subject independent classification. The proposed algorithm achieves state-of-the-art results on the SEED-VIG dataset and the SADT dataset. The accuracy of the drowsy class achieves 92% and 94% for 1-shot and 5-shot support samples in the SEED-VIG dataset, and 62% and 78% for 1-shot and 5-shot support samples in the SADT dataset.
A deterministic near-linear time approximation scheme for geometric transportation
Venue: arXiv cs.CG 2023
Year: 2023

Given a set of points $P = (P^+ \sqcup P^-) \subset \mathbb{R}^d$ for some constant $d$ and a supply function $μ:P\to \mathbb{R}$ such that $μ(p) > 0~\forall p \in P^+$, $μ(p) < 0~\forall p \in P^-$, and $\sum_{p\in P}{μ(p)} = 0$, the geometric transportation problem asks one to find a transportation map $τ: P^+\times P^-\to \mathbb{R}_{\ge 0}$ such that $\sum_{q\in P^-}{τ(p, q)} = μ(p)~\forall p \in P^+$, $\sum_{p\in P^+}{τ(p, q)} = -μ(q)~ \forall q \in P^-$, and the weighted sum of Euclidean distances for the pairs $\sum_{(p,q)\in P^+\times P^-}τ(p, q)\cdot ||q-p||_2$ is minimized. We present the first deterministic algorithm that computes, in near-linear time, a transportation map whose cost is within a $(1 + \varepsilon)$ factor of optimal. More precisely, our algorithm runs in $O(n\varepsilon^{-(d+2)}\log^5{n}\log{\log{n}})$ time for any constant $\varepsilon > 0$. Surprisingly, our result is not only a generalization of a bipartite matching one to arbitrary instances of geometric transportation, but it also reduces the running time for all previously known $(1 + \varepsilon)$-approximation algorithms, randomized or deterministic, even for geometric bipartite matching. In particular, we give the first $(1 + \varepsilon)$-approximate deterministic algorithm for geometric bipartite matching and the first $(1 + \varepsilon)$-approximate deterministic or randomized algorithm for geometric transportation with no dependence on $d$ in the exponent of the running time's polylog. As an additional application of our main ideas, we also give the first randomized near-linear $O(\varepsilon^{-2} m \log^{O(1)} n)$ time $(1 + \varepsilon)$-approximation algorithm for the uncapacitated minimum cost flow (transshipment) problem in undirected graphs with arbitrary real edge costs.
Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots
Venue: arXiv cs.DS 2023
Year: 2023

We give an $\widetilde{O}(\sqrt{n})$-space single-pass $0.483$-approximation streaming algorithm for estimating the maximum directed cut size (Max-DICUT) in a directed graph on $n$ vertices. This improves over an $O(\log n)$-space $4/9 < 0.45$ approximation algorithm due to Chou, Golovnev, and Velusamy (FOCS 2020), which was known to be optimal for $o(\sqrt{n})$-space algorithms. Max-DICUT is a special case of a constraint satisfaction problem (CSP). In this broader context, we give the first CSP for which algorithms with $\widetilde{O}(\sqrt{n})$ space can provably outperform $o(\sqrt{n})$-space algorithms. The key technical contribution of our work is development of the notions of a first-order snapshot of a (directed) graph and of estimates of such snapshots. These snapshots can be used to simulate certain (non-streaming) Max-DICUT algorithms, including the "oblivious" algorithms introduced by Feige and Jozeph (Algorithmica, 2015), who showed that one such algorithm achieves a 0.483-approximation. Previous work of the authors (SODA 2023) studied the restricted case of bounded-degree graphs, and observed that in this setting, it is straightforward to estimate the snapshot with $\ell_1$ errors and this suffices to simulate oblivious algorithms. But for unbounded-degree graphs, even defining an achievable and sufficient notion of estimation is subtle. We describe a new notion of snapshot estimation and prove its sufficiency using careful smoothing techniques, and then develop an algorithm which sketches such an estimate via a delicate process of intertwined vertex- and edge-subsampling. Prior to our work, the only streaming algorithms for any CSP on general instances were based on generalizations of the $O(\log n)$-space algorithm for Max-DICUT, and thus our work opens the possibility of a new class of algorithms for approximating CSPs.
Does an ensemble of GANs lead to better performance when training segmentation networks with synthetic images?
Venue: arXiv cs.CV 2023
Year: 2023

Large annotated datasets are required to train segmentation networks. In medical imaging, it is often difficult, time consuming and expensive to create such datasets, and it may also be difficult to share these datasets with other researchers. Different AI models can today generate very realistic synthetic images, which can potentially be openly shared as they do not belong to specific persons. However, recent work has shown that using synthetic images for training deep networks often leads to worse performance compared to using real images. Here we demonstrate that using synthetic images and annotations from an ensemble of 20 GANs, instead of from a single GAN, increases the Dice score on real test images with 4.7 % to 14.0 % on specific classes.