OpenRaiser/Intern-Atlas huggingface dataset:
Post-training 4-bit quantization of convolution networks for rapid-deployment
Venue: arXiv cs.CV 2019
Year: 2019

Convolutional neural networks require significant memory bandwidth and storage for intermediate computations, apart from substantial computing resources. Neural network quantization has significant benefits in reducing the amount of intermediate results, but it often requires the full datasets and time-consuming fine tuning to recover the accuracy lost after quantization. This paper introduces the first practical 4-bit post training quantization approach: it does not involve training the quantized model (fine-tuning), nor it requires the availability of the full dataset. We target the quantization of both activations and weights and suggest three complementary methods for minimizing quantization error at the tensor level, two of whom obtain a closed-form analytical solution. Combining these methods, our approach achieves accuracy that is just a few percents less the state-of-the-art baseline across a wide range of convolutional models. The source code to replicate all experiments is available on GitHub: \url{https://github.com/submission2019/cnn-quantization}.
Resource Allocation in Wireless Powered IoT Networks
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, efficient resource allocation for the uplink transmission of wireless powered IoT networks is investigated. We adopt LoRa technology as an example in the IoT network, but this work is still suitable for other communication technologies. Allocating limited resources, like spectrum and energy resources, among a massive number of users faces critical challenges. We consider grouping wireless powered IoT users into available channels first and then investigate power allocation for users grouped in the same channel to improve the network throughput. Specifically, the user grouping problem is formulated as a many to one matching game. It is achieved by considering IoT users and channels as selfish players which belong to two disjoint sets. Both selfish players focus on maximizing their own utilities. Then we propose an efficient channel allocation algorithm (ECAA) with low complexity for user grouping. Additionally, a Markov Decision Process (MDP) is used to model unpredictable energy arrival and channel conditions uncertainty at each user, and a power allocation algorithm is proposed to maximize the accumulative network throughput over a finite-horizon of time slots. By doing so, we can distribute the channel access and dynamic power allocation local to IoT users. Numerical results demonstrate that our proposed ECAA algorithm achieves near-optimal performance and is superior to random channel assignment, but has much lower computational complexity. Moreover, simulations show that the distributed power allocation policy for each user is obtained with better performance than a centralized offline scheme.
Refacing: reconstructing anonymized facial features using GANs
Venue: arXiv cs.CV 2019
Year: 2019

Anonymization of medical images is necessary for protecting the identity of the test subjects, and is therefore an essential step in data sharing. However, recent developments in deep learning may raise the bar on the amount of distortion that needs to be applied to guarantee anonymity. To test such possibilities, we have applied the novel CycleGAN unsupervised image-to-image translation framework on sagittal slices of T1 MR images, in order to reconstruct facial features from anonymized data. We applied the CycleGAN framework on both face-blurred and face-removed images. Our results show that face blurring may not provide adequate protection against malicious attempts at identifying the subjects, while face removal provides more robust anonymization, but is still partially reversible.
SynSeg-Net: Synthetic Segmentation Without Target Modality Ground Truth
Venue: arXiv cs.CV 2019
Year: 2019

A key limitation of deep convolutional neural networks (DCNN) based image segmentation methods is the lack of generalizability. Manually traced training images are typically required when segmenting organs in a new imaging modality or from distinct disease cohort. The manual efforts can be alleviated if the manually traced images in one imaging modality (e.g., MRI) are able to train a segmentation network for another imaging modality (e.g., CT). In this paper, we propose an end-to-end synthetic segmentation network (SynSeg-Net) to train a segmentation network for a target imaging modality without having manual labels. SynSeg-Net is trained by using (1) unpaired intensity images from source and target modalities, and (2) manual labels only from source modality. SynSeg-Net is enabled by the recent advances of cycle generative adversarial networks (CycleGAN) and DCNN. We evaluate the performance of the SynSeg-Net on two experiments: (1) MRI to CT splenomegaly synthetic segmentation for abdominal images, and (2) CT to MRI total intracranial volume synthetic segmentation (TICV) for brain images. The proposed end-to-end approach achieved superior performance to two stage methods. Moreover, the SynSeg-Net achieved comparable performance to the traditional segmentation network using target modality labels in certain scenarios. The source code of SynSeg-Net is publicly available (https://github.com/MASILab/SynSeg-Net).
Diacritization of Maghrebi Arabic Sub-Dialects
Venue: arXiv cs.CL 2019
Year: 2019

Diacritization process attempt to restore the short vowels in Arabic written text; which typically are omitted. This process is essential for applications such as Text-to-Speech (TTS). While diacritization of Modern Standard Arabic (MSA) still holds the lion share, research on dialectal Arabic (DA) diacritization is very limited. In this paper, we present our contribution and results on the automatic diacritization of two sub-dialects of Maghrebi Arabic, namely Tunisian and Moroccan, using a character-level deep neural network architecture that stacks two bi-LSTM layers over a CRF output layer. The model achieves word error rate of 2.7% and 3.6% for Moroccan and Tunisian respectively and is capable of implicitly identifying the sub-dialect of the input.
Multi-budgeted directed cuts
Venue: arXiv cs.DS 2019
Year: 2019

We study multi-budgeted variants of the classic minimum cut problem and graph separation problems that turned out to be important in parameterized complexity: Skew Multicut and Directed Feedback Arc Set. In our generalization, we assign colors $1,2,...,\ell$ to some edges and give separate budgets $k_{1},k_{2},...,k_{\ell}$. Let $E_{i}$ be the set of edges of color $i$. The solution $C$ for the multi-budgeted variant of a graph separation problem not only needs to satisfy the usual separation requirements, but also needs to satisfy that $|C\cap E_{i}|\leq k_{i}$ for every $i\in \{1,...,\ell\}$. Contrary to the classic minimum cut problem, the multi-budgeted variant turns out to be NP-hard even for $\ell = 2$. We propose FPT algorithms parameterized by $k=k_{1}+...+k_{\ell}$ for all three problems. To this end, we develop a branching procedure for the multi-budgeted minimum cut problem that measures the progress of the algorithm not by reducing $k$ as usual, by but elevating the capacity of some edges and thus increasing the size of maximum source-to-sink flow. Using the fact that a similar strategy is used to enumerate all important separators of a given size, we merge this process with the flow-guided branching and show an FPT bound on the number of (appropriately defined) important multi-budgeted separators. This allows us to extend our algorithm to the Skew Multicut and Directed Feedback Arc Set problems. Furthermore, we show connections of the multi-budgeted variants with weighted variants of the directed cut problems and the Chain $\ell$-SAT problem, whose parameterized complexity remains an open problem. We show that these problems admit a bounded-in-parameter number of "maximally pushed" solutions (in a similar spirit as important separators are maximally pushed), giving somewhat weak evidence towards their tractability.
Topographic Representation for Quantum Machine Learning
Venue: arXiv cs.LG 2019
Year: 2019

This paper proposes a brain-inspired approach to quantum machine learning with the goal of circumventing many of the complications of other approaches. The fact that quantum processes are unitary presents both opportunities and challenges. A principal opportunity is that a large number of computations can be carried out in parallel in linear superposition, that is, quantum parallelism. The challenge is that the process is linear, and most approaches to machine learning depend significantly on nonlinear processes. Fortunately, the situation is not hopeless, for we know that nonlinear processes can be embedded in unitary processes, as is familiar from the circuit model of quantum computation. This paper explores an approach to the quantum implementation of machine learning involving nonlinear functions operating on information represented topographically (by computational maps), as common in neural cortex.
Locally Private Mean Estimation: Z-test and Tight Confidence Intervals
Venue: arXiv cs.DS 2019
Year: 2019

This work provides tight upper- and lower-bounds for the problem of mean estimation under $ε$-differential privacy in the local model, when the input is composed of $n$ i.i.d. drawn samples from a normal distribution with variance $σ$. Our algorithms result in a $(1-β)$-confidence interval for the underlying distribution's mean $μ$ of length $\tilde O\left( \frac{σ\sqrt{\log(\frac 1 β)}}{ε\sqrt n} \right)$. In addition, our algorithms leverage binary search using local differential privacy for quantile estimation, a result which may be of separate interest. Moreover, we prove a matching lower-bound (up to poly-log factors), showing that any one-shot (each individual is presented with a single query) local differentially private algorithm must return an interval of length $Ω\left( \frac{σ\sqrt{\log(1/β)}}{ε\sqrt{n}}\right)$.
AutoGraph: Imperative-style Coding with Graph-based Performance
Venue: arXiv cs.PL 2019
Year: 2019

There is a perceived trade-off between machine learning code that is easy to write, and machine learning code that is scalable or fast to execute. In machine learning, imperative style libraries like Autograd and PyTorch are easy to write, but suffer from high interpretive overhead and are not easily deployable in production or mobile settings. Graph-based libraries like TensorFlow and Theano benefit from whole-program optimization and can be deployed broadly, but make expressing complex models more cumbersome. We describe how the use of staged programming in Python, via source code transformation, offers a midpoint between these two library design patterns, capturing the benefits of both. A key insight is to delay all type-dependent decisions until runtime, via dynamic dispatch. We instantiate these principles in AutoGraph, a software system that improves the programming experience of the TensorFlow library, and demonstrate usability improvements with no loss in performance compared to native TensorFlow graphs. We also show that our system is backend agnostic, and demonstrate targeting an alternate IR with characteristics not found in TensorFlow graphs.
Logic Negation with Spiking Neural P Systems
Venue: arXiv cs.AI 2019
Year: 2019

Nowadays, the success of neural networks as reasoning systems is doubtless. Nonetheless, one of the drawbacks of such reasoning systems is that they work as black-boxes and the acquired knowledge is not human readable. In this paper, we present a new step in order to close the gap between connectionist and logic based reasoning systems. We show that two of the most used inference rules for obtaining negative information in rule based reasoning systems, the so-called Closed World Assumption and Negation as Finite Failure can be characterized by means of spiking neural P systems, a formal model of the third generation of neural networks born in the framework of membrane computing.
Alphabet-Dependent Bounds for Linear Locally Repairable Codes Based on Residual Codes
Venue: arXiv cs.IT 2019
Year: 2019

Locally repairable codes (LRCs) have gained significant interest for the design of large distributed storage systems as they allow a small number of erased nodes to be recovered by accessing only a few others. Several works have thus been carried out to understand the optimal rate-distance tradeoff, but only recently the size of the alphabet has been taken into account. In this paper, a novel definition of locality is proposed to keep track of the precise number of nodes required for a local repair when the repair sets do not yield MDS codes. Then, a new alphabet-dependent bound is derived, which applies both to the new definition and the initial definition of locality. The new bound is based on consecutive residual codes and intrinsically uses the Griesmer bound. A special case of the bound yields both the extension of the Cadambe-Mazumdar bound and the Singleton-type bound for codes with locality $(r, δ)$, implying that the new bound is at least as good as these bounds. Furthermore, an upper bound on the asymptotic rate-distance tradeoff of LRCs is derived, and yields the tightest known upper bound for large relative minimum distances. Achievability results are also provided by deriving the locality of the family of Simplex codes together with a few examples of optimal codes.
Nonlinear Mapping and Distance Geometry
Venue: arXiv cs.CG 2019
Year: 2019

Distance Geometry Problem (DGP) and Nonlinear Mapping (NLM) are two well established questions: Distance Geometry Problem is about finding a Euclidean realization of an incomplete set of distances in a Euclidean space, whereas Nonlinear Mapping is a weighted Least Square Scaling (LSS) method. We show how all these methods (LSS, NLM, DGP) can be assembled in a common framework, being each identified as an instance of an optimization problem with a choice of a weight matrix. We study the continuity between the solutions (which are point clouds) when the weight matrix varies, and the compactness of the set of solutions (after centering). We finally study a numerical example, showing that solving the optimization problem is far from being simple and that the numerical solution for a given procedure may be trapped in a local minimum.
MMLSpark: Unifying Machine Learning Ecosystems at Massive Scales
Venue: arXiv cs.LG 2019
Year: 2019

We introduce Microsoft Machine Learning for Apache Spark (MMLSpark), an ecosystem of enhancements that expand the Apache Spark distributed computing library to tackle problems in Deep Learning, Micro-Service Orchestration, Gradient Boosting, Model Interpretability, and other areas of modern computation. Furthermore, we present a novel system called Spark Serving that allows users to run any Apache Spark program as a distributed, sub-millisecond latency web service backed by their existing Spark Cluster. All MMLSpark contributions have the same API to enable simple composition across frameworks and usage across batch, streaming, and RESTful web serving scenarios on static, elastic, or serverless clusters. We showcase MMLSpark by creating a method for deep object detection capable of learning without human labeled data and demonstrate its effectiveness for Snow Leopard conservation.
Collective Learning From Diverse Datasets for Entity Typing in the Wild
Venue: arXiv cs.CL 2019
Year: 2019

Entity typing (ET) is the problem of assigning labels to given entity mentions in a sentence. Existing works for ET require knowledge about the domain and target label set for a given test instance. ET in the absence of such knowledge is a novel problem that we address as ET in the wild. We hypothesize that the solution to this problem is to build supervised models that generalize better on the ET task as a whole, rather than a specific dataset. In this direction, we propose a Collective Learning Framework (CLF), which enables learning from diverse datasets in a unified way. The CLF first creates a unified hierarchical label set (UHLS) and a label mapping by aggregating label information from all available datasets. Then it builds a single neural network classifier using UHLS, label mapping, and a partial loss function. The single classifier predicts the finest possible label across all available domains even though these labels may not be present in any domain-specific dataset. We also propose a set of evaluation schemes and metrics to evaluate the performance of models in this novel problem. Extensive experimentation on seven diverse real-world datasets demonstrates the efficacy of our CLF.
Proportionality Degree of Multiwinner Rules
Venue: arXiv cs.GT 2019
Year: 2019

We study multiwinner elections with approval-based preferences. An instance of a multiwinner election consists of a set of alternatives, a population of voters---each voter approves a subset of alternatives, and the desired committee size $k$; the goal is to select a committee (a~subset) of $k$ alternatives according to the preferences of the voters. We investigate a number of election rules and ask whether the committees that they return represent the voters proportionally. In contrast to the classic literature, we employ quantitative techniques that allow to measure the extent to which the considered rules are proportional. This allows us to arrange the rules in a clear hierarchy. For example, we find that Proportional Approval Voting (PAV) has better proportionality guarantees than its sequential counterpart, and that Phragmén's Sequential Rule is worse than Sequential PAV. Yet, the loss of proportionality for the two sequential rules is moderate and in some contexts can be outweighed by their other appealing properties. Finally, we measure the tradeoff between proportionality and utilitarian efficiency for a broad subclass of committee election rules.
Learning-based Application-Agnostic 3D NoC Design for Heterogeneous Manycore Systems
Venue: arXiv cs.DC 2019
Year: 2019

The rising use of deep learning and other big-data algorithms has led to an increasing demand for hardware platforms that are computationally powerful, yet energy-efficient. Due to the amount of data parallelism in these algorithms, high-performance 3D manycore platforms that incorporate both CPUs and GPUs present a promising direction. However, as systems use heterogeneity (e.g., a combination of CPUs, GPUs, and accelerators) to improve performance and efficiency, it becomes more pertinent to address the distinct and likely conflicting communication requirements (e.g., CPU memory access latency or GPU network throughput) that arise from such heterogeneity. Unfortunately, it is difficult to quickly explore the hardware design space and choose appropriate tradeoffs between these heterogeneous requirements. To address these challenges, we propose the design of a 3D Network-on-Chip (NoC) for heterogeneous manycore platforms that considers the appropriate design objectives for a 3D heterogeneous system and explores various tradeoffs using an efficient ML-based multi-objective optimization technique. The proposed design space exploration considers the various requirements of its heterogeneous components and generates a set of 3D NoC architectures that efficiently trades off these design objectives. Our findings show that by jointly considering these requirements (latency, throughput, temperature, and energy), we can achieve 9.6% better Energy-Delay Product on average at nearly iso-temperature conditions when compared to a thermally-optimized design for 3D heterogeneous NoCs. More importantly, our results suggest that our 3D NoCs optimized for a few applications can be generalized for unknown applications as well. Our results show that these generalized 3D NoCs only incur a 1.8% (36-tile system) and 1.1% (64-tile system) average performance loss compared to application-specific NoCs.
Pose consensus based on dual quaternion algebra with application to decentralized formation control of mobile manipulators
Venue: arXiv cs.RO 2019
Year: 2019

This paper presents a solution based on dual quaternion algebra to the general problem of pose (i.e., position and orientation) consensus for systems composed of multiple rigid-bodies. The dual quaternion algebra is used to model the agents' poses and also in the distributed control laws, making the proposed technique easily applicable to time-varying formation control of general robotic systems. The proposed pose consensus protocol has guaranteed convergence when the interaction among the agents is represented by directed graphs with directed spanning trees, which is a more general result when compared to the literature on formation control. In order to illustrate the proposed pose consensus protocol and its extension to the problem of formation control, we present a numerical simulation with a large number of free-flying agents and also an application of cooperative manipulation by using real mobile manipulators.
Dynamic Average Diffusion with randomized Coordinate Updates
Venue: arXiv cs.SI 2019
Year: 2019

This work derives and analyzes an online learning strategy for tracking the average of time-varying distributed signals by relying on randomized coordinate-descent updates. During each iteration, each agent selects or observes a random entry of the observation vector, and different agents may select different entries of their observations before engaging in a consultation step. Careful coordination of the interactions among agents is necessary to avoid bias and ensure convergence. We provide a convergence analysis for the proposed methods, and illustrate the results by means of simulations.
Fluctuation Bounds for the Max-Weight Policy, with Applications to State Space Collapse
Venue: arXiv cs.NI 2019
Year: 2019

We consider a multi-hop switched network operating under a Max-Weight (MW) scheduling policy, and show that the distance between the queue length process and a fluid solution remains bounded by a constant multiple of the deviation of the cumulative arrival process from its average. We then exploit this result to prove matching upper and lower bounds for the time scale over which additive state space collapse (SSC) takes place. This implies, as two special cases, an additive SSC result in diffusion scaling under non-Markovian arrivals and, for the case of i.i.d. arrivals, an additive SSC result over an exponential time scale.
On The Stability of Interpretable Models
Venue: arXiv cs.LG 2019
Year: 2019

Interpretable classification models are built with the purpose of providing a comprehensible description of the decision logic to an external oversight agent. When considered in isolation, a decision tree, a set of classification rules, or a linear model, are widely recognized as human-interpretable. However, such models are generated as part of a larger analytical process. Bias in data collection and preparation, or in model's construction may severely affect the accountability of the design process. We conduct an experimental study of the stability of interpretable models with respect to feature selection, instance selection, and model selection. Our conclusions should raise awareness and attention of the scientific community on the need of a stability impact assessment of interpretable models.
Perturbation Bounds for Procrustes, Classical Scaling, and Trilateration, with Applications to Manifold Learning
Venue: arXiv cs.LG 2019
Year: 2019

One of the common tasks in unsupervised learning is dimensionality reduction, where the goal is to find meaningful low-dimensional structures hidden in high-dimensional data. Sometimes referred to as manifold learning, this problem is closely related to the problem of localization, which aims at embedding a weighted graph into a low-dimensional Euclidean space. Several methods have been proposed for localization, and also manifold learning. Nonetheless, the robustness property of most of them is little understood. In this paper, we obtain perturbation bounds for classical scaling and trilateration, which are then applied to derive performance bounds for Isomap, Landmark Isomap, and Maximum Variance Unfolding. A new perturbation bound for procrustes analysis plays a key role.