OpenRaiser/Intern-Atlas huggingface dataset:
Discriminative Adversarial Domain Generalization with Meta-learning based Cross-domain Validation
Venue: arXiv cs.LG 2022
Year: 2022

The generalization capability of machine learning models, which refers to generalizing the knowledge for an "unseen" domain via learning from one or multiple seen domain(s), is of great importance to develop and deploy machine learning applications in the real-world conditions. Domain Generalization (DG) techniques aim to enhance such generalization capability of machine learning models, where the learnt feature representation and the classifier are two crucial factors to improve generalization and make decisions. In this paper, we propose Discriminative Adversarial Domain Generalization (DADG) with meta-learning-based cross-domain validation. Our proposed framework contains two main components that work synergistically to build a domain-generalized DNN model: (i) discriminative adversarial learning, which proactively learns a generalized feature representation on multiple "seen" domains, and (ii) meta-learning based cross-domain validation, which simulates train/test domain shift via applying meta-learning techniques in the training process. In the experimental evaluation, a comprehensive comparison has been made among our proposed approach and other existing approaches on three benchmark datasets. The results shown that DADG consistently outperforms a strong baseline DeepAll, and outperforms the other existing DG algorithms in most of the evaluation cases.
BayesBeat: Reliable Atrial Fibrillation Detection from Noisy Photoplethysmography Data
Venue: arXiv cs.LG 2022
Year: 2022

Smartwatches or fitness trackers have garnered a lot of popularity as potential health tracking devices due to their affordable and longitudinal monitoring capabilities. To further widen their health tracking capabilities, in recent years researchers have started to look into the possibility of Atrial Fibrillation (AF) detection in real-time leveraging photoplethysmography (PPG) data, an inexpensive sensor widely available in almost all smartwatches. A significant challenge in AF detection from PPG signals comes from the inherent noise in the smartwatch PPG signals. In this paper, we propose a novel deep learning based approach, BayesBeat that leverages the power of Bayesian deep learning to accurately infer AF risks from noisy PPG signals, and at the same time provides an uncertainty estimate of the prediction. Extensive experiments on two publicly available dataset reveal that our proposed method BayesBeat outperforms the existing state-of-the-art methods. Moreover, BayesBeat is substantially more efficient having 40-200X fewer parameters than state-of-the-art baseline approaches making it suitable for deployment in resource constrained wearable devices.
CaCL: Class-aware Codebook Learning for Weakly Supervised Segmentation on Diffuse Image Patterns
Venue: arXiv cs.CV 2022
Year: 2022

Weakly supervised learning has been rapidly advanced in biomedical image analysis to achieve pixel-wise labels (segmentation) from image-wise annotations (classification), as biomedical images naturally contain image-wise labels in many scenarios. The current weakly supervised learning algorithms from the computer vision community are largely designed for focal objects (e.g., dogs and cats). However, such algorithms are not optimized for diffuse patterns in biomedical imaging (e.g., stains and fluorescence in microscopy imaging). In this paper, we propose a novel class-aware codebook learning (CaCL) algorithm to perform weakly supervised learning for diffuse image patterns. Specifically, the CaCL algorithm is deployed to segment protein expressed brush border regions from histological images of human duodenum. Our contribution is three-fold: (1) we approach the weakly supervised segmentation from a novel codebook learning perspective; (2) the CaCL algorithm segments diffuse image patterns rather than focal objects; and (3) the proposed algorithm is implemented in a multi-task framework based on Vector Quantised-Variational AutoEncoder (VQ-VAE) via joint image reconstruction, classification, feature embedding, and segmentation. The experimental results show that our method achieved superior performance compared with baseline weakly supervised algorithms. The code is available at https://github.com/ddrrnn123/CaCL.
Distributed Machine Learning with Strategic Network Design: A Game-Theoretic Perspective
Venue: arXiv cs.GT 2022
Year: 2022

This paper considers a game-theoretic framework for distributed machine learning problems over networks where the information acquisition at a node is modeled as a rational choice of a player. In the proposed game, players decide both the learning parameters and the network structure. The Nash equilibrium characterizes the tradeoff between the local performance and the global agreement of the learned classifiers. We first introduce a commutative approach which features a joint learning process that integrates the iterative learning at each node and the network formation. We show that our game is equivalent to a generalized potential game in the setting of undirected networks. We study the convergence of the proposed commutative algorithm, analyze the network structures determined by our game, and show the improvement of the social welfare in comparison with standard distributed learning over fixed networks. To adapt our framework to streaming data, we derive a distributed Kalman filter. A concurrent algorithm based on the online mirror descent algorithm is also introduced for solving for Nash equilibria in a holistic manner. In the case study, we use telemonitoring of Parkinson's disease to corroborate the results.
MalFox: Camouflaged Adversarial Malware Example Generation Based on Conv-GANs Against Black-Box Detectors
Venue: arXiv cs.CR 2022
Year: 2022

Deep learning is a thriving field currently stuffed with many practical applications and active research topics. It allows computers to learn from experience and to understand the world in terms of a hierarchy of concepts, with each being defined through its relations to simpler concepts. Relying on the strong capabilities of deep learning, we propose a convolutional generative adversarial network-based (Conv-GAN) framework titled MalFox, targeting adversarial malware example generation against third-party black-box malware detectors. Motivated by the rival game between malware authors and malware detectors, MalFox adopts a confrontational approach to produce perturbation paths, with each formed by up to three methods (namely Obfusmal, Stealmal, and Hollowmal) to generate adversarial malware examples. To demonstrate the effectiveness of MalFox, we collect a large dataset consisting of both malware and benignware programs, and investigate the performance of MalFox in terms of accuracy, detection rate, and evasive rate of the generated adversarial malware examples. Our evaluation indicates that the accuracy can be as high as 99.0% which significantly outperforms the other 12 well-known learning models. Furthermore, the detection rate is dramatically decreased by 56.8% on average, and the average evasive rate is noticeably improved by up to 56.2%.
Graph Neural Networks in Recommender Systems: A Survey
Venue: arXiv cs.IR 2022
Year: 2022

With the explosive growth of online information, recommender systems play a key role to alleviate such information overload. Due to the important application value of recommender systems, there have always been emerging works in this field. In recommender systems, the main challenge is to learn the effective user/item representations from their interactions and side information (if any). Recently, graph neural network (GNN) techniques have been widely utilized in recommender systems since most of the information in recommender systems essentially has graph structure and GNN has superiority in graph representation learning. This article aims to provide a comprehensive review of recent research efforts on GNN-based recommender systems. Specifically, we provide a taxonomy of GNN-based recommendation models according to the types of information used and recommendation tasks. Moreover, we systematically analyze the challenges of applying GNN on different types of data and discuss how existing works in this field address these challenges. Furthermore, we state new perspectives pertaining to the development of this field. We collect the representative papers along with their open-source implementations in https://github.com/wusw14/GNN-in-RS.
Evolving test instances of the Hamiltonian completion problem
Venue: arXiv cs.AI 2022
Year: 2022

Predicting and comparing algorithm performance on graph instances is challenging for multiple reasons. First, there is usually no standard set of instances to benchmark performance. Second, using existing graph generators results in a restricted spectrum of difficulty and the resulting graphs are usually not diverse enough to draw sound conclusions. That is why recent work proposes a new methodology to generate a diverse set of instances by using an evolutionary algorithm. We can then analyze the resulting graphs and get key insights into which attributes are most related to algorithm performance. We can also fill observed gaps in the instance space in order to generate graphs with previously unseen combinations of features. This methodology is applied to the instance space of the Hamiltonian completion problem using two different solvers, namely the Concorde TSP Solver and a multi-start local search algorithm.
Wasserstein-based fairness interpretability framework for machine learning models
Venue: arXiv cs.LG 2022
Year: 2022

The objective of this article is to introduce a fairness interpretability framework for measuring and explaining the bias in classification and regression models at the level of a distribution. In our work, we measure the model bias across sub-population distributions in the model output using the Wasserstein metric. To properly quantify the contributions of predictors, we take into account the favorability of both the model and predictors with respect to the non-protected class. The quantification is accomplished by the use of transport theory, which gives rise to the decomposition of the model bias and bias explanations to positive and negative contributions. To gain more insight into the role of favorability and allow for additivity of bias explanations, we adapt techniques from cooperative game theory.
Reliable Off-policy Evaluation for Reinforcement Learning
Venue: arXiv cs.LG 2022
Year: 2022

In a sequential decision-making problem, off-policy evaluation estimates the expected cumulative reward of a target policy using logged trajectory data generated from a different behavior policy, without execution of the target policy. Reinforcement learning in high-stake environments, such as healthcare and education, is often limited to off-policy settings due to safety or ethical concerns, or inability of exploration. Hence it is imperative to quantify the uncertainty of the off-policy estimate before deployment of the target policy. In this paper, we propose a novel framework that provides robust and optimistic cumulative reward estimates using one or multiple logged trajectories data. Leveraging methodologies from distributionally robust optimization, we show that with proper selection of the size of the distributional uncertainty set, these estimates serve as confidence bounds with non-asymptotic and asymptotic guarantees under stochastic or adversarial environments. Our results are also generalized to batch reinforcement learning and are supported by empirical analysis.
Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes
Venue: arXiv cs.IT 2022
Year: 2022

In this work, we initiate the study of proximity testing to Algebraic Geometry (AG) codes. An AG code $C = C(\mathcal{X}, \mathcal{P}, D)$ over an algebraic curve $\mathcal{X}$ is a vector space associated to evaluations on $\mathcal{P}$ of functions in the Riemann-Roch space $L_\mathcal{X}(D)$. The problem of testing proximity to an error-correcting code $C$ consists in distinguishing between the case where an input word, given as an oracle, belongs to $C$ and the one where it is far from every codeword of $C$. AG codes are good candidates to construct short proof systems, but there exists no efficient proximity tests for them. We aim to fill this gap. We construct an Interactive Oracle Proof of Proximity (IOPP) for some families of AG codes by generalizing an IOPP for Reed-Solomon codes introduced by Ben-Sasson, Bentov, Horesh and Riabzev, known as the FRI protocol. We identify suitable requirements for designing efficient IOPP systems for AG codes. Our approach relies on a neat decomposition of the Riemann-Roch space of any invariant divisor under a group action on a curve into several explicit Riemann-Roch spaces on the quotient curve. We provide sufficient conditions on an AG code $C$ that allow to reduce a proximity testing problem for $C$ to a membership problem for a significantly smaller code $C'$. As concrete instantiations, we study AG codes on Kummer curves and curves in the Hermitian tower. The latter can be defined over polylogarithmic-size alphabet. We specialize the generic AG-IOPP construction to reach linear prover running time and logarithmic verification on Kummer curves, and quasilinear prover time with polylogarithmic verification on the Hermitian tower.
A translation of weighted LTL formulas to weighted Büchi automata over ω-valuation monoids
Venue: arXiv cs.FL 2022
Year: 2022

In this paper we introduce a weighted LTL over product $ω$-valuation monoids that satisfy specific properties. We also introduce weighted generalized Büchi automata with $\varepsilon$-transitions, as well as weighted Büchi automata with $\varepsilon$-transitions over product $ω$-valuation monoids and prove that these two models are expressively equivalent and also equivalent to weighted Büchi automata already introduced in the literature. We prove that every formula of a syntactic fragment of our logic can be effectively translated to a weighted generalized Büchi automaton with $\varepsilon$-transitions. For generalized product $ω$-valuation monoids that satisfy specific properties we define a weighted LTL, weighted generalized Büchi automata with $\varepsilon$-transitions, and weighted Büchi automata with $\varepsilon$-transitions, and we prove the aforementioned results for generalized product $ω$-valuation monoids as well. The translation of weighted LTL formulas to weighted generalized Büchi automata with $\varepsilon$-transitions is now obtained for a restricted syntactical fragment of the logic.
Optimizing Age-of-Information in Adversarial and Stochastic Environments
Venue: arXiv cs.IT 2022
Year: 2022

We design efficient online scheduling policies to maximize the freshness of information delivered to the users in a cellular network under both adversarial and stochastic channel and mobility assumptions. The information freshness achieved by a policy is investigated through the lens of a recently proposed metric - Age-of-Information (AoI). We show that a natural greedy scheduling policy is competitive against any optimal offline policy in minimizing the AoI in the adversarial setting. We also derive universal lower bounds to the competitive ratio achievable by any online policy in the adversarial framework. In the stochastic setting, we show that a simple index policy is near-optimal for minimizing the average AoI in two different mobility scenarios. Further, we prove that the greedy scheduling policy minimizes the peak AoI for static users in the stochastic setting. Simulation results show that the proposed policies perform well under realistic conditions.
A Small Survey On Event Detection Using Twitter
Venue: arXiv cs.SI 2022
Year: 2022

A small survey on event detection using Twitter. This work first defines the problem statement, and then summarizes and collates the different research works towards solving the problem.
Counting Homomorphic Cycles in Degenerate Graphs
Venue: arXiv cs.DS 2022
Year: 2022

Since counting subgraphs in general graphs is, by and large, a computationally demanding problem, it is natural to try and design fast algorithms for restricted families of graphs. One such family that has been extensively studied is that of graphs of bounded degeneracy (e.g., planar graphs). This line of work, which started in the early 80's, culminated in a recent work of Gishboliner et al., which highlighted the importance of the task of counting homomorphic copies of cycles (i.e., cyclic walks) in graphs of bounded degeneracy. Our main result in this paper is a surprisingly tight relation between the above task and the well-studied problem of detecting (standard) copies of directed cycles in general directed graphs. More precisely, we prove the following: 1. One can compute the number of homomorphic copies of $C_{2k}$ and $C_{2k+1}$ in $n$-vertex graphs of bounded degeneracy in time $\tilde{O}(n^{d_{k}})$, where the fastest known algorithm for detecting directed copies of $C_k$ in general $m$-edge digraphs runs in time $\tilde{O}(m^{d_{k}})$. 2. Conversely, one can transform any $O(n^{b_{k}})$ algorithm for computing the number of homomorphic copies of $C_{2k}$ or of $C_{2k+1}$ in $n$-vertex graphs of bounded degeneracy, into an $\tilde{O}(m^{b_{k}})$ time algorithm for detecting directed copies of $C_k$ in general $m$-edge digraphs. We emphasize that our first result does not use a black-box reduction (as opposed to the second result which does). Instead, we design an algorithm for computing the number of $C_k$-homomorphisms in degenerate graphs and show that one part of its analysis can be reduced to the analysis of the fastest known algorithm for detecting directed cycles in general digraphs, which was carried out in a recent breakthrough of Dalirrooyfard, Vuong and Vassilevska Williams.
FPT-Algorithms for the \ell-Matchoid Problem with a Coverage Objective
Venue: arXiv cs.DS 2022
Year: 2022

We consider the problem of optimizing a coverage function under a $\ell$-matchoid of rank $k$. We design fixed-parameter algorithms as well as streaming algorithms to compute an exact solution. Unlike previous work that presumes linear representativity of matroids, we consider the general oracle model. For the special case where the coverage function is linear, we give a deterministic fixed-parameter algorithm parameterized by $\ell$ and $k$. This result, combined with the lower bounds of Lovasz, and Jensen and Korte demonstrates a separation between the $\ell$-matchoid and the matroid $\ell$-parity problems in the setting of fixed-parameter tractability. For a general coverage function, we give both deterministic and randomized fixed-parameter algorithms, parameterized by $\ell$ and $z$, where $z$ is the number of points covered in an optimal solution. The resulting algorithms can be directly translated into streaming algorithms. For unweighted coverage functions, we show that we can find an exact solution even when the function is given in the form of a value oracle (and so we do not have access to an explicit representation of the set system). Our result can be implemented in the streaming setting and stores a number of elements depending only on $\ell$ and $z$, but completely indpendent of the total size $n$ of the ground set. This shows that it is possible to circumvent the recent space lower bound of Feldman et al, by parameterizing the solution value. This result, combined with existing lower bounds, also provides a new separation between the space and time complexity of maximizing an arbitrary submodular function and a coverage function in the value oracle model.
Educational robotics for children and their teachers
Venue: arXiv cs.RO 2022
Year: 2022

This paper describes a Google Educator funded project devoted to the training of teachers (primary and secondary school) through an e-learning platform that will introduce them to educational robotics using Wolly, a social, educational and affective robot.
Collaborative Three-Tier Architecture Non-contact Respiratory Rate Monitoring using Target Tracking and False Peaks Eliminating Algorithms
Venue: arXiv cs.RO 2022
Year: 2022

Monitoring the respiratory rate is crucial for helping us identify respiratory disorders. Devices for conventional respiratory monitoring are inconvenient and scarcely available. Recent research has demonstrated the ability of non-contact technologies, such as photoplethysmography and infrared thermography, to gather respiratory signals from the face and monitor breathing. However, the current non-contact respiratory monitoring techniques have poor accuracy because they are sensitive to environmental influences like lighting and motion artifacts. Furthermore, frequent contact between users and the cloud in real-world medical application settings might cause service request delays and potentially the loss of personal data. We proposed a non-contact respiratory rate monitoring system with a cooperative three-layer design to increase the precision of respiratory monitoring and decrease data transmission latency. To reduce data transmission and network latency, our three-tier architecture layer-by-layer decomposes the computing tasks of respiration monitoring. Moreover, we improved the accuracy of respiratory monitoring by designing a target tracking algorithm and an algorithm for eliminating false peaks to extract high-quality respiratory signals. By gathering the data and choosing several regions of interest on the face, we were able to extract the respiration signal and investigate how different regions affected the monitoring of respiration. The results of the experiment indicate that when the nasal region is used to extract the respiratory signal, it performs experimentally best. Our approach performs better than rival approaches while transferring fewer data.
Whale: Efficient Giant Model Training over Heterogeneous GPUs
Venue: arXiv cs.DC 2022
Year: 2022

The scaling up of deep neural networks has been demonstrated to be effective in improving model quality, but also encompasses several training challenges in terms of training efficiency, programmability, and resource adaptability. We present Whale, a general and efficient distributed training framework for giant models. To support various parallel strategies and their hybrids, Whale generalizes the programming interface by defining two new primitives in the form of model annotations, allowing for incorporating user hints. The Whale runtime utilizes those annotations and performs graph optimizations to transform a local deep learning DAG graph for distributed multi-GPU execution. Whale further introduces a novel hardware-aware parallel strategy, which improves the performance of model training on heterogeneous GPUs in a balanced manner. Deployed in a production cluster with 512 GPUs, Whale successfully trains an industry-scale multimodal model with over ten trillion model parameters, named M6, demonstrating great scalability and efficiency.