OpenRaiser/Intern-Atlas huggingface dataset:
Stochastic Wasserstein Barycenters
Venue: arXiv cs.LG 2018
Year: 2018

We present a stochastic algorithm to compute the barycenter of a set of probability distributions under the Wasserstein metric from optimal transport. Unlike previous approaches, our method extends to continuous input distributions and allows the support of the barycenter to be adjusted in each iteration. We tackle the problem without regularization, allowing us to recover a sharp output whose support is contained within the support of the true barycenter. We give examples where our algorithm recovers a more meaningful barycenter than previous work. Our method is versatile and can be extended to applications such as generating super samples from a given distribution and recovering blue noise approximations.
Cross-topic Argument Mining from Heterogeneous Sources Using Attention-based Neural Networks
Venue: arXiv cs.CL 2018
Year: 2018

Argument mining is a core technology for automating argument search in large document collections. Despite its usefulness for this task, most current approaches to argument mining are designed for use only with specific text types and fall short when applied to heterogeneous texts. In this paper, we propose a new sentential annotation scheme that is reliably applicable by crowd workers to arbitrary Web texts. We source annotations for over 25,000 instances covering eight controversial topics. The results of cross-topic experiments show that our attention-based neural network generalizes best to unseen topics and outperforms vanilla BiLSTM models by 6% in accuracy and 11% in F-score.
A Faster FPTAS for #Knapsack
Venue: arXiv cs.DS 2018
Year: 2018

Given a set $W = \{w_1,\ldots, w_n\}$ of non-negative integer weights and an integer $C$, the #Knapsack problem asks to count the number of distinct subsets of $W$ whose total weight is at most $C$. In the more general integer version of the problem, the subsets are multisets. That is, we are also given a set $ \{u_1,\ldots, u_n\}$ and we are allowed to take up to $u_i$ items of weight $w_i$. We present a deterministic FPTAS for #Knapsack running in $O(n^{2.5}\varepsilon^{-1.5}\log(n \varepsilon^{-1})\log (n \varepsilon))$ time. The previous best deterministic algorithm [FOCS 2011] runs in $O(n^3 \varepsilon^{-1} \log(n\varepsilon^{-1}))$ time (see also [ESA 2014] for a logarithmic factor improvement). The previous best randomized algorithm [STOC 2003] runs in $O(n^{2.5} \sqrt{\log (n\varepsilon^{-1}) } + \varepsilon^{-2} n^2 )$ time. Therefore, in the natural setting of constant $\varepsilon$, we close the gap between the $\tilde O(n^{2.5})$ randomized algorithm and the $\tilde O(n^3)$ deterministic algorithm. For the integer version with $U = \max_i \{u_i\}$, we present a deterministic FPTAS running in $O(n^{2.5}\varepsilon^{-1.5}\log(n\varepsilon^{-1} \log U)\log (n \varepsilon) \log^2 U)$ time. The previous best deterministic algorithm [APPROX 2016] runs in $O(n^3\varepsilon^{-1}\log(n \varepsilon^{-1} \log U) \log^2 U)$ time.
SpaRTA - Tracking across occlusions via global partitioning of 3D clouds of points
Venue: arXiv cs.CV 2018
Year: 2018

Any 3D tracking algorithm has to deal with occlusions: multiple targets get so close to each other that the loss of their identities becomes likely. In the best case scenario, trajectories are interrupted, thus curbing the completeness of the data-set; in the worse case scenario, identity switches arise, potentially affecting in severe ways the very quality of the data. Here, we present a novel tracking method that addresses the problem of occlusions within large groups of featureless objects by means of three steps: i) it represents each target as a cloud of points in 3D; ii) once a 3D cluster corresponding to an occlusion occurs, it defines a partitioning problem by introducing a cost function that uses both attractive and repulsive spatio-temporal proximity links; iii) it minimizes the cost function through a semi-definite optimization technique specifically designed to cope with link frustration. The algorithm is independent of the specific experimental method used to collect the data. By performing tests on public data-sets, we show that the new algorithm produces a significant improvement over the state-of-the-art tracking methods, both by reducing the number of identity switches and by increasing the accuracy of the actual positions of the targets in real space.
Coding Block-Level Perceptual Video Coding for 4:4:4 Data in HEVC
Venue: arXiv cs.MM 2018
Year: 2018

There is an increasing consumer demand for high bit-depth 4:4:4 HD video data playback due to its superior perceptual visual quality compared with standard 8-bit subsampled 4:2:0 video data. Due to vast file sizes and associated bitrates, it is desirable to compress raw high bit-depth 4:4:4 HD video sequences as much as possible without incurring a discernible decrease in visual quality. In this paper, we propose a Coding Block (CB)-level perceptual video coding technique for HEVC named Full Color Perceptual Quantization (FCPQ). FCPQ is designed to adjust the Quantization Parameter (QP) at the CB level (i.e., the luma CB and the chroma Cb and Cr CBs) according to the variances of pixel data in each CB. FCPQ is based on the default perceptual quantization method in HEVC called AdaptiveQP. AdaptiveQP adjusts the QP of an entire CU based only on the spatial activity of the constituent luma CB. As demonstrated in this paper, by not accounting for the spatial activity of the constituent chroma CBs, as is the case with AdaptiveQP, coding performance can be significantly affected; this is because the variance of pixel data in a luma CB is notably different from the variances of pixel data in chroma Cb and Cr CBs. FCPQ, therefore, addresses this problem. In terms of coding performance, FCPQ achieves BD-Rate improvements of up to 39.5% (Y), 16% (Cb) and 29.9% (Cr) compared with AdaptiveQP.
An Image Processing based Object Counting Approach for Machine Vision Application
Venue: arXiv cs.CV 2018
Year: 2018

Machine vision applications are low cost and high precision measurement systems which are frequently used in production lines. With these systems that provide contactless control and measurement, production facilities are able to reach high production numbers without errors. Machine vision operations such as product counting, error control, dimension measurement can be performed through a camera. In this paper, a machine vision application is proposed, which can perform object-independent product counting. The proposed approach is based on Otsu thresholding and Hough transformation and performs automatic counting independently of product type and color. Basically one camera is used in the system. Through this camera, an image of the products passing through a conveyor is taken and various image processing algorithms are applied to these images. In this approach using images obtained from a real experimental setup, a real-time machine vision application was installed. As a result of the experimental studies performed, it has been determined that the proposed approach gives fast, accurate and reliable results.
Instance-based Inductive Deep Transfer Learning by Cross-Dataset Querying with Locality Sensitive Hashing
Venue: arXiv cs.CL 2018
Year: 2018

Supervised learning models are typically trained on a single dataset and the performance of these models rely heavily on the size of the dataset, i.e., amount of data available with the ground truth. Learning algorithms try to generalize solely based on the data that is presented with during the training. In this work, we propose an inductive transfer learning method that can augment learning models by infusing similar instances from different learning tasks in the Natural Language Processing (NLP) domain. We propose to use instance representations from a source dataset, \textit{without inheriting anything} from the source learning model. Representations of the instances of \textit{source} \& \textit{target} datasets are learned, retrieval of relevant source instances is performed using soft-attention mechanism and \textit{locality sensitive hashing}, and then, augmented into the model during training on the target dataset. Our approach simultaneously exploits the local \textit{instance level information} as well as the macro statistical viewpoint of the dataset. Using this approach we have shown significant improvements for three major news classification datasets over the baseline. Experimental evaluations also show that the proposed approach reduces dependency on labeled data by a significant margin for comparable performance. With our proposed cross dataset learning procedure we show that one can achieve competitive/better performance than learning from a single dataset.
Innovation Initiatives in Large Software Companies: A Systematic Mapping Study
Venue: arXiv cs.SE 2018
Year: 2018

To keep the competitive advantage and adapt to changes in the market and technology, companies need to innovate in an organised, purposeful and systematic manner. However, due to their size and complexity, large companies tend to focus on maintaining their business, which can potentially lower their agility to innovate. This study aims to provide an overview of the current research on innovation initiatives and to identify the challenges of implementing the initiatives in the context of large software companies. The investigation was performed using a systematic mapping approach of published literature on corporate innovation and entrepreneurship. Then it was complemented with interviews with four experts with rich industry experience. Our study results suggest that, there is a lack of high quality empirical studies on innovation initiative in the context of large software companies. A total of 7 studies are conducted in such context, which reported 5 types of initiatives: intrapreneurship, bootlegging, internal venture, spin-off and crowdsourcing. Our study offers three contributions. First, this paper represents the map of existing literature on innovation initiatives inside large companies. The second contribution is to provide an innovation initiative tree. The third contribution is to identify key challenges faced by each initiative in large software companies. At the strategic and tactical levels, there is no difference between large software companies and other companies. At the operational level, large software companies are highly influenced by the advancement of Internet technology. Large software companies use open innovation paradigm as part of their innovation initiatives. We envision a future work is to further empirically evaluate the innovation initiative tree in large software companies, which involves more practitioners from different companies.
Abductive reasoning as the basis to reproduce expert criteria in ECG Atrial Fibrillation identification
Venue: arXiv cs.AI 2018
Year: 2018

Objective: This work aims at providing a new method for the automatic detection of atrial fibrillation, other arrhythmia and noise on short single lead ECG signals, emphasizing the importance of the interpretability of the classification results. Approach: A morphological and rhythm description of the cardiac behavior is obtained by a knowledge-based interpretation of the signal using the \textit{Construe} abductive framework. Then, a set of meaningful features are extracted for each individual heartbeat and as a summary of the full record. The feature distributions were used to elucidate the expert criteria underlying the labeling of the 2017 Physionet/CinC Challenge dataset, enabling a manual partial relabeling to improve the consistency of the classification rules. Finally, state-of-the-art machine learning methods are combined to provide an answer on the basis of the feature values. Main results: The proposal tied for the first place in the official stage of the Challenge, with a combined $F_1$ score of 0.83, and was even improved in the follow-up stage to 0.85 with a significant simplification of the model. Significance: This approach demonstrates the potential of \textit{Construe} to provide robust and valuable descriptions of temporal data even with significant amounts of noise and artifacts. Also, we discuss the importance of a consistent classification criteria in manually labeled training datasets, and the fundamental advantages of knowledge-based approaches to formalize and validate that criteria.
Computational synthesis of large deformation compliant mechanisms undergoing self and mutual contact
Venue: arXiv cs.CE 2018
Year: 2018

Topologies of large deformation Contact-aided Compliant Mechanisms (CCMs), with self and mutual contact, exemplified via path generation applications, are designed using the continuum synthesis approach. Design domains are parameterized using honeycomb tessellation. Assignment of material to each cell, and generation of rigid contact surfaces, are accomplished via suitably sizing and positioning negative circular masks. To facilitate contact analysis, boundary smoothing is implemented. Mean value coordinates are employed to compute shape functions, as many regular hexagonal cells get degenerated into irregular, concave polygons as a consequence of boundary smoothing. Both, geometric and material nonlinearities are considered in the finite element analysis. The augmented Lagrange multiplier method in association with an active set strategy is employed to incorporate both self and mutual contact. CCMs are evolved using the stochastic hill climber search. Synthesized contact-aided compliant continua trace paths with single and importantly, multiple kinks and experience multiple contact interactions pertaining to both self and mutual contact modes.
Viewport Adaptation-Based Immersive Video Streaming: Perceptual Modeling and Applications
Venue: arXiv cs.MM 2018
Year: 2018

Immersive video offers the freedom to navigate inside virtualized environment. Instead of streaming the bulky immersive videos entirely, a viewport (also referred to as field of view, FoV) adaptive streaming is preferred. We often stream the high-quality content within current viewport, while reducing the quality of representation elsewhere to save the network bandwidth consumption. Consider that we could refine the quality when focusing on a new FoV, in this paper, we model the perceptual impact of the quality variations (through adapting the quantization stepsize and spatial resolution) with respect to the refinement duration, and yield a product of two closed-form exponential functions that well explain the joint quantization and resolution induced quality impact. Analytical model is cross-validated using another set of data, where both Pearson and Spearman's rank correlation coefficients are close to 0.98. Our work is devised to optimize the adaptive FoV streaming of the immersive video under limited network resource. Numerical results show that our proposed model significantly improves the quality of experience of users, with about 9.36\% BD-Rate (Bjontegaard Delta Rate) improvement on average as compared to other representative methods, particularly under the limited bandwidth.
Variance-based Gradient Compression for Efficient Distributed Deep Learning
Venue: arXiv cs.LG 2018
Year: 2018

Due to the substantial computational cost, training state-of-the-art deep neural networks for large-scale datasets often requires distributed training using multiple computation workers. However, by nature, workers need to frequently communicate gradients, causing severe bottlenecks, especially on lower bandwidth connections. A few methods have been proposed to compress gradient for efficient communication, but they either suffer a low compression ratio or significantly harm the resulting model accuracy, particularly when applied to convolutional neural networks. To address these issues, we propose a method to reduce the communication overhead of distributed deep learning. Our key observation is that gradient updates can be delayed until an unambiguous (high amplitude, low variance) gradient has been calculated. We also present an efficient algorithm to compute the variance with negligible additional cost. We experimentally show that our method can achieve very high compression ratio while maintaining the result model accuracy. We also analyze the efficiency using computation and communication cost models and provide the evidence that this method enables distributed deep learning for many scenarios with commodity environments.
Gradient descent with identity initialization efficiently learns positive definite linear transformations by deep residual networks
Venue: arXiv cs.LG 2018
Year: 2018

We analyze algorithms for approximating a function $f(x) = Φx$ mapping $\Re^d$ to $\Re^d$ using deep linear neural networks, i.e. that learn a function $h$ parameterized by matrices $Θ_1,...,Θ_L$ and defined by $h(x) = Θ_L Θ_{L-1} ... Θ_1 x$. We focus on algorithms that learn through gradient descent on the population quadratic loss in the case that the distribution over the inputs is isotropic. We provide polynomial bounds on the number of iterations for gradient descent to approximate the least squares matrix $Φ$, in the case where the initial hypothesis $Θ_1 = ... = Θ_L = I$ has excess loss bounded by a small enough constant. On the other hand, we show that gradient descent fails to converge for $Φ$ whose distance from the identity is a larger constant, and we show that some forms of regularization toward the identity in each layer do not help. If $Φ$ is symmetric positive definite, we show that an algorithm that initializes $Θ_i = I$ learns an $ε$-approximation of $f$ using a number of updates polynomial in $L$, the condition number of $Φ$, and $\log(d/ε)$. In contrast, we show that if the least squares matrix $Φ$ is symmetric and has a negative eigenvalue, then all members of a class of algorithms that perform gradient descent with identity initialization, and optionally regularize toward the identity in each layer, fail to converge. We analyze an algorithm for the case that $Φ$ satisfies $u^{\top} Φu > 0$ for all $u$, but may not be symmetric. This algorithm uses two regularizers: one that maintains the invariant $u^{\top} Θ_L Θ_{L-1} ... Θ_1 u > 0$ for all $u$, and another that "balances" $Θ_1, ..., Θ_L$ so that they have the same singular values.
Real-Time 3D Shape of Micro-Details
Venue: arXiv cs.CV 2018
Year: 2018

Motivated by the growing demand for interactive environments, we propose an accurate real-time 3D shape reconstruction technique. To provide a reliable 3D reconstruction which is still a challenging task when dealing with real-world applications, we integrate several components including (i) Photometric Stereo (PS), (ii) perspective Cook-Torrance reflectance model that enables PS to deal with a broad range of possible real-world object reflections, (iii) realistic lightening situation, (iv) a Recurrent Optimization Network (RON) and finally (v) heuristic Dijkstra Gaussian Mean Curvature (DGMC) initialization approach. We demonstrate the potential benefits of our hybrid model by providing 3D shape with highly-detailed information from micro-prints for the first time. All real-world images are taken by a mobile phone camera under a simple setup as a consumer-level equipment. In addition, complementary synthetic experiments confirm the beneficial properties of our novel method and its superiority over the state-of-the-art approaches.
A generic characterization of Pol(C)
Venue: arXiv cs.FL 2018
Year: 2018

We investigate the polynomial closure operation (C -> Pol(C)) defined on classes of regular languages. We present an interesting and useful connection relating the separation problem for the class C and the membership problem for it polynomial closure Pol(C). This connection is formulated as an algebraic characterization of Pol(C) which holds when C is an arbitrary \pvari of regular languages and whose statement is parameterized by C-separation. Its main application is an effective reduction from Pol(C)-membership to C-separation. Thus, as soon as one designs a C-separation algorithm, this yields "for free" a membership algorithm for the more complex class Pol(C).
Attack on the Edon-K Key Encapsulation Mechanism
Venue: arXiv cs.CR 2018
Year: 2018

The key encapsulation mechanism Edon-K was proposed in response to the call for post-quantum cryptography standardization issued by the National Institute of Standards and Technologies (NIST). This scheme is inspired by the McEliece scheme but uses another family of codes defined over $\mathbb{F}_{2^{128}}$ instead of $\mathbb{F}_2$ and is not based on the Hamming metric. It allows significantly shorter public keys than the McEliece scheme. In this paper, we give a polynomial time algorithm that recovers the encapsulated secret. This attack makes the scheme insecure for the intended use. We obtain this result by observing that recovering the error in the McEliece scheme corresponding to Edon-K can be viewed as a decoding problem for the rank-metric. We show that the code used in Edon-K is in fact a super-code of a Low Rank Parity Check (LRPC) code of very small rank (1 or 2). A suitable parity-check matrix for the super-code of such low rank can be easily derived from for the public key. We then use this parity-check matrix in a decoding algorithm that was devised for LRPC codes to recover the error. Finally we explain how we decapsulate the secret once we have found the error.
Building a Word Segmenter for Sanskrit Overnight
Venue: arXiv cs.CL 2018
Year: 2018

There is an abundance of digitised texts available in Sanskrit. However, the word segmentation task in such texts are challenging due to the issue of 'Sandhi'. In Sandhi, words in a sentence often fuse together to form a single chunk of text, where the word delimiter vanishes and sounds at the word boundaries undergo transformations, which is also reflected in the written text. Here, we propose an approach that uses a deep sequence to sequence (seq2seq) model that takes only the sandhied string as the input and predicts the unsandhied string. The state of the art models are linguistically involved and have external dependencies for the lexical and morphological analysis of the input. Our model can be trained "overnight" and be used for production. In spite of the knowledge lean approach, our system preforms better than the current state of the art by gaining a percentage increase of 16.79 % than the current state of the art.
Randomness of formal languages via automatic martingales
Venue: arXiv cs.FL 2018
Year: 2018

We define a notion of randomness for individual and collections of formal languages based on automatic martingales acting on sequences of words from some underlying domain. An automatic martingale bets if the incoming word belongs to the target language or not. Then randomness of both single languages and collections of languages is defined as a failure of automatic martingale to gain an unbounded capital by betting on the target language according to an incoming sequence of words, or a text. The randomness of formal languages turned out to be heavily dependent on the text. For very general classes of texts, any nonregular language happens to be random when considered individually. As for collections of languages, very general classes of texts permits nonrandomness of automatic families of languages only. On the other hand, an arbitrary computable language is be shown to be nonrandom under certain dynamic texts.
A Deep Q-Learning Agent for the L-Game with Variable Batch Training
Venue: arXiv cs.LG 2018
Year: 2018

We employ the Deep Q-Learning algorithm with Experience Replay to train an agent capable of achieving a high-level of play in the L-Game while self-learning from low-dimensional states. We also employ variable batch size for training in order to mitigate the loss of the rare reward signal and significantly accelerate training. Despite the large action space due to the number of possible moves, the low-dimensional state space and the rarity of rewards, which only come at the end of a game, DQL is successful in training an agent capable of strong play without the use of any search methods or domain knowledge.