OpenRaiser/Intern-Atlas huggingface dataset:
Optimization and Manipulation of Contextual Mutual Spaces for Multi-User Virtual and Augmented Reality Interaction
Venue: arXiv cs.HC 2020
Year: 2020

Spatial computing experiences are physically constrained by the geometry and semantics of the local user environment. This limitation is elevated in remote multi-user interaction scenarios, where finding a common virtual ground physically accessible for all participants becomes challenging. Locating a common accessible virtual ground is difficult for the users themselves, particularly if they are not aware of the spatial properties of other participants. In this paper, we introduce a framework to generate an optimal mutual virtual space for a multi-user interaction setting where remote users' room spaces can have different layout and sizes. The framework further recommends movement of surrounding furniture objects that expand the size of the mutual space with minimal physical effort. Finally, we demonstrate the performance of our solution on real-world datasets and also a real HoloLens application. Results show the proposed algorithm can effectively discover optimal shareable space for multi-user virtual interaction and hence facilitate remote spatial computing communication in various collaborative workflows.
An Optimal Algorithm for Adversarial Bandits with Arbitrary Delays
Venue: arXiv cs.LG 2020
Year: 2020

We propose a new algorithm for adversarial multi-armed bandits with unrestricted delays. The algorithm is based on a novel hybrid regularizer applied in the Follow the Regularized Leader (FTRL) framework. It achieves $\mathcal{O}(\sqrt{kn}+\sqrt{D\log(k)})$ regret guarantee, where $k$ is the number of arms, $n$ is the number of rounds, and $D$ is the total delay. The result matches the lower bound within constants and requires no prior knowledge of $n$ or $D$. Additionally, we propose a refined tuning of the algorithm, which achieves $\mathcal{O}(\sqrt{kn}+\min_{S}|S|+\sqrt{D_{\bar S}\log(k)})$ regret guarantee, where $S$ is a set of rounds excluded from delay counting, $\bar S = [n]\setminus S$ are the counted rounds, and $D_{\bar S}$ is the total delay in the counted rounds. If the delays are highly unbalanced, the latter regret guarantee can be significantly tighter than the former. The result requires no advance knowledge of the delays and resolves an open problem of Thune et al. (2019). The new FTRL algorithm and its refined tuning are anytime and require no doubling, which resolves another open problem of Thune et al. (2019).
Comment on "AndrODet: An adaptive Android obfuscation detector"
Venue: arXiv cs.CR 2020
Year: 2020

We have identified a methodological problem in the empirical evaluation of the string encryption detection capabilities of the AndrODet system described by Mirzaei et al. in the recent paper "AndrODet: An adaptive Android obfuscation detector". The accuracy of string encryption detection is evaluated using samples from the AMD and PraGuard malware datasets. However, the authors failed to account for the fact that many of the AMD samples are highly similar due to the fact that they come from the same malware family. This introduces a risk that a machine learning system trained on these samples could fail to learn a generalizable model for string encryption detection, and might instead learn to classify samples based on characteristics of each malware family. Our own evaluation strongly indicates that the reported high accuracy of AndrODet's string encryption detection is indeed due to this phenomenon. When we evaluated AndrODet, we found that when we ensured that samples from the same family never appeared in both training and testing data, the accuracy dropped to around 50%. Moreover, the PraGuard dataset is not suitable for evaluating a static string encryption detector such as AndrODet, since the particular obfuscation tool used to produce the dataset effectively makes it impossible to extract meaningful features of static strings in Android apps.
An evolutionary approach to continuously estimate CPR quality parameters from a wrist-worn inertial sensor
Venue: arXiv cs.NE 2020
Year: 2020

Cardiopulmonary resuscitation (CPR) is one of the most critical emergency interventions for sudden cardiac arrest. In this paper, a robust sinusoidal model-fitting method based on a Evolution Strategy inspired algorithm for CPR quality parameters -- naming chest compression frequency and depth -- as measured by an inertial measurement unit (IMU) attached to the wrist is presented. The proposed approach will allow bystanders to improve CPR as part of a continuous closed-loop support system once integrated into a smartphone or smartwatch application. By evaluating the model's precision with data recorded by a training mannequin as reference standard, a variance for the compression frequency of $\pm 2.22$ compressions per minute (cpm) has been found for the IMU attached to the wrist. It was found that this previously unconsidered position and thus, the use of smartwatches is a suitable alternative to the typical placement of phones in hand for CPR training.
In-training Matrix Factorization for Parameter-frugal Neural Machine Translation
Venue: arXiv cs.CL 2020
Year: 2020

In this paper, we propose the use of in-training matrix factorization to reduce the model size for neural machine translation. Using in-training matrix factorization, parameter matrices may be decomposed into the products of smaller matrices, which can compress large machine translation architectures by vastly reducing the number of learnable parameters. We apply in-training matrix factorization to different layers of standard neural architectures and show that in-training factorization is capable of reducing nearly 50% of learnable parameters without any associated loss in BLEU score. Further, we find that in-training matrix factorization is especially powerful on embedding layers, providing a simple and effective method to curtail the number of parameters with minimal impact on model performance, and, at times, an increase in performance.
Approximate Equilibria in Generalized Colonel Blotto and Generalized Lottery Blotto Games
Venue: arXiv cs.GT 2020
Year: 2020

In the Colonel Blotto game, two players with a fixed budget simultaneously allocate their resources across n battlefields to maximize the aggregate value gained from the battlefields where they have the higher allocation. Despite its long-standing history and important applications, the Colonel Blotto game still lacks a complete Nash equilibrium characterization in its most general form where players are asymmetric and battlefields' values are heterogeneous across battlefields and different between the two players---this is called the Generalized Colonel Blotto game. In this work, we propose a simply-constructed class of strategies---the independently uniform strategies---and we prove that they are approximate equilibria of the Generalized Colonel Blotto game; moreover, we characterize the approximation error according to the game's parameters. We also consider an extension called the Generalized Lottery Blotto game, with stochastic winner-determination rules allowing more flexibility in modeling practical contests. We prove that the proposed strategies are also approximate equilibria of the Generalized Lottery Blotto game.
Semantic Guided and Response Times Bounded Top-k Similarity Search over Knowledge Graphs
Venue: arXiv cs.DB 2020
Year: 2020

Recently, graph query is widely adopted for querying knowledge graphs. Given a query graph $G_Q$, the graph query finds subgraphs in a knowledge graph $G$ that exactly or approximately match $G_Q$. We face two challenges on graph query: (1) the structural gap between $G_Q$ and the predefined schema in $G$ causes mismatch with query graph, (2) users cannot view the answers until the graph query terminates, leading to a longer system response time (SRT). In this paper, we propose a semantic-guided and response-time-bounded graph query to return the top-k answers effectively and efficiently. We leverage a knowledge graph embedding model to build the semantic graph $SG_Q$, and we define the path semantic similarity ($pss$) over $SG_Q$ as the metric to evaluate the answer's quality. Then, we propose an A* semantic search on $SG_Q$ to find the top-k answers with the greatest $pss$ via a heuristic $pss$ estimation. Furthermore, we make an approximate optimization on A* semantic search to allow users to trade off the effectiveness for SRT within a user-specific time bound. Extensive experiments over real datasets confirm the effectiveness and efficiency of our solution.
Entanglement-assisted Quantum MDS Codes from generalized Reed-Solomon Codes
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we produce some new classes of entanglement-assisted quantum MDS codes(EAQMDS codes for short) via generalized Reed-Solomon codes over finite fields of odd characteristic. Among our constructions, there are many EAQMDS codes with new lengths which have never been reported. Moreover, some of them have larger minimum distance than known results.
Compact Network Training for Person ReID
Venue: arXiv cs.CV 2020
Year: 2020

The task of person re-identification (ReID) has attracted growing attention in recent years leading to improved performance, albeit with little focus on real-world applications. Most SotA methods are based on heavy pre-trained models, e.g. ResNet50 (~25M parameters), which makes them less practical and more tedious to explore architecture modifications. In this study, we focus on a small-sized randomly initialized model that enables us to easily introduce architecture and training modifications suitable for person ReID. The outcomes of our study are a compact network and a fitting training regime. We show the robustness of the network by outperforming the SotA on both Market1501 and DukeMTMC. Furthermore, we show the representation power of our ReID network via SotA results on a different task of multi-object tracking.
DeepErase: Weakly Supervised Ink Artifact Removal in Document Text Images
Venue: arXiv cs.CV 2020
Year: 2020

Paper-intensive industries like insurance, law, and government have long leveraged optical character recognition (OCR) to automatically transcribe hordes of scanned documents into text strings for downstream processing. Even in 2019, there are still many scanned documents and mail that come into businesses in non-digital format. Text to be extracted from real world documents is often nestled inside rich formatting, such as tabular structures or forms with fill-in-the-blank boxes or underlines whose ink often touches or even strikes through the ink of the text itself. Further, the text region could have random ink smudges or spurious strokes. Such ink artifacts can severely interfere with the performance of recognition algorithms or other downstream processing tasks. In this work, we propose DeepErase, a neural-based preprocessor to erase ink artifacts from text images. We devise a method to programmatically assemble real text images and real artifacts into realistic-looking "dirty" text images, and use them to train an artifact segmentation network in a weakly supervised manner, since pixel-level annotations are automatically obtained during the assembly process. In addition to high segmentation accuracy, we show that our cleansed images achieve a significant boost in recognition accuracy by popular OCR software such as Tesseract 4.0. Finally, we test DeepErase on out-of-distribution datasets (NIST SDB) of scanned IRS tax return forms and achieve double-digit improvements in accuracy. All experiments are performed on both printed and handwritten text. Code for all experiments is available at https://github.com/yikeqicn/DeepErase
Consentio: Managing Consent to Data Access using Permissioned Blockchains
Venue: arXiv cs.DC 2020
Year: 2020

The increasing amount of personal data is raising serious issues in the context of privacy, security, and data ownership. Entities whose data are being collected can benefit from mechanisms to manage the parties that can access their data and to audit who has accessed their data. Consent management systems address these issues. We present Consentio, a scalable consent management system based on the Hyperledger Fabric permissioned blockchain. The data management challenge we address is to ensure high throughput and low latency of endorsing data access requests and granting or revoking consent. Experimental results show that our system can handle as many as 6,000 access requests per second, allowing it to scale to very large deployments.
Hidden Unit Specialization in Layered Neural Networks: ReLU vs. Sigmoidal Activation
Venue: arXiv cs.LG 2020
Year: 2020

We study layered neural networks of rectified linear units (ReLU) in a modelling framework for stochastic training processes. The comparison with sigmoidal activation functions is in the center of interest. We compute typical learning curves for shallow networks with K hidden units in matching student teacher scenarios. The systems exhibit sudden changes of the generalization performance via the process of hidden unit specialization at critical sizes of the training set. Surprisingly, our results show that the training behavior of ReLU networks is qualitatively different from that of networks with sigmoidal activations. In networks with K >= 3 sigmoidal hidden units, the transition is discontinuous: Specialized network configurations co-exist and compete with states of poor performance even for very large training sets. On the contrary, the use of ReLU activations results in continuous transitions for all K: For large enough training sets, two competing, differently specialized states display similar generalization abilities, which coincide exactly for large networks in the limit K to infinity.
Scaling up Psychology via Scientific Regret Minimization: A Case Study in Moral Decisions
Venue: arXiv cs.CY 2020
Year: 2020

Do large datasets provide value to psychologists? Without a systematic methodology for working with such datasets, there is a valid concern that analyses will produce noise artifacts rather than true effects. In this paper, we offer a way to enable researchers to systematically build models and identify novel phenomena in large datasets. One traditional approach is to analyze the residuals of models---the biggest errors they make in predicting the data---to discover what might be missing from those models. However, once a dataset is sufficiently large, machine learning algorithms approximate the true underlying function better than the data, suggesting instead that the predictions of these data-driven models should be used to guide model-building. We call this approach "Scientific Regret Minimization" (SRM) as it focuses on minimizing errors for cases that we know should have been predictable. We demonstrate this methodology on a subset of the Moral Machine dataset, a public collection of roughly forty million moral decisions. Using SRM, we found that incorporating a set of deontological principles that capture dimensions along which groups of agents can vary (e.g. sex and age) improves a computational model of human moral judgment. Furthermore, we were able to identify and independently validate three interesting moral phenomena: criminal dehumanization, age of responsibility, and asymmetric notions of responsibility.
Quality of Service in IEEE 802.11 WLANs: An Experimental Study
Venue: arXiv cs.NI 2020
Year: 2020

While the IEEE 802.11 protocol is being widely used, it is not specifically designed to handle multimedia traffic, which covers an important portion of the Internet traffic today. Voice and video multicast streaming is inefficient, as there is lack of transmission reliability in such approaches where delay is not guaranteed. In this work, we focus on the performance of Enhanced Distributed Channel Access (EDCA) mechanism proposed by IEEE 802.11e which provides traffic prioritization and since most of the previous works are done based on simulation results, we test the performance of this protocol in a real platform using sofware Defined Networks. We then validate the impact of different EDCA parameters ( e.g., AIFS and TXOP) by tuning them to see their impact on the delay of the network and eventually on network traffic.
The other side of the Coin: Risks of the Libra Blockchain
Venue: arXiv cs.CY 2020
Year: 2020

Libra was presented as a cryptocurrency on June 18, 2019 by Facebook. On the same day, Facebook announced plans for Calibra, a subsidiary in charge of the development of an electronic wallet and financial services. In view of the primary risk of sovereignty posed by the creation of Libra, regulators and Central Banks quickly took very clear positions against the project and expressed a lot of questions focusing on regulation aspects and national sovereignty. The purpose of this paper is to provide a holistic analysis of the project encompassing several aspects of its implementation and the issues it raises. We address a set of questions that are part of the cryptocurrency environment and blockchain technology that support the Libra project. We describe the governance of the project based on two levels, one for the Association and the other for the Libra Blockchain. We identify the main risks considering at the same time political, financial, economic, technological and ethical risks. We emphasize the difficulty to regulate such a project as it will depend on several countries whose legislations are very different. Finally, the future of this kind of projects is discussed through the emergence of Central Bank Digital Currencies.
Zero-Determinant strategies in repeated multiplayer social dilemmas with discounted payoffs
Venue: arXiv cs.GT 2020
Year: 2020

In two-player repeated games, Zero-Determinant (ZD) strategies enable a player to unilaterally enforce a linear payoff relation between her own and her opponent's payoff irrespective of the opponent's strategy. This manipulative nature of the ZD strategies attracted significant attention from researchers due to its close connection to controlling distributively the outcome of evolutionary games in large populations. In this paper, necessary and sufficient conditions are derived for a payoff relation to be enforceable in multiplayer social dilemmas with a finite expected number of rounds that is determined by a fixed and common discount factor. Thresholds exist for such a discount factor above which desired payoff relations can be enforced. Our results show that depending on the group size and the ZD-strategist's initial probability to cooperate there exist extortionate, generous and equalizer ZD-strategies. The threshold discount factors rely on the desired payoff relation and the variation in the single-round payoffs. To show the utility of our results, we apply them to multiplayer social dilemmas, and show how discounting affects ZD Nash equilibria.
Solving Linear Programs with Sqrt(rank) Linear System Solves
Venue: arXiv cs.DS 2020
Year: 2020

We present an algorithm that given a linear program with $n$ variables, $m$ constraints, and constraint matrix $A$, computes an $ε$-approximate solution in $\tilde{O}(\sqrt{rank(A)}\log(1/ε))$ iterations with high probability. Each iteration of our method consists of solving $\tilde{O}(1)$ linear systems and additional nearly linear time computation, improving by a factor of $\tildeΩ((m/rank(A))^{1/2})$ over the previous fastest method with this iteration cost due to Renegar (1988). Further, we provide a deterministic polynomial time computable $\tilde{O}(rank(A))$-self-concordant barrier function for the polytope, resolving an open question of Nesterov and Nemirovski (1994) on the theory of "universal barriers" for interior point methods. Applying our techniques to the linear program formulation of maximum flow yields an $\tilde{O}(|E|\sqrt{|V|}\log(U))$ time algorithm for solving the maximum flow problem on directed graphs with $|E|$ edges, $|V|$ vertices, and integer capacities of size at most $U$. This improves upon the previous fastest polynomial running time of $O(|E|\min\{|E|^{1/2},|V|^{2/3}\}\log(|V|^{2}/|E|)\log(U))$ achieved by Goldberg and Rao (1998). In the special case of solving dense directed unit capacity graphs our algorithm improves upon the previous fastest running times of $O(|E|\min\{|E|^{1/2},|V|^{2/3}\})$ achieved by Even and Tarjan (1975) and Karzanov (1973) and of $\tilde{O}(|E|^{10/7})$ achieved more recently by Mądry (2013).
Neural Spectrum Alignment: Empirical Study
Venue: arXiv cs.LG 2020
Year: 2020

Expressiveness and generalization of deep models was recently addressed via the connection between neural networks (NNs) and kernel learning, where first-order dynamics of NN during a gradient-descent (GD) optimization were related to gradient similarity kernel, also known as Neural Tangent Kernel (NTK). In the majority of works this kernel is considered to be time-invariant, with its properties being defined entirely by NN architecture and independent of the learning task at hand. In contrast, in this paper we empirically explore these properties along the optimization and show that in practical applications the NTK changes in a very dramatic and meaningful way, with its top eigenfunctions aligning toward the target function learned by NN. Moreover, these top eigenfunctions serve as basis functions for NN output - a function represented by NN is spanned almost completely by them for the entire optimization process. Further, since the learning along top eigenfunctions is typically fast, their alignment with the target function improves the overall optimization performance. In addition, we study how the neural spectrum is affected by learning rate decay, typically done by practitioners, showing various trends in the kernel behavior. We argue that the presented phenomena may lead to a more complete theoretical understanding behind NN learning.
RLScheduler: An Automated HPC Batch Job Scheduler Using Reinforcement Learning
Venue: arXiv cs.DC 2020
Year: 2020

Today high-performance computing (HPC) platforms are still dominated by batch jobs. Accordingly, effective batch job scheduling is crucial to obtain high system efficiency. Existing HPC batch job schedulers typically leverage heuristic priority functions to prioritize and schedule jobs. But, once configured and deployed by the experts, such priority functions can hardly adapt to the changes of job loads, optimization goals, or system settings, potentially leading to degraded system efficiency when changes occur. To address this fundamental issue, we present RLScheduler, an automated HPC batch job scheduler built on reinforcement learning. RLScheduler relies on minimal manual interventions or expert knowledge, but can learn high-quality scheduling policies via its own continuous 'trial and error'. We introduce a new kernel-based neural network structure and trajectory filtering mechanism in RLScheduler to improve and stabilize the learning process. Through extensive evaluations, we confirm that RLScheduler can learn high-quality scheduling policies towards various workloads and various optimization goals with relatively low computation cost. Moreover, we show that the learned models perform stably even when applied to unseen workloads, making them practical for production use.
Discovering the Compositional Structure of Vector Representations with Role Learning Networks
Venue: arXiv cs.LG 2020
Year: 2020

How can neural networks perform so well on compositional tasks even though they lack explicit compositional representations? We use a novel analysis technique called ROLE to show that recurrent neural networks perform well on such tasks by converging to solutions which implicitly represent symbolic structure. This method uncovers a symbolic structure which, when properly embedded in vector space, closely approximates the encodings of a standard seq2seq network trained to perform the compositional SCAN task. We verify the causal importance of the discovered symbolic structure by showing that, when we systematically manipulate hidden embeddings based on this symbolic structure, the model's output is changed in the way predicted by our analysis.