OpenRaiser/Intern-Atlas huggingface dataset:
Causal Model Analysis using Collider v-structure with Negative Percentage Mapping
Venue: arXiv cs.AI 2015
Year: 2015

A major problem of causal inference is the arrangement of dependent nodes in a directed acyclic graph (DAG) with path coefficients and observed confounders. Path coefficients do not provide the units to measure the strength of information flowing from one node to the other. Here we proposed the method of causal structure learning using collider v-structures (CVS) with Negative Percentage Mapping (NPM) to get selective thresholds of information strength, to direct the edges and subjective confounders in a DAG. The NPM is used to scale the strength of information passed through nodes in units of percentage from interval from 0 to 1. The causal structures are constructed by bottom up approach using path coefficients, causal directions and confounders, derived implementing collider v-structure and NPM. The method is self-sufficient to observe all the latent confounders present in the causal model and capable of detecting every responsible causal direction. The results are tested for simulated datasets of non-Gaussian distributions and compared with DirectLiNGAM and ICA-LiNGAM to check efficiency of the proposed method.
Human and Sheep Facial Landmarks Localisation by Triplet Interpolated Features
Venue: arXiv cs.CV 2015
Year: 2015

In this paper we present a method for localisation of facial landmarks on human and sheep. We introduce a new feature extraction scheme called triplet-interpolated feature used at each iteration of the cascaded shape regression framework. It is able to extract features from similar semantic location given an estimated shape, even when head pose variations are large and the facial landmarks are very sparsely distributed. Furthermore, we study the impact of training data imbalance on model performance and propose a training sample augmentation scheme that produces more initialisations for training samples from the minority. More specifically, the augmentation number for a training sample is made to be negatively correlated to the value of the fitted probability density function at the sample's position. We evaluate the proposed scheme on both human and sheep facial landmarks localisation. On the benchmark 300w human face dataset, we demonstrate the benefits of our proposed methods and show very competitive performance when comparing to other methods. On a newly created sheep face dataset, we get very good performance despite the fact that we only have a limited number of training samples and a set of sparse landmarks are annotated.
The effect of randomness for dependency map on the robustness of interdependent lattices
Venue: arXiv cs.SI 2015
Year: 2015

For interdependent networks with identity dependency map, percolation is exactly the same with that on a single network and follows a second-order phase transition, while for random dependency, percolation follows a first-order phase transition. In real networks, the dependency relations between networks are neither identical nor completely random. Thus in this paper, we study the influence of randomness for dependency maps on the robustness of interdependent lattice networks. We introduce approximate entropy($ApEn$) as the measure of randomness of the dependency maps. We find that there is critical $ApEn_c$ below which the percolation is continuous, but for larger $ApEn$, it is a first-order transition. With the increment of $ApEn$, the $p_c$ increases until $ApEn$ reaching ${ApEn}_c'$ and then remains almost constant. The time scale of the system shows rich properties as $ApEn$ increases. Our results uncover that randomness is one of the important factors that lead to cascading failures of spatially interdependent networks.
Some Theorems for Feed Forward Neural Networks
Venue: arXiv cs.NE 2015
Year: 2015

In this paper we introduce a new method which employs the concept of "Orientation Vectors" to train a feed forward neural network and suitable for problems where large dimensions are involved and the clusters are characteristically sparse. The new method is not NP hard as the problem size increases. We `derive' the method by starting from Kolmogrov's method and then relax some of the stringent conditions. We show for most classification problems three layers are sufficient and the network size depends on the number of clusters. We prove as the number of clusters increase from N to N+dN the number of processing elements in the first layer only increases by d(logN), and are proportional to the number of classes, and the method is not NP hard. Many examples are solved to demonstrate that the method of Orientation Vectors requires much less computational effort than Radial Basis Function methods and other techniques wherein distance computations are required, in fact the present method increases logarithmically with problem size compared to the Radial Basis Function method and the other methods which depend on distance computations e.g statistical methods where probabilistic distances are calculated. A practical method of applying the concept of Occum's razor to choose between two architectures which solve the same classification problem has been described. The ramifications of the above findings on the field of Deep Learning have also been briefly investigated and we have found that it directly leads to the existence of certain types of NN architectures which can be used as a "mapping engine", which has the property of "invertibility", thus improving the prospect of their deployment for solving problems involving Deep Learning and hierarchical classification. The latter possibility has a lot of future scope in the areas of machine learning and cloud computing.
Improved Residual Vector Quantization for High-dimensional Approximate Nearest Neighbor Search
Venue: arXiv cs.CV 2015
Year: 2015

Quantization methods have been introduced to perform large scale approximate nearest search tasks. Residual Vector Quantization (RVQ) is one of the effective quantization methods. RVQ uses a multi-stage codebook learning scheme to lower the quantization error stage by stage. However, there are two major limitations for RVQ when applied to on high-dimensional approximate nearest neighbor search: 1. The performance gain diminishes quickly with added stages. 2. Encoding a vector with RVQ is actually NP-hard. In this paper, we propose an improved residual vector quantization (IRVQ) method, our IRVQ learns codebook with a hybrid method of subspace clustering and warm-started k-means on each stage to prevent performance gain from dropping, and uses a multi-path encoding scheme to encode a vector with lower distortion. Experimental results on the benchmark datasets show that our method gives substantially improves RVQ and delivers better performance compared to the state-of-the-art.
Extraction of evidence tables from abstracts of randomized clinical trials using a maximum entropy classifier and global constraints
Venue: arXiv cs.CL 2015
Year: 2015

Systematic use of the published results of randomized clinical trials is increasingly important in evidence-based medicine. In order to collate and analyze the results from potentially numerous trials, evidence tables are used to represent trials concerning a set of interventions of interest. An evidence table has columns for the patient group, for each of the interventions being compared, for the criterion for the comparison (e.g. proportion who survived after 5 years from treatment), and for each of the results. Currently, it is a labour-intensive activity to read each published paper and extract the information for each field in an evidence table. There have been some NLP studies investigating how some of the features from papers can be extracted, or at least the relevant sentences identified. However, there is a lack of an NLP system for the systematic extraction of each item of information required for an evidence table. We address this need by a combination of a maximum entropy classifier, and integer linear programming. We use the later to handle constraints on what is an acceptable classification of the features to be extracted. With experimental results, we demonstrate substantial advantages in using global constraints (such as the features describing the patient group, and the interventions, must occur before the features describing the results of the comparison).
Hand-held Video Deblurring via Efficient Fourier Aggregation
Venue: arXiv cs.CV 2015
Year: 2015

Videos captured with hand-held cameras often suffer from a significant amount of blur, mainly caused by the inevitable natural tremor of the photographer's hand. In this work, we present an algorithm that removes blur due to camera shake by combining information in the Fourier domain from nearby frames in a video. The dynamic nature of typical videos with the presence of multiple moving objects and occlusions makes this problem of camera shake removal extremely challenging, in particular when low complexity is needed. Given an input video frame, we first create a consistent registered version of temporally adjacent frames. Then, the set of consistently registered frames is block-wise fused in the Fourier domain with weights depending on the Fourier spectrum magnitude. The method is motivated from the physiological fact that camera shake blur has a random nature and therefore, nearby video frames are generally blurred differently. Experiments with numerous videos recorded in the wild, along with extensive comparisons, show that the proposed algorithm achieves state-of-the-art results while at the same time being much faster than its competitors.
Sync-and-Burst: Force-Directed Graph Drawing with Uniform Force Magnitudes
Venue: arXiv cs.CG 2015
Year: 2015

We introduce a force-directed algorithm, called Sync-and-Burst, which falls into the category of classical force-directed graph drawing algorithms. A distinct feature in Sync-and-Burst is the use of simplified forces of attraction and repulsion whose magnitude does not depend on the distance between vertices. Instead, magnitudes are uniform throughout the graph at each iteration and monotonically increase as the number of iterations grows. The Sync-and-Burst layouts are always circular in shape with relatively even distribution of vertices throughout the drawing area. We demonstrate that aesthetically pleasing layouts are achieved in O(n) iterations.
Deep Multi-task Learning for Railway Track Inspection
Venue: arXiv cs.CV 2015
Year: 2015

Railroad tracks need to be periodically inspected and monitored to ensure safe transportation. Automated track inspection using computer vision and pattern recognition methods have recently shown the potential to improve safety by allowing for more frequent inspections while reducing human errors. Achieving full automation is still very challenging due to the number of different possible failure modes as well as the broad range of image variations that can potentially trigger false alarms. Also, the number of defective components is very small, so not many training examples are available for the machine to learn a robust anomaly detector. In this paper, we show that detection performance can be improved by combining multiple detectors within a multi-task learning framework. We show that this approach results in better accuracy in detecting defects on railway ties and fasteners.
Humans Are Easily Fooled by Digital Images
Venue: arXiv cs.GR 2015
Year: 2015

Digital images are ubiquitous in our modern lives, with uses ranging from social media to news, and even scientific papers. For this reason, it is crucial evaluate how accurate people are when performing the task of identify doctored images. In this paper, we performed an extensive user study evaluating subjects capacity to detect fake images. After observing an image, users have been asked if it had been altered or not. If the user answered the image has been altered, he had to provide evidence in the form of a click on the image. We collected 17,208 individual answers from 383 users, using 177 images selected from public forensic databases. Different from other previously studies, our method propose different ways to avoid lucky guess when evaluating users answers. Our results indicate that people show inaccurate skills at differentiating between altered and non-altered images, with an accuracy of 58%, and only identifying the modified images 46.5% of the time. We also track user features such as age, answering time, confidence, providing deep analysis of how such variables influence on the users' performance.
Iteration Algebras for UnQL Graphs and Completeness for Bisimulation
Venue: arXiv cs.LO 2015
Year: 2015

This paper shows an application of Bloom and Esik's iteration algebras to model graph data in a graph database query language. About twenty years ago, Buneman et al. developed a graph database query language UnQL on the top of a functional meta-language UnCAL for describing and manipulating graphs. Recently, the functional programming community has shown renewed interest in UnCAL, because it provides an efficient graph transformation language which is useful for various applications, such as bidirectional computation. However, no mathematical semantics of UnQL/UnCAL graphs has been developed. In this paper, we give an equational axiomatisation and algebraic semantics of UnCAL graphs. The main result of this paper is to prove that completeness of our equational axioms for UnCAL for the original bisimulation of UnCAL graphs via iteration algebras. Another benefit of algebraic semantics is a clean characterisation of structural recursion on graphs using free iteration algebra.
Mutual Information as Privacy-Loss Measure in Strategic Communication
Venue: arXiv cs.GT 2015
Year: 2015

A game is introduced to study the effect of privacy in strategic communication between well-informed senders and a receiver. The receiver wants to accurately estimate a random variable. The sender, however, wants to communicate a message that balances a trade-off between providing an accurate measurement and minimizing the amount of leaked private information, which is assumed to be correlated with the to-be-estimated variable. The mutual information between the transmitted message and the private information is used as a measure of the amount of leaked information. An equilibrium is constructed and its properties are investigated.
Color-Stripe Structured Light Robust to Surface Color and Discontinuity
Venue: arXiv cs.CV 2015
Year: 2015

Multiple color stripes have been employed for structured light-based rapid range imaging to increase the number of uniquely identifiable stripes. The use of multiple color stripes poses two problems: (1) object surface color may disturb the stripe color and (2) the number of adjacent stripes required for identifying a stripe may not be maintained near surface discontinuities such as occluding boundaries. In this paper, we present methods to alleviate those problems. Log-gradient filters are employed to reduce the influence of object colors, and color stripes in two and three directions are used to increase the chance of identifying correct stripes near surface discontinuities. Experimental results demonstrate the effectiveness of our methods.
Gray coding planar maps
Venue: arXiv cs.DM 2015
Year: 2015

The idea of (combinatorial) Gray codes is to list objects in question in such a way that two successive objects differ in some pre-specified small way. In this paper, we utilize beta-description trees to cyclicly Gray code three classes of cubic planar maps, namely, bicubic planar maps, 3-connected cubic planar maps, and cubic non-separable planar maps.
The Incorrect Usage of Propositional Logic in Game Theory: The Case of Disproving Oneself
Venue: arXiv cs.GT 2015
Year: 2015

Recently, we had to realize that more and more game theoretical articles have been published in peer-reviewed journals with severe logical deficiencies. In particular, we observed that the indirect proof was not applied correctly. These authors confuse between statements of propositional logic. They apply an indirect proof while assuming a prerequisite in order to get a contradiction. For instance, to find out that "if A then B" is valid, they suppose that the assumptions "A and not B" are valid to derive a contradiction in order to deduce "if A then B". Hence, they want to establish the equivalent proposition "A and not B implies A and not A" to conclude that "if A then B" is valid. In fact, they prove that a truth implies a falsehood, which is a wrong statement. As a consequence, "if A then B" is invalid, disproving their own results. We present and discuss some selected cases from the literature with severe logical flaws, invalidating the articles.
Complexity Analysis of CSMA Scheduling via Dependencies Matrix
Venue: arXiv cs.IT 2015
Year: 2015

The complexity of a CSMA algorithm has been translated to the norm properties of a dependencies matrix. The maximum throughput optimization is reformulated by including the dependencies matrix in the formulations. It has been shown that for the interference graphs $\mathcal{G}$ that have minimum vertex cover size $\mathcal{C}(\mathcal{G})=\log n$ where $n$ is the number of the links, the optimal strategy of the links is to transmit with the probability 1, i.e a service-rate agnostic approach. Several numerical analyses have been conducted in order to illustrate the effect of the interference graph, transmission strategy and arrival rate on the dependencies matrix.
Multi-Objective Beamforming for Energy-Efficient SWIPT Systems
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we study the resource allocation algorithm design for energy-efficient simultaneous wireless information and power transfer (SWIPT) systems. The considered system comprises a transmitter, an information receiver, and multiple energy harvesting receivers equipped with multiple antennas. We propose a multi-objective optimization framework to study the trade-off between the maximization of the energy efficiency of information transmission and the maximization of wireless power transfer efficiency. The proposed problem formulation takes into account the per antenna circuit power consumption of the transmitter and the imperfect channel state information of the energy harvesting receivers. The adopted non-convex multi-objective optimization problem is transformed into an equivalent rank-constrained semidefinite program (SDP) and optimally solved by SDP relaxation. Numerical results unveil an interesting trade-off between the considered conflicting system design objectives and reveal the benefits of multiple transmit antennas for improving system energy efficiency.
Capacity and Expressiveness of Genomic Tandem Duplication
Venue: arXiv cs.IT 2015
Year: 2015

The majority of the human genome consists of repeated sequences. An important type of repeated sequences common in the human genome are tandem repeats, where identical copies appear next to each other. For example, in the sequence $AGTC\underline{TGTG}C$, $TGTG$ is a tandem repeat, that may be generated from $AGTCTGC$ by a tandem duplication of length $2$. In this work, we investigate the possibility of generating a large number of sequences from a \textit{seed}, i.e.\ a small initial string, by tandem duplications of bounded length. We study the capacity of such a system, a notion that quantifies the system's generating power. Our results include \textit{exact capacity} values for certain tandem duplication string systems. In addition, motivated by the role of DNA sequences in expressing proteins via RNA and the genetic code, we define the notion of the \textit{expressiveness} of a tandem duplication system as the capability of expressing arbitrary substrings. We then \textit{completely} characterize the expressiveness of tandem duplication systems for general alphabet sizes and duplication lengths. In particular, based on a celebrated result by Axel Thue from 1906, presenting a construction for ternary square-free sequences, we show that for alphabets of size 4 or larger, bounded tandem duplication systems, regardless of the seed and the bound on duplication length, are not fully expressive, i.e. they cannot generate all strings even as substrings of other strings. Note that the alphabet of size 4 is of particular interest as it pertains to the genomic alphabet. Building on this result, we also show that these systems do not have full capacity. In general, our results illustrate that duplication lengths play a more significant role than the seed in generating a large number of sequences for these systems.
A linear approximation algorithm for the BPP with the best possible absolute approximation ratio
Venue: arXiv cs.DS 2015
Year: 2015

The Bin Packing Problem is one of the most important Combinatorial Optimization problems in optimization and has a lot of real-world applications. Many approximation algorithms have been presented for this problem because of its NP-hard nature. In this article also a new creative approximation algorithm is presented for this important problem. It has been proven that the best approximation ratio and the best time order for the Bin Packing Problem are 3/2 and O(n), respectively unless P=NP. The presented algorithm in this article has the best possible factors, O(n) and 3/2.
Perfect Numbers in ACL2
Venue: arXiv cs.LO 2015
Year: 2015

A perfect number is a positive integer n such that n equals the sum of all positive integer divisors of n that are less than n. That is, although n is a divisor of n, n is excluded from this sum. Thus 6 = 1 + 2 + 3 is perfect, but 12 < 1 + 2 + 3 + 4 + 6 is not perfect. An ACL2 theory of perfect numbers is developed and used to prove, in ACL2(r), this bit of mathematical folklore: Even if there are infinitely many perfect numbers the series of the reciprocals of all perfect numbers converges.
A New Storage Optimized Honeyword Generation Approach for Enhancing Security and Usability
Venue: arXiv cs.CR 2015
Year: 2015

Inverting the hash values by performing brute force computation is one of the latest security threats on password based authentication technique. New technologies are being developed for brute force computation and these increase the success rate of inversion attack. Honeyword base authentication protocol can successfully mitigate this threat by making password cracking detectable. However, the existing schemes have several limitations like Multiple System Vulnerability, Weak DoS Resistivity, Storage Overhead, etc. In this paper we have proposed a new honeyword generation approach, identified as Paired Distance Protocol (PDP) which overcomes almost all the drawbacks of previously proposed honeyword generation approaches. The comprehensive analysis shows that PDP not only attains a high detection rate of 97.23% but also reduces the storage cost to a great extent.
Noise Robust IOA/CAS Speech Separation and Recognition System For The Third 'CHIME' Challenge
Venue: arXiv cs.SD 2015
Year: 2015

This paper presents the contribution to the third 'CHiME' speech separation and recognition challenge including both front-end signal processing and back-end speech recognition. In the front-end, Multi-channel Wiener filter (MWF) is designed to achieve background noise reduction. Different from traditional MWF, optimized parameter for the tradeoff between noise reduction and target signal distortion is built according to the desired noise reduction level. In the back-end, several techniques are taken advantage to improve the noisy Automatic Speech Recognition (ASR) performance including Deep Neural Network (DNN), Convolutional Neural Network (CNN) and Long short-term memory (LSTM) using medium vocabulary, Lattice rescoring with a big vocabulary language model finite state transducer, and ROVER scheme. Experimental results show the proposed system combining front-end and back-end is effective to improve the ASR performance.