OpenRaiser/Intern-Atlas huggingface dataset:
Polynomial invariants by linear algebra
Venue: arXiv cs.LO 2016
Year: 2016

We present in this paper a new technique for generating polynomial invariants, divided in two independent parts : a procedure that reduces polynomial assignments composed loops analysis to linear loops under certain hypotheses and a procedure for generating inductive invariants for linear loops. Both of these techniques have a polynomial complexity for a bounded number of variables and we guarantee the completeness of the technique for a bounded degree which we successfully implemented for C programs verification.
MESL: Proposal for a Non-volatile Cascadable Magneto-Electric Spin Logic
Venue: arXiv cs.ET 2016
Year: 2016

In the quest for novel, scalable and energy-efficient computing technologies, many non-charge based logic devices are being explored. Recent advances in multi-ferroic materials have paved the way for electric field induced low energy and fast switching of nano-magnets using the magneto-electric (ME) effect. In this paper, we propose a voltage driven logic-device based on the ME induced switching of nano-magnets. We further demonstrate that the proposed logic-device, which exhibits decoupled read and write paths, can be used to construct a complete logic family including XNOR, NAND and NOR gates. The proposed logic family shows good scalability with a quadratic dependence of switching energy with respect to the switching voltage. Further, the proposed logic-device has better robustness against the effect of thermal noise as compared to the conventional current driven switching of nano-magnets. A device-to-circuit level coupled simulation framework, including magnetization dynamics and electron transport model, has been developed for analyzing the present proposal. Using our simulation framework, we present energy and delay results for the proposed Magneto-Electric Spin Logic (MESL) gates.
Synthesizing invariants by solving solvable loops
Venue: arXiv cs.LO 2016
Year: 2016

When proving invariance properties of a program, we face two problems. The first problem is related to the necessity of proving tautologies of considered assertion language, whereas the second manifests in the need of finding sufficiently strong invariants. This paper focuses on the second problem and describes a new method for the automatic generation of loop invariants that handles polynomial and non deterministic assignments. This technique is based on the eigenvector generation for a given linear transformation and on the polynomial optimization problem, which we implemented in the open-source tool Pilat.
Object Detection using Image Processing
Venue: arXiv cs.CV 2016
Year: 2016

An Unmanned Ariel vehicle (UAV) has greater importance in the army for border security. The main objective of this article is to develop an OpenCV-Python code using Haar Cascade algorithm for object and face detection. Currently, UAVs are used for detecting and attacking the infiltrated ground targets. The main drawback for this type of UAVs is that sometimes the object are not properly detected, which thereby causes the object to hit the UAV. This project aims to avoid such unwanted collisions and damages of UAV. UAV is also used for surveillance that uses Voila-jones algorithm to detect and track humans. This algorithm uses cascade object detector function and vision. train function to train the algorithm. The main advantage of this code is the reduced processing time. The Python code was tested with the help of available database of video and image, the output was verified.
Multiscale Inverse Reinforcement Learning using Diffusion Wavelets
Venue: arXiv cs.LG 2016
Year: 2016

This work presents a multiscale framework to solve an inverse reinforcement learning (IRL) problem for continuous-time/state stochastic systems. We take advantage of a diffusion wavelet representation of the associated Markov chain to abstract the state space. This not only allows for effectively handling the large (and geometrically complex) decision space but also provides more interpretable representations of the demonstrated state trajectories and also of the resulting policy of IRL. In the proposed framework, the problem is divided into the global and local IRL, where the global approximation of the optimal value functions are obtained using coarse features and the local details are quantified using fine local features. An illustrative numerical example on robot path control in a complex environment is presented to verify the proposed method.
Automatically Building Face Datasets of New Domains from Weakly Labeled Data with Pretrained Models
Venue: arXiv cs.CV 2016
Year: 2016

Training data are critical in face recognition systems. However, labeling a large scale face data for a particular domain is very tedious. In this paper, we propose a method to automatically and incrementally construct datasets from massive weakly labeled data of the target domain which are readily available on the Internet under the help of a pretrained face model. More specifically, given a large scale weakly labeled dataset in which each face image is associated with a label, i.e. the name of an identity, we create a graph for each identity with edges linking matched faces verified by the existing model under a tight threshold. Then we use the maximal subgraph as the cleaned data for that identity. With the cleaned dataset, we update the existing face model and use the new model to filter the original dataset to get a larger cleaned dataset. We collect a large weakly labeled dataset containing 530,560 Asian face images of 7,962 identities from the Internet, which will be published for the study of face recognition. By running the filtering process, we obtain a cleaned datasets (99.7+% purity) of size 223,767 (recall 70.9%). On our testing dataset of Asian faces, the model trained by the cleaned dataset achieves recognition rate 93.1%, which obviously outperforms the model trained by the public dataset CASIA whose recognition rate is 85.9%.
Extraction of airway trees using multiple hypothesis tracking and template matching
Venue: arXiv cs.CV 2016
Year: 2016

Knowledge of airway tree morphology has important clinical applications in diagnosis of chronic obstructive pulmonary disease. We present an automatic tree extraction method based on multiple hypothesis tracking and template matching for this purpose and evaluate its performance on chest CT images. The method is adapted from a semi-automatic method devised for vessel segmentation. Idealized tubular templates are constructed that match airway probability obtained from a trained classifier and ranked based on their relative significance. Several such regularly spaced templates form the local hypotheses used in constructing a multiple hypothesis tree, which is then traversed to reach decisions. The proposed modifications remove the need for local thresholding of hypotheses as decisions are made entirely based on statistical comparisons involving the hypothesis tree. The results show improvements in performance when compared to the original method and region growing on intensity images. We also compare the method with region growing on the probability images, where the presented method does not show substantial improvement, but we expect it to be less sensitive to local anomalies in the data.
Interferences in match kernels
Venue: arXiv cs.CV 2016
Year: 2016

We consider the design of an image representation that embeds and aggregates a set of local descriptors into a single vector. Popular representations of this kind include the bag-of-visual-words, the Fisher vector and the VLAD. When two such image representations are compared with the dot-product, the image-to-image similarity can be interpreted as a match kernel. In match kernels, one has to deal with interference, i.e. with the fact that even if two descriptors are unrelated, their matching score may contribute to the overall similarity. We formalise this problem and propose two related solutions, both aimed at equalising the individual contributions of the local descriptors in the final representation. These methods modify the aggregation stage by including a set of per-descriptor weights. They differ by the objective function that is optimised to compute those weights. The first is a "democratisation" strategy that aims at equalising the relative importance of each descriptor in the set comparison metric. The second one involves equalising the match of a single descriptor to the aggregated vector. These concurrent methods give a substantial performance boost over the state of the art in image search with short or mid-size vectors, as demonstrated by our experiments on standard public image retrieval benchmarks.
Researches on Dynamic Load Balancing Algorithms and hp-Adaptivity in 3-D Parallel Adaptive Finite Element Computations
Venue: arXiv cs.CE 2016
Year: 2016

This work is related to PHG (Parallel Hierarchical Grid). PHG is a toolbox for developing parallel adaptive finite element programs, which is under active development at the State Key Laboratory of Scientific and Engineering Computing. The main results of this work are as follows. 1) For the tetrahedral meshes used in PHG, under reasonable assumptions, we proved the existence of through-vertex Hamiltonian paths between arbitrary two vertices, as well as the existence of through-vertex Hamiltonian cycles, and designed an efficient algorithm with linear complexity for constructing through-vertex Hamiltonian paths. The resulting algorithm has been implemented in PHG, and is used for ordering elements in the coarsest mesh for the refinement tree mesh partitioning algorithm. 2) We designed encoding and decoding algorithms for high dimensional Hilbert order. Hilbert order has good locality, and it has wide applications in various fields in computer science, such as memory management, database, and dynamic load balancing. 3) We implemented refinement tree and space filling curve based mesh partitioning algorithms in PHG, and designed the dynamic load balancing module of PHG. The refinement tree based partitioning algorithm was originally proposed by Mitchell, the one implemented in PHG was improved in several aspects. The space filling curve based mesh partitioning function in PHG can use either Hilbert or Morton space filling curve. 4) We studied existing hp-adaptive strategies in the literature, and proposed a new strategy. Numerical experiments show that our new strategy achieves exponential convergence, and is superior, in both precision of the solutions and computation time, to the strategy compared. This part of the work also serves to validate the hp-adaptivity module of PHG.
State Sensitivity Evaluation Within UD Based Array Covariance Filters
Venue: arXiv cs.SY 2016
Year: 2016

This technical note addresses the UD factorization based Kalman filtering (KF) algorithms. Using this important class of numerically stable KF schemes, we extend its functionality and develop an elegant and simple method for computation of sensitivities of the system state to unknown parameters required in a variety of applications. For instance, it can be used for efficient calculations in sensitivity analysis and in gradient-search optimization algorithms for the maximum likelihood estimation. The new theory presented in this technical note is a solution to the problem formulated by Bierman in , which has been open since 1990s. As in the cited paper, our method avoids the standard approach based on the conventional KF (and its derivatives with respect to unknown system parameters) with its inherent numerical instabilities and, hence, improves the robustness of computations against roundoff errors.
Neural Machine Translation with Latent Semantic of Image and Text
Venue: arXiv cs.CL 2016
Year: 2016

Although attention-based Neural Machine Translation have achieved great success, attention-mechanism cannot capture the entire meaning of the source sentence because the attention mechanism generates a target word depending heavily on the relevant parts of the source sentence. The report of earlier studies has introduced a latent variable to capture the entire meaning of sentence and achieved improvement on attention-based Neural Machine Translation. We follow this approach and we believe that the capturing meaning of sentence benefits from image information because human beings understand the meaning of language not only from textual information but also from perceptual information such as that gained from vision. As described herein, we propose a neural machine translation model that introduces a continuous latent variable containing an underlying semantic extracted from texts and images. Our model, which can be trained end-to-end, requires image information only when training. Experiments conducted with an English--German translation task show that our model outperforms over the baseline.
An Analysis of Tournament Structure
Venue: arXiv cs.AI 2016
Year: 2016

This paper explores a novel way for analyzing the tournament structures to find a best suitable one for the tournament under consideration. It concerns about three aspects such as tournament conducting cost, competitiveness development and ranking precision. It then proposes a new method using progress tree to detect potential throwaway matches. The analysis performed using the proposed method reveals the strengths and weaknesses of tournament structures. As a conclusion, single elimination is best if we want to qualify one winner only, all matches conducted are exciting in term of competitiveness. Double elimination with proper seeding system is a better choice if we want to qualify more winners. A reasonable number of extra matches need to be conducted in exchange of being able to qualify top four winners. Round-robin gives reliable ranking precision for all participants. However, its conduction cost is very high, and it fails to maintain competitiveness development.
A Simple, Fast Diverse Decoding Algorithm for Neural Generation
Venue: arXiv cs.CL 2016
Year: 2016

In this paper, we propose a simple, fast decoding algorithm that fosters diversity in neural generation. The algorithm modifies the standard beam search algorithm by adding an inter-sibling ranking penalty, favoring choosing hypotheses from diverse parents. We evaluate the proposed model on the tasks of dialogue response generation, abstractive summarization and machine translation. We find that diverse decoding helps across all tasks, especially those for which reranking is needed. We further propose a variation that is capable of automatically adjusting its diversity decoding rates for different inputs using reinforcement learning (RL). We observe a further performance boost from this RL technique. This paper includes material from the unpublished script "Mutual Information and Diverse Decoding Improve Neural Machine Translation" (Li and Jurafsky, 2016).
Bipolar Weighted Argumentation Graphs
Venue: arXiv cs.AI 2016
Year: 2016

This paper discusses the semantics of weighted argumentation graphs that are biplor, i.e. contain both attacks and support graphs. The work builds on previous work by Amgoud, Ben-Naim et. al., which presents and compares several semantics for argumentation graphs that contain only supports or only attacks relationships, respectively.
Learning from Maps: Visual Common Sense for Autonomous Driving
Venue: arXiv cs.CV 2016
Year: 2016

Today's autonomous vehicles rely extensively on high-definition 3D maps to navigate the environment. While this approach works well when these maps are completely up-to-date, safe autonomous vehicles must be able to corroborate the map's information via a real time sensor-based system. Our goal in this work is to develop a model for road layout inference given imagery from on-board cameras, without any reliance on high-definition maps. However, no sufficient dataset for training such a model exists. Here, we leverage the availability of standard navigation maps and corresponding street view images to construct an automatically labeled, large-scale dataset for this complex scene understanding problem. By matching road vectors and metadata from navigation maps with Google Street View images, we can assign ground truth road layout attributes (e.g., distance to an intersection, one-way vs. two-way street) to the images. We then train deep convolutional networks to predict these road layout attributes given a single monocular RGB image. Experimental evaluation demonstrates that our model learns to correctly infer the road attributes using only panoramas captured by car-mounted cameras as input. Additionally, our results indicate that this method may be suitable to the novel application of recommending safety improvements to infrastructure (e.g., suggesting an alternative speed limit for a street).
A conservation rule for constructing bibliometric network matrices
Venue: arXiv cs.DL 2016
Year: 2016

The social network analysis of bibliometric data needs matrices to be recast in a network framework. In this paper we argue that a simple conservation rule requires that this should be done only using fractional counting so that conservation at the paper level will be faithfully reproduced at higher levels ofaggregation (i.e. author, institute, country, journal etc.) of the complex network.
Dual MCDRR Scheduler for Hybrid TDM/WDM Optical Networks
Venue: arXiv cs.NI 2016
Year: 2016

In this paper we propose and investigate the performance of a dual multi-channel deficit round-robin (D-MCDRR) scheduler based on the existing single MCDRR scheduler. The existing scheduler is used for multiple channels with tunable transmitters and fixed receivers in hybrid time division multiplexing (TDM)/wavelength division multiplexing (WDM) optical networks. The proposed dual scheduler will also be used in the same optical networks. We extend the existing MCDRR scheduling algorithm for n channels to the case of considering two schedulers for the same n channels. Simulation results show that the proposed dual MCDRR (D-MCDRR) scheduler can provide better throughput when compared to the existing single MCDRR scheduler.
Secure Fast Fourier Transform using Fully Homomorphic Encryption
Venue: arXiv cs.CR 2016
Year: 2016

Secure signal processing is becoming a de facto model for preserving privacy. We propose a model based on the Fully Homomorphic Encryption (FHE) technique to mitigate security breaches. Our framework provides a method to perform a Fast Fourier Transform (FFT) on a user-specified signal. Using encryption of individual binary values and FHE operations over addition and multiplication, we enable a user to perform the FFT in a fixed point fractional representation in binary. Our approach bounds the error of the implementation to enable user-selectable parameters based on the specific application. We verified our framework against test cases for one dimensional signals and images (two dimensional signals).
Embedded Bandits for Large-Scale Black-Box Optimization
Venue: arXiv cs.AI 2016
Year: 2016

Random embedding has been applied with empirical success to large-scale black-box optimization problems with low effective dimensions. This paper proposes the EmbeddedHunter algorithm, which incorporates the technique in a hierarchical stochastic bandit setting, following the optimism in the face of uncertainty principle and breaking away from the multiple-run framework in which random embedding has been conventionally applied similar to stochastic black-box optimization solvers. Our proposition is motivated by the bounded mean variation in the objective value for a low-dimensional point projected randomly into the decision space of Lipschitz-continuous problems. In essence, the EmbeddedHunter algorithm expands optimistically a partitioning tree over a low-dimensional---equal to the effective dimension of the problem---search space based on a bounded number of random embeddings of sampled points from the low-dimensional space. In contrast to the probabilistic theoretical guarantees of multiple-run random-embedding algorithms, the finite-time analysis of the proposed algorithm presents a theoretical upper bound on the regret as a function of the algorithm's number of iterations. Furthermore, numerical experiments were conducted to validate its performance. The results show a clear performance gain over recently proposed random embedding methods for large-scale problems, provided the intrinsic dimensionality is low.
Fixed-Parameter Algorithms for DAG Partitioning
Venue: arXiv cs.DS 2016
Year: 2016

Finding the origin of short phrases propagating through the web has been formalized by Leskovec et al. [ACM SIGKDD 2009] as DAG Partitioning: given an arc-weighted directed acyclic graph on $n$ vertices and $m$ arcs, delete arcs with total weight at most $k$ such that each resulting weakly-connected component contains exactly one sink---a vertex without outgoing arcs. DAG Partitioning is NP-hard. We show an algorithm to solve DAG Partitioning in $O(2^k \cdot (n+m))$ time, that is, in linear time for fixed $k$. We complement it with linear-time executable data reduction rules. Our experiments show that, in combination, they can optimally solve DAG Partitioning on simulated citation networks within five minutes for $k\leq190$ and $m$ being $10^7$ and larger. We use our obtained optimal solutions to evaluate the solution quality of Leskovec et al.'s heuristic. We show that Leskovec et al.'s heuristic works optimally on trees and generalize this result by showing that DAG Partitioning is solvable in $2^{O(w^2)}\cdot n$ time if a width-$w$ tree decomposition of the input graph is given. Thus, we improve an algorithm and answer an open question of Alamdari and Mehrabian [WAW 2012]. We complement our algorithms by lower bounds on the running time of exact algorithms and on the effectivity of data reduction.
Learning-Based Coexistence in Two-Tier Heterogeneous Networks with Cognitive Small Cells
Venue: arXiv cs.IT 2016
Year: 2016

We study the coexistence problem in a two-tier heterogeneous network (HetNet) with cognitive small cells. In particular, we consider an underlay HetNet, where the cognitive small base station (C-SBS) is allowed to use the frequency bands of the macro cell with an access probability (AP) as long as the C-SBS satisfies a preset interference probability (IP) constraint at macro users (MUs). To enhance the AP (or transmission opportunity) of the C-SBS, we propose a learning-based algorithm for the C-SBS and exploit the distance information between the macro base station (MBS) and MUs. Generally, the signal from the MBS to a specific MU contains the distance information between the MBS to the MU. We enable the C-SBS to analyze the MBS signal on a target frequency band, and learn the distance information between the MBS and the corresponding MU. With the learnt distance information, we calculate the upper bound of the probability that the C-SBS may interfere with the MU, and design an AP with a closed-form expression under the IP constraint. Numerical results indicate that the proposed algorithm outperforms the existing methods up to $60\%$ AP (or transmission opportunity).