OpenRaiser/Intern-Atlas huggingface dataset:
A Frequency-based Parent Selection for Reducing the Effect of Evaluation Time Bias in Asynchronous Parallel Multi-objective Evolutionary Algorithms
Venue: arXiv cs.NE 2022
Year: 2022

Parallel evolutionary algorithms (PEAs) have been studied for reducing the execution time of evolutionary algorithms by utilizing parallel computing. An asynchronous PEA (APEA) is a scheme of PEAs that increases computational efficiency by generating a new solution immediately after a solution evaluation completes without the idling time of computing nodes. However, because APEA gives more search opportunities to solutions with shorter evaluation times, the evaluation time bias of solutions negatively affects the search performance. To overcome this drawback, this paper proposes a new parent selection method to reduce the effect of evaluation time bias in APEAs. The proposed method considers the search frequency of solutions and selects the parent solutions so that the search progress in the population is uniform regardless of the evaluation time bias. This paper conducts experiments on multi-objective optimization problems that simulate the evaluation time bias. The experiments use NSGA-III, a well-known multi-objective evolutionary algorithm, and compare the proposed method with the conventional synchronous/asynchronous parallelization. The experimental results reveal that the proposed method can reduce the effect of the evaluation time bias while reducing the computing time of the parallel NSGA-III.
QoE Evaluation for Adaptive Video Streaming: Enhanced MDT with Deep Learning
Venue: arXiv cs.NI 2022
Year: 2022

The network performance is usually assessed by drive tests, where teams of people with specially equipped vehicles physically drive out to test various locations throughout a radio network. However, intelligent and autonomous troubleshooting is considered a crucial enabler for 5G- and 6G-networks. In this paper, we propose an architecture for performing virtual drive tests by facilitating radio-quality data from the user equipment. Our architecture comprises three main components: i) a pattern recognizer that learns a typical pattern for the application from application Key Performance Indicators (KPI); ii) a predictor for mapping network KPI with the application KPI; iii) an anomaly detector that compares the predicted application performance with that of the typical application pattern. In this work, we use a commercial state-of-the-art network optimization tool to collect network and application KPI at different geographical locations and at various times of the day for training an initial learning model. We perform extensive numerical analysis to demonstrate key parameters impacting correct video quality prediction and anomaly detection. We show that the playback time is the single most important parameter affecting the video quality, since video packets are usually buffered ahead of time during the playback. However, radio frequency (RF) performance indicators characterizing the quality of the cellular connection improve the QoE estimation in exceptional cases. We demonstrate the efficacy of our approach by showing that the mean maximum F1-score of our method is 77%. Finally, the proposed architecture is flexible and autonomous, and it can operate with different user applications as long as the relevant user-based traces are available.
Towards Unbiased Visual Emotion Recognition via Causal Intervention
Venue: arXiv cs.CV 2022
Year: 2022

Although much progress has been made in visual emotion recognition, researchers have realized that modern deep networks tend to exploit dataset characteristics to learn spurious statistical associations between the input and the target. Such dataset characteristics are usually treated as dataset bias, which damages the robustness and generalization performance of these recognition systems. In this work, we scrutinize this problem from the perspective of causal inference, where such dataset characteristic is termed as a confounder which misleads the system to learn the spurious correlation. To alleviate the negative effects brought by the dataset bias, we propose a novel Interventional Emotion Recognition Network (IERN) to achieve the backdoor adjustment, which is one fundamental deconfounding technique in causal inference. Specifically, IERN starts by disentangling the dataset-related context feature from the actual emotion feature, where the former forms the confounder. The emotion feature will then be forced to see each confounder stratum equally before being fed into the classifier. A series of designed tests validate the efficacy of IERN, and experiments on three emotion benchmarks demonstrate that IERN outperforms state-of-the-art approaches for unbiased visual emotion recognition. Code is available at https://github.com/donydchen/causal_emotion
Pressure Test: Quantifying the impact of positive stress on companies from online employee reviews
Venue: arXiv cs.SI 2022
Year: 2022

Workplace stress is often considered to be negative, yet lab studies on individuals suggest that not all stress is bad. There are two types of stress: distress refers to harmful stimuli, while eustress refers to healthy, euphoric stimuli that create a sense of fulfillment and achievement. Telling the two types of stress apart is challenging, let alone quantifying their impact across corporations. By leveraging a dataset of 440K reviews about S&P 500 companies published during twelve successive years, we developed a deep learning framework to extract stress mentions from these reviews. We proposed a new methodology that places each company on a stress-by-rating quadrant (based on its overall stress score and overall rating on the site), and accordingly scores the company to be, on average, either a low stress}, passive, negative stress, or positive stress company. We found that (former) employees of positive stress companies tended to describe high-growth and collaborative workplaces in their reviews, and that such companies' stock evaluations grew, on average, 5.1 times in 10 years (2009-2019) as opposed to the companies of the other three stress types that grew, on average, 3.7 times in the same time period. We also found that the four stress scores aggregated every year -- from 2008 to 2020 -- closely followed the unemployment rate in the U.S.: a year of positive stress (2008) was rapidly followed by several years of negative stress (2009-2015), which peaked during the Great Recession (2009-2011). These results suggest that automated analyses of the language used by employees on corporate social-networking tools offer yet another way of tracking workplace stress, allowing quantification of its impact on corporations.
Restricted Boltzmann Machine and Deep Belief Network: Tutorial and Survey
Venue: arXiv cs.LG 2022
Year: 2022

This is a tutorial and survey paper on Boltzmann Machine (BM), Restricted Boltzmann Machine (RBM), and Deep Belief Network (DBN). We start with the required background on probabilistic graphical models, Markov random field, Gibbs sampling, statistical physics, Ising model, and the Hopfield network. Then, we introduce the structures of BM and RBM. The conditional distributions of visible and hidden variables, Gibbs sampling in RBM for generating variables, training BM and RBM by maximum likelihood estimation, and contrastive divergence are explained. Then, we discuss different possible discrete and continuous distributions for the variables. We introduce conditional RBM and how it is trained. Finally, we explain deep belief network as a stack of RBM models. This paper on Boltzmann machines can be useful in various fields including data science, statistics, neural computation, and statistical physics.
QA Dataset Explosion: A Taxonomy of NLP Resources for Question Answering and Reading Comprehension
Venue: arXiv cs.CL 2022
Year: 2022

Alongside huge volumes of research on deep learning models in NLP in the recent years, there has been also much work on benchmark datasets needed to track modeling progress. Question answering and reading comprehension have been particularly prolific in this regard, with over 80 new datasets appearing in the past two years. This study is the largest survey of the field to date. We provide an overview of the various formats and domains of the current resources, highlighting the current lacunae for future work. We further discuss the current classifications of "skills" that question answering/reading comprehension systems are supposed to acquire, and propose a new taxonomy. The supplementary materials survey the current multilingual resources and monolingual resources for languages other than English, and we discuss the implications of over-focusing on English. The study is aimed at both practitioners looking for pointers to the wealth of existing data, and at researchers working on new resources.
Efficient Parallel Graph Trimming by Arc-Consistency
Venue: arXiv cs.DC 2022
Year: 2022

Given a large data graph, trimming techniques can reduce the search space by removing vertices without outgoing edges. One application is to speed up the parallel decomposition of graphs into strongly connected components (SCC decomposition), which is a fundamental step for analyzing graphs. We observe that graph trimming is essentially a kind of arc-consistency problem, and AC-3, AC-4, and AC-6 are the most relevant arc-consistency algorithms for application to graph trimming. The existing parallel graph trimming methods require worst-case $\mathcal O(nm)$ time and worst-case $\mathcal O(n)$ space for graphs with $n$ vertices and $m$ edges. We call these parallel AC-3-based as they are much like the AC-3 algorithm. In this work, we propose AC-4-based and AC-6-based trimming methods. That is, AC-4-based trimming has an improved worst-case time of $\mathcal O(n+m)$ but requires worst-case space of $\mathcal O(n+m)$; compared with AC-4-based trimming, AC-6-based has the same worst-case time of $\mathcal O(n+m)$ but an improved worst-case space of $\mathcal O(n)$. We parallelize the AC-4-based and AC-6-based algorithms to be suitable for shared-memory multi-core machines. The algorithms are designed to minimize synchronization overhead. For these algorithms, we also prove the correctness and analyze time complexities with the work-depth model. In experiments, we compare these three parallel trimming algorithms over a variety of real and synthetic graphs. Specifically, for the maximum number of traversed edges per worker by using 16 workers, AC-3-based traverses up to 58.3 and 36.5 times more edges than AC-6-based trimming and AC-4-based trimming, respectively.
Physics-constrained Deep Learning for Robust Inverse ECG Modeling
Venue: arXiv cs.LG 2022
Year: 2022

The rapid developments in advanced sensing and imaging bring about a data-rich environment, facilitating the effective modeling, monitoring, and control of complex systems. For example, the body-sensor network captures multi-channel information pertinent to the electrical activity of the heart (i.e., electrocardiograms (ECG)), which enables medical scientists to monitor and detect abnormal cardiac conditions. However, the high-dimensional sensing data are generally complexly structured and realizing the full data potential depends to a great extent on advanced analytical and predictive methods. This paper presents a physics-constrained deep learning (P-DL) framework for high-dimensional inverse ECG modeling. This method integrates the physical laws of the complex system with the advanced deep learning infrastructure for effective prediction of the system dynamics. The proposed P-DL approach is implemented to solve the inverse ECG model and predict the time-varying distribution of electric potentials in the heart from the ECG data measured by the body-surface sensor network. Experimental results show that the proposed P-DL method significantly outperforms existing methods that are commonly used in current practice.
RingBFT: Resilient Consensus over Sharded Ring Topology
Venue: arXiv cs.DB 2022
Year: 2022

The recent surge in federated data management applications has brought forth concerns about the security of underlying data and the consistency of replicas in the presence of malicious attacks. A prominent solution in this direction is to employ a permissioned blockchain framework that is modeled around traditional Byzantine Fault-Tolerant (BFT) consensus protocols. Any federated application expects its data to be globally scattered to achieve faster access. But, prior works have shown that traditional BFT protocols are slow. This has led to the rise of sharded-replicated blockchains. Existing BFT protocols for these sharded blockchains are efficient if client transactions require access to a single-shard, but face performance degradation if there is a cross-shard transaction that requires access to multiple shards. As cross-shard transactions are common, to resolve this dilemma, we present RingBFT, a novel meta-BFT protocol for sharded blockchains. RingBFT requires shards to adhere to the ring order, and follow the principle of process, forward, and re-transmit while ensuring the communication between shards is linear. Our evaluation of RingBFT against state-of-the-art sharding BFT protocols illustrates that RingBFT achieves up to 18x higher throughput, gracefully scales to nearly 500 globally distributed nodes, and achieves a peak throughput of 1.2 million transactions per second.
Unsupervised Learning of Neurosymbolic Encoders
Venue: arXiv cs.LG 2022
Year: 2022

We present a framework for the unsupervised learning of neurosymbolic encoders, which are encoders obtained by composing neural networks with symbolic programs from a domain-specific language. Our framework naturally incorporates symbolic expert knowledge into the learning process, which leads to more interpretable and factorized latent representations compared to fully neural encoders. We integrate modern program synthesis techniques with the variational autoencoding (VAE) framework, in order to learn a neurosymbolic encoder in conjunction with a standard decoder. The programmatic descriptions from our encoders can benefit many analysis workflows, such as in behavior modeling where interpreting agent actions and movements is important. We evaluate our method on learning latent representations for real-world trajectory data from animal biology and sports analytics. We show that our approach offers significantly better separation of meaningful categories than standard VAEs and leads to practical gains on downstream analysis tasks, such as for behavior classification.
Dense Graph Partitioning on sparse and dense graphs
Venue: arXiv cs.CC 2022
Year: 2022

We consider the problem of partitioning a graph into a non-fixed number of non-overlapping subgraphs of maximum density. The density of a partition is the sum of the densities of the subgraphs, where the density of a subgraph is its average degree, that is, the ratio of its number of edges and its number of vertices. This problem, called Dense Graph Partition, is known to be NP-hard on general graphs and polynomial-time solvable on trees, and polynomial-time 2-approximable. In this paper we study the restriction of Dense Graph Partition to particular sparse and dense graph classes. In particular, we prove that it is NP-hard on dense bipartite graphs as well as on cubic graphs. On dense graphs on $n$ vertices, it is polynomial-time solvable on graphs with minimum degree $n-3$ and NP-hard on $(n-4)$-regular graphs. We prove that it is polynomial-time $4/3$-approximable on cubic graphs and admits an efficient polynomial-time approximation scheme on graphs of minimum degree $n-t$ for any constant $t\geq 4$.
A monogamy-of-entanglement game for subspace coset states
Venue: arXiv cs.CR 2022
Year: 2022

We establish a strong monogamy-of-entanglement property for subspace coset states, which are uniform superpositions of vectors in a linear subspace of $\mathbb{F}_2^n$ to which has been applied a quantum one-time pad. This property was conjectured recently by [Coladangelo, Liu, Liu, and Zhandry, Crypto'21] and shown to have applications to unclonable decryption and copy-protection of pseudorandom functions. We present two proofs, one which directly follows the method of the original paper and the other which uses an observation from [Vidick and Zhang, Eurocrypt'20] to reduce the analysis to a simpler monogamy game based on BB'84 states. Both proofs ultimately rely on the same proof technique, introduced in [Tomamichel, Fehr, Kaniewski and Wehner, New Journal of Physics '13].
Large sample spectral analysis of graph-based multi-manifold clustering
Venue: arXiv cs.LG 2022
Year: 2022

In this work we study statistical properties of graph-based algorithms for multi-manifold clustering (MMC). In MMC the goal is to retrieve the multi-manifold structure underlying a given Euclidean data set when this one is assumed to be obtained by sampling a distribution on a union of manifolds $\mathcal{M} = \mathcal{M}_1 \cup\dots \cup \mathcal{M}_N$ that may intersect with each other and that may have different dimensions. We investigate sufficient conditions that similarity graphs on data sets must satisfy in order for their corresponding graph Laplacians to capture the right geometric information to solve the MMC problem. Precisely, we provide high probability error bounds for the spectral approximation of a tensorized Laplacian on $\mathcal{M}$ with a suitable graph Laplacian built from the observations; the recovered tensorized Laplacian contains all geometric information of all the individual underlying manifolds. We provide an example of a family of similarity graphs, which we call annular proximity graphs with angle constraints, satisfying these sufficient conditions. We contrast our family of graphs with other constructions in the literature based on the alignment of tangent planes. Extensive numerical experiments expand the insights that our theory provides on the MMC problem.
Multimodal Co-learning: Challenges, Applications with Datasets, Recent Advances and Future Directions
Venue: arXiv cs.LG 2022
Year: 2022

Multimodal deep learning systems which employ multiple modalities like text, image, audio, video, etc., are showing better performance in comparison with individual modalities (i.e., unimodal) systems. Multimodal machine learning involves multiple aspects: representation, translation, alignment, fusion, and co-learning. In the current state of multimodal machine learning, the assumptions are that all modalities are present, aligned, and noiseless during training and testing time. However, in real-world tasks, typically, it is observed that one or more modalities are missing, noisy, lacking annotated data, have unreliable labels, and are scarce in training or testing and or both. This challenge is addressed by a learning paradigm called multimodal co-learning. The modeling of a (resource-poor) modality is aided by exploiting knowledge from another (resource-rich) modality using transfer of knowledge between modalities, including their representations and predictive models. Co-learning being an emerging area, there are no dedicated reviews explicitly focusing on all challenges addressed by co-learning. To that end, in this work, we provide a comprehensive survey on the emerging area of multimodal co-learning that has not been explored in its entirety yet. We review implementations that overcome one or more co-learning challenges without explicitly considering them as co-learning challenges. We present the comprehensive taxonomy of multimodal co-learning based on the challenges addressed by co-learning and associated implementations. The various techniques employed to include the latest ones are reviewed along with some of the applications and datasets. Our final goal is to discuss challenges and perspectives along with the important ideas and directions for future work that we hope to be beneficial for the entire research community focusing on this exciting domain.
QuPeD: Quantized Personalization via Distillation with Applications to Federated Learning
Venue: arXiv cs.LG 2022
Year: 2022

Traditionally, federated learning (FL) aims to train a single global model while collaboratively using multiple clients and a server. Two natural challenges that FL algorithms face are heterogeneity in data across clients and collaboration of clients with {\em diverse resources}. In this work, we introduce a \textit{quantized} and \textit{personalized} FL algorithm QuPeD that facilitates collective (personalized model compression) training via \textit{knowledge distillation} (KD) among clients who have access to heterogeneous data and resources. For personalization, we allow clients to learn \textit{compressed personalized models} with different quantization parameters and model dimensions/structures. Towards this, first we propose an algorithm for learning quantized models through a relaxed optimization problem, where quantization values are also optimized over. When each client participating in the (federated) learning process has different requirements for the compressed model (both in model dimension and precision), we formulate a compressed personalization framework by introducing knowledge distillation loss for local client objectives collaborating through a global model. We develop an alternating proximal gradient update for solving this compressed personalization problem, and analyze its convergence properties. Numerically, we validate that QuPeD outperforms competing personalized FL methods, FedAvg, and local training of clients in various heterogeneous settings.
Improving Latency with Active Queue Management (AQM) During COVID-19
Venue: arXiv cs.NI 2022
Year: 2022

During the COVID-19 pandemic the Comcast network performed well in response to unprecedented changes in Internet usage and video communications applications that are sensitive to network latency have exploded in popularity. However, in today's typical networks-such as a home network-those applications often degrade if they are sharing a network link with other network traffic. This is a problem caused by a network design flaw often described using the term 'buffer bloat'. Several years ago, Comcast helped to fund research and development in the technical community into new Active Queue Management (AQM) techniques to eliminate this issue and AQM was later built into Data Over Cable Service Interface Specification (DOCSIS) standards. Just prior to the pandemic, Comcast also deployed a large-scale network performance measurement system that included a latency under load test. In addition, Comcast happened to deploy two otherwise identical cable modems; one with upstream AQM enabled, and the other without. This fortuitous confluence of events has enabled Comcast to perform a comparative analysis of the differences between cable modem gateways using AQM with those that lack that enhancement, at a unique level of scale across many months of time and millions of devices. The data reveals significantly better upstream latency under load performance when AQM is used. For the device with AQM, most of the latency under load tests resulted in 15-30 milliseconds of latency. In comparison, the device without AQM averaged roughly 250 milliseconds of latency, between 8-16 times higher, a highly significant difference to the end user quality of experience. These large-scale measurement comparisons should provide additional data to justify accelerated deployment of AQM in DOCSIS and other Internet Service Provider networks and user-purchased home network equipment.