OpenRaiser/Intern-Atlas huggingface dataset:
The Eighth Dialog System Technology Challenge
Venue: arXiv cs.CL 2019
Year: 2019

This paper introduces the Eighth Dialog System Technology Challenge. In line with recent challenges, the eighth edition focuses on applying end-to-end dialog technologies in a pragmatic way for multi-domain task-completion, noetic response selection, audio visual scene-aware dialog, and schema-guided dialog state tracking tasks. This paper describes the task definition, provided datasets, and evaluation set-up for each track. We also summarize the results of the submitted systems to highlight the overall trends of the state-of-the-art technologies for the tasks.
Gated Variational AutoEncoders: Incorporating Weak Supervision to Encourage Disentanglement
Venue: arXiv cs.CV 2019
Year: 2019

Variational AutoEncoders (VAEs) provide a means to generate representational latent embeddings. Previous research has highlighted the benefits of achieving representations that are disentangled, particularly for downstream tasks. However, there is some debate about how to encourage disentanglement with VAEs and evidence indicates that existing implementations of VAEs do not achieve disentanglement consistently. The evaluation of how well a VAE's latent space has been disentangled is often evaluated against our subjective expectations of which attributes should be disentangled for a given problem. Therefore, by definition, we already have domain knowledge of what should be achieved and yet we use unsupervised approaches to achieve it. We propose a weakly-supervised approach that incorporates any available domain knowledge into the training process to form a Gated-VAE. The process involves partitioning the representational embedding and gating backpropagation. All partitions are utilised on the forward pass but gradients are backpropagated through different partitions according to selected image/target pairings. The approach can be used to modify existing VAE models such as beta-VAE, InfoVAE and DIP-VAE-II. Experiments demonstrate that using gated backpropagation, latent factors are represented in their intended partition. The approach is applied to images of faces for the purpose of disentangling head-pose from facial expression. Quantitative metrics show that using Gated-VAE improves average disentanglement, completeness and informativeness, as compared with un-gated implementations. Qualitative assessment of latent traversals demonstrate its disentanglement of head-pose from expression, even when only weak/noisy supervision is available.
CASTER: Predicting Drug Interactions with Chemical Substructure Representation
Venue: arXiv cs.LG 2019
Year: 2019

Adverse drug-drug interactions (DDIs) remain a leading cause of morbidity and mortality. Identifying potential DDIs during the drug design process is critical for patients and society. Although several computational models have been proposed for DDI prediction, there are still limitations: (1) specialized design of drug representation for DDI predictions is lacking; (2) predictions are based on limited labelled data and do not generalize well to unseen drugs or DDIs; and (3) models are characterized by a large number of parameters, thus are hard to interpret. In this work, we develop a ChemicAl SubstrucTurE Representation (CASTER) framework that predicts DDIs given chemical structures of drugs.CASTER aims to mitigate these limitations via (1) a sequential pattern mining module rooted in the DDI mechanism to efficiently characterize functional sub-structures of drugs; (2) an auto-encoding module that leverages both labelled and unlabelled chemical structure data to improve predictive accuracy and generalizability; and (3) a dictionary learning module that explains the prediction via a small set of coefficients which measure the relevance of each input sub-structures to the DDI outcome. We evaluated CASTER on two real-world DDI datasets and showed that it performed better than state-of-the-art baselines and provided interpretable predictions.
Learning To Characterize Adversarial Subspaces
Venue: arXiv cs.CV 2019
Year: 2019

Deep Neural Networks (DNNs) are known to be vulnerable to the maliciously generated adversarial examples. To detect these adversarial examples, previous methods use artificially designed metrics to characterize the properties of \textit{adversarial subspaces} where adversarial examples lie. However, we find these methods are not working in practical attack detection scenarios. Because the artificially defined features are lack of robustness and show limitation in discriminative power to detect strong attacks. To solve this problem, we propose a novel adversarial detection method which identifies adversaries by adaptively learning reasonable metrics to characterize adversarial subspaces. As auxiliary context information, \textit{k} nearest neighbors are used to represent the surrounded subspace of the detected sample. We propose an innovative model called Neighbor Context Encoder (NCE) to learn from \textit{k} neighbors context and infer if the detected sample is normal or adversarial. We conduct thorough experiment on CIFAR-10, CIFAR-100 and ImageNet dataset. The results demonstrate that our approach surpasses all existing methods under three settings: \textit{attack-aware black-box detection}, \textit{attack-unaware black-box detection} and \textit{white-box detection}.
On the Relativized Alon Second Eigenvalue Conjecture V: Proof of the Relativized Alon Conjecture for Regular Base Graphs
Venue: arXiv cs.DM 2019
Year: 2019

This is the fifth in a series of articles devoted to showing that a typical covering map of large degree to a fixed, regular graph has its new adjacency eigenvalues within the bound conjectured by Alon for random regular graphs. In this article we use the results of Articles~III and IV in this series to prove that if the base graph is regular, then as the degree, $n$, of the covering map tends to infinity, some new adjacency eigenvalue has absolute value outside the Alon bound with probability bounded by $O(1/n)$. In addition, we give upper and lower bounds on this probability that are tight to within a multiplicative constant times the degree of the covering map. These bounds depend on two positive integers, the \emph{algebraic power} (which can also be $+\infty$) and the \emph{tangle power} of the model of random covering map. We conjecture that the algebraic power of the models we study is always $+\infty$, and in Article~VI we prove this when the base graph is regular and \emph{Ramanujan}. When the algebraic power of the model is $+\infty$, then the results in this article imply stronger results, such as (1) the upper and lower bounds mentioned above are matching to within a multiplicative constant, and (2) with probability smaller than any negative power of the degree, the some new eigenvalue fails to be within the Alon bound only if the covering map contains one of finitely many "tangles" as a subgraph (and this event has low probability).
Sample Drop Detection for Distant-speech Recognition with Asynchronous Devices Distributed in Space
Venue: arXiv cs.SD 2019
Year: 2019

In many applications of multi-microphone multi-device processing, the synchronization among different input channels can be affected by the lack of a common clock and isolated drops of samples. In this work, we address the issue of sample drop detection in the context of a conversational speech scenario, recorded by a set of microphones distributed in space. The goal is to design a neural-based model that given a short window in the time domain, detects whether one or more devices have been subjected to a sample drop event. The candidate time windows are selected from a set of large time intervals, possibly including a sample drop, and by using a preprocessing step. The latter is based on the application of normalized cross-correlation between signals acquired by different devices. The architecture of the neural network relies on a CNN-LSTM encoder, followed by multi-head attention. The experiments are conducted using both artificial and real data. Our proposed approach obtained F1 score of 88% on an evaluation set extracted from the CHiME-5 corpus. A comparable performance was found in a larger set of experiments conducted on a set of multi-channel artificial scenes.
Semi-Algebraic Proofs, IPS Lower Bounds and the $τ$-Conjecture: Can a Natural Number be Negative?
Venue: arXiv cs.CC 2019
Year: 2019

We introduce the binary value principle which is a simple subset-sum instance expressing that a natural number written in binary cannot be negative, relating it to central problems in proof and algebraic complexity. We prove conditional superpolynomial lower bounds on the Ideal Proof System (IPS) refutation size of this instance, based on a well-known hypothesis by Shub and Smale about the hardness of computing factorials, where IPS is the strong algebraic proof system introduced by Grochow and Pitassi (2018). Conversely, we show that short IPS refutations of this instance bridge the gap between sufficiently strong algebraic and semi-algebraic proof systems. Our results extend to full-fledged IPS the paradigm introduced in Forbes et al. (2016), whereby lower bounds against subsystems of IPS were obtained using restricted algebraic circuit lower bounds, and demonstrate that the binary value principle captures the advantage of semi-algebraic over algebraic reasoning, for sufficiently strong systems. Specifically, we show the following: (abstract continues in document.)
Penalized k-means algorithms for finding the correct number of clusters in a dataset
Venue: arXiv cs.LG 2019
Year: 2019

In many applications we want to find the number of clusters in a dataset. A common approach is to use the penalized k-means algorithm with an additive penalty term linear in the number of clusters. An open problem is estimating the value of the coefficient of the penalty term. Since estimating the value of the coefficient in a principled manner appears to be intractable for general clusters, we investigate "ideal clusters", i.e. identical spherical clusters with no overlaps and no outlier background noise. In this paper: (a) We derive, for the case of ideal clusters, rigorous bounds for the coefficient of the additive penalty. Unsurprisingly, the bounds depend on the correct number of clusters, which we want to find in the first place. We further show that additive penalty, even for this simplest case of ideal clusters, typically produces a weak and often ambiguous signature for the correct number of clusters. (b) As an alternative, we examine the k-means with multiplicative penalty, and show that this parameter-free formulation has a stronger, and less often ambiguous, signature for the correct number of clusters. We also empirically investigate certain types of deviations from ideal cluster assumption and show that combination of k-means with additive and multiplicative penalties can resolve ambiguous solutions.
Towards Personalized Dialog Policies for Conversational Skill Discovery
Venue: arXiv cs.CL 2019
Year: 2019

Many businesses and consumers are extending the capabilities of voice-based services such as Amazon Alexa, Google Home, Microsoft Cortana, and Apple Siri to create custom voice experiences (also known as skills). As the number of these experiences increases, a key problem is the discovery of skills that can be used to address a user's request. In this paper, we focus on conversational skill discovery and present a conversational agent which engages in a dialog with users to help them find the skills that fulfill their needs. To this end, we start with a rule-based agent and improve it by using reinforcement learning. In this way, we enable the agent to adapt to different user attributes and conversational styles as it interacts with users. We evaluate our approach in a real production setting by deploying the agent to interact with real users, and show the effectiveness of the conversational agent in helping users find the skills that serve their request.
Non-Orthogonal Multiple Access for Visible Light Communications with Ambient Light and User Mobility
Venue: arXiv cs.IT 2019
Year: 2019

The ever-increasing demand for high data-rate applications and the proliferation of connected devices pose several theoretical and technological challenges for the fifth generation (5G) networks and beyond. Among others, this includes the spectrum scarcity and massive connectivity of devices, particularly in the context of the Internet of Things (IoT) ecosystem. In this respect, visible light communication (VLC) has recently emerged as a potential solution for these challenges, particularly in scenarios relating to indoor communications. Additionally, non-orthogonal multiple access (NOMA) for VLC has been envisioned to address some of the key challenges in the next generation wireless networks. However, in realistic environments, it has been shown that VLC systems suffer from additive optical interference due to ambient light, and user-mobility which cause detrimental outages and overall degraded data rates. Motivated by this, in this work, we first derive the statistics of the incurred additive interference, and then analyze the rate of the considered NOMA-VLC channel. An analytical expression is subsequently derived for the rate of NOMA-VLC systems with ambient light and user-mobility, followed by the formulation of a power-allocation technique for the underlying scenario, which has been shown to outperform classical gain-ratio power allocation in terms of achievable rate. The obtained analytical results are corroborated with computer simulations for various realistic VLC scenarios of interest, which lead to useful insights of theoretical and practical interest. For example, it is shown that, in a NOMA-enabled VLC system, the maximum rate at which information can be transmitted over a static VLC communication channel with ambient light asymptotically converges to the Shannon Hartley capacity formula.
Large-Scale Parallel Matching of Social Network Profiles
Venue: arXiv cs.SI 2019
Year: 2019

A profile matching algorithm takes as input a user profile of one social network and returns, if existing, the profile of the same person in another social network. Such methods have immediate applications in Internet marketing, search, security, and a number of other domains, which is why this topic saw a recent surge in popularity. In this paper, we present a user identity resolution approach that uses minimal supervision and achieves a precision of 0.98 at a recall of 0.54. Furthermore, the method is computationally efficient and easily parallelizable. We show that the method can be used to match Facebook, the most popular social network globally, with VKontakte, the most popular social network among Russian-speaking users.
Applying Rational Envelope curves for skinning purposes
Venue: arXiv cs.GR 2019
Year: 2019

Special curves in the Minkowski space such as Minkowski Pythagorean hodographs play an important role in Computer Aided Geometric Design, and their usages have been thoroughly studied in the recent years. Also, several papers have been published which describe methods for interpolating Hermite data in R2,1 by MPH curves. Bizzarri et al.introduced the class of RE curves and presented an interpolation method for G1 Hermite data, where the resulting RE curve yields a rational boundary for the represented domain. We now propose a new application area for RE curves: skinning of a discrete set of input circles. We find the appropriate Hermite data to interpolate so that the obtained rational envelope curves touch each circle at previously defined points of contact. This way we overcome the problematic scenarios when the location of the touching points would not be appropriate for skinning purposes.
Inverse Reinforcement Learning with Missing Data
Venue: arXiv cs.LG 2019
Year: 2019

We consider the problem of recovering an expert's reward function with inverse reinforcement learning (IRL) when there are missing/incomplete state-action pairs or observations in the demonstrated trajectories. This issue of missing trajectory data or information occurs in many situations, e.g., GPS signals from vehicles moving on a road network are intermittent. In this paper, we propose a tractable approach to directly compute the log-likelihood of demonstrated trajectories with incomplete/missing data. Our algorithm is efficient in handling a large number of missing segments in the demonstrated trajectories, as it performs the training with incomplete data by solving a sequence of systems of linear equations, and the number of such systems to be solved does not depend on the number of missing segments. Empirical evaluation on a real-world dataset shows that our training algorithm outperforms other conventional techniques.
Memory-Efficient Performance Monitoring on Programmable Switches with Lean Algorithms
Venue: arXiv cs.DS 2019
Year: 2019

Network performance problems are notoriously difficult to diagnose. Prior profiling systems collect performance statistics by keeping information about each network flow, but maintaining per-flow state is not scalable on resource-constrained NIC and switch hardware. Instead, we propose sketch-based performance monitoring using memory that is sublinear in the number of flows. Existing sketches estimate flow monitoring metrics based on flow sizes. In contrast, performance monitoring typically requires combining information across pairs of packets, such as matching a data packet with its acknowledgment to compute a round-trip time. We define a new class of \emph{lean} algorithms that use memory sublinear in both the size of input data and the number of flows. We then introduce lean algorithms for a set of important statistics, such as identifying flows with high latency, loss, out-of-order, or retransmitted packets. We implement prototypes of our lean algorithms on a commodity programmable switch using the P4 language. Our experiments show that lean algorithms detect $\sim$82\% of top 100 problematic flows among real-world packet traces using just 40KB memory.
An "outside the box" solution for imbalanced data classification
Venue: arXiv cs.LG 2019
Year: 2019

A common problem of the real-world data sets is the class imbalance, which can significantly affect the classification abilities of classifiers. Numerous methods have been proposed to cope with this problem; however, even state-of-the-art methods offer a limited improvement (if any) for data sets with critically under-represented minority classes. For such problematic cases, an "outside the box" solution is required. Therefore, we propose a novel technique, called enrichment, which uses the information (observations) from the external data set(s). We present three approaches to implement enrichment technique: (1) selecting observations randomly, (2) iteratively choosing observations that improve the classification result, (3) adding observations that help the classifier to determine the border between classes better. We then thoroughly analyze developed solutions on ten real-world data sets to experimentally validate their usefulness. On average, our best approach improves the classification quality by 27\%, and in the best case, by outstanding 66\%. We also compare our technique with the universally applicable state-of-the-art methods. We find that our technique surpasses the existing methods performing, on average, 21\% better. The advantage is especially noticeable for the smallest data sets, for which existing methods failed, while our solutions achieved the best results. Additionally, our technique applies to both the multi-class and binary classification tasks. It can also be combined with other techniques dealing with the class imbalance problem.
IDEALEM: Statistical Similarity Based Data Reduction
Venue: arXiv cs.DB 2019
Year: 2019

Many applications such as scientific simulation, sensing, and power grid monitoring tend to generate massive amounts of data, which should be compressed first prior to storage and transmission. These data, mostly comprised of floating-point values, are known to be difficult to compress using lossless compression. A few compression methods based on lossy compression have been proposed to compress this seemingly incompressible data. Unfortunately, they are all designed to minimize the Euclidean distance between the original data and the decompressed data, which fundamentally limits compression performance. We recently proposed a new class of lossy compression based on statistical similarity, called IDEALEM, which was also provided as a software package. IDEALEM has demonstrated its performance by reducing data volume much more than state-of-the-art compression methods while preserving unique patterns of data. IDEALEM can operate in two different modes depending on the stationarity of input data. This paper presents compression performance analyses of these two modes, and investigates the difference between two transform techniques targeted for non-stationary data. This paper also discusses the data reconstruction quality of IDEALEM using spectral analysis and shows that important frequency components in application domain are well preserved. We expand the capability of IDEALEM by adding a new min/max check that facilitates preserving significant patterns lasting only for a brief duration which were previously hard to capture. This min/max check also accelerates the encoding process significantly. Experiments show IDEALEM preserves significant patterns in the original data with faster encoding time.
Contribution au Niveau de l'Approche Indirecte à Base de Transfert dans la Traduction Automatique
Venue: arXiv cs.CL 2019
Year: 2019

In this thesis, we address several important issues concerning the morphological analysis of Arabic language applied to textual data and machine translation. First, we provided an overview on machine translation, its history and its development, then we exposed human translation techniques for eventual inspiration in machine translation, and we exposed linguistic approaches and particularly indirect transfer approaches. Finally, we presented our contributions to the resolution of morphosyntactic problems in computer linguistics as multilingual information retrieval and machine translation. As a first contribution, we developed a morphological analyzer for Arabic, and we have exploited it in the bilingual information retrieval such as a computer application of multilingual documentary. Results validation showed a statistically significant performance. In a second contribution, we proposed a list of morphosyntactic transfer rules from English to Arabic for translation in three phases: analysis, transfer, generation. We focused on the transfer phase without semantic distortion for an abstraction of English in a sufficient subset of Arabic.