OpenRaiser/Intern-Atlas huggingface dataset:
Non-Preemptive Flow-Time Minimization via Rejections
Venue: arXiv cs.DS 2018
Year: 2018

We consider the online problem of minimizing weighted flow-time on unrelated machines. Although much is known about this problem in the resource-augmentation setting, these results assume that jobs can be preempted. We give the first constant-competitive algorithm for the non-preemptive setting in the rejection model. In this rejection model, we are allowed to reject an $\varepsilon$-fraction of the total weight of jobs, and compare the resulting flow-time to that of the offline optimum which is required to schedule all jobs. This is arguably the weakest assumption in which such a result is known for weighted flow-time on unrelated machines. While our algorithms are simple, we need a delicate dual-fitting argument to bound the flow-time while only a small fraction of elements are rejected.
Infinite-server queueing model with MAPkGk Markov arrival streams, random volume of customers in random environment subject to catastrophe
Venue: arXiv cs.PF 2018
Year: 2018

In this paper the infinite server queue model in semi-Markov random environment with k Markov arrival streams, random resources of customers, and catastrophes is considered. After catastrophes occur, all customers in the model are flashed out and the system jumps into recovery station. After the recovery time the model works from the empty state. The transient and stationary joint distributions of numbers of different types of customers in the model at moment t, numbers of different types of served in some interval customers, volume of accumulated resources in the model at moment t, and total volume of served resources in an interval for the model without catastrophes are found. The transient and stationary joint distributions of numbers of different types of customers in the model at moment t, and volume of accumulated resources in the model at moment t and their moments for the model with catastrophes are obtained. All results are obtained using Danzig collective marks method and renewal theory methods.
Corpus Conversion Service: A machine learning platform to ingest documents at scale [Poster abstract]
Venue: arXiv cs.DL 2018
Year: 2018

Over the past few decades, the amount of scientific articles and technical literature has increased exponentially in size. Consequently, there is a great need for systems that can ingest these documents at scale and make their content discoverable. Unfortunately, both the format of these documents (e.g. the PDF format or bitmap images) as well as the presentation of the data (e.g. complex tables) make the extraction of qualitative and quantitive data extremely challenging. We present a platform to ingest documents at scale which is powered by Machine Learning techniques and allows the user to train custom models on document collections. We show precision/recall results greater than 97% with regard to conversion to structured formats, as well as scaling evidence for each of the microservices constituting the platform.
Mining Procedures from Technical Support Documents
Venue: arXiv cs.AI 2018
Year: 2018

Guided troubleshooting is an inherent task in the domain of technical support services. When a customer experiences an issue with the functioning of a technical service or a product, an expert user helps guide the customer through a set of steps comprising a troubleshooting procedure. The objective is to identify the source of the problem through a set of diagnostic steps and observations, and arrive at a resolution. Procedures containing these set of diagnostic steps and observations in response to different problems are common artifacts in the body of technical support documentation. The ability to use machine learning and linguistics to understand and leverage these procedures for applications like intelligent chatbots or robotic process automation, is crucial. Existing research on question answering or intelligent chatbots does not look within procedures or deep-understand them. In this paper, we outline a system for mining procedures from technical support documents. We create models for solving important subproblems like extraction of procedures, identifying decision points within procedures, identifying blocks of instructions corresponding to these decision points and mapping instructions within a decision block. We also release a dataset containing our manual annotations on publicly available support documents, to promote further research on the problem.
A Corpus for Multilingual Document Classification in Eight Languages
Venue: arXiv cs.CL 2018
Year: 2018

Cross-lingual document classification aims at training a document classifier on resources in one language and transferring it to a different language without any additional resources. Several approaches have been proposed in the literature and the current best practice is to evaluate them on a subset of the Reuters Corpus Volume 2. However, this subset covers only few languages (English, German, French and Spanish) and almost all published works focus on the the transfer between English and German. In addition, we have observed that the class prior distributions differ significantly between the languages. We argue that this complicates the evaluation of the multilinguality. In this paper, we propose a new subset of the Reuters corpus with balanced class priors for eight languages. By adding Italian, Russian, Japanese and Chinese, we cover languages which are very different with respect to syntax, morphology, etc. We provide strong baselines for all language transfer directions using multilingual word and sentence embeddings respectively. Our goal is to offer a freely available framework to evaluate cross-lingual document classification, and we hope to foster by these means, research in this important area.
Polynomially Coded Regression: Optimal Straggler Mitigation via Data Encoding
Venue: arXiv cs.IT 2018
Year: 2018

We consider the problem of training a least-squares regression model on a large dataset using gradient descent. The computation is carried out on a distributed system consisting of a master node and multiple worker nodes. Such distributed systems are significantly slowed down due to the presence of slow-running machines (stragglers) as well as various communication bottlenecks. We propose "polynomially coded regression" (PCR) that substantially reduces the effect of stragglers and lessens the communication burden in such systems. The key idea of PCR is to encode the partial data stored at each worker, such that the computations at the workers can be viewed as evaluating a polynomial at distinct points. This allows the master to compute the final gradient by interpolating this polynomial. PCR significantly reduces the recovery threshold, defined as the number of workers the master has to wait for prior to computing the gradient. In particular, PCR requires a recovery threshold that scales inversely proportionally with the amount of computation/storage available at each worker. In comparison, state-of-the-art straggler-mitigation schemes require a much higher recovery threshold that only decreases linearly in the per worker computation/storage load. We prove that PCR's recovery threshold is near minimal and within a factor two of the best possible scheme. Our experiments over Amazon EC2 demonstrate that compared with state-of-the-art schemes, PCR improves the run-time by 1.50x ~ 2.36x with naturally occurring stragglers, and by as much as 2.58x ~ 4.29x with artificial stragglers.
Part-based Visual Tracking via Structural Support Correlation Filter
Venue: arXiv cs.CV 2018
Year: 2018

Recently, part-based and support vector machines (SVM) based trackers have shown favorable performance. Nonetheless, the time-consuming online training and updating process limit their real-time applications. In order to better deal with the partial occlusion issue and improve their efficiency, we propose a novel part-based structural support correlation filter tracking method, which absorbs the strong discriminative ability from SVM and the excellent property of part-based tracking methods which is less sensitive to partial occlusion. Then, our proposed model can learn the support correlation filter of each part jointly by a star structure model, which preserves the spatial layout structure among parts and tolerates outliers of parts. In addition, to mitigate the issue of drift away from object further, we introduce inter-frame consistencies of local parts into our model. Finally, in our model, we accurately estimate the scale changes of object by the relative distance change among reliable parts. The extensive empirical evaluations on three benchmark datasets: OTB2015, TempleColor128 and VOT2015 demonstrate that the proposed method performs superiorly against several state-of-the-art trackers in terms of tracking accuracy, speed and robustness.
Deep Graph Translation
Venue: arXiv cs.LG 2018
Year: 2018

Inspired by the tremendous success of deep generative models on generating continuous data like image and audio, in the most recent year, few deep graph generative models have been proposed to generate discrete data such as graphs. They are typically unconditioned generative models which has no control on modes of the graphs being generated. Differently, in this paper, we are interested in a new problem named \emph{Deep Graph Translation}: given an input graph, we want to infer a target graph based on their underlying (both global and local) translation mapping. Graph translation could be highly desirable in many applications such as disaster management and rare event forecasting, where the rare and abnormal graph patterns (e.g., traffic congestions and terrorism events) will be inferred prior to their occurrence even without historical data on the abnormal patterns for this graph (e.g., a road network or human contact network). To achieve this, we propose a novel Graph-Translation-Generative Adversarial Networks (GT-GAN) which will generate a graph translator from input to target graphs. GT-GAN consists of a graph translator where we propose new graph convolution and deconvolution layers to learn the global and local translation mapping. A new conditional graph discriminator has also been proposed to classify target graphs by conditioning on input graphs. Extensive experiments on multiple synthetic and real-world datasets demonstrate the effectiveness and scalability of the proposed GT-GAN.
Algorithms for Anti-Powers in Strings
Venue: arXiv cs.DS 2018
Year: 2018

A string $S[1,n]$ is a power (or tandem repeat) of order $k$ and period $n/k$ if it can decomposed into $k$ consecutive equal-length blocks of letters. Powers and periods are fundamental to string processing, and algorithms for their efficient computation have wide application and are heavily studied. Recently, Fici et al. (Proc. ICALP 2016) defined an {\em anti-power} of order $k$ to be a string composed of $k$ pairwise-distinct blocks of the same length ($n/k$, called {\em anti-period}). Anti-powers are a natural converse to powers, and are objects of combinatorial interest in their own right. In this paper we initiate the algorithmic study of anti-powers. Given a string $S$, we describe an optimal algorithm for locating all substrings of $S$ that are anti-powers of a specified order. The optimality of the algorithm follows form a combinatorial lemma that provides a lower bound on the number of distinct anti-powers of a given order: we prove that a string of length $n$ can contain $Θ(n^2/k)$ distinct anti-powers of order $k$.
A Novel High-Rate Polar-Staircase Coding Scheme
Venue: arXiv cs.IT 2018
Year: 2018

The long-haul communication systems can offer ultra high-speed data transfer rates but suffer from burst errors. The high-rate and high-performance staircase codes provide an efficient way for long-haul transmission. The staircase coding scheme is a concatenation structure, which provides the opportunity to improve the performance of high-rate polar codes. At the same time, the polar codes make the staircase structure more reliable. Thus, a high-rate polar-staircase coding scheme is proposed, where the systematic polar codes are applied as the component codes. The soft cancellation decoding of the systematic polar codes is proposed as a basic ingredient. The encoding of the polar-staircase codes is designed with the help of density evolution, where the unreliable parts of the polar codes are enhanced. The corresponding decoding is proposed with low complexity, and is also optimized for burst error channels. With the well designed encoding and decoding algorithms, the polar-staircase codes perform well on both AWGN channels and burst error channels.
Certified Ordered Completion
Venue: arXiv cs.LO 2018
Year: 2018

On the one hand, ordered completion is a fundamental technique in equational theorem proving that is employed by automated tools. On the other hand, their complexity makes such tools inherently error prone. As a remedy to this situation we give an Isabelle/HOL formalization of ordered rewriting and completion that comes with a formally verified certifier for ordered completion proofs. By validating generated proof certificates, our certifier increases the reliability of ordered completion tools.
Few self-involved agents among BC agents can lead to polarized local or global consensus
Venue: arXiv cs.MA 2018
Year: 2018

Social issues are generally discussed by highly-involved and less-involved people to build social norms defining what has to be thought and done about them. As self-involved agents share different attitude dynamics to other agents Wood, Pool et al, 1996, we study the emergence and evolution of norms through an individual-based model involving these two types of agents. The dynamics of self-involved agents is drawn from Huet and Deffuant, 2010, and the dynamics of others, from Deffuant et al, 2001. The attitude of an agent is represented as a segment on a continuous attitudinal space. Two agents are close if their attitude segments share sufficient overlap. Our agents discuss two different issues, one of which, called main issue, is more important for the self-involved agents than the other, called secondary issue. Self-involved agents are attracted on both issues if they are close on main issue, but shift away from their peer's opinion if they are only close on secondary issue. Differently, non-self-involved agents are attracted by other agents when they are close on both the main and secondary issues. We observe the emergence of various types of extreme minor clusters. In one or different groups of attitudes, they can lead to an already-built moderate norm or a norm polarized on secondary and/or main issues. They can also push disagreeing agents gathered in different groups to a global moderate consensus.
Snips Voice Platform: an embedded Spoken Language Understanding system for private-by-design voice interfaces
Venue: arXiv cs.CL 2018
Year: 2018

This paper presents the machine learning architecture of the Snips Voice Platform, a software solution to perform Spoken Language Understanding on microprocessors typical of IoT devices. The embedded inference is fast and accurate while enforcing privacy by design, as no personal user data is ever collected. Focusing on Automatic Speech Recognition and Natural Language Understanding, we detail our approach to training high-performance Machine Learning models that are small enough to run in real-time on small devices. Additionally, we describe a data generation procedure that provides sufficient, high-quality training data without compromising user privacy.
Cooperative access networks: Optimum fronthaul quantization in distributed Massive MIMO and cloud RAN
Venue: arXiv cs.IT 2018
Year: 2018

We consider cooperative radio access network architectures, especially distributed massive MIMO and Cloud RAN, considering their similarities and differences. We address in particular the major challenge posed to both by the implementation of a high capacity fronthaul network to link the distributed access points to the central processing unit, and consider the effect on uplink performance of quantization of received signals in order to limit fronthaul load. We use the Bussgang decomposition along with a new approach to MMSE estimation of both channel and data to provide the basis of our analysis.
Psychophysics, Gestalts and Games
Venue: arXiv cs.CV 2018
Year: 2018

Many psychophysical studies are dedicated to the evaluation of the human gestalt detection on dot or Gabor patterns, and to model its dependence on the pattern and background parameters. Nevertheless, even for these constrained percepts, psychophysics have not yet reached the challenging prediction stage, where human detection would be quantitatively predicted by a (generic) model. On the other hand, Computer Vision has attempted at defining automatic detection thresholds. This chapter sketches a procedure to confront these two methodologies inspired in gestaltism. Using a computational quantitative version of the non-accidentalness principle, we raise the possibility that the psychophysical and the (older) gestaltist setups, both applicable on dot or Gabor patterns, find a useful complement in a Turing test. In our perceptual Turing test, human performance is compared by the scientist to the detection result given by a computer. This confrontation permits to revive the abandoned method of gestaltic games. We sketch the elaboration of such a game, where the subjects of the experiment are confronted to an alignment detection algorithm, and are invited to draw examples that will fool it. We show that in that way a more precise definition of the alignment gestalt and of its computational formulation seems to emerge. Detection algorithms might also be relevant to more classic psychophysical setups, where they can again play the role of a Turing test. To a visual experiment where subjects were invited to detect alignments in Gabor patterns, we associated a single function measuring the alignment detectability in the form of a number of false alarms (NFA). The first results indicate that the values of the NFA, as a function of all simulation parameters, are highly correlated to the human detection. This fact, that we intend to support by further experiments , might end up confirming that human alignment detection is the result of a single mechanism.
SLSDeep: Skin Lesion Segmentation Based on Dilated Residual and Pyramid Pooling Networks
Venue: arXiv cs.CV 2018
Year: 2018

Skin lesion segmentation (SLS) in dermoscopic images is a crucial task for automated diagnosis of melanoma. In this paper, we present a robust deep learning SLS model, so-called SLSDeep, which is represented as an encoder-decoder network. The encoder network is constructed by dilated residual layers, in turn, a pyramid pooling network followed by three convolution layers is used for the decoder. Unlike the traditional methods employing a cross-entropy loss, we investigated a loss function by combining both Negative Log Likelihood (NLL) and End Point Error (EPE) to accurately segment the melanoma regions with sharp boundaries. The robustness of the proposed model was evaluated on two public databases: ISBI 2016 and 2017 for skin lesion analysis towards melanoma detection challenge. The proposed model outperforms the state-of-the-art methods in terms of segmentation accuracy. Moreover, it is capable to segment more than $100$ images of size 384x384 per second on a recent GPU.
Detecting Influence Campaigns in Social Networks Using the Ising Model
Venue: arXiv cs.SI 2018
Year: 2018

We consider the problem of identifying coordinated influence campaigns conducted by automated agents or bots in a social network. We study several different Twitter datasets which contain such campaigns and find that the bots exhibit heterophily - they interact more with humans than with each other. We use this observation to develop a probability model for the network structure and bot labels based on the Ising model from statistical physics. We present a method to find the maximum likelihood assignment of bot labels by solving a minimum cut problem. Our algorithm allows for the simultaneous detection of multiple bots that are potentially engaging in a coordinated influence campaign, in contrast to other methods that identify bots one at a time. We find that our algorithm is able to more accurately find bots than existing methods when compared to a human labeled ground truth. We also look at the content posted by the bots we identify and find that they seem to have a coordinated agenda.
Training verified learners with learned verifiers
Venue: arXiv cs.LG 2018
Year: 2018

This paper proposes a new algorithmic framework, predictor-verifier training, to train neural networks that are verifiable, i.e., networks that provably satisfy some desired input-output properties. The key idea is to simultaneously train two networks: a predictor network that performs the task at hand,e.g., predicting labels given inputs, and a verifier network that computes a bound on how well the predictor satisfies the properties being verified. Both networks can be trained simultaneously to optimize a weighted combination of the standard data-fitting loss and a term that bounds the maximum violation of the property. Experiments show that not only is the predictor-verifier architecture able to train networks to achieve state of the art verified robustness to adversarial examples with much shorter training times (outperforming previous algorithms on small datasets like MNIST and SVHN), but it can also be scaled to produce the first known (to the best of our knowledge) verifiably robust networks for CIFAR-10.
Extended Formulations for Radial Cones
Venue: arXiv cs.DM 2018
Year: 2018

This paper studies extended formulations for radial cones at vertices of polyhedra, where the radial cone of a polyhedron $ P $ at a vertex $ v \in P $ is the polyhedron defined by the constraints of $ P $ that are active at $ v $. Given an extended formulation for $ P $, it is easy to obtain an extended formulation of comparable size for each its radial cones. On the contrary, it is possible that radial cones of $ P $ admit much smaller extended formulations than $ P $ itself. A prominent example of this type is the perfect-matching polytope, which cannot be described by subexponential-size extended formulations (Rothvoß 2014). However, Ventura & Eisenbrand (2003) showed that its radial cones can be described by polynomial-size extended formulations. Moreover, they generalized their construction to $ V $-join polyhedra. In the same paper, the authors asked whether the same holds for the odd-cut polyhedron, the blocker of the $ V $-join polyhedron. We answer this question negatively. Precisely, we show that radial cones of odd-cut polyhedra cannot be described by subexponential-size extended formulations. To obtain our result, for a polyhedron $ P $ of blocking type, we establish a general relationship between its radial cones and certain faces of the blocker of $ P $.
Zero-Shot Dual Machine Translation
Venue: arXiv cs.CL 2018
Year: 2018

Neural Machine Translation (NMT) systems rely on large amounts of parallel data. This is a major challenge for low-resource languages. Building on recent work on unsupervised and semi-supervised methods, we present an approach that combines zero-shot and dual learning. The latter relies on reinforcement learning, to exploit the duality of the machine translation task, and requires only monolingual data for the target language pair. Experiments show that a zero-shot dual system, trained on English-French and English-Spanish, outperforms by large margins a standard NMT system in zero-shot translation performance on Spanish-French (both directions). The zero-shot dual method approaches the performance, within 2.2 BLEU points, of a comparable supervised setting. Our method can obtain improvements also on the setting where a small amount of parallel data for the zero-shot language pair is available. Adding Russian, to extend our experiments to jointly modeling 6 zero-shot translation directions, all directions improve between 4 and 15 BLEU points, again, reaching performance near that of the supervised setting.