OpenRaiser/Intern-Atlas huggingface dataset:
General form of almost instantaneous fixed-to-variable-length codes
Venue: arXiv cs.IT 2023
Year: 2023

A general class of the almost instantaneous fixed-to-variable-length (AIFV) codes is proposed, which contains every possible binary code we can make when allowing finite bits of decoding delay. The contribution of the paper lies in the following. (i) Introducing $N$-bit-delay AIFV codes, constructed by multiple code trees with higher flexibility than the conventional AIFV codes. (ii) Proving that the proposed codes can represent any uniquely-encodable and uniquely-decodable variable-to-variable length codes. (iii) Showing how to express codes as multiple code trees with minimum decoding delay. (iv) Formulating the constraints of decodability as the comparison of intervals in the real number line. The theoretical results in this paper are expected to be useful for further study on AIFV codes.
AI Autonomy : Self-Initiated Open-World Continual Learning and Adaptation
Venue: arXiv cs.AI 2023
Year: 2023

As more and more AI agents are used in practice, it is time to think about how to make these agents fully autonomous so that they can (1) learn by themselves continually in a self-motivated and self-initiated manner rather than being retrained offline periodically on the initiation of human engineers and (2) accommodate or adapt to unexpected or novel circumstances. As the real-world is an open environment that is full of unknowns or novelties, the capabilities of detecting novelties, characterizing them, accommodating/adapting to them, gathering ground-truth training data and incrementally learning the unknowns/novelties become critical in making the AI agent more and more knowledgeable, powerful and self-sustainable over time. The key challenge here is how to automate the process so that it is carried out continually on the agent's own initiative and through its own interactions with humans, other agents and the environment just like human on-the-job learning. This paper proposes a framework (called SOLA) for this learning paradigm to promote the research of building autonomous and continual learning enabled AI agents. To show feasibility, an implemented agent is also described.
MotionAug: Augmentation with Physical Correction for Human Motion Prediction
Venue: arXiv cs.CV 2023
Year: 2023

This paper presents a motion data augmentation scheme incorporating motion synthesis encouraging diversity and motion correction imposing physical plausibility. This motion synthesis consists of our modified Variational AutoEncoder (VAE) and Inverse Kinematics (IK). In this VAE, our proposed sampling-near-samples method generates various valid motions even with insufficient training motion data. Our IK-based motion synthesis method allows us to generate a variety of motions semi-automatically. Since these two schemes generate unrealistic artifacts in the synthesized motions, our motion correction rectifies them. This motion correction scheme consists of imitation learning with physics simulation and subsequent motion debiasing. For this imitation learning, we propose the PD-residual force that significantly accelerates the training process. Furthermore, our motion debiasing successfully offsets the motion bias induced by imitation learning to maximize the effect of augmentation. As a result, our method outperforms previous noise-based motion augmentation methods by a large margin on both Recurrent Neural Network-based and Graph Convolutional Network-based human motion prediction models. The code is available at https://github.com/meaten/MotionAug.
On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets
Venue: arXiv cs.CC 2023
Year: 2023

Synthesis consists in deciding whether a given labeled transition system (TS) $A$ can be implemented by a net $N$ of type $τ$. In case of a negative decision, it may be possible to convert $A$ into an implementable TS $B$ by applying various modification techniques, like relabeling edges that previously had the same label, suppressing edges/states/events, etc. It may however be useful to limit the number of such modifications to stay close to the original problem, or optimize the technique. In this paper, we show that most of the corresponding problems are NP-complete if $τ$ corresponds to the type of flip-flop nets or some flip-flop net derivatives.
ECOLA: Enhanced Temporal Knowledge Embeddings with Contextualized Language Representations
Venue: arXiv cs.CL 2023
Year: 2023

Since conventional knowledge embedding models cannot take full advantage of the abundant textual information, there have been extensive research efforts in enhancing knowledge embedding using texts. However, existing enhancement approaches cannot apply to temporal knowledge graphs (tKGs), which contain time-dependent event knowledge with complex temporal dynamics. Specifically, existing enhancement approaches often assume knowledge embedding is time-independent. In contrast, the entity embedding in tKG models usually evolves, which poses the challenge of aligning temporally relevant texts with entities. To this end, we propose to study enhancing temporal knowledge embedding with textual data in this paper. As an approach to this task, we propose Enhanced Temporal Knowledge Embeddings with Contextualized Language Representations (ECOLA), which takes the temporal aspect into account and injects textual information into temporal knowledge embedding. To evaluate ECOLA, we introduce three new datasets for training and evaluating ECOLA. Extensive experiments show that ECOLA significantly enhances temporal KG embedding models with up to 287% relative improvements regarding Hits@1 on the link prediction task. The code and models are publicly available on https://anonymous.4open.science/r/ECOLA.
Class-wise Classifier Design Capable of Continual Learning using Adaptive Resonance Theory-based Topological Clustering
Venue: arXiv cs.LG 2023
Year: 2023

This paper proposes a supervised classification algorithm capable of continual learning by utilizing an Adaptive Resonance Theory (ART)-based growing self-organizing clustering algorithm. The ART-based clustering algorithm is theoretically capable of continual learning, and the proposed algorithm independently applies it to each class of training data for generating classifiers. Whenever an additional training data set from a new class is given, a new ART-based clustering will be defined in a different learning space. Thanks to the above-mentioned features, the proposed algorithm realizes continual learning capability. Simulation experiments showed that the proposed algorithm has superior classification performance compared with state-of-the-art clustering-based classification algorithms capable of continual learning.
A Model and Survey of Distributed Data-Intensive Systems
Venue: arXiv cs.DC 2023
Year: 2023

Data is a precious resource in today's society, and is generated at an unprecedented and constantly growing pace. The need to store, analyze, and make data promptly available to a multitude of users introduces formidable challenges in modern software platforms. These challenges radically transformed all research fields that gravitate around data management and processing, with the introduction of distributed data-intensive systems that offer new programming models and implementation strategies to handle data characteristics such as its volume, the rate at which it is produced, its heterogeneity, and its distribution. Each data-intensive system brings its specific choices in terms of data model, usage assumptions, synchronization, processing strategy, deployment, guarantees in terms of consistency, fault tolerance, ordering. Yet, the problems data-intensive systems face and the solutions they propose are frequently overlapping. This paper proposes a unifying model that dissects the core functionalities of data-intensive systems, and precisely discusses alternative design and implementation strategies, pointing out their assumptions and implications. The model offers a common ground to understand and compare highly heterogeneous solutions, with the potential of fostering cross-fertilization across research communities and advancing the field. We apply our model by classifying tens of systems: an exercise that brings to interesting observations on the current trends in the domain of data-intensive systems and suggests open research directions.
Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for $Δ$-Coloring
Venue: arXiv cs.DS 2023
Year: 2023

Every graph with maximum degree $Δ$ can be colored with $(Δ+1)$ colors using a simple greedy algorithm. Remarkably, recent work has shown that one can find such a coloring even in the semi-streaming model. But, in reality, one almost never needs $(Δ+1)$ colors to properly color a graph. Indeed, the celebrated \Brooks' theorem states that every (connected) graph beside cliques and odd cycles can be colored with $Δ$ colors. Can we find a $Δ$-coloring in the semi-streaming model as well? We settle this key question in the affirmative by designing a randomized semi-streaming algorithm that given any graph, with high probability, either correctly declares that the graph is not $Δ$-colorable or outputs a $Δ$-coloring of the graph. The proof of this result starts with a detour. We first (provably) identify the extent to which the previous approaches for streaming coloring fail for $Δ$-coloring: for instance, all these approaches can handle streams with repeated edges and they can run in $o(n^2)$ time -- we prove that neither of these tasks is possible for $Δ$-coloring. These impossibility results however pinpoint exactly what is missing from prior approaches when it comes to $Δ$-coloring. We then build on these insights to design a semi-streaming algorithm that uses $(i)$ a novel sparse-recovery approach based on sparse-dense decompositions to (partially) recover the "problematic" subgraphs of the input -- the ones that form the basis of our impossibility results -- and $(ii)$ a new coloring approach for these subgraphs that allows for recoloring of other vertices in a controlled way without relying on local explorations or finding "augmenting paths" that are generally impossible for semi-streaming algorithms. We believe both these techniques can be of independent interest.
Telling Stories from Computational Notebooks: AI-Assisted Presentation Slides Creation for Presenting Data Science Work
Venue: arXiv cs.HC 2023
Year: 2023

Creating presentation slides is a critical but time-consuming task for data scientists. While researchers have proposed many AI techniques to lift data scientists' burden on data preparation and model selection, few have targeted the presentation creation task. Based on the needs identified from a formative study, this paper presents NB2Slides, an AI system that facilitates users to compose presentations of their data science work. NB2Slides uses deep learning methods as well as example-based prompts to generate slides from computational notebooks, and take users' input (e.g., audience background) to structure the slides. NB2Slides also provides an interactive visualization that links the slides with the notebook to help users further edit the slides. A follow-up user evaluation with 12 data scientists shows that participants believed NB2Slides can improve efficiency and reduces the complexity of creating slides. Yet, participants questioned the future of full automation and suggested a human-AI collaboration paradigm.
Improving Quality of Service for Users of DAG-based Distributed Ledgers
Venue: arXiv cs.DC 2023
Year: 2023

An outstanding problem in the design of distributed ledgers concerns policies that govern the manner in which users interact with the network. Network usability is crucial to the mainstream adoption of distributed ledgers, particularly for enterprise applications in which most users do not wish to operate full node. For DAG-based ledgers such as IOTA, we propose a user-node interaction mechanism that is designed to ensure the risk of a user experiencing a poor quality of service is low. Our mechanism involves users selecting nodes to issue their transactions to the ledger based on quality of service indicators advertised by the nodes. Simulation results are presented to illustrate the efficacy of the proposed policies.
Adaptive Transformers for Robust Few-shot Cross-domain Face Anti-spoofing
Venue: arXiv cs.CV 2023
Year: 2023

While recent face anti-spoofing methods perform well under the intra-domain setups, an effective approach needs to account for much larger appearance variations of images acquired in complex scenes with different sensors for robust performance. In this paper, we present adaptive vision transformers (ViT) for robust cross-domain face antispoofing. Specifically, we adopt ViT as a backbone to exploit its strength to account for long-range dependencies among pixels. We further introduce the ensemble adapters module and feature-wise transformation layers in the ViT to adapt to different domains for robust performance with a few samples. Experiments on several benchmark datasets show that the proposed models achieve both robust and competitive performance against the state-of-the-art methods for cross-domain face anti-spoofing using a few samples.
Geometry-Aware Supertagging with Heterogeneous Dynamic Convolutions
Venue: arXiv cs.CL 2023
Year: 2023

The syntactic categories of categorial grammar formalisms are structured units made of smaller, indivisible primitives, bound together by the underlying grammar's category formation rules. In the trending approach of constructive supertagging, neural models are increasingly made aware of the internal category structure, which in turn enables them to more reliably predict rare and out-of-vocabulary categories, with significant implications for grammars previously deemed too complex to find practical use. In this work, we revisit constructive supertagging from a graph-theoretic perspective, and propose a framework based on heterogeneous dynamic graph convolutions aimed at exploiting the distinctive structure of a supertagger's output space. We test our approach on a number of categorial grammar datasets spanning different languages and grammar formalisms, achieving substantial improvements over previous state of the art scores. Code will be made available at https://github.com/konstantinosKokos/dynamic-graph-supertagging
Automatic Speech Recognition for Speech Assessment of Persian Preschool Children
Venue: arXiv cs.CL 2023
Year: 2023

Preschool evaluation is crucial because it gives teachers and parents influential knowledge about children's growth and development. The COVID-19 pandemic has highlighted the necessity of online assessment for preschool children. One of the areas that should be tested is their ability to speak. Employing an Automatic Speech Recognition (ASR) system would not help since they are pre-trained on voices that differ from children's in terms of frequency and amplitude. Because most of these are pre-trained with data in a specific range of amplitude, their objectives do not make them ready for voices in different amplitudes. To overcome this issue, we added a new objective to the masking objective of the Wav2Vec 2.0 model called Random Frequency Pitch (RFP). In addition, we used our newly introduced dataset to fine-tune our model for Meaningless Words (MW) and Rapid Automatic Naming (RAN) tests. Using masking in concatenation with RFP outperforms the masking objective of Wav2Vec 2.0 by reaching a Word Error Rate (WER) of 1.35. Our new approach reaches a WER of 6.45 on the Persian section of the CommonVoice dataset. Furthermore, our novel methodology produces positive outcomes in zero- and few-shot scenarios.
A DNN Optimizer that Improves over AdaBelief by Suppression of the Adaptive Stepsize Range
Venue: arXiv cs.LG 2023
Year: 2023

We make contributions towards improving adaptive-optimizer performance. Our improvements are based on suppression of the range of adaptive stepsizes in the AdaBelief optimizer. Firstly, we show that the particular placement of the parameter epsilon within the update expressions of AdaBelief reduces the range of the adaptive stepsizes, making AdaBelief closer to SGD with momentum. Secondly, we extend AdaBelief by further suppressing the range of the adaptive stepsizes. To achieve the above goal, we perform mutual layerwise vector projections between the gradient g_t and its first momentum m_t before using them to estimate the second momentum. The new optimization method is referred to as Aida. Thirdly, extensive experimental results show that Aida outperforms nine optimizers when training transformers and LSTMs for NLP, and VGG and ResNet for image classification over CIAF10 and CIFAR100 while matching the best performance of the nine methods when training WGAN-GP models for image generation tasks. Furthermore, Aida produces higher validation accuracies than AdaBelief for training ResNet18 over ImageNet. Code is available <a href="https://github.com/guoqiang-x-zhang/AidaOptimizer">at this URL</a>
Sparse Federated Learning with Hierarchical Personalized Models
Venue: arXiv cs.LG 2023
Year: 2023

Federated learning (FL) can achieve privacy-safe and reliable collaborative training without collecting users' private data. Its excellent privacy security potential promotes a wide range of FL applications in Internet-of-Things (IoT), wireless networks, mobile devices, autonomous vehicles, and cloud medical treatment. However, the FL method suffers from poor model performance on non-i.i.d. data and excessive traffic volume. To this end, we propose a personalized FL algorithm using a hierarchical proximal mapping based on the moreau envelop, named sparse federated learning with hierarchical personalized models (sFedHP), which significantly improves the global model performance facing diverse data. A continuously differentiable approximated L1-norm is also used as the sparse constraint to reduce the communication cost. Convergence analysis shows that sFedHP's convergence rate is state-of-the-art with linear speedup and the sparse constraint only reduces the convergence rate to a small extent while significantly reducing the communication cost. Experimentally, we demonstrate the benefits of sFedHP compared with the FedAvg, HierFAVG (hierarchical FedAvg), and personalized FL methods based on local customization, including FedAMP, FedProx, Per-FedAvg, pFedMe, and pFedGP.
Sublinear-Time Probabilistic Cellular Automata
Venue: arXiv cs.FL 2023
Year: 2023

We propose and investigate a probabilistic model of sublinear-time one-dimensional cellular automata. In particular, we modify the model of ACA (which are cellular automata that accept if and only if all cells simultaneously accept) so that every cell changes its state not only dependent on the states it sees in its neighborhood but also on an unbiased coin toss of its own. The resulting model is dubbed probabilistic ACA (PACA). We consider one- and two-sided error versions of the model (in the same spirit as the classes $\mathsf{RP}$ and $\mathsf{BPP}$) and establish a separation between the classes of languages they can recognize all the way up to $o(\sqrt{n})$ time. As a consequence, we have a $Ω(\sqrt{n})$ lower bound for derandomizing constant-time two-sided error PACAs (using deterministic ACAs). We also prove that derandomization of $T(n)$-time PACAs (to polynomial-time deterministic cellular automata) for various regimes of $T(n) = ω(\log n)$ implies non-trivial derandomization results for the class $\mathsf{RP}$ (e.g., $\mathsf{P} = \mathsf{RP}$). The main contribution is an almost full characterization of the constant-time PACA classes: For one-sided error, the class equals that of the deterministic model; that is, constant-time one-sided error PACAs can be fully derandomized with only a constant multiplicative overhead in time complexity. As for two-sided error, we identify a natural class we call the linearly testable languages ($\mathsf{LLT}$) and prove that the languages decidable by constant-time two-sided error PACAs are "sandwiched" in-between the closure of $\mathsf{LLT}$ under union and intersection and the class of locally threshold testable languages ($\mathsf{LTT}$).
Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics
Venue: arXiv cs.DS 2023
Year: 2023

We consider the design of sublinear space and query complexity algorithms for estimating the cost of a minimum spanning tree (MST) and the cost of a minimum traveling salesman (TSP) tour in a metric on $n$ points. We first consider the $o(n)$-space regime and show that, when the input is a stream of all $\binom{n}{2}$ entries of the metric, for any $α\ge 2$, both MST and TSP cost can be $α$-approximated using $\tilde{O}(n/α)$ space, and that $Ω(n/α^2)$ space is necessary for this task. Moreover, we show that even if the streaming algorithm is allowed $p$ passes over a metric stream, it still requires $\tildeΩ(\sqrt{n/αp^2})$ space. We next consider the semi-streaming regime, where computing even the exact MST cost is easy and the main challenge is to estimate TSP cost to within a factor that is strictly better than $2$. We show that, if the input is a stream of all edges of the weighted graph that induces the underlying metric, for any $\varepsilon > 0$, any one-pass $(2-\varepsilon)$-approximation of TSP cost requires $Ω(\varepsilon^2 n^2)$ space; on the other hand, there is an $\tilde{O}(n)$ space two-pass algorithm that approximates the TSP cost to within a factor of 1.96. Finally, we consider the query complexity of estimating metric TSP cost to within a factor that is strictly better than $2$, when the algorithm is given access to a matrix that specifies pairwise distances between all points. For MST estimation in this model, it is known that a $(1+\varepsilon)$-approximation is achievable with $\tilde{O}(n/\varepsilon^{O(1)})$ queries. We design an algorithm that performs $\tilde{O}(n^{1.5})$ distance queries and achieves a strictly better than $2$-approximation when either the metric is known to contain a spanning tree supported on weight-$1$ edges or the algorithm is given access to a minimum spanning tree of the graph.
Online Algorithms for Matching Platforms with Multi-Channel Traffic
Venue: arXiv cs.GT 2023
Year: 2023

Two-sided platforms rely on their recommendation algorithms to help visitors successfully find a match. However, on platforms such as VolunteerMatch (VM) -- which has facilitated millions of connections between volunteers and nonprofits -- a sizable fraction of website traffic arrives directly to a nonprofit's volunteering page via an external link, thus bypassing the platform's recommendation algorithm. We study how such platforms should account for this external traffic in the design of their recommendation algorithms, given the goal of maximizing successful matches. We model the platform's problem as a special case of online matching, where (using VM terminology) volunteers arrive sequentially and probabilistically match with one opportunity, each of which has finite need for volunteers. In our framework, external traffic is interested only in their targeted opportunity; by contrast, internal traffic may be interested in many opportunities, and the platform's online algorithm selects which opportunity to recommend. In evaluating different algorithms, we parameterize the competitive ratio based on the amount of external traffic. After demonstrating the shortcomings of a commonly-used algorithm that is optimal in the absence of external traffic, we propose a new algorithm -- Adaptive Capacity (AC) -- which accounts for matches differently based on whether they originate from internal or external traffic. We provide a lower bound on AC's competitive ratio that is increasing in the amount of external traffic and that is close to (and, in some regimes, exactly matches) the parameterized upper bound we establish on the competitive ratio of any online algorithm. We complement our theoretical results with a numerical study motivated by VM data that demonstrates the strong performance of AC and furthers our understanding of the difference between AC and other commonly-used algorithms.