OpenRaiser/Intern-Atlas huggingface dataset:
Engineering flexible machine learning systems by traversing functionally-invariant paths
Venue: arXiv cs.LG 2023
Year: 2023

Transformers have emerged as the state of the art neural network architecture for natural language processing and computer vision. In the foundation model paradigm, large transformer models (BERT, GPT3/4, Bloom, ViT) are pre-trained on self-supervised tasks such as word or image masking, and then, adapted through fine-tuning for downstream user applications including instruction following and Question Answering. While many approaches have been developed for model fine-tuning including low-rank weight update strategies (eg. LoRA), underlying mathematical principles that enable network adaptation without knowledge loss remain poorly understood. Here, we introduce a differential geometry framework, functionally invariant paths (FIP), that provides flexible and continuous adaptation of neural networks for a range of machine learning goals and network sparsification objectives. We conceptualize the weight space of a neural network as a curved Riemannian manifold equipped with a metric tensor whose spectrum defines low rank subspaces in weight space that accommodate network adaptation without loss of prior knowledge. We formalize adaptation as movement along a geodesic path in weight space while searching for networks that accommodate secondary objectives. With modest computational resources, the FIP algorithm achieves comparable to state of the art performance on continual learning and sparsification tasks for language models (BERT), vision transformers (ViT, DeIT), and the CNNs. Broadly, we conceptualize a neural network as a mathematical object that can be iteratively transformed into distinct configurations by the path-sampling algorithm to define a sub-manifold of weight space that can be harnessed to achieve user goals.
An efficient topology optimization method based on adaptive reanalysis with projection reduction
Venue: arXiv cs.CE 2023
Year: 2023

Efficient topology optimization based on the adaptive auxiliary reduced model reanalysis (AARMR) is proposed to improve computational efficiency and scale. In this method, a projection auxiliary reduced model (PARM) is integrated into the combined approximation reduced model (CARM) to reduce the dimension of the model in different aspects. First, the CARM restricts the solution space to avoid large matrix factorization. Second, the PARM is proposed to construct the CARM dynamically to save computational cost. Furthermore, the multi-grid conjugate gradient method is suggested to update PARM adaptively. Finally, several classic numerical examples are tested to show that the proposed method not only significantly improves computational efficiency, but also can solve large-scale problems that are difficult to solve by direct solvers due to the memory limitations.
A Survey on Distributed Online Optimization and Game
Venue: arXiv cs.LG 2023
Year: 2023

Distributed online optimization and game have been increasingly researched in the last decade, mostly motivated by its wide applications in sensor networks, robotics (e.g., distributed target tracking and formation control), smart grids, deep learning, and so forth. In these problems, there is a network of agents who may be cooperative (i.e., distributed online optimization) or noncooperative (i.e., online game) through local information exchanges. And the local cost function of each agent is often time-varying in dynamic and even adversarial environments. At each time, a decision must be made by each agent based on historical information at hand without knowing future information on cost functions. For these problems, a comprehensive survey is still lacking. This paper aims to provide a thorough overview of distributed online optimization and game from the perspective of problem settings, communication, computation, algorithms, and performances. In addition, some potential future directions are also discussed.
Assessing Routing Algorithms for PCNs: Full Evaluation Results
Venue: arXiv cs.DC 2023
Year: 2023

Within this Technical Report, we present the full analysis of 61 routing protocols for Wireless Sensor Networks (WSNs) for the purposes of routing in Payment Channel Networks (PCNs). In addition, we present the full results of the implementation of the three algorithms E-TORA, TERP, and M-DART.
Weighted Counting of Matchings in Unbounded-Treewidth Graph Families
Venue: arXiv cs.CC 2023
Year: 2023

We consider a weighted counting problem on matchings, denoted $\textrm{PrMatching}(\mathcal{G})$, on an arbitrary fixed graph family $\mathcal{G}$. The input consists of a graph $G\in \mathcal{G}$ and of rational probabilities of existence on every edge of $G$, assuming independence. The output is the probability of obtaining a matching of $G$ in the resulting distribution, i.e., a set of edges that are pairwise disjoint. It is known that, if $\mathcal{G}$ has bounded treewidth, then $\textrm{PrMatching}(\mathcal{G})$ can be solved in polynomial time. In this paper we show that, under some assumptions, bounded treewidth in fact characterizes the tractable graph families for this problem. More precisely, we show intractability for all graph families $\mathcal{G}$ satisfying the following treewidth-constructibility requirement: given an integer $k$ in unary, we can construct in polynomial time a graph $G \in \mathcal{G}$ with treewidth at least $k$. Our hardness result is then the following: for any treewidth-constructible graph family $\mathcal{G}$, the problem $\textrm{PrMatching}(\mathcal{G})$ is intractable. This generalizes known hardness results for weighted matching counting under some restrictions that do not bound treewidth, e.g., being planar, 3-regular, or bipartite; it also answers a question left open in Amarilli, Bourhis and Senellart (PODS'16). We also obtain a similar lower bound for the weighted counting of edge covers.
Reality-based UTXO Ledger
Venue: arXiv cs.DC 2023
Year: 2023

The Unspent Transaction Output (UTXO) model is commonly used in the field of Distributed Ledger Technology (DLT) to transfer value between participants. One of its advantages is that it allows parallel processing of transactions, as independent transactions can be added in any order. This property of order invariance and parallelisability has potential benefits in terms of scalability. However, since the UTXO Ledger is an append-only data structure, this advantage is compromised through the presence of conflicting transactions. We propose an extended UTXO Ledger model that optimistically updates the ledger and keeps track of the dependencies of the possible conflicts. In the presence of a conflict resolution mechanism, we propose a method to reduce the extended ledger back to a consistent UTXO Ledger.
Optimal $(r,δ)$-LRCs from monomial-Cartesian codes and their subfield-subcodes
Venue: arXiv cs.IT 2023
Year: 2023

We study monomial-Cartesian codes (MCCs) which can be regarded as $(r,δ)$-locally recoverable codes (LRCs). These codes come with a natural bound for their minimum distance and we determine those giving rise to $(r,δ)$-optimal LRCs for that distance, which are in fact $(r,δ)$-optimal. A large subfamily of MCCs admits subfield-subcodes with the same parameters of certain optimal MCCs but over smaller supporting fields. This fact allows us to determine infinitely many sets of new $(r,δ)$-optimal LRCs and their parameters.
Intelligent Trajectory Design for RIS-NOMA aided Multi-robot Communications
Venue: arXiv cs.RO 2023
Year: 2023

A novel reconfigurable intelligent surface-aided multi-robot network is proposed, where multiple mobile robots are served by an access point (AP) through non-orthogonal multiple access (NOMA). The goal is to maximize the sum-rate of whole trajectories for the multi-robot system by jointly optimizing trajectories and NOMA decoding orders of robots, phase-shift coefficients of the RIS, and the power allocation of the AP, subject to predicted initial and final positions of robots and the quality of service (QoS) of each robot. To tackle this problem, an integrated machine learning (ML) scheme is proposed, which combines long short-term memory (LSTM)-autoregressive integrated moving average (ARIMA) model and dueling double deep Q-network (D$^{3}$QN) algorithm. For initial and final position prediction for robots, the LSTM-ARIMA is able to overcome the problem of gradient vanishment of non-stationary and non-linear sequences of data. For jointly determining the phase shift matrix and robots' trajectories, D$^{3}$QN is invoked for solving the problem of action value overestimation. Based on the proposed scheme, each robot holds an optimal trajectory based on the maximum sum-rate of a whole trajectory, which reveals that robots pursue long-term benefits for whole trajectory design. Numerical results demonstrated that: 1) LSTM-ARIMA model provides high accuracy predicting model; 2) The proposed D$^{3}$QN algorithm can achieve fast average convergence; and 3) RIS-NOMA networks have superior network performance compared to RIS-aided orthogonal counterparts.
Mapping the landscape of histomorphological cancer phenotypes using self-supervised learning on unlabeled, unannotated pathology slides
Venue: arXiv cs.CV 2023
Year: 2023

Definitive cancer diagnosis and management depend upon the extraction of information from microscopy images by pathologists. These images contain complex information requiring time-consuming expert human interpretation that is prone to human bias. Supervised deep learning approaches have proven powerful for classification tasks, but they are inherently limited by the cost and quality of annotations used for training these models. To address this limitation of supervised methods, we developed Histomorphological Phenotype Learning (HPL), a fully blue{self-}supervised methodology that requires no expert labels or annotations and operates via the automatic discovery of discriminatory image features in small image tiles. Tiles are grouped into morphologically similar clusters which constitute a library of histomorphological phenotypes, revealing trajectories from benign to malignant tissue via inflammatory and reactive phenotypes. These clusters have distinct features which can be identified using orthogonal methods, linking histologic, molecular and clinical phenotypes. Applied to lung cancer tissues, we show that they align closely with patient survival, with histopathologically recognised tumor types and growth patterns, and with transcriptomic measures of immunophenotype. We then demonstrate that these properties are maintained in a multi-cancer study. These results show the clusters represent recurrent host responses and modes of tumor growth emerging under natural selection. Code, pre-trained models, learned embeddings, and documentation are available to the community at https://github.com/AdalbertoCq/Histomorphological-Phenotype-Learning
Hyperbolic Relevance Matching for Neural Keyphrase Extraction
Venue: arXiv cs.CL 2023
Year: 2023

Keyphrase extraction is a fundamental task in natural language processing and information retrieval that aims to extract a set of phrases with important information from a source document. Identifying important keyphrase is the central component of the keyphrase extraction task, and its main challenge is how to represent information comprehensively and discriminate importance accurately. In this paper, to address these issues, we design a new hyperbolic matching model (HyperMatch) to represent phrases and documents in the same hyperbolic space and explicitly estimate the phrase-document relevance via the Poincaré distance as the important score of each phrase. Specifically, to capture the hierarchical syntactic and semantic structure information, HyperMatch takes advantage of the hidden representations in multiple layers of RoBERTa and integrates them as the word embeddings via an adaptive mixing layer. Meanwhile, considering the hierarchical structure hidden in the document, HyperMatch embeds both phrases and documents in the same hyperbolic space via a hyperbolic phrase encoder and a hyperbolic document encoder. This strategy can further enhance the estimation of phrase-document relevance due to the good properties of hyperbolic space. In this setting, the keyphrase extraction can be taken as a matching problem and effectively implemented by minimizing a hyperbolic margin-based triplet loss. Extensive experiments are conducted on six benchmarks and demonstrate that HyperMatch outperforms the state-of-the-art baselines.
Hybrid Transformer with Multi-level Fusion for Multimodal Knowledge Graph Completion
Venue: arXiv cs.CL 2023
Year: 2023

Multimodal Knowledge Graphs (MKGs), which organize visual-text factual knowledge, have recently been successfully applied to tasks such as information retrieval, question answering, and recommendation system. Since most MKGs are far from complete, extensive knowledge graph completion studies have been proposed focusing on the multimodal entity, relation extraction and link prediction. However, different tasks and modalities require changes to the model architecture, and not all images/objects are relevant to text input, which hinders the applicability to diverse real-world scenarios. In this paper, we propose a hybrid transformer with multi-level fusion to address those issues. Specifically, we leverage a hybrid transformer architecture with unified input-output for diverse multimodal knowledge graph completion tasks. Moreover, we propose multi-level fusion, which integrates visual and text representation via coarse-grained prefix-guided interaction and fine-grained correlation-aware fusion modules. We conduct extensive experiments to validate that our MKGformer can obtain SOTA performance on four datasets of multimodal link prediction, multimodal RE, and multimodal NER. Code is available in https://github.com/zjunlp/MKGformer.
Intra and Cross-spectrum Iris Presentation Attack Detection in the NIR and Visible Domains
Venue: arXiv cs.CV 2023
Year: 2023

Iris Presentation Attack Detection (PAD) is essential to secure iris recognition systems. Recent iris PAD solutions achieved good performance by leveraging deep learning techniques. However, most results were reported under intra-database scenarios and it is unclear if such solutions can generalize well across databases and capture spectra. These PAD methods run the risk of overfitting because of the binary label supervision during the network training, which serves global information learning but weakens the capture of local discriminative features. This chapter presents a novel attention-based deep pixel-wise binary supervision (A-PBS) method. A-PBS utilizes pixel-wise supervision to capture the fine-grained pixel/patch-level cues and attention mechanism to guide the network to automatically find regions where most contribute to an accurate PAD decision. Extensive experiments are performed on six NIR and one visible-light iris databases to show the effectiveness and robustness of proposed A-PBS methods. We additionally conduct extensive experiments under intra-/cross-database and intra-/cross-spectrum for detailed analysis. The results of our experiments indicates the generalizability of the A-PBS iris PAD approach.
Unsupervised Mismatch Localization in Cross-Modal Sequential Data with Application to Mispronunciations Localization
Venue: arXiv cs.LG 2023
Year: 2023

Content mismatch usually occurs when data from one modality is translated to another, e.g. language learners producing mispronunciations (errors in speech) when reading a sentence (target text) aloud. However, most existing alignment algorithms assume that the content involved in the two modalities is perfectly matched, thus leading to difficulty in locating such mismatch between speech and text. In this work, we develop an unsupervised learning algorithm that can infer the relationship between content-mismatched cross-modal sequential data, especially for speech-text sequences. More specifically, we propose a hierarchical Bayesian deep learning model, dubbed mismatch localization variational autoencoder (ML-VAE), which decomposes the generative process of the speech into hierarchically structured latent variables, indicating the relationship between the two modalities. Training such a model is very challenging due to the discrete latent variables with complex dependencies involved. To address this challenge, we propose a novel and effective training procedure that alternates between estimating the hard assignments of the discrete latent variables over a specifically designed mismatch localization finite-state acceptor (ML-FSA) and updating the parameters of neural networks. In this work, we focus on the mismatch localization problem for speech and text, and our experimental results show that ML-VAE successfully locates the mismatch between text and speech, without the need for human annotations for model training.
Cut-Down de Bruijn Sequences
Venue: arXiv cs.DS 2023
Year: 2023

A cut-down de Bruijn sequence is a cyclic string of length $L$, where $1 \leq L \leq k^n$, such that every substring of length $n$ appears at most once. Etzion [Theor. Comp. Sci 44 (1986)] gives an algorithm to construct binary cut-down de Bruijn sequences that requires $o(n)$ simple $n$-bit operations per symbol generated. In this paper, we simplify the algorithm and improve the running time to $\mathcal{O}(n)$ time per symbol generated using $\mathcal{O}(n)$ space. We then provide the first successor-rule approach for constructing a binary cut-down de Bruijn sequence by leveraging recent ranking algorithms for fixed-density Lyndon words. Finally, we develop an algorithm to generate cut-down de Bruijn sequences for $k>2$ that runs in $\mathcal{O}(n)$ time per symbol using $\mathcal{O}(n)$ space after some initialization. While our $k$-ary algorithm is based on our simplified version of Etzion's binary algorithm, a number of non-trivial adaptations are required to generalize to larger alphabets.
Understanding Urban Water Consumption using Remotely Sensed Data
Venue: arXiv cs.CV 2023
Year: 2023

Urban metabolism is an active field of research that deals with the estimation of emissions and resource consumption from urban regions. The analysis could be carried out through a manual surveyor by the implementation of elegant machine learning algorithms. In this exploratory work, we estimate the water consumption by the buildings in the region captured by satellite imagery. To this end, we break our analysis into three parts: i) Identification of building pixels, given a satellite image, followed by ii) identification of the building type (residential/non-residential) from the building pixels, and finally iii) using the building pixels along with their type to estimate the water consumption using the average per unit area consumption for different building types as obtained from municipal surveys.
Aksharantar: Open Indic-language Transliteration datasets and models for the Next Billion Users
Venue: arXiv cs.CL 2023
Year: 2023

Transliteration is very important in the Indian language context due to the usage of multiple scripts and the widespread use of romanized inputs. However, few training and evaluation sets are publicly available. We introduce Aksharantar, the largest publicly available transliteration dataset for Indian languages created by mining from monolingual and parallel corpora, as well as collecting data from human annotators. The dataset contains 26 million transliteration pairs for 21 Indic languages from 3 language families using 12 scripts. Aksharantar is 21 times larger than existing datasets and is the first publicly available dataset for 7 languages and 1 language family. We also introduce the Aksharantar testset comprising 103k word pairs spanning 19 languages that enables a fine-grained analysis of transliteration models on native origin words, foreign words, frequent words, and rare words. Using the training set, we trained IndicXlit, a multilingual transliteration model that improves accuracy by 15% on the Dakshina test set, and establishes strong baselines on the Aksharantar testset introduced in this work. The models, mining scripts, transliteration guidelines, and datasets are available at https://github.com/AI4Bharat/IndicXlit under open-source licenses. We hope the availability of these large-scale, open resources will spur innovation for Indic language transliteration and downstream applications. We hope the availability of these large-scale, open resources will spur innovation for Indic language transliteration and downstream applications.
Constrained Backward Time Travel Planning is in P
Venue: arXiv cs.CC 2023
Year: 2023

We consider transportation networks that are modeled by dynamic graphs, and introduce the possibility for traveling agents to use Backward Time-Travel (BTT) devices at any node to go back in time (to some extent, and with some appropriate fee) before resuming their trip. We focus on dynamic line graphs. In more detail, we propose exact algorithms to compute travel plans with constraints on the BTT cost or on how far back in time you can go, while minimizing travel delay (that is, the time difference between the arrival instant and the starting instant), in polynomial time. We study the impact of the BTT devices pricing policies on the computation process of those plans considering travel delay and cost, and provide necessary properties that pricing policies should satisfy to enable to compute such plans. Finally, we provide an optimal online algorithm for the unconstrained problem when the cost function is the identity.
Graph Fusion Network for Multi-Oriented Object Detection
Venue: arXiv cs.CV 2023
Year: 2023

In object detection, non-maximum suppression (NMS) methods are extensively adopted to remove horizontal duplicates of detected dense boxes for generating final object instances. However, due to the degraded quality of dense detection boxes and not explicit exploration of the context information, existing NMS methods via simple intersection-over-union (IoU) metrics tend to underperform on multi-oriented and long-size objects detection. Distinguishing with general NMS methods via duplicate removal, we propose a novel graph fusion network, named GFNet, for multi-oriented object detection. Our GFNet is extensible and adaptively fuse dense detection boxes to detect more accurate and holistic multi-oriented object instances. Specifically, we first adopt a locality-aware clustering algorithm to group dense detection boxes into different clusters. We will construct an instance sub-graph for the detection boxes belonging to one cluster. Then, we propose a graph-based fusion network via Graph Convolutional Network (GCN) to learn to reason and fuse the detection boxes for generating final instance boxes. Extensive experiments both on public available multi-oriented text datasets (including MSRA-TD500, ICDAR2015, ICDAR2017-MLT) and multi-oriented object datasets (DOTA) verify the effectiveness and robustness of our method against general NMS methods in multi-oriented object detection.