OpenRaiser/Intern-Atlas huggingface dataset:
A New Technique for Reachability of States in Concatenation Automata
Venue: arXiv cs.FL 2017
Year: 2017

We present a new technique for demonstrating the reachability of states in deterministic finite automata representing the concatenation of two languages. Such demonstrations are a necessary step in establishing the state complexity of the concatenation of two languages, and thus in establishing the state complexity of concatenation as an operation. Typically, ad-hoc induction arguments are used to show particular states are reachable in concatenation automata. We prove some results that seem to capture the essence of many of these induction arguments. Using these results, reachability proofs in concatenation automata can often be done more simply and without using induction directly.
Video Classification With CNNs: Using The Codec As A Spatio-Temporal Activity Sensor
Venue: arXiv cs.CV 2017
Year: 2017

We investigate video classification via a two-stream convolutional neural network (CNN) design that directly ingests information extracted from compressed video bitstreams. Our approach begins with the observation that all modern video codecs divide the input frames into macroblocks (MBs). We demonstrate that selective access to MB motion vector (MV) information within compressed video bitstreams can also provide for selective, motion-adaptive, MB pixel decoding (a.k.a., MB texture decoding). This in turn allows for the derivation of spatio-temporal video activity regions at extremely high speed in comparison to conventional full-frame decoding followed by optical flow estimation. In order to evaluate the accuracy of a video classification framework based on such activity data, we independently train two CNN architectures on MB texture and MV correspondences and then fuse their scores to derive the final classification of each test video. Evaluation on two standard datasets shows that the proposed approach is competitive to the best two-stream video classification approaches found in the literature. At the same time: (i) a CPU-based realization of our MV extraction is over 977 times faster than GPU-based optical flow methods; (ii) selective decoding is up to 12 times faster than full-frame decoding; (iii) our proposed spatial and temporal CNNs perform inference at 5 to 49 times lower cloud computing cost than the fastest methods from the literature.
Resource Allocation for D2D Communications Underlaying a NOMA-Based Cellular Network
Venue: arXiv cs.IT 2017
Year: 2017

This letter investigates the power control and channel assignment problem in device-to-device (D2D) communications underlaying a non-orthogonal multiple access (NOMA) cellular network. With the successive interference cancellation decoding order constraints, our target is to maximize the sum rate of D2D pairs while guaranteeing the minimum rate requirements of NOMA-based cellular users. Specifically, the optimal conditions for power control of cellular users on each subchannel are derived first. Then, based on these results, we propose a dual-based iterative algorithm to solve the resource allocation problem. Simulation results validate the superiority of proposed resource allocation algorithm over the existing orthogonal multiple access scheme.
High Throughput 2D Spatial Image Filters on FPGAs
Venue: arXiv cs.AR 2017
Year: 2017

FPGAs are well established in the signal processing domain, where their fine-grained programmable nature allows the inherent parallelism in these applications to be exploited for enhanced performance. As architectures have evolved, FPGA vendors have added more heterogeneous resources to allow often-used functions to be implemented with higher performance, at lower power and using less area. DSP blocks, for example, have evolved from basic multipliers to support the multiply-accumulate operations that are the core of many signal processing tasks. While more features were added to DSP blocks, their structure and connectivity has been optimised primarily for one-dimensional signal processing. Basic operations in image processing are similar, but performed in a two-dimensional structure, and hence, many of the optimisations in newer DSP blocks are not exploited when mapping image processing algorithms to them. We present a detailed study of two-dimensional spatial filter implementation on FPGAs, showing how to maximise performance through exploitation of DSP block capabilities, while also presenting a lean border pixel management policy.
A graphical, scalable and intuitive method for the placement and the connection of biological cells
Venue: arXiv cs.NE 2017
Year: 2017

We introduce a graphical method originating from the computer graphics domain that is used for the arbitrary and intuitive placement of cells over a two-dimensional manifold. Using a bitmap image as input, where the color indicates the identity of the different structures and the alpha channel indicates the local cell density, this method guarantees a discrete distribution of cell position respecting the local density function. This method scales to any number of cells, allows to specify several different structures at once with arbitrary shapes and provides a scalable and versatile alternative to the more classical assumption of a uniform non-spatial distribution. Furthermore, several connection schemes can be derived from the paired distances between cells using either an automatic mapping or a user-defined local reference frame, providing new computational properties for the underlying model. The method is illustrated on a discrete homogeneous neural field, on the distribution of cones and rods in the retina and on a coronal view of the basal ganglia.
An Adaptive Framework for Missing Depth Inference Using Joint Bilateral Filter
Venue: arXiv cs.CV 2017
Year: 2017

Depth imaging has largely focused on sensor and intrinsics properties. However, the accuracy of acquire pixel is largely dependent on the capture. We propose a new depth estimation and approximation algorithm which takes an arbitrary 3D point cloud as input, with potentially complex geometric structures, and generates automatically a bounding box which is used to clamp the 3D distribution into a valid range. We then infer the desired compact geometric network from complex 3D geometries by using a series of adaptive joint bilateral filters. Our approach leverages these input depth in the construction of a compact descriptive adaptive filter framework. The built system that allows a user to control the result of capture depth map to fit the target geometry. In addition, it is desirable to visualize structurally problematic areas of the depth data in a dynamic environment. To provide this feature, we investigate a fast update algorithm for the fragility of each pixel's corresponding 3D point using machine learning. We present a new for of feature vector analysis and demonstrate the effectiveness in the dataset. In our experiment, we demonstrate the practicality and benefits of our proposed method by computing accurate solutions captured depth map from different types of sensors and shows better results than existing methods.
Ensemble Kalman Filters (EnKF) for State Estimation and Prediction of Two-time Scale Nonlinear Systems with Application to Gas Turbine Engines
Venue: arXiv cs.SY 2017
Year: 2017

In this paper, we propose and develop a methodology for nonlinear systems health monitoring by modeling the damage and degradation mechanism dynamics as "slow" states that are augmented with the system "fast" dynamical states. This augmentation results in a two-time scale nonlinear system that is utilized for development of health estimation and prediction modules within a health monitoring framework. Towards this end, a two-time scale filtering approach is developed based on the ensemble Kalman filtering (EnKF) approach by taking advantage of the model reduction concept. The performance of our proposed two-time scale ensemble Kalman filters is shown to be superior and less computationally intensive in terms of the equivalent flop (EF) complexity metric when compared to well-known particle filtering (PF) approaches. Our proposed methodology is then applied to a gas turbine engine that is affected by erosion of the turbine as the degradation phenomenon and damage mechanism. Extensive comparative studies are conducted to validate and demonstrate the advantages and capabilities of our proposed framework and methodology.
Vector Quantization using the Improved Differential Evolution Algorithm for Image Compression
Venue: arXiv cs.CV 2017
Year: 2017

Vector Quantization, VQ is a popular image compression technique with a simple decoding architecture and high compression ratio. Codebook designing is the most essential part in Vector Quantization. LindeBuzoGray, LBG is a traditional method of generation of VQ Codebook which results in lower PSNR value. A Codebook affects the quality of image compression, so the choice of an appropriate codebook is a must. Several optimization techniques have been proposed for global codebook generation to enhance the quality of image compression. In this paper, a novel algorithm called IDE-LBG is proposed which uses Improved Differential Evolution Algorithm coupled with LBG for generating optimum VQ Codebooks. The proposed IDE works better than the traditional DE with modifications in the scaling factor and the boundary control mechanism. The IDE generates better solutions by efficient exploration and exploitation of the search space. Then the best optimal solution obtained by the IDE is provided as the initial Codebook for the LBG. This approach produces an efficient Codebook with less computational time and the consequences include excellent PSNR values and superior quality reconstructed images. It is observed that the proposed IDE-LBG find better VQ Codebooks as compared to IPSO-LBG, BA-LBG and FA-LBG.
Nivat's conjecture holds for sums of two periodic configurations
Venue: arXiv cs.DM 2017
Year: 2017

Nivat's conjecture is a long-standing open combinatorial problem. It concerns two-dimensional configurations, that is, maps $\mathbb Z^2 \rightarrow \mathcal A$ where $\mathcal A$ is a finite set of symbols. Such configurations are often understood as colorings of a two-dimensional square grid. Let $P_c(m,n)$ denote the number of distinct $m \times n$ block patterns occurring in a configuration $c$. Configurations satisfying $P_c(m,n) \leq mn$ for some $m,n \in \mathbb N$ are said to have low rectangular complexity. Nivat conjectured that such configurations are necessarily periodic. Recently, Kari and the author showed that low complexity configurations can be decomposed into a sum of periodic configurations. In this paper we show that if there are at most two components, Nivat's conjecture holds. As a corollary we obtain an alternative proof of a result of Cyr and Kra: If there exist $m,n \in \mathbb N$ such that $P_c(m,n) \leq mn/2$, then $c$ is periodic. The technique used in this paper combines the algebraic approach of Kari and the author with balanced sets of Cyr and Kra.
Safe Learning of Quadrotor Dynamics Using Barrier Certificates
Venue: arXiv cs.LG 2017
Year: 2017

To effectively control complex dynamical systems, accurate nonlinear models are typically needed. However, these models are not always known. In this paper, we present a data-driven approach based on Gaussian processes that learns models of quadrotors operating in partially unknown environments. What makes this challenging is that if the learning process is not carefully controlled, the system will go unstable, i.e., the quadcopter will crash. To this end, barrier certificates are employed for safe learning. The barrier certificates establish a non-conservative forward invariant safe region, in which high probability safety guarantees are provided based on the statistics of the Gaussian Process. A learning controller is designed to efficiently explore those uncertain states and expand the barrier certified safe region based on an adaptive sampling scheme. In addition, a recursive Gaussian Process prediction method is developed to learn the complex quadrotor dynamics in real-time. Simulation results are provided to demonstrate the effectiveness of the proposed approach.
The Devils in The Details: Placing Decoy Routers in the Internet
Venue: arXiv cs.CR 2017
Year: 2017

Decoy Routing, the use of routers (rather than end hosts) as proxies, is a new direction in anti-censorship research. Decoy Routers (DRs), placed in Autonomous Systems, proxy traffic from users; so the adversary, e.g., a censorious government, attempts to avoid them. It is quite difficult to place DRs so the adversary cannot route around them for example, we need the cooperation of 850 ASes to contain China alone. In this paper, we consider a different approach. We begin by noting that DRs need not intercept all the network paths from a country, just those leading to Overt Destinations, i.e., unfiltered websites hosted outside the country (usually popular ones, so that client traffic to the OD does not make the censor suspicious. Our first question is; How many ASes are required for installing DRs to intercept a large fraction of paths from, e.g., China to the top n websites (as per Alexa)? How does this number grow with n? Few ASes (approx. 30) intercept over 90% of paths to the top n sites, for n = 10, 20...200. Our first contribution is to demonstrate with real paths that the number of ASes required for a world-wide DR framework is small (approx. 30). Further, censor nations attempts to filter traffic along the paths transiting these 30 ASes will not only block their own citizens, but others residing in foreign ASes. Our second contribution in this paper is to consider the details of DR placement: not just in which ASes DRs should be placed to intercept traffic, but exactly where in each AS. We find that even with our small number of ASes, we still need a total of about 11,700 DRs.We conclude that, even though a DR system involves far fewer ASes than previously thought, it is still a major undertaking. For example, the current routers cost over 10.3 billion USD, so if DR at line speed requires all new hardware, the cost alone would make such a project unfeasible for most actors.
How PHP Releases Are Adopted in the Wild?
Venue: arXiv cs.SE 2017
Year: 2017

This empirical paper examines the adoption of PHP releases in the the contemporary world wide web. Motivated by continuous software engineering practices and software traceability improvements for release engineering, the empirical analysis is based on big data collected by web crawling. According to the empirical results based on discrete time-homogeneous Markov chain (DTMC) analysis, (i)~adoption of PHP releases has been relatively uniform across the domains observed, (ii) which tend to also adopt either old or new PHP releases relatively infrequently. Although there are outliers, (iii) downgrading of PHP releases is generally rare. To some extent, (iv) the results vary between the recent history from 2016 to early 2017 and the long-run evolution in the 2010s. In addition to these empirical results, the paper contributes to the software evolution and release engineering research traditions by elaborating the applied use of DTMCs for systematic empirical tracing of online software deployments.
How to Generate Pseudorandom Permutations Over Other Groups
Venue: arXiv cs.CR 2017
Year: 2017

Recent results by Alagic and Russell have given some evidence that the Even-Mansour cipher may be secure against quantum adversaries with quantum queries, if considered over other groups than $(\mathbb{Z}/2)^n$. This prompts the question as to whether or not other classical schemes may be generalized to arbitrary groups and whether classical results still apply to those generalized schemes. In this thesis, we generalize the Even-Mansour cipher and the Feistel cipher. We show that Even and Mansour's original notions of secrecy are obtained on a one-key, group variant of the Even-Mansour cipher. We generalize the result by Kilian and Rogaway, that the Even-Mansour cipher is pseudorandom, to super pseudorandomness, also in the one-key, group case. Using a Slide Attack we match the bound found above. After generalizing the Feistel cipher to arbitrary groups we resolve an open problem of Patel, Ramzan, and Sundaram by showing that the 3-round Feistel cipher over an arbitrary group is not super pseudorandom. We generalize a result by Gentry and Ramzan showing that the Even-Mansour cipher can be implemented using the Feistel cipher as the public permutation. In this result, we also consider the one-key case over a group and generalize their bound. Finally, we consider Zhandry's result on quantum pseudorandom permutations, showing that his result may be generalized to hold for arbitrary groups. In this regard, we consider whether certain card shuffles may be generalized as well.
Deep Self-Paced Learning for Person Re-Identification
Venue: arXiv cs.CV 2017
Year: 2017

Person re-identification (Re-ID) usually suffers from noisy samples with background clutter and mutual occlusion, which makes it extremely difficult to distinguish different individuals across the disjoint camera views. In this paper, we propose a novel deep self-paced learning (DSPL) algorithm to alleviate this problem, in which we apply a self-paced constraint and symmetric regularization to help the relative distance metric training the deep neural network, so as to learn the stable and discriminative features for person Re-ID. Firstly, we propose a soft polynomial regularizer term which can derive the adaptive weights to samples based on both the training loss and model age. As a result, the high-confidence fidelity samples will be emphasized and the low-confidence noisy samples will be suppressed at early stage of the whole training process. Such a learning regime is naturally implemented under a self-paced learning (SPL) framework, in which samples weights are adaptively updated based on both model age and sample loss using an alternative optimization method. Secondly, we introduce a symmetric regularizer term to revise the asymmetric gradient back-propagation derived by the relative distance metric, so as to simultaneously minimize the intra-class distance and maximize the inter-class distance in each triplet unit. Finally, we build a part-based deep neural network, in which the features of different body parts are first discriminately learned in the lower convolutional layers and then fused in the higher fully connected layers. Experiments on several benchmark datasets have demonstrated the superior performance of our method as compared with the state-of-the-art approaches.
ACCBench: A Framework for Comparing Causality Algorithms
Venue: arXiv cs.AI 2017
Year: 2017

Modern socio-technical systems are increasingly complex. A fundamental problem is that the borders of such systems are often not well-defined a-priori, which among other problems can lead to unwanted behavior during runtime. Ideally, unwanted behavior should be prevented. If this is not possible the system shall at least be able to help determine potential cause(s) a-posterori, identify responsible parties and make them accountable for their behavior. Recently, several algorithms addressing these concepts have been proposed. However, the applicability of the corresponding approaches, specifically their effectiveness and performance, is mostly unknown. Therefore, in this paper, we propose ACCBench, a benchmark tool that allows to compare and evaluate causality algorithms under a consistent setting. Furthermore, we contribute an implementation of the two causality algorithms by Gößler and Metayer and Gößler and Astefanoaei as well as of a policy compliance approach based on some concepts of Main et al. Lastly, we conduct a case study of an Intelligent Door Control System, which exposes concrete strengths and weaknesses of all algorithms under different aspects. In the course of this, we show that the effectiveness of the algorithms in terms of cause detection as well as their performance differ to some extent. In addition, our analysis reports on some qualitative aspects that should be considered when evaluating each algorithm. For example, the human effort needed to configure the algorithm and model the use case is analyzed.
Convolutional Neural Networks for Histopathology Image Classification: Training vs. Using Pre-Trained Networks
Venue: arXiv cs.CV 2017
Year: 2017

We explore the problem of classification within a medical image data-set based on a feature vector extracted from the deepest layer of pre-trained Convolution Neural Networks. We have used feature vectors from several pre-trained structures, including networks with/without transfer learning to evaluate the performance of pre-trained deep features versus CNNs which have been trained by that specific dataset as well as the impact of transfer learning with a small number of samples. All experiments are done on Kimia Path24 dataset which consists of 27,055 histopathology training patches in 24 tissue texture classes along with 1,325 test patches for evaluation. The result shows that pre-trained networks are quite competitive against training from scratch. As well, fine-tuning does not seem to add any tangible improvement for VGG16 to justify additional training while we observed considerable improvement in retrieval and classification accuracy when we fine-tuned the Inception structure.
Characterizing Driving Context from Driver Behavior
Venue: arXiv cs.AI 2017
Year: 2017

Because of the increasing availability of spatiotemporal data, a variety of data-analytic applications have become possible. Characterizing driving context, where context may be thought of as a combination of location and time, is a new challenging application. An example of such a characterization is finding the correlation between driving behavior and traffic conditions. This contextual information enables analysts to validate observation-based hypotheses about the driving of an individual. In this paper, we present DriveContext, a novel framework to find the characteristics of a context, by extracting significant driving patterns (e.g., a slow-down), and then identifying the set of potential causes behind patterns (e.g., traffic congestion). Our experimental results confirm the feasibility of the framework in identifying meaningful driving patterns, with improvements in comparison with the state-of-the-art. We also demonstrate how the framework derives interesting characteristics for different contexts, through real-world examples.
A retrieval-based dialogue system utilizing utterance and context embeddings
Venue: arXiv cs.CL 2017
Year: 2017

Finding semantically rich and computer-understandable representations for textual dialogues, utterances and words is crucial for dialogue systems (or conversational agents), as their performance mostly depends on understanding the context of conversations. Recent research aims at finding distributed vector representations (embeddings) for words, such that semantically similar words are relatively close within the vector-space. Encoding the "meaning" of text into vectors is a current trend, and text can range from words, phrases and documents to actual human-to-human conversations. In recent research approaches, responses have been generated utilizing a decoder architecture, given the vector representation of the current conversation. In this paper, the utilization of embeddings for answer retrieval is explored by using Locality-Sensitive Hashing Forest (LSH Forest), an Approximate Nearest Neighbor (ANN) model, to find similar conversations in a corpus and rank possible candidates. Experimental results on the well-known Ubuntu Corpus (in English) and a customer service chat dataset (in Dutch) show that, in combination with a candidate selection method, retrieval-based approaches outperform generative ones and reveal promising future research directions towards the usability of such a system.