OpenRaiser/Intern-Atlas huggingface dataset:
Communication-Efficient Distributed Deep Learning: A Comprehensive Survey
Venue: arXiv cs.DC 2023
Year: 2023

Distributed deep learning (DL) has become prevalent in recent years to reduce training time by leveraging multiple computing devices (e.g., GPUs/TPUs) due to larger models and datasets. However, system scalability is limited by communication becoming the performance bottleneck. Addressing this communication issue has become a prominent research topic. In this paper, we provide a comprehensive survey of the communication-efficient distributed training algorithms, focusing on both system-level and algorithmic-level optimizations. We first propose a taxonomy of data-parallel distributed training algorithms that incorporates four primary dimensions: communication synchronization, system architectures, compression techniques, and parallelism of communication and computing tasks. We then investigate state-of-the-art studies that address problems in these four dimensions. We also compare the convergence rates of different algorithms to understand their convergence speed. Additionally, we conduct extensive experiments to empirically compare the convergence performance of various mainstream distributed training algorithms. Based on our system-level communication cost analysis, theoretical and experimental convergence speed comparison, we provide readers with an understanding of which algorithms are more efficient under specific distributed environments. Our research also extrapolates potential directions for further optimizations.
Hyperplane Arrangements of Trained ConvNets Are Biased
Venue: arXiv cs.CV 2023
Year: 2023

We investigate the geometric properties of the functions learned by trained ConvNets in the preactivation space of their convolutional layers, by performing an empirical study of hyperplane arrangements induced by a convolutional layer. We introduce statistics over the weights of a trained network to study local arrangements and relate them to the training dynamics. We observe that trained ConvNets show a significant statistical bias towards regular hyperplane configurations. Furthermore, we find that layers showing biased configurations are critical to validation performance for the architectures considered, trained on CIFAR10, CIFAR100 and ImageNet.
Information-Theoretic Foundations of Mismatched Decoding
Venue: arXiv cs.IT 2023
Year: 2023

Shannon's channel coding theorem characterizes the maximal rate of information that can be reliably transmitted over a communication channel when optimal encoding and decoding strategies are used. In many scenarios, however, practical considerations such as channel uncertainty and implementation constraints rule out the use of an optimal decoder. The mismatched decoding problem addresses such scenarios by considering the case that the decoder cannot be optimized, but is instead fixed as part of the problem statement. This problem is not only of direct interest in its own right, but also has close connections with other long-standing theoretical problems in information theory. In this monograph, we survey both classical literature and recent developments on the mismatched decoding problem, with an emphasis on achievable random-coding rates for memoryless channels. We present two widely-considered achievable rates known as the generalized mutual information (GMI) and the LM rate, and overview their derivations and properties. In addition, we survey several improved rates via multi-user coding techniques, as well as recent developments and challenges in establishing upper bounds on the mismatch capacity, and an analogous mismatched encoding problem in rate-distortion theory. Throughout the monograph, we highlight a variety of applications and connections with other prominent information theory problems.
Last Round Convergence and No-Instant Regret in Repeated Games with Asymmetric Information
Venue: arXiv cs.GT 2023
Year: 2023

This paper considers repeated games in which one player has more information about the game than the other players. In particular, we investigate repeated two-player zero-sum games where only the column player knows the payoff matrix A of the game. Suppose that while repeatedly playing this game, the row player chooses her strategy at each round by using a no-regret algorithm to minimize her (pseudo) regret. We develop a no-instant-regret algorithm for the column player to exhibit last round convergence to a minimax equilibrium. We show that our algorithm is efficient against a large set of popular no-regret algorithms of the row player, including the multiplicative weight update algorithm, the online mirror descent method/follow-the-regularized-leader, the linear multiplicative weight update algorithm, and the optimistic multiplicative weight update.
Using constraint structure and an improved object detection network to detect the 12^{th} Vertebra from CT images with a limited field of view for image-guided radiotherapy
Venue: arXiv cs.CV 2023
Year: 2023

Image guidance has been widely used in radiation therapy. Correctly identifying the bounding box of the anatomical landmarks from limited field of views is the key to success. In image-guided radiation therapy (IGRT), the detection of those landmarks like the 12th vertebra (T12) still requires tedious manual inspections and annotations; and superior-inferior misalignment to the wrong vertebral body is still relatively common. It is necessary to develop an automated approach to detect those landmarks from images. The challenges of training a model to identify T12 vertebrae automatically mainly are high shape similarity between T12 and neighboring vertebrae, limited annotated data, and class imbalance. This study proposed a novel 3D detection network, requiring only a small amount of training data. Our approach has the following innovations, including 1) the introduction of an auxiliary network to build constraint feature map for improving the model's generalization, especially when the constraint structure is easier to be detected than the main one; 2) an improved detection head and target functions for accurate bounding box detection; and 3) an improved loss functions to address the high class imbalance. Our proposed network was trained, validated and tested on anotated CT images from 55 patients and demonstrated accurate distinguish T12 vertebra from its neighboring vertebrae of high shape similarity. Our proposed algorithm yielded the bounding box center and size errors of 3.98\pm2.04mm and 16.83\pm8.34mm, respectively. Our approach significantly outperformed state-of-the-arts Retina-Net3D in average precision (AP) at IoU thresholds of 0.35 and 0.5, with AP increasing from 0 to 95.4 and 0 to 64.7, respectively. In summary, our approach has a great potential to be integrated into the clinical workflow to improve the safety of IGRT.
Comparison of a Head-Mounted Display and a Curved Screen in a Multi-Talker Audiovisual Listening Task
Venue: arXiv cs.HC 2023
Year: 2023

Introduction: Virtual audiovisual technology and its methodology has yet to be established for psychoacoustic research. This study examined the effects of different audiovisual conditions on preference when listening to multi-talker conversations. The study's goal is to explore and assess audiovisual technologies in the context of hearing research. Methods: The participants listened to audiovisual conversations between four talkers. Two displays were tested and compared: a curved screen (CS) and a head-mounted display (HMD). Using three visual conditions (audio-only, virtual characters and video recordings), three groups of participants were tested: seventeen young normal-hearing, ten older normal-hearing, and ten older hearing-impaired listeners. Results: Open interviews showed that the CS was preferred over the HMD for older normal-hearing participants and that video recordings were the preferred visual condition. Young and older hearing-impaired participants did not show a preference between the CS and the HMD. Conclusions: CSs and video recordings should be the preferred audiovisual setup of laboratories and clinics, although HMDs and virtual characters can be used for hearing research when necessary and suitable.
Completeness of Nominal PROPs
Venue: arXiv cs.LO 2023
Year: 2023

We introduce nominal string diagrams as string diagrams internal in the category of nominal sets. This leads us to define nominal PROPs and nominal monoidal theories. We show that the categories of ordinary PROPs and nominal PROPs are equivalent. This equivalence is then extended to symmetric monoidal theories and nominal monoidal theories, which allows us to transfer completeness results between ordinary and nominal calculi for string diagrams.
Calculating Pose with Vanishing Points of Visual-Sphere Perspective Model
Venue: arXiv cs.CV 2023
Year: 2023

The goal of the proposed method is to directly obtain a pose matrix of a known rectangular target, without estimation, using geometric techniques. This method is specifically tailored for real-time, extreme imaging setups exceeding 180° field of view, such as a fish-eye camera view. The introduced algorithm employs geometric algebra to determine the pose for a pair of coplanar parallel lines (ideally a tangent pair as in a rectangle). This is achieved by computing vanishing points on a visual unit sphere, which correspond to pose matrix vectors. The algorithm can determine pose for an extremely distorted view source without prior rectification, owing to a visual-sphere perspective model mapping of view coordinates. Mapping can be performed using either a perspective map lookup or a parametric universal perspective distortion model, which is also presented in this paper. The outcome is a robust pose matrix computation that can be executed on an embedded system using a microcontroller, offering high accuracy and low latency. This method can be further extended to a cubic target setup for comprehensive camera calibration. It may also prove valuable in other applications requiring low latency and extreme viewing angles.
Church Synthesis on Register Automata over Linearly Ordered Data Domains
Venue: arXiv cs.FL 2023
Year: 2023

In a Church synthesis game, two players, Adam and Eve, alternately pick some element in a finite alphabet, for an infinite number of rounds. The game is won by Eve if the omega-word formed by this infinite interaction belongs to a given language S, called the specification. It is well-known that for omega-regular specifications, it is decidable whether Eve has a strategy to enforce the specification no matter what Adam does. We study the extension of Church synthesis games to the linearly ordered data domains (Q, <) and (N, <). In this setting, the infinite interaction between Adam and Eve results in an omega-data word, i.e., an infinite sequence of elements in the domain. We study this problem when specifications are given as register automata. Those automata consist in finite automata equipped with a finite set of registers in which they can store data values, that they can then compare with incoming data values with respect to the linear order. Church games over (N, <) are however undecidable, even for deterministic register automata. Thus, we introduce one-sided Church games, where Eve instead operates over a finite alphabet, while Adam still manipulates data. We show that they are determined, and that deciding the existence of a winning strategy is in ExpTime, both for Q and N. This follows from a study of constraint sequences, which abstract the behaviour of register automata, and allow us to reduce Church games to omega-regular games. We present an application of one-sided Church games to a transducer synthesis problem. In this application, a transducer models a reactive system (Eve) which outputs data stored in its registers, depending on its interaction with an environment (Adam) which inputs data to the system.
Multi-Center Federated Learning: Clients Clustering for Better Personalization
Venue: arXiv cs.LG 2023
Year: 2023

Federated learning has received great attention for its capability to train a large-scale model in a decentralized manner without needing to access user data directly. It helps protect the users' private data from centralized collecting. Unlike distributed machine learning, federated learning aims to tackle non-IID data from heterogeneous sources in various real-world applications, such as those on smartphones. Existing federated learning approaches usually adopt a single global model to capture the shared knowledge of all users by aggregating their gradients, regardless of the discrepancy between their data distributions. However, due to the diverse nature of user behaviors, assigning users' gradients to different global models (i.e., centers) can better capture the heterogeneity of data distributions across users. Our paper proposes a novel multi-center aggregation mechanism for federated learning, which learns multiple global models from the non-IID user data and simultaneously derives the optimal matching between users and centers. We formulate the problem as a joint optimization that can be efficiently solved by a stochastic expectation maximization (EM) algorithm. Our experimental results on benchmark datasets show that our method outperforms several popular federated learning methods.
Complexity of $C_k$-coloring in hereditary classes of graphs
Venue: arXiv cs.DS 2023
Year: 2023

For a graph $F$, a graph $G$ is \emph{$F$-free} if it does not contain an induced subgraph isomorphic to $F$. For two graphs $G$ and $H$, an \emph{$H$-coloring} of $G$ is a mapping $f:V(G)\rightarrow V(H)$ such that for every edge $uv\in E(G)$ it holds that $f(u)f(v)\in E(H)$. We are interested in the complexity of the problem $H$-{\sc Coloring}, which asks for the existence of an $H$-coloring of an input graph $G$. In particular, we consider $H$-{\sc Coloring} of $F$-free graphs, where $F$ is a fixed graph and $H$ is an odd cycle of length at least 5. This problem is closely related to the well known open problem of determining the complexity of 3-{\sc Coloring} of $P_t$-free graphs. We show that for every odd $k \geq 5$ the $C_k$-{\sc Coloring} problem, even in the list variant, can be solved in polynomial time in $P_9$-free graphs. The algorithm extends for the case of list version of $C_k$-{\sc Coloring}, where $k$ is an even number of length at least 10. On the other hand, we prove that if some component of $F$ is not a subgraph of a subdividecd claw, then the following problems are NP-complete in $F$-free graphs: a)extension version of $C_k$-{\sc Coloring} for every odd $k \geq 5$, b) list version of $C_k$-{\sc Coloring} for every even $k \geq 6$.
Predictions and algorithmic statistics for infinite sequence
Venue: arXiv cs.IT 2023
Year: 2023

Consider the following prediction problem. Assume that there is a block box that produces bits according to some unknown computable distribution on the binary tree. We know first $n$ bits $x_1 x_2 \ldots x_n$. We want to know the probability of the event that that the next bit is equal to $1$. Solomonoff suggested to use universal semimeasure $m$ for solving this task. He proved that for every computable distribution $P$ and for every $b \in \{0,1\}$ the following holds: $$\sum_{n=1}^{\infty}\sum_{x: l(x)=n} P(x) (P(b | x) - m(b | x))^2 < \infty\ .$$ However, Solomonoff's method has a negative aspect: Hutter and Muchnik proved that there are an universal semimeasure $m$, computable distribution $P$ and a random (in Martin-L{ö}f sense) sequence $x_1 x_2\ldots$ such that $\lim_{n \to \infty} P(x_{n+1} | x_1\ldots x_n) - m(x_{n+1} | x_1\ldots x_n) \nrightarrow 0$. We suggest a new way for prediction. For every finite string $x$ we predict the new bit according to the best (in some sence) distribution for $x$. We prove the similar result as Solomonoff theorem for our way of prediction. Also we show that our method of prediction has no that negative aspect as Solomonoff's method.
Algorithmic Averaging for Studying Periodic Orbits of Planar Differential Systems
Venue: arXiv cs.SC 2023
Year: 2023

One of the main open problems in the qualitative theory of real planar differential systems is the study of limit cycles. In this article, we present an algorithmic approach for detecting how many limit cycles can bifurcate from the periodic orbits of a given polynomial differential center when it is perturbed inside a class of polynomial differential systems via the averaging method. We propose four symbolic algorithms to implement the averaging method. The first algorithm is based on the change of polar coordinates that allows one to transform a considered differential system to the normal form of averaging. The second algorithm is used to derive the solutions of certain differential systems associated to the unperturbed term of the normal of averaging. The third algorithm exploits the partial Bell polynomials and allows one to compute the integral formula of the averaged functions at any order. The last algorithm is based on the aforementioned algorithms and determines the exact expressions of the averaged functions for the considered differential systems. The implementation of our algorithms is discussed and evaluated using several examples. The experimental results have extended the existing relevant results for certain classes of differential systems.
Towards AI Forensics: Did the Artificial Intelligence System Do It?
Venue: arXiv cs.AI 2023
Year: 2023

Artificial intelligence (AI) makes decisions impacting our daily lives in an increasingly autonomous manner. Their actions might cause accidents, harm, or, more generally, violate regulations. Determining whether an AI caused a specific event and, if so, what triggered the AI's action, are key forensic questions. We provide a conceptualization of the problems and strategies for forensic investigation. We focus on AI that is potentially ``malicious by design'' and grey box analysis. Our evaluation using convolutional neural networks illustrates challenges and ideas for identifying malicious AI.
The Power of Factorial Powers: New Parameter settings for (Stochastic) Optimization
Venue: arXiv cs.LG 2023
Year: 2023

The convergence rates for convex and non-convex optimization methods depend on the choice of a host of constants, including step sizes, Lyapunov function constants and momentum constants. In this work we propose the use of factorial powers as a flexible tool for defining constants that appear in convergence proofs. We list a number of remarkable properties that these sequences enjoy, and show how they can be applied to convergence proofs to simplify or improve the convergence rates of the momentum method, accelerated gradient and the stochastic variance reduced method (SVRG).
Impact-Aware Task-Space Quadratic-Programming Control
Venue: arXiv cs.RO 2023
Year: 2023

Robots usually establish contacts at rigid surfaces with near-zero relative velocities. Otherwise, impact-induced energy propagates in the robot's linkage and may cause irreversible damage to the hardware. Moreover, abrupt changes in task-space contact velocity and peak impact forces also result in abrupt changes in robot joint velocities and torques; which can compromise controllers' stability, especially for those based on smooth models. In reality, several tasks would require establishing contact with moderately high velocity. We propose to enhance task-space multi-objective controllers formulated as a quadratic program to be resilient to frictional impacts in three dimensions. We devise new constraints and reformulate the usual ones to be robust to the abrupt joint state changes mentioned earlier. The impact event becomes a controlled process once the optimal control search space is aware of: (1) the hardware-affordable impact bounds and (2) analytically-computed feasible set (polyhedra) that constrain post-impact critical states. Prior to and nearby the targeted contact spot, we assume, at each control cycle, that the impact will occur at the next iteration. This somewhat one-step preview makes our controller robust to impact time and location. To assess our approach, we experimented its resilience to moderate impacts with the Panda manipulator and achieved swift grabbing tasks with the HRP-4 humanoid robot.
Analogical proportions
Venue: arXiv cs.LO 2023
Year: 2023

Analogy-making is at the core of human and artificial intelligence and creativity with applications to such diverse tasks as proving mathematical theorems and building mathematical theories, common sense reasoning, learning, language acquisition, and story telling. This paper introduces from first principles an abstract algebraic framework of analogical proportions of the form `$a$ is to $b$ what $c$ is to $d$' in the general setting of universal algebra. This enables us to compare mathematical objects possibly across different domains in a uniform way which is crucial for AI-systems. It turns out that our notion of analogical proportions has appealing mathematical properties. As we construct our model from first principles using only elementary concepts of universal algebra, and since our model questions some basic properties of analogical proportions presupposed in the literature, to convince the reader of the plausibility of our model we show that it can be naturally embedded into first-order logic via model-theoretic types and prove from that perspective that analogical proportions are compatible with structure-preserving mappings. This provides conceptual evidence for its applicability. In a broader sense, this paper is a first step towards a theory of analogical reasoning and learning systems with potential applications to fundamental AI-problems like common sense reasoning and computational learning and creativity.
NewB: 200,000+ Sentences for Political Bias Detection
Venue: arXiv cs.CL 2023
Year: 2023

We present the Newspaper Bias Dataset (NewB), a text corpus of more than 200,000 sentences from eleven news sources regarding Donald Trump. While previous datasets have labeled sentences as either liberal or conservative, NewB covers the political views of eleven popular media sources, capturing more nuanced political viewpoints than a traditional binary classification system does. We train two state-of-the-art deep learning models to predict the news source of a given sentence from eleven newspapers and find that a recurrent neural network achieved top-1, top-3, and top-5 accuracies of 33.3%, 61.4%, and 77.6%, respectively, significantly outperforming a baseline logistic regression model's accuracies of 18.3%, 42.6%, and 60.8%. Using the news source label of sentences, we analyze the top n-grams with our model to gain meaningful insight into the portrayal of Trump by media sources.We hope that the public release of our dataset will encourage further research in using natural language processing to analyze more complex political biases. Our dataset is posted at https://github.com/JerryWeiAI/NewB .