OpenRaiser/Intern-Atlas huggingface dataset:
Occupational Fraud Detection Through Visualization
Venue: arXiv cs.CY 2013
Year: 2013

Occupational fraud affects many companies worldwide causing them economic loss and liability issues towards their customers and other involved entities. Detecting internal fraud in a company requires significant effort and, unfortunately cannot be entirely prevented. The internal auditors have to process a huge amount of data produced by diverse systems, which are in most cases in textual form, with little automated support. In this paper, we exploit the advantages of information visualization and present a system that aims to detect occupational fraud in systems which involve a pair of entities (e.g., an employee and a client) and periodic activity. The main visualization is based on a spiral system on which the events are drawn appropriately according to their time-stamp. Suspicious events are considered those which appear along the same radius or on close radii of the spiral. Before producing the visualization, the system ranks both involved entities according to the specifications of the internal auditor and generates a video file of the activity such that events with strong evidence of fraud appear first in the video. The system is also equipped with several different visualizations and mechanisms in order to meet the requirements of an internal fraud detection system.
Nonanticipative Rate Distortion Function for General Source-Channel Matching
Venue: arXiv cs.IT 2013
Year: 2013

In this paper we invoke a nonanticipative information Rate Distortion Function (RDF) for sources with memory, and we analyze its importance in probabilistic matching of the source to the channel so that transmission of a symbol-by-symbol code with memory without anticipation is optimal, with respect to an average distortion and excess distortion probability. We show achievability of the symbol-by-symbol code with memory without anticipation, and we evaluate the probabilistic performance of the code for a Markov source.
Performance Analysis of Protograph LDPC Codes for Nakagami-$m$ Fading Relay Channels
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we investigate the error performance of the protograph (LDPC) codes over Nakagami-$m$ fading relay channels. We first calculate the decoding thresholds of the protograph codes over such channels with different fading depths (i.e., different values of $m$) by exploiting the modified protograph extrinsic information transfer (PEXIT) algorithm. Furthermore, based on the PEXIT analysis and using Gaussian approximation, we derive the bit-error-rate (BER) expressions for the error-free (EF) relaying protocol and decode-and-forward (DF) relaying protocol. We finally compare the threshold with the theoretical BER and the simulated BER results of the protograph codes. It reveals that the performance of DF protocol is approximately the same as that of EF protocol. Moreover, the theoretical BER expressions, which are shown to be reasonably consistent with the decoding thresholds and the simulated BERs, are able to evaluate the system performance and predict the decoding threshold with lower complexity as compared to the modified PEXIT algorithm. As a result, this work can facilitate the design of the protograph codes for the wireless communication systems.
Clustering Consumption in Queues: A Scalable Model for Electric Vehicle Scheduling
Venue: arXiv cs.SY 2013
Year: 2013

In this paper, we introduce a scalable model for the aggregate electricity demand of a fleet of electric vehicles, which can provide the right balance between model simplicity and accuracy. The model is based on classification of tasks with similar energy consumption characteristics into a finite number of clusters. The aggregator responsible for scheduling the charge of the vehicles has two goals: 1) to provide a hard QoS guarantee to the vehicles at the lowest possible cost; 2) to offer load or generation following services to the wholesale market. In order to achieve these goals, we combine the scalable demand model we propose with two scheduling mechanisms, a near-optimal and a heuristic technique. The performance of the two mechanisms is compared under a realistic setting in our numerical experiments.
Inference and learning in probabilistic logic programs using weighted Boolean formulas
Venue: arXiv cs.AI 2013
Year: 2013

Probabilistic logic programs are logic programs in which some of the facts are annotated with probabilities. This paper investigates how classical inference and learning tasks known from the graphical model community can be tackled for probabilistic logic programs. Several such tasks such as computing the marginals given evidence and learning from (partial) interpretations have not really been addressed for probabilistic logic programs before. The first contribution of this paper is a suite of efficient algorithms for various inference tasks. It is based on a conversion of the program and the queries and evidence to a weighted Boolean formula. This allows us to reduce the inference tasks to well-studied tasks such as weighted model counting, which can be solved using state-of-the-art methods known from the graphical model and knowledge compilation literature. The second contribution is an algorithm for parameter estimation in the learning from interpretations setting. The algorithm employs Expectation Maximization, and is built on top of the developed inference algorithms. The proposed approach is experimentally evaluated. The results show that the inference algorithms improve upon the state-of-the-art in probabilistic logic programming and that it is indeed possible to learn the parameters of a probabilistic logic program from interpretations.
Maximum Matching and Linear Programming in Fixed-Point Logic with Counting
Venue: arXiv cs.LO 2013
Year: 2013

We establish the expressibility in fixed-point logic with counting (FPC) of a number of natural polynomial-time problems. In particular, we show that the size of a maximum matching in a graph is definable in FPC. This settles an open problem first posed by Blass, Gurevich and Shelah, who asked whether the existence of perfect matchings in general graphs could be determined in the more powerful formalism of choiceless polynomial time with counting. Our result is established by showing that the ellipsoid method for solving linear programs can be implemented in FPC. This allows us to prove that linear programs can be optimised in FPC if the corresponding separation oracle problem can be defined in FPC. On the way to defining a suitable separation oracle for the maximum matching problem, we provide FPC formulas defining maximum flows and canonical minimum cuts in capacitated graphs.
Security Issues In Speech Watermarking for Information Transmission
Venue: arXiv cs.MM 2013
Year: 2013

The secure transmission of speech information is a significant issue faced by many security professionals and individuals. By applying voice-encryption technique any kind of encrypted sensitive speech data such as password can be transmitted. But this has the serious disadvantage that by means of cryptanalysis attack encrypted data can be compromised. Increasing the strength of encryption/decryption results in an associated increased in the cost. Additional techniques like stenography and digital watermarking can be used to conceal information in an undetectable way in audio data. However this watermarked audio data has to be send through unreliable media and an eavesdropper might get hold of secret message and can also determine the identity of a speaker who is sending the information since human voice contains information based on its characteristics such as frequency, pitch, and energy. This paper proposes Normalized Speech Watermarking technique. Speech signal is normalized to hide the identity of the speaker who is sending the information and then speech watermarking technique is applied on this normalized signal that contains the message (password) so that what information is transmitted should not be unauthorizedly revealed.
Digit Recognition in Handwritten Weather Records
Venue: arXiv cs.CV 2013
Year: 2013

This paper addresses the automatic recognition of handwritten temperature values in weather records. The localization of table cells is based on line detection using projection profiles. Further, a stroke-preserving line removal method which is based on gradient images is proposed. The presented digit recognition utilizes features which are extracted using a set of filters and a Support Vector Machine classifier. It was evaluated on the MNIST and the USPS dataset and our own database with about 17,000 RGB digit images. An accuracy of 99.36% per digit is achieved for the entire system using a set of 84 weather records.
Batched Kronecker product for 2-D matrices and 3-D arrays on NVIDIA GPUs
Venue: arXiv cs.MS 2013
Year: 2013

We describe an interface and an implementation for performing Kronecker product actions on NVIDIA GPUs for multiple small 2-D matrices and 3-D arrays processed in parallel as a batch. This method is suited to cases where the Kronecker product component matrices are identical but the operands in a matrix-free application vary in the batch. Any batched GEMM (General Matrix Multiply) implementation, for example ours [1] or the one in cuBLAS, can also be used for performing batched Kronecker products on GPUs. However, the specialized implementation presented here is faster and uses less memory. Partly this is because a simple GEMM based approach would require extra copies to and from main memory. We focus on matrix sizes less than or equal to 16, since these are the typical polynomial degrees in Finite Elements, but the implementation can be easily extended for other sizes. We obtain 143 and 285 GFlop/s for single precision real when processing matrices of size 10 and 16, respectively on NVIDIA Tesla K20c using CUDA 5.0. The corresponding speeds for 3-D array Kronecker products are 126 and 268 GFlop/s, respectively. Double precision is easily supported using the C++ template mechanism.
Stochastic Cellular Automata: Correlations, Decidability and Simulations
Venue: arXiv cs.DM 2013
Year: 2013

This paper introduces a simple formalism for dealing with deterministic, non- deterministic and stochastic cellular automata in an unified and composable manner. This formalism allows for local probabilistic correlations, a feature which is not present in usual definitions. We show that this feature allows for strictly more behaviors (for instance, number conserving stochastic cellular automata require these local probabilistic correlations). We also show that several problems which are deceptively simple in the usual definitions, become undecidable when we allow for local probabilistic correlations, even in dimension one. Armed with this formalism, we extend the notion of intrinsic simulation between deterministic cellular automata, to the non-deterministic and stochas- tic settings. Although the intrinsic simulation relation is shown to become undecidable in dimension two and higher, we provide explicit tools to prove or disprove the existence of such a simulation between any two given stochastic cellular automata. Those tools rely upon a characterization of equality of stochastic global maps, shown to be equivalent to the existence of a stochastic coupling between the random sources. We apply them to prove that there is no universal stochastic cellular automaton. Yet we provide stochastic cellular automata achieving optimal partial universality, as well as a universal non-deterministic cellular automaton.
Correction of inertial navigation system's errors by the help of video-based navigator based on Digital Terrarium Map
Venue: arXiv cs.SY 2013
Year: 2013

This paper deals with the error analysis of a novel navigation algorithm that uses as input the sequence of images acquired from a moving camera and a Digital Terrain (or Elevation) Map (DTM/DEM). More specifically, it has been shown that the optical flow derived from two consecutive camera frames can be used in combination with a DTM to estimate the position, orientation and ego-motion parameters of the moving camera. As opposed to previous works, the proposed approach does not require an intermediate explicit reconstruction of the 3D world. In the present work the sensitivity of the algorithm outlined above is studied. The main sources for errors are identified to be the optical-flow evaluation and computation, the quality of the information about the terrain, the structure of the observed terrain and the trajectory of the camera. By assuming appropriate characterization of these error sources, a closed form expression for the uncertainty of the pose and motion of the camera is first developed and then the influence of these factors is confirmed using extensive numerical simulations. The main conclusion of this paper is to establish that the proposed navigation algorithm generates accurate estimates for reasonable scenarios and error sources, and thus can be effectively used as part of a navigation system of autonomous vehicles.
Robust Belief Roadmap: Planning Under Intermittent Sensing
Venue: arXiv cs.RO 2013
Year: 2013

In this paper, we extend the recent body of work on planning under uncertainty to include the fact that sensors may not provide any measurement owing to misdetection. This is caused either by adverse environmental conditions that prevent the sensors from making measurements or by the fundamental limitations of the sensors. Examples include RF-based ranging devices that intermittently do not receive the signal from beacons because of obstacles; the misdetection of features by a camera system in detrimental lighting conditions; a LIDAR sensor that is pointed at a glass-based material such as a window, etc. The main contribution of this paper is twofold. We first show that it is possible to obtain an analytical bound on the performance of a state estimator under sensor misdetection occurring stochastically over time in the environment. We then show how this bound can be used in a sample-based path planning algorithm to produce a path that trades off accuracy and robustness. Computational results demonstrate the benefit of the approach and comparisons are made with the state of the art in path planning under state uncertainty.
On Adaptive Control with Closed-loop Reference Models: Transients, Oscillations, and Peaking
Venue: arXiv cs.SY 2013
Year: 2013

One of the main features of adaptive systems is an oscillatory convergence that exacerbates with the speed of adaptation. Recently it has been shown that Closed-loop Reference Models (CRMs) can result in improved transient performance over their open-loop counterparts in model reference adaptive control. In this paper, we quantify both the transient performance in the classical adaptive systems and their improvement with CRMs. In addition to deriving bounds on L-2 norms of the derivatives of the adaptive parameters which are shown to be smaller, an optimal design of CRMs is proposed which minimizes an underlying peaking phenomenon. The analytical tools proposed are shown to be applicable for a range of adaptive control problems including direct control and composite control with observer feedback. The presence of CRMs in adaptive backstepping and adaptive robot control are also discussed. Simulation results are presented throughout the paper to support the theoretical derivations.
Improved Capacity Approximations for Gaussian Relay Networks
Venue: arXiv cs.IT 2013
Year: 2013

Consider a Gaussian relay network where a number of sources communicate to a destination with the help of several layers of relays. Recent work has shown that a compress-and-forward based strategy at the relays can achieve the capacity of this network within an additive gap. In this strategy, the relays quantize their observations at the noise level and map it to a random Gaussian codebook. The resultant capacity gap is independent of the SNR's of the channels in the network but linear in the total number of nodes. In this paper, we show that if the relays quantize their signals at a resolution decreasing with the number of nodes in the network, the additive gap to capacity can be made logarithmic in the number of nodes for a class of layered, time-varying wireless relay networks. This suggests that the rule-of-thumb to quantize the received signals at the noise level used for compress-and-forward in the current literature can be highly suboptimal.
Attacks and Countermeasures in Fingerprint Based Biometric Cryptosystems
Venue: arXiv cs.CR 2013
Year: 2013

We investigate implementations of biometric cryptosystems protecting fingerprint templates (which are mostly based on the fuzzy vault scheme by Juels and Sudan in 2002) with respect to the security they provide. We show that attacks taking advantage of the system's false acceptance rate, i.e. false-accept attacks, pose a very serious risk --- even if brute-force attacks are impractical to perform. Our observations lead to the clear conclusion that currently a single fingerprint is not sufficient to provide a secure biometric cryptosystem. But there remain other problems that can not be resolved by merely switching to multi-finger: Kholmatov and Yanikoglu in 2007 demonstrated that it is possible to break two matching vault records at quite a high rate via the correlation attack. We propose an implementation of a minutiae fuzzy vault that is inherently resistant against cross-matching and the correlation attack. Surprisingly, achieving cross-matching resistance is not at the cost of authentication performance. In particular, we propose to use a randomized decoding procedure and find that it is possible to achieve a GAR=91% at which no false accepts are observed on a database generally used. Our ideas can be adopted into an implementation of a multibiometric cryptosystem. All experiments described in this paper can fully be reproduced using software available for download.
A Universal Grammar-Based Code For Lossless Compression of Binary Trees
Venue: arXiv cs.IT 2013
Year: 2013

We consider the problem of lossless compression of binary trees, with the aim of reducing the number of code bits needed to store or transmit such trees. A lossless grammar-based code is presented which encodes each binary tree into a binary codeword in two steps. In the first step, the tree is transformed into a context-free grammar from which the tree can be reconstructed. In the second step, the context-free grammar is encoded into a binary codeword. The decoder of the grammar-based code decodes the original tree from its codeword by reversing the two encoding steps. It is shown that the resulting grammar-based binary tree compression code is a universal code on a family of probabilistic binary tree source models satisfying certain weak restrictions.
Sybil-proof Mechanisms in Query Incentive Networks
Venue: arXiv cs.GT 2013
Year: 2013

In this paper, we study incentive mechanisms for retrieving information from networked agents. Following the model in [Kleinberg and Raghavan 2005], the agents are represented as nodes in an infinite tree, which is generated by a random branching process. A query is issued by the root, and each node possesses an answer with an independent probability $p=1/n$. Further, each node in the tree acts strategically to maximize its own payoff. In order to encourage the agents to participate in the information acquisition process, an incentive mechanism is needed to reward agents who provide the information as well as agents who help to facilitate such acquisition. We focus on designing efficient sybil-proof incentive mechanisms, i.e., which are robust to fake identity attacks. %We consider incentive mechanisms which are sybil-proof, i.e., robust to fake identity attacks. We propose a family of mechanisms, called the direct referral (DR) mechanisms, which allocate most reward to the information holder as well as its direct parent (or direct referral). We show that, when designed properly, the direct referral mechanism is sybil-proof and efficient. In particular, we show that we may achieve an expected cost of $O(h^2)$ for propagating the query down $h$ levels for any branching factor $b>1$. This result exponentially improves on previous work when requiring to find an answer with high probability. When the underlying network is a deterministic chain, our mechanism is optimal under some mild assumptions. In addition, due to its simple reward structure, the DR mechanism might have good chance to be adopted in practice.
Statistical characterization of kappa-mu shadowed fading
Venue: arXiv cs.IT 2013
Year: 2013

This paper investigates a natural generalization of the kappa-mu fading channel in which the line-of-sight (LOS) component is subject to shadowing. This fading distribution has a clear physical interpretation, good analytical properties and unifies the one-side Gaussian, Rayleigh, Nakagami-m, Ricean, kappa-mu and Ricean shadowed fading distributions. The three basic statistical characterizations, i.e. probability density function (PDF), cumulative distribution function (CDF) and moment generating function (MGF), of the kappa-mu shadowed distribution are obtained in closed-form. Then, it is also shown that the sum and maximum distributions of independent but arbitrarily distributed kappa-mu shadowed variates can be expressed in closed-form. This set of new statistical results is finally applied to the performance analysis of several wireless communication systems.
Non-positive curvature, and the planar embedding conjecture
Venue: arXiv cs.CG 2013
Year: 2013

The planar embedding conjecture asserts that any planar metric admits an embedding into L_1 with constant distortion. This is a well-known open problem with important algorithmic implications, and has received a lot of attention over the past two decades. Despite significant efforts, it has been verified only for some very restricted cases, while the general problem remains elusive. In this paper we make progress towards resolving this conjecture. We show that every planar metric of non-positive curvature admits a constant-distortion embedding into L_1. This confirms the planar embedding conjecture for the case of non-positively curved metrics.
Improved Approximation Algorithms for (Budgeted) Node-weighted Steiner Problems
Venue: arXiv cs.DS 2013
Year: 2013

Moss and Rabani[12] study constrained node-weighted Steiner tree problems with two independent weight values associated with each node, namely, cost and prize (or penalty). They give an O(log n)-approximation algorithm for the prize-collecting node-weighted Steiner tree problem (PCST). They use the algorithm for PCST to obtain a bicriteria (2, O(log n))-approximation algorithm for the Budgeted node-weighted Steiner tree problem. Their solution may cost up to twice the budget, but collects a factor Omega(1/log n) of the optimal prize. We improve these results from at least two aspects. Our first main result is a primal-dual O(log h)-approximation algorithm for a more general problem, prize-collecting node-weighted Steiner forest, where we have (h) demands each requesting the connectivity of a pair of vertices. Our algorithm can be seen as a greedy algorithm which reduces the number of demands by choosing a structure with minimum cost-to-reduction ratio. This natural style of argument (also used by Klein and Ravi[10] and Guha et al.[8]) leads to a much simpler algorithm than that of Moss and Rabani[12] for PCST. Our second main contribution is for the Budgeted node-weighted Steiner tree problem, which is also an improvement to [12] and [8]. In the unrooted case, we improve upon an O(log^2(n))-approximation of [8], and present an O(log n)-approximation algorithm without any budget violation. For the rooted case, where a specified vertex has to appear in the solution tree, we improve the bicriteria result of [12] to a bicriteria approximation ratio of (1+eps, O(log n)/(eps^2)) for any positive (possibly subconstant) (eps). That is, for any permissible budget violation (1+eps), we present an algorithm achieving a tradeoff in the guarantee for prize. Indeed, we show that this is almost tight for the natural linear-programming relaxation used by us as well as in [12].