OpenRaiser/Intern-Atlas huggingface dataset:
Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars
Venue: arXiv cs.CC 2018
Year: 2018

Tree-adjoining grammars are a generalization of context-free grammars that are well suited to model human languages and are thus popular in computational linguistics. In the tree-adjoining grammar recognition problem, given a grammar $Γ$ and a string $s$ of length $n$, the task is to decide whether $s$ can be obtained from $Γ$. Rajasekaran and Yooseph's parser (JCSS'98) solves this problem in time $O(n^{2ω})$, where $ω< 2.373$ is the matrix multiplication exponent. The best algorithms avoiding fast matrix multiplication take time $O(n^6)$. The first evidence for hardness was given by Satta (J. Comp. Linguist.'94): For a more general parsing problem, any algorithm that avoids fast matrix multiplication and is significantly faster than $O(|Γ| n^6)$ in the case of $|Γ| = Θ(n^{12})$ would imply a breakthrough for Boolean matrix multiplication. Following an approach by Abboud et al. (FOCS'15) for context-free grammar recognition, in this paper we resolve many of the disadvantages of the previous lower bound. We show that, even on constant-size grammars, any improvement on Rajasekaran and Yooseph's parser would imply a breakthrough for the $k$-Clique problem. This establishes tree-adjoining grammar parsing as a practically relevant problem with the unusual running time of $n^{2ω}$, up to lower order factors.
Peak Effects in Stable Linear Difference Equations
Venue: arXiv cs.SY 2018
Year: 2018

We consider asymptotically stable scalar difference equations with unit-norm initial conditions. First, it is shown that the solution may happen to deviate far away from the equilibrium point at finite time instants prior to converging to zero. Second, for a number of root distributions and initial conditions, exact values of deviations or lower bounds are provided. Several specific difference equations known from the literature are also analyzed and estimates of deviations are proposed. Third, we consider difference equations with non-random noise (i.e., bounded-noise autoregression) and provide upper bounds on the solutions. Possible generalizations, e.g., to the vector case are discussed and directions for future research are outlined.
Realizability Interpretation and Normalization of Typed Call-by-Need $$λ$$-calculus With Control
Venue: arXiv cs.LO 2018
Year: 2018

We define a variant of realizability where realizers are pairs of a term and a substitution. This variant allows us to prove the normalization of a simply-typed call-by-need $$λ$-$calculus with control due to Ariola et al. Indeed, in such call-by-need calculus, substitutions have to be delayed until knowing if an argument is really needed. In a second step, we extend the proof to a call-by-need $$λ$$-calculus equipped with a type system equivalent to classical second-order predicate logic, representing one step towards proving the normalization of the call-by-need classical second-order arithmetic introduced by the second author to provide a proof-as-program interpretation of the axiom of dependent choice.
Online Scheduling of Spark Workloads with Mesos using Different Fair Allocation Algorithms
Venue: arXiv cs.PF 2018
Year: 2018

In the following, we present example illustrative and experimental results comparing fair schedulers allocating resources from multiple servers to distributed application frameworks. Resources are allocated so that at least one resource is exhausted in every server. Schedulers considered include DRF (DRFH) and Best-Fit DRF (BF-DRF), TSF, and PS-DSF. We also consider server selection under Randomized Round Robin (RRR) and based on their residual (unreserved) resources. In the following, we consider cases with frameworks of equal priority and without server-preference constraints. We first give typical results of a illustrative numerical study and then give typical results of a study involving Spark workloads on Mesos which we have modified and open-sourced to prototype different schedulers.
Protecting JPEG Images Against Adversarial Attacks
Venue: arXiv cs.CV 2018
Year: 2018

As deep neural networks (DNNs) have been integrated into critical systems, several methods to attack these systems have been developed. These adversarial attacks make imperceptible modifications to an image that fool DNN classifiers. We present an adaptive JPEG encoder which defends against many of these attacks. Experimentally, we show that our method produces images with high visual quality while greatly reducing the potency of state-of-the-art attacks. Our algorithm requires only a modest increase in encoding time, produces a compressed image which can be decompressed by an off-the-shelf JPEG decoder, and classified by an unmodified classifier
Energy Efficiency of Opportunistic Device-to-Device Relaying Under Lognormal Shadowing
Venue: arXiv cs.IT 2018
Year: 2018

Energy consumption is a major limitation of low power and mobile devices. Efficient transmission protocols are required to minimize an energy consumption of the mobile devices for ubiquitous connectivity in the next generation wireless networks. Opportunistic schemes select a single relay using the criteria of the best channel and achieve a near-optimal diversity performance in a cooperative wireless system. In this paper, we study the energy efficiency of the opportunistic schemes for device-to-device communication. In the opportunistic approach, an energy consumed by devices is minimized by selecting a single neighboring device as a relay using the criteria of minimum consumed energy in each transmission in the uplink of a wireless network. We derive analytical bounds and scaling laws on the expected energy consumption when the devices experience log-normal shadowing with respect to a base station considering both the transmission as well as circuit energy consumptions. We show that the protocol improves the energy efficiency of the network comparing to the direct transmission even if only a few devices are considered for relaying. We also demonstrate the effectiveness of the protocol by means of simulations in realistic scenarios of the wireless network.
Hashing with Mutual Information
Venue: arXiv cs.CV 2018
Year: 2018

Binary vector embeddings enable fast nearest neighbor retrieval in large databases of high-dimensional objects, and play an important role in many practical applications, such as image and video retrieval. We study the problem of learning binary vector embeddings under a supervised setting, also known as hashing. We propose a novel supervised hashing method based on optimizing an information-theoretic quantity: mutual information. We show that optimizing mutual information can reduce ambiguity in the induced neighborhood structure in the learned Hamming space, which is essential in obtaining high retrieval performance. To this end, we optimize mutual information in deep neural networks with minibatch stochastic gradient descent, with a formulation that maximally and efficiently utilizes available supervision. Experiments on four image retrieval benchmarks, including ImageNet, confirm the effectiveness of our method in learning high-quality binary embeddings for nearest neighbor retrieval.
Analyzing Business Process Anomalies Using Autoencoders
Venue: arXiv cs.AI 2018
Year: 2018

Businesses are naturally interested in detecting anomalies in their internal processes, because these can be indicators for fraud and inefficiencies. Within the domain of business intelligence, classic anomaly detection is not very frequently researched. In this paper, we propose a method, using autoencoders, for detecting and analyzing anomalies occurring in the execution of a business process. Our method does not rely on any prior knowledge about the process and can be trained on a noisy dataset already containing the anomalies. We demonstrate its effectiveness by evaluating it on 700 different datasets and testing its performance against three state-of-the-art anomaly detection methods. This paper is an extension of our previous work from 2016 [30]. Compared to the original publication we have further refined the approach in terms of performance and conducted an elaborate evaluation on more sophisticated datasets including real-life event logs from the Business Process Intelligence Challenges of 2012 and 2017. In our experiments our approach reached an F1 score of 0.87, whereas the best unaltered state-of-the-art approach reached an F1 score of 0.72. Furthermore, our approach can be used to analyze the detected anomalies in terms of which event within one execution of the process causes the anomaly.
Focal Loss Dense Detector for Vehicle Surveillance
Venue: arXiv cs.CV 2018
Year: 2018

Deep learning has been widely recognized as a promising approach in different computer vision applications. Specifically, one-stage object detector and two-stage object detector are regarded as the most important two groups of Convolutional Neural Network based object detection methods. One-stage object detector could usually outperform two-stage object detector in speed; However, it normally trails in detection accuracy, compared with two-stage object detectors. In this study, focal loss based RetinaNet, which works as one-stage object detector, is utilized to be able to well match the speed of regular one-stage detectors and also defeat two-stage detectors in accuracy, for vehicle detection. State-of-the-art performance result has been showed on the DETRAC vehicle dataset.
Stylize Aesthetic QR Code
Venue: arXiv cs.MM 2018
Year: 2018

With the continued proliferation of smart mobile devices, Quick Response (QR) code has become one of the most-used types of two-dimensional code in the world. Aiming at beautifying the visual-unpleasant appearance of QR codes, existing works have developed a series of techniques. However, these works still leave much to be desired, such as personalization, artistry, and robustness. To address these issues, in this paper, we propose a novel type of aesthetic QR codes, SEE (Stylize aEsthEtic) QR code, and a three-stage approach to automatically produce such robust style-oriented codes. Specifically, in the first stage, we propose a method to generate an optimized baseline aesthetic QR code, which reduces the visual contrast between the noise-like black/white modules and the blended image. In the second stage, to obtain art style QR code, we tailor an appropriate neural style transformation network to endow the baseline aesthetic QR code with artistic elements. In the third stage, we design an error-correction mechanism by balancing two competing terms, visual quality and readability, to ensure the performance robust. Extensive experiments demonstrate that SEE QR code has high quality in terms of both visual appearance and robustness, and also offers a greater variety of personalized choices to users.
The History Began from AlexNet: A Comprehensive Survey on Deep Learning Approaches
Venue: arXiv cs.CV 2018
Year: 2018

Deep learning has demonstrated tremendous success in variety of application domains in the past few years. This new field of machine learning has been growing rapidly and applied in most of the application domains with some new modalities of applications, which helps to open new opportunity. There are different methods have been proposed on different category of learning approaches, which includes supervised, semi-supervised and un-supervised learning. The experimental results show state-of-the-art performance of deep learning over traditional machine learning approaches in the field of Image Processing, Computer Vision, Speech Recognition, Machine Translation, Art, Medical imaging, Medical information processing, Robotics and control, Bio-informatics, Natural Language Processing (NLP), Cyber security, and many more. This report presents a brief survey on development of DL approaches, including Deep Neural Network (DNN), Convolutional Neural Network (CNN), Recurrent Neural Network (RNN) including Long Short Term Memory (LSTM) and Gated Recurrent Units (GRU), Auto-Encoder (AE), Deep Belief Network (DBN), Generative Adversarial Network (GAN), and Deep Reinforcement Learning (DRL). In addition, we have included recent development of proposed advanced variant DL techniques based on the mentioned DL approaches. Furthermore, DL approaches have explored and evaluated in different application domains are also included in this survey. We have also comprised recently developed frameworks, SDKs, and benchmark datasets that are used for implementing and evaluating deep learning approaches. There are some surveys have published on Deep Learning in Neural Networks [1, 38] and a survey on RL [234]. However, those papers have not discussed the individual advanced techniques for training large scale deep learning models and the recently developed method of generative models [1].
Tag-Enhanced Tree-Structured Neural Networks for Implicit Discourse Relation Classification
Venue: arXiv cs.CL 2018
Year: 2018

Identifying implicit discourse relations between text spans is a challenging task because it requires understanding the meaning of the text. To tackle this task, recent studies have tried several deep learning methods but few of them exploited the syntactic information. In this work, we explore the idea of incorporating syntactic parse tree into neural networks. Specifically, we employ the Tree-LSTM model and Tree-GRU model, which are based on the tree structure, to encode the arguments in a relation. Moreover, we further leverage the constituent tags to control the semantic composition process in these tree-structured neural networks. Experimental results show that our method achieves state-of-the-art performance on PDTB corpus.
Automatic Instrument Segmentation in Robot-Assisted Surgery Using Deep Learning
Venue: arXiv cs.CV 2018
Year: 2018

Semantic segmentation of robotic instruments is an important problem for the robot-assisted surgery. One of the main challenges is to correctly detect an instrument's position for the tracking and pose estimation in the vicinity of surgical scenes. Accurate pixel-wise instrument segmentation is needed to address this challenge. In this paper we describe our winning solution for MICCAI 2017 Endoscopic Vision SubChallenge: Robotic Instrument Segmentation. Our approach demonstrates an improvement over the state-of-the-art results using several novel deep neural network architectures. It addressed the binary segmentation problem, where every pixel in an image is labeled as an instrument or background from the surgery video feed. In addition, we solve a multi-class segmentation problem, where we distinguish different instruments or different parts of an instrument from the background. In this setting, our approach outperforms other methods in every task subcategory for automatic instrument segmentation thereby providing state-of-the-art solution for this problem. The source code for our solution is made publicly available at https://github.com/ternaus/robot-surgery-segmentation
Deep Bayesian Active Semi-Supervised Learning
Venue: arXiv cs.LG 2018
Year: 2018

In many applications the process of generating label information is expensive and time consuming. We present a new method that combines active and semi-supervised deep learning to achieve high generalization performance from a deep convolutional neural network with as few known labels as possible. In a setting where a small amount of labeled data as well as a large amount of unlabeled data is available, our method first learns the labeled data set. This initialization is followed by an expectation maximization algorithm, where further training reduces classification entropy on the unlabeled data by targeting a low entropy fit which is consistent with the labeled data. In addition the algorithm asks at a specified frequency an oracle for labels of data with entropy above a certain entropy quantile. Using this active learning component we obtain an agile labeling process that achieves high accuracy, but requires only a small amount of known labels. For the MNIST dataset we report an error rate of 2.06% using only 300 labels and 1.06% for 1000 labels. These results are obtained without employing any special network architecture or data augmentation.
Imprecise temporal associations and decision support systems
Venue: arXiv cs.DB 2018
Year: 2018

The quick and pervasive infiltration of decision support systems, artificial intelligence, and data mining in consumer electronics and everyday life in general has been significant in recent years. Fields such as UX have been facilitating the integration of such technologies into software and hardware, but the back-end processing is still based on binary foundations. This article describes an approach to mining for imprecise temporal associations among events in data streams, taking into account the very natural concept of approximation. This type of association analysis is likely to lead to more meaningful and actionable decision support systems.
Design, Generation, and Validation of Extreme Scale Power-Law Graphs
Venue: arXiv cs.DC 2018
Year: 2018

Massive power-law graphs drive many fields: metagenomics, brain mapping, Internet-of-things, cybersecurity, and sparse machine learning. The development of novel algorithms and systems to process these data requires the design, generation, and validation of enormous graphs with exactly known properties. Such graphs accelerate the proper testing of new algorithms and systems and are a prerequisite for success on real applications. Many random graph generators currently exist that require realizing a graph in order to know its exact properties: number of vertices, number of edges, degree distribution, and number of triangles. Designing graphs using these random graph generators is a time-consuming trial-and-error process. This paper presents a novel approach that uses Kronecker products to allow the exact computation of graph properties prior to graph generation. In addition, when a real graph is desired, it can be generated quickly in memory on a parallel computer with no-interprocessor communication. To test this approach, graphs with $10^{12}$ edges are generated on a 40,000+ core supercomputer in 1 second and exactly agree with those predicted by the theory. In addition, to demonstrate the extensibility of this approach, decetta-scale graphs with up to $10^{30}$ edges are simulated in a few minutes on a laptop.
Angora: Efficient Fuzzing by Principled Search
Venue: arXiv cs.CR 2018
Year: 2018

Fuzzing is a popular technique for finding software bugs. However, the performance of the state-of-the-art fuzzers leaves a lot to be desired. Fuzzers based on symbolic execution produce quality inputs but run slow, while fuzzers based on random mutation run fast but have difficulty producing quality inputs. We propose Angora, a new mutation-based fuzzer that outperforms the state-of-the-art fuzzers by a wide margin. The main goal of Angora is to increase branch coverage by solving path constraints without symbolic execution. To solve path constraints efficiently, we introduce several key techniques: scalable byte-level taint tracking, context-sensitive branch count, search based on gradient descent, and input length exploration. On the LAVA-M data set, Angora found almost all the injected bugs, found more bugs than any other fuzzer that we compared with, and found eight times as many bugs as the second-best fuzzer in the program who. Angora also found 103 bugs that the LAVA authors injected but could not trigger. We also tested Angora on eight popular, mature open source programs. Angora found 6, 52, 29, 40 and 48 new bugs in file, jhead, nm, objdump and size, respectively. We measured the coverage of Angora and evaluated how its key techniques contribute to its impressive performance.
Deep Network Regularization via Bayesian Inference of Synaptic Connectivity
Venue: arXiv cs.LG 2018
Year: 2018

Deep neural networks (DNNs) often require good regularizers to generalize well. Currently, state-of-the-art DNN regularization techniques consist in randomly dropping units and/or connections on each iteration of the training algorithm. Dropout and DropConnect are characteristic examples of such regularizers, that are widely popular among practitioners. However, a drawback of such approaches consists in the fact that their postulated probability of random unit/connection omission is a constant that must be heuristically selected based on the obtained performance in some validation set. To alleviate this burden, in this paper we regard the DNN regularization problem from a Bayesian inference perspective: We impose a sparsity-inducing prior over the network synaptic weights, where the sparsity is induced by a set of Bernoulli-distributed binary variables with Beta (hyper-)priors over their prior parameters. This way, we eventually allow for marginalizing over the DNN synaptic connectivity for output generation, thus giving rise to an effective, heuristics-free, network regularization scheme. We perform Bayesian inference for the resulting hierarchical model by means of an efficient Black-Box Variational inference scheme. We exhibit the advantages of our method over existing approaches by conducting an extensive experimental evaluation using benchmark datasets.
New Results on Multi-Step Traffic Flow Prediction
Venue: arXiv cs.AI 2018
Year: 2018

In its simplest form, the traffic flow prediction problem is restricted to predicting a single time-step into the future. Multi-step traffic flow prediction extends this set-up to the case where predicting multiple time-steps into the future based on some finite history is of interest. This problem is significantly more difficult than its single-step variant and is known to suffer from degradation in predictions as the time step increases. In this paper, two approaches to improve multi-step traffic flow prediction performance in recursive and multi-output settings are introduced. In particular, a model that allows recursive prediction approaches to take into account the temporal context in term of time-step index when making predictions is introduced. In addition, a conditional generative adversarial network-based data augmentation method is proposed to improve prediction performance in the multi-output setting. The experiments on a real-world traffic flow dataset show that the two methods improve on multi-step traffic flow prediction in recursive and multi-output settings, respectively.
A real-time decision support system for bridge management based on the rules generalized by CART decision tree and SMO algorithms
Venue: arXiv cs.AI 2018
Year: 2018

Under dynamic conditions on bridges, we need a real-time management. To this end, this paper presents a rule-based decision support system in which the necessary rules are extracted from simulation results made by Aimsun traffic micro-simulation software. Then, these rules are generalized by the aid of fuzzy rule generation algorithms. Then, they are trained by a set of supervised and the unsupervised learning algorithms to get an ability to make decision in real cases. As a pilot case study, Nasr Bridge in Tehran is simulated in Aimsun and WEKA data mining software is used to execute the learning algorithms. Based on this experiment, the accuracy of the supervised algorithms to generalize the rules is greater than 80%. In addition, CART decision tree and sequential minimal optimization (SMO) provides 100% accuracy for normal data and these algorithms are so reliable for crisis management on bridge. This means that, it is possible to use such machine learning methods to manage bridges in the real-time conditions.