OpenRaiser/Intern-Atlas huggingface dataset:
Enabling Reasoning with LegalRuleML
Venue: arXiv cs.AI 2018
Year: 2018

In order to automate verification process, regulatory rules written in natural language need to be translated into a format that machines can understand. However, none of the existing formalisms can fully represent the elements that appear in legal norms. For instance, most of these formalisms do not provide features to capture the behavior of deontic effects, which is an important aspect in automated compliance checking. This paper presents an approach for transforming legal norms represented using LegalRuleML to a variant of Modal Defeasible Logic (and vice versa) such that a legal statement represented using LegalRuleML can be transformed into a machine-readable format that can be understood and reasoned about depending upon the client's preferences.
Reliable Video Streaming over mmWave with Multi Connectivity and Network Coding
Venue: arXiv cs.NI 2018
Year: 2018

The next generation of multimedia applications will require the telecommunication networks to support a higher bitrate than today, in order to deliver virtual reality and ultra-high quality video content to the users. Most of the video content will be accessed from mobile devices, prompting the provision of very high data rates by next generation (5G) cellular networks. A possible enabler in this regard is communication at mmWave frequencies, given the vast amount of available spectrum that can be allocated to mobile users; however, the harsh propagation environment at such high frequencies makes it hard to provide a reliable service. This paper presents a reliable video streaming architecture for mmWave networks, based on multi connectivity and network coding, and evaluates its performance using a novel combination of the ns-3 mmWave module, real video traces and the network coding library Kodo. The results show that it is indeed possible to reliably stream video over cellular mmWave links, while the combination of multi connectivity and network coding can support high video quality with low latency.
Vision Based Railway Track Monitoring using Deep Learning
Venue: arXiv cs.CV 2018
Year: 2018

Computer vision based methods have been explored in the past for detection of railway track defects, but full automation has always been a challenge because both traditional image processing methods and deep learning classifiers trained from scratch fail to generalize that well to infinite novel scenarios seen in the real world, given limited amount of labeled data. Advancements have been made recently to make machine learning models utilize knowledge from a different but related domain. In this paper, we show that even though similar domain data is not available, transfer learning provides the model understanding of other real world objects and enables training production scale deep learning classifiers for uncontrolled real world data. Our models efficiently detect both track defects like sunkinks, loose ballast and railway assets like switches and signals. Models were validated with hours of track videos recorded in different continents resulting in different weather conditions, different ambience and surroundings. A track health index concept has also been proposed to monitor complete rail network.
GPI-based Secrecy Rate Maximization Beamforming Scheme for Wireless Transmission with AN-aided Directional Modulation
Venue: arXiv cs.IT 2018
Year: 2018

In a directional modulation network, a general power iterative (GPI) based beamforming scheme is proposed to maximize the secrecy rate (SR), where there are two optimization variables required to be optimized. The first one is the useful precoding vector of transmitting confidential messages to the desired user while the second one is the artificial noise (AN) projection matrix of forcing more AN to eavesdroppers. In such a secure network, the paramount problem is how to design or optimize the two optimization variables by different criteria. To maximize the SR (Max-SR), an alternatively iterative structure (AIS) is established between the AN projection matrix and the precoding vector for confidential messages. To choose a good initial value of iteration process of GPI, the proposed Max-SR method can readily double its convergence speed compared to the random choice of initial value. With only four iterations, it may rapidly converge to its rate ceil. From simulation results, it follows that the SR performance of the proposed AIS of GPI-based Max-SR is much better than those of conventional leakage-based and null-space projection methods in the medium and large signal-to-noise ratio (SNR) regions, and its achievable SR performance gain gradually increases as SNR increases.
An Iterative Closest Points Approach to Neural Generative Models
Venue: arXiv cs.LG 2018
Year: 2018

We present a simple way to learn a transformation that maps samples of one distribution to the samples of another distribution. Our algorithm comprises an iteration of 1) drawing samples from some simple distribution and transforming them using a neural network, 2) determining pairwise correspondences between the transformed samples and training data (or a minibatch), and 3) optimizing the weights of the neural network being trained to minimize the distances between the corresponding vectors. This can be considered as a variant of the Iterative Closest Points (ICP) algorithm, common in geometric computer vision, although ICP typically operates on sensor point clouds and linear transforms instead of random sample sets and neural nonlinear transforms. We demonstrate the algorithm on simple synthetic data and MNIST data. We furthermore demonstrate that the algorithm is capable of handling distributions with both continuous and discrete variables.
Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms
Venue: arXiv cs.DS 2018
Year: 2018

We present a simple randomized reduction from fully-dynamic integral matching algorithms to fully-dynamic "approximately-maximal" fractional matching algorithms. Applying this reduction to the recent fractional matching algorithm of Bhattacharya, Henzinger, and Nanongkai (SODA 2017), we obtain a novel result for the integral problem. Specifically, our main result is a randomized fully-dynamic $(2+ε)$-approximate integral matching algorithm with small polylog worst-case update time. For the $(2+ε)$-approximation regime only a \emph{fractional} fully-dynamic $(2+ε)$-matching algorithm with worst-case polylog update time was previously known, due to Bhattacharya et al.~(SODA 2017). Our algorithm is the first algorithm that maintains approximate matchings with worst-case update time better than polynomial, for any constant approximation ratio. As a consequence, we also obtain the first constant-approximate worst-case polylogarithmic update time maximum weight matching algorithm.
Towards the Adoption of Anti-spoofing Protocols
Venue: arXiv cs.CR 2018
Year: 2018

Email spoofing is a critical step of phishing, where the attacker impersonates someone the victim knows or trusts. In this paper, we conduct a qualitative study to explore why email spoofing is still possible after years of efforts to develop and deploy anti-spoofing protocols (e.g., SPF, DKIM, DMARC). First, we measure the protocol adoption by scanning 1 million Internet domains. We find the adoption rates are still low, especially for the new DMARC (3.1%). Second, to understand the reasons behind the low-adoption rate, we collect 4293 discussion threads (25.7K messages) from the Internet Engineering Task Force (IETF), a working group formed to develop and promote Internet standards. Our analysis shows key security and usability limitations in the protocol design, which makes it difficult to generate a positive "net effect" for a wide adoption. We validate our results by interviewing email administrators and discuss key implications for future anti-spoofing solutions.
A Probabilistic Characterization of Random and Malicious Communication Failures in Multi-Hop Networked Control
Venue: arXiv cs.SY 2018
Year: 2018

The control problem of a linear discrete-time dynamical system over a multi-hop network is explored. The network is assumed to be subject to packet drops by malicious and nonmalicious nodes as well as random and malicious data corruption issues. We utilize asymptotic tail-probability bounds of transmission failure ratios to characterize the links and paths of a network as well as the network itself. This probabilistic characterization allows us to take into account multiple failures that depend on each other, and coordinated malicious attacks on the network. We obtain a sufficient condition for the stability of the networked control system by utilizing our probabilistic approach. We then demonstrate the efficacy of our results in different scenarios concerning transmission failures on a multi-hop network.
Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Barrier for Worst-Case Time Bounds
Venue: arXiv cs.DS 2018
Year: 2018

Despite significant research efforts, the state-of-the-art algorithm for maintaining an approximate matching in fully dynamic graphs has a polynomial {worst-case} update time, even for very poor approximation guarantees. In a recent breakthrough, Bhattacharya, Henzinger and Nanongkai showed how to maintain a constant approximation to the minimum vertex cover, and thus also a constant-factor estimate of the maximum matching size, with polylogarithmic worst-case update time. Later (in SODA'17 Proc.) they improved the approximation factor all the way to $2+ε$. Nevertheless, the longstanding fundamental problem of {maintaining} an approximate matching with sub-polynomial worst-case time bounds remained open. We present a randomized algorithm for maintaining an {almost-maximal} matching in fully dynamic graphs with polylogarithmic worst-case update time. Such a matching provides $(2+ε)$-approximations for both the maximum matching and the minimum vertex cover, for any $ε> 0$. Our result was done independently of the $(2+ε)$-approximation result of Bhattacharya et al., so it provides the first $(2+ε)$-approximation for minimum vertex cover (together with Bhattacharya et al.'s result) and the first $(2+ε)$-approximation for maximum (integral) matching. The polylogarithmic worst-case update time of our algorithm holds deterministically, while the almost-maximality guarantee holds with high probability. This result not only settles the aforementioned problem on dynamic matchings, but also provides essentially the best possible approximation guarantee for dynamic vertex cover (assuming the unique games conjecture).
Optical Character Recognition (OCR) for Telugu: Database, Algorithm and Application
Venue: arXiv cs.CV 2018
Year: 2018

Telugu is a Dravidian language spoken by more than 80 million people worldwide. The optical character recognition (OCR) of the Telugu script has wide ranging applications including education, health-care, administration etc. The beautiful Telugu script however is very different from Germanic scripts like English and German. This makes the use of transfer learning of Germanic OCR solutions to Telugu a non-trivial task. To address the challenge of OCR for Telugu, we make three contributions in this work: (i) a database of Telugu characters, (ii) a deep learning based OCR algorithm, and (iii) a client server solution for the online deployment of the algorithm. For the benefit of the Telugu people and the research community, we will make our code freely available at https://gayamtrishal.github.io/OCR_Telugu.github.io/
Residual Gated Graph ConvNets
Venue: arXiv cs.LG 2018
Year: 2018

Graph-structured data such as social networks, functional brain networks, gene regulatory networks, communications networks have brought the interest in generalizing deep learning techniques to graph domains. In this paper, we are interested to design neural networks for graphs with variable length in order to solve learning problems such as vertex classification, graph classification, graph regression, and graph generative tasks. Most existing works have focused on recurrent neural networks (RNNs) to learn meaningful representations of graphs, and more recently new convolutional neural networks (ConvNets) have been introduced. In this work, we want to compare rigorously these two fundamental families of architectures to solve graph learning tasks. We review existing graph RNN and ConvNet architectures, and propose natural extension of LSTM and ConvNet to graphs with arbitrary size. Then, we design a set of analytically controlled experiments on two basic graph problems, i.e. subgraph matching and graph clustering, to test the different architectures. Numerical results show that the proposed graph ConvNets are 3-17% more accurate and 1.5-4x faster than graph RNNs. Graph ConvNets are also 36% more accurate than variational (non-learning) techniques. Finally, the most effective graph ConvNet architecture uses gated edges and residuality. Residuality plays an essential role to learn multi-layer architectures as they provide a 10% gain of performance.
A two-dimensional decomposition approach for matrix completion through gossip
Venue: arXiv cs.LG 2018
Year: 2018

Factoring a matrix into two low rank matrices is at the heart of many problems. The problem of matrix completion especially uses it to decompose a sparse matrix into two non sparse, low rank matrices which can then be used to predict unknown entries of the original matrix. We present a scalable and decentralized approach in which instead of learning two factors for the original input matrix, we decompose the original matrix into a grid blocks, each of whose factors can be individually learned just by communicating (gossiping) with neighboring blocks. This eliminates any need for a central server. We show that our algorithm performs well on both synthetic and real datasets.
Multichannel Speech Separation and Enhancement Using the Convolutive Transfer Function
Venue: arXiv cs.SD 2018
Year: 2018

This paper addresses the problem of speech separation and enhancement from multichannel convolutive and noisy mixtures, \emph{assuming known mixing filters}. We propose to perform the speech separation and enhancement task in the short-time Fourier transform domain, using the convolutive transfer function (CTF) approximation. Compared to time-domain filters, CTF has much less taps, consequently it has less near-common zeros among channels and less computational complexity. The work proposes three speech-source recovery methods, namely: i) the multichannel inverse filtering method, i.e. the multiple input/output inverse theorem (MINT), is exploited in the CTF domain, and for the multi-source case, ii) a beamforming-like multichannel inverse filtering method applying single source MINT and using power minimization, which is suitable whenever the source CTFs are not all known, and iii) a constrained Lasso method, where the sources are recovered by minimizing the $\ell_1$-norm to impose their spectral sparsity, with the constraint that the $\ell_2$-norm fitting cost, between the microphone signals and the mixing model involving the unknown source signals, is less than a tolerance. The noise can be reduced by setting a tolerance onto the noise power. Experiments under various acoustic conditions are carried out to evaluate the three proposed methods. The comparison between them as well as with the baseline methods is presented.
Posterior Sampling for Large Scale Reinforcement Learning
Venue: arXiv cs.LG 2018
Year: 2018

We propose a practical non-episodic PSRL algorithm that unlike recent state-of-the-art PSRL algorithms uses a deterministic, model-independent episode switching schedule. Our algorithm termed deterministic schedule PSRL (DS-PSRL) is efficient in terms of time, sample, and space complexity. We prove a Bayesian regret bound under mild assumptions. Our result is more generally applicable to multiple parameters and continuous state action problems. We compare our algorithm with state-of-the-art PSRL algorithms on standard discrete and continuous problems from the literature. Finally, we show how the assumptions of our algorithm satisfy a sensible parametrization for a large class of problems in sequential recommendations.
Compressed Indexing with Signature Grammars
Venue: arXiv cs.DS 2018
Year: 2018

The compressed indexing problem is to preprocess a string $S$ of length $n$ into a compressed representation that supports pattern matching queries. That is, given a string $P$ of length $m$ report all occurrences of $P$ in $S$. We present a data structure that supports pattern matching queries in $O(m + occ (\lg\lg n + \lg^εz))$ time using $O(z \lg(n / z))$ space where $z$ is the size of the LZ77 parse of $S$ and $ε> 0$ is an arbitrarily small constant, when the alphabet is small or $z = O(n^{1 - δ})$ for any constant $δ> 0$. We also present two data structures for the general case; one where the space is increased by $O(z\lg\lg z)$, and one where the query time changes from worst-case to expected. These results improve the previously best known solutions. Notably, this is the first data structure that decides if $P$ occurs in $S$ in $O(m)$ time using $O(z\lg(n/z))$ space. Our results are mainly obtained by a novel combination of a randomized grammar construction algorithm with well known techniques relating pattern matching to 2D-range reporting.
Traffic Allocation for Low-Latency Multi-Hop Networks with Buffers
Venue: arXiv cs.NI 2018
Year: 2018

For millimeter-wave (mm-wave) buffer-aided tandem networks consisting of relay nodes and multiple channels per hop, we consider two traffic allocation schemes, namely local allocation and global allocation, and investigate the end-to-end latency of a file transfer. We formulate the problem for generic multi-hop queuing systems and subsequently derive closed-form expressions of the end-to-end latency. We quantify the advantages of the global allocation scheme relative to its local allocation counterpart, and we conduct an asymptotic analysis on the performance gain when the number of channels in each hop increases to infinity. The traffic allocations and the analytical delay performance are validated through simulations. Furthermore, taking a specific two-hop mm-wave network as an example, we derive lower bounds on the average end-to-end latency, where Nakagami-$m$ fading is considered. Numerical results demonstrate that, compared to the local allocation scheme, the advantage of global allocation grows as the number of relay nodes increases, at the expense of higher complexity that linearly increases with the number of relay nodes. It is also demonstrated that a proper deployment of relay nodes in a linear mm-wave network plays an important role in reducing the average end-to-end latency, and the average latency decays as the mm-wave channels become more deterministic. These findings provide insights for designing multi-hop mm-wave networks with low end-to-end latency.
Mixture-of-tastes Models for Representing Users with Diverse Interests
Venue: arXiv cs.IR 2018
Year: 2018

Most existing recommendation approaches implicitly treat user tastes as unimodal, resulting in an average-of-tastes representations when multiple distinct interests are present. We show that appropriately modelling the multi-faceted nature of user tastes through a mixture-of-tastes model leads to large increases in recommendation quality. Our result holds both for deep sequence-based and traditional factorization models, and is robust to careful selection and tuning of baseline models. In sequence-based models, this improvement is achieved at a very modest cost in model complexity, making mixture-of-tastes models a straightforward improvement on existing baselines.
Unsupervised End-to-end Learning for Deformable Medical Image Registration
Venue: arXiv cs.CV 2018
Year: 2018

We propose a registration algorithm for 2D CT/MRI medical images with a new unsupervised end-to-end strategy using convolutional neural networks. The contributions of our algorithm are threefold: (1) We transplant traditional image registration algorithms to an end-to-end convolutional neural network framework, while maintaining the unsupervised nature of image registration problems. The image-to-image integrated framework can simultaneously learn both image features and transformation matrix for registration. (2) Training with additional data without any label can further improve the registration performance by approximately 10 %. (3) The registration speed is 100x faster than traditional methods. The proposed network is easy to implement and can be trained efficiently. Experiments demonstrate that our system achieves state-of-the-art results on 2D brain registration and achieves comparable results on 2D liver registration. It can be extended to register other organs beyond liver and brain such as kidney, lung, and heart.
Summarizing First-Person Videos from Third Persons' Points of Views
Venue: arXiv cs.CV 2018
Year: 2018

Video highlight or summarization is among interesting topics in computer vision, which benefits a variety of applications like viewing, searching, or storage. However, most existing studies rely on training data of third-person videos, which cannot easily generalize to highlight the first-person ones. With the goal of deriving an effective model to summarize first-person videos, we propose a novel deep neural network architecture for describing and discriminating vital spatiotemporal information across videos with different points of view. Our proposed model is realized in a semi-supervised setting, in which fully annotated third-person videos, unlabeled first-person videos, and a small number of annotated first-person ones are presented during training. In our experiments, qualitative and quantitative evaluations on both benchmarks and our collected first-person video datasets are presented.
Robust Subspace Learning: Robust PCA, Robust Subspace Tracking, and Robust Subspace Recovery
Venue: arXiv cs.IT 2018
Year: 2018

PCA is one of the most widely used dimension reduction techniques. A related easier problem is "subspace learning" or "subspace estimation". Given relatively clean data, both are easily solved via singular value decomposition (SVD). The problem of subspace learning or PCA in the presence of outliers is called robust subspace learning or robust PCA (RPCA). For long data sequences, if one tries to use a single lower dimensional subspace to represent the data, the required subspace dimension may end up being quite large. For such data, a better model is to assume that it lies in a low-dimensional subspace that can change over time, albeit gradually. The problem of tracking such data (and the subspaces) while being robust to outliers is called robust subspace tracking (RST). This article provides a magazine-style overview of the entire field of robust subspace learning and tracking. In particular solutions for three problems are discussed in detail: RPCA via sparse+low-rank matrix decomposition (S+LR), RST via S+LR, and "robust subspace recovery (RSR)". RSR assumes that an entire data vector is either an outlier or an inlier. The S+LR formulation instead assumes that outliers occur on only a few data vector indices and hence are well modeled as sparse corruptions.