OpenRaiser/Intern-Atlas huggingface dataset:
Using Tree-Decomposable Structures to Approximate Belief Networks
Venue: arXiv cs.AI 2013
Year: 2013

Tree structures have been shown to provide an efficient framework for propagating beliefs [Pearl,1986]. This paper studies the problem of finding an optimal approximating tree. The star decomposition scheme for sets of three binary variables [Lazarsfeld,1966; Pearl,1986] is shown to enhance the class of probability distributions that can support tree structures; such structures are called tree-decomposable structures. The logarithm scoring rule is found to be an appropriate optimality criterion to evaluate different tree-decomposable structures. Characteristics of such structures closest to the actual belief network are identified using the logarithm rule, and greedy and exact techniques are developed to find the optimal approximation.
On reasoning in networks with qualitative uncertainty
Venue: arXiv cs.AI 2013
Year: 2013

In this paper some initial work towards a new approach to qualitative reasoning under uncertainty is presented. This method is not only applicable to qualitative probabilistic reasoning, as is the case with other methods, but also allows the qualitative propagation within networks of values based upon possibility theory and Dempster-Shafer evidence theory. The method is applied to two simple networks from which a large class of directed graphs may be constructed. The results of this analysis are used to compare the qualitative behaviour of the three major quantitative uncertainty handling formalisms, and to demonstrate that the qualitative integration of the formalisms is possible under certain assumptions.
Discounting and Combination Operations in Evidential Reasoning
Venue: arXiv cs.AI 2013
Year: 2013

Evidential reasoning is now a leading topic in Artificial Intelligence. Evidence is represented by a variety of evidential functions. Evidential reasoning is carried out by certain kinds of fundamental operation on these functions. This paper discusses two of the basic operations on evidential functions, the discount operation and the well-known orthogonal sum operation. We show that the discount operation is not commutative with the orthogonal sum operation, and derive expressions for the two operations applied to the various evidential function.
Inference with Possibilistic Evidence
Venue: arXiv cs.AI 2013
Year: 2013

In this paper, the concept of possibilistic evidence which is a possibility distribution as well as a body of evidence is proposed over an infinite universe of discourse. The inference with possibilistic evidence is investigated based on a unified inference framework maintaining both the compatibility of concepts and the consistency of the probability logic.
On Robust Face Recognition via Sparse Encoding: the Good, the Bad, and the Ugly
Venue: arXiv cs.CV 2013
Year: 2013

In the field of face recognition, Sparse Representation (SR) has received considerable attention during the past few years. Most of the relevant literature focuses on holistic descriptors in closed-set identification applications. The underlying assumption in SR-based methods is that each class in the gallery has sufficient samples and the query lies on the subspace spanned by the gallery of the same class. Unfortunately, such assumption is easily violated in the more challenging face verification scenario, where an algorithm is required to determine if two faces (where one or both have not been seen before) belong to the same person. In this paper, we first discuss why previous attempts with SR might not be applicable to verification problems. We then propose an alternative approach to face verification via SR. Specifically, we propose to use explicit SR encoding on local image patches rather than the entire face. The obtained sparse signals are pooled via averaging to form multiple region descriptors, which are then concatenated to form an overall face descriptor. Due to the deliberate loss spatial relations within each region (caused by averaging), the resulting descriptor is robust to misalignment & various image deformations. Within the proposed framework, we evaluate several SR encoding techniques: l1-minimisation, Sparse Autoencoder Neural Network (SANN), and an implicit probabilistic technique based on Gaussian Mixture Models. Thorough experiments on AR, FERET, exYaleB, BANCA and ChokePoint datasets show that the proposed local SR approach obtains considerably better and more robust performance than several previous state-of-the-art holistic SR methods, in both verification and closed-set identification problems. The experiments also show that l1-minimisation based encoding has a considerably higher computational than the other techniques, but leads to higher recognition rates.
Testing Mutual Duality of Planar Graphs
Venue: arXiv cs.DS 2013
Year: 2013

We introduce and study the problem \mpd, which asks for two planar graphs $G_1$ and $G_2$ whether $G_1$ can be embedded such that its dual is isomorphic to $G_2$. Our algorithmic main result is an NP-completeness proof for the general case and a linear-time algorithm for biconnected graphs. To shed light onto the combinatorial structure of the duals of a planar graph, we consider the \emph{common dual relation} $\sim$, where $G_1 \sim G_2$ if and only if they have a common dual. While $\sim$ is generally not transitive, we show that the restriction to biconnected graphs is an equivalence relation. In this case, being dual to each other carries over to the equivalence classes, i.e., two graphs are dual to each other if and only if any two elements of their respective equivalence classes are dual to each other. To achieve the efficient testing algorithm for \mpd on biconnected graphs, we devise a succinct representation of the equivalence class of a biconnected planar graph. It is similar to SPQR-trees and represents exactly the graphs that are contained in the equivalence class. The testing algorithm then works by testing in linear time whether two such representations are isomorphic. We note that a special case of \mpd is testing whether a graph $G$ is self-dual. Our algorithm handles the case where $G$ is biconnected and our NP-hardness proof extends to testing self-duality of general planar graphs and also to testing map self-duality, where a graph $G$ is map self-dual if it admits a planar embedding $\mathcal G$ such that $G^\star$ is isomorphic to $G$, and additionally the embedding induced by $\mathcal G$ on $G^\star$ is $\mathcal G$.
Another Disjoint Compression Algorithm for OCT
Venue: arXiv cs.DS 2013
Year: 2013

We describe an elegant O*(2^k) algorithm for the disjoint compression problem for Odd Cycle Transversal based on a reduction to Above Guarantee Vertex Cover. We believe that this algorithm refines the understanding of the Odd Cycle Transversal algorithm by Reed, Smith and Vetta.
Exact Conditional and Unconditional Cramèr-Rao Bounds for Near Field Localization
Venue: arXiv cs.CE 2013
Year: 2013

This paper considers the Cramèr-Rao lower Bound (CRB) for the source localization problem in the near field. More specifically, we use the exact expression of the delay parameter for the CRB derivation and show how this exact CRB can be significantly different from the one given in the literature and based on an approximate time delay expression (usually considered in the Fresnel region). This CRB derivation is then generalized by considering the exact expression of the received power profile (i.e., variable gain case) which, to our best knowledge, has been ignored in the literature. Finally, we exploit the CRB expression to introduce the new concept of Near Field Localization (NFL) region for a target localization performance associated to the application at hand. We illustrate the usefulness of the proposed CRB derivation and its developments as well as the NFL region concept through numerical simulations in different scenarios.
Mixing local and global information for community detection in large networks
Venue: arXiv cs.SI 2013
Year: 2013

The problem of clustering large complex networks plays a key role in several scientific fields ranging from Biology to Sociology and Computer Science. Many approaches to clustering complex networks are based on the idea of maximizing a network modularity function. Some of these approaches can be classified as global because they exploit knowledge about the whole network topology to find clusters. Other approaches, instead, can be interpreted as local because they require only a partial knowledge of the network topology, e.g., the neighbors of a vertex. Global approaches are able to achieve high values of modularity but they do not scale well on large networks and, therefore, they cannot be applied to analyze on-line social networks like Facebook or YouTube. In contrast, local approaches are fast and scale up to large, real-life networks, at the cost of poorer results than those achieved by local methods. In this article we propose a glocal method to maximizing modularity, i.e., our method uses information at the global level, yet its scalability on large networks is comparable to that of local methods. The proposed method is called COmplex Network CLUster DEtection (or, shortly, CONCLUDE.) It works in two stages: in the first stage it uses an information-propagation model, based on random and non-backtracking walks of finite length, to compute the importance of each edge in keeping the network connected (called edge centrality.) Then, edge centrality is used to map network vertices onto points of an Euclidean space and to compute distances between all pairs of connected vertices. In the second stage, CONCLUDE uses the distances computed in the first stage to partition the network into clusters. CONCLUDE is computationally efficient since in the average case its cost is roughly linear in the number of edges of the network.
Maximum Possibility Of Spectrum Access In Cognitive Radio Using Fuzzy Logic System
Venue: arXiv cs.NI 2013
Year: 2013

Many spectrum methods have been proposed to use spectrum effectively, the opportunistic spectrum access has become the most viable approach to achieve near-optimal spectrum utilization by allowing secondary users to sense and access available spectrum opportunistically. However, a naive spectrum access for secondary users can make spectrum utilization inefficient and increase interference to adjacent users. In this paper, we propose a novel approach using Fuzzy Logic System (FLS) to control the spectrum access. We have to minimize the call blocking and interference. The linguistic knowledge of spectrum access are based on three descriptors namely spectrum utilization efficiency of the secondary user, its degree of mobility, and its distance to the primary user. The spectrum is chosen for accessing based on the maximum possibility for better utilization of the spectrum
A Novel Measure of Edge Centrality in Social Networks
Venue: arXiv cs.SI 2013
Year: 2013

The problem of assigning centrality values to nodes and edges in graphs has been widely investigated during last years. Recently, a novel measure of node centrality has been proposed, called k-path centrality index, which is based on the propagation of messages inside a network along paths consisting of at most k edges. On the other hand, the importance of computing the centrality of edges has been put into evidence since 1970's by Anthonisse and, subsequently by Girvan and Newman. In this work we propose the generalization of the concept of k-path centrality by defining the k-path edge centrality, a measure of centrality introduced to compute the importance of edges. We provide an efficient algorithm, running in O(k m), being m the number of edges in the graph. Thus, our technique is feasible for large scale network analysis. Finally, the performance of our algorithm is analyzed, discussing the results obtained against large online social network datasets.
Analytical Model of Proportional Fair Scheduling in Interference-limited OFDMA/LTE Networks
Venue: arXiv cs.NI 2013
Year: 2013

Various system tasks like interference coordination, handover decisions, admission control etc. in upcoming cellular networks require precise mid-term (spanning over a few seconds) performance models. Due to channel-dependent scheduling at the base station, these performance models are not simple to obtain. Furthermore, upcoming cellular systems will be interference-limited, hence, the way interference is modeled is crucial for the accuracy. In this paper we present an analytical model for the SINR distribution of the \textit{scheduled} subcarriers of an OFDMA system with proportional fair scheduling. The model takes the precise SINR distribution into account. We furthermore refine our model with respect to uniform modulation and coding, as applied in LTE networks. The derived models are validated by means of simulations. In additon, we show that our models are approximate estimators for the performance of rate-based proportional fair scheduling, while they outperform some simpler prediction models from related work significantly.
Random Subdictionaries and Coherence Conditions for Sparse Signal Recovery
Venue: arXiv cs.IT 2013
Year: 2013

The most frequently used condition for sampling matrices employed in compressive sampling is the restricted isometry (RIP) property of the matrix when restricted to sparse signals. At the same time, imposing this condition makes it difficult to find explicit matrices that support recovery of signals from sketches of the optimal (smallest possible)dimension. A number of attempts have been made to relax or replace the RIP property in sparse recovery algorithms. We focus on the relaxation under which the near-isometry property holds for most rather than for all submatrices of the sampling matrix, known as statistical RIP or StRIP condition. We show that sampling matrices of dimensions $m\times N$ with maximum coherence $μ=O((k\log^3 N)^{-1/4})$ and mean square coherence $\bar μ^2=O(1/(k\log N))$ support stable recovery of $k$-sparse signals using Basis Pursuit. These assumptions are satisfied in many examples. As a result, we are able to construct sampling matrices that support recovery with low error for sparsity $k$ higher than $\sqrt m,$ which exceeds the range of parameters of the known classes of RIP matrices.
On the Minimum Distance of Generalized Spatially Coupled LDPC Codes
Venue: arXiv cs.IT 2013
Year: 2013

Families of generalized spatially-coupled low-density parity-check (GSC-LDPC) code ensembles can be formed by terminating protograph-based generalized LDPC convolutional (GLDPCC) codes. It has previously been shown that ensembles of GSC-LDPC codes constructed from a protograph have better iterative decoding thresholds than their block code counterparts, and that, for large termination lengths, their thresholds coincide with the maximum a-posteriori (MAP) decoding threshold of the underlying generalized LDPC block code ensemble. Here we show that, in addition to their excellent iterative decoding thresholds, ensembles of GSC-LDPC codes are asymptotically good and have large minimum distance growth rates.
Selecting polynomials for the Function Field Sieve
Venue: arXiv cs.CR 2013
Year: 2013

The Function Field Sieve algorithm is dedicated to computing discrete logarithms in a finite field GF(q^n), where q is small an prime power. The scope of this article is to select good polynomials for this algorithm by defining and measuring the size property and the so-called root and cancellation properties. In particular we present an algorithm for rapidly testing a large set of polynomials. Our study also explains the behaviour of inseparable polynomials, in particular we give an easy way to see that the algorithm encompass the Coppersmith algorithm as a particular case.
Energy Efficient MAC Protocols in Wireless Body Area Sensor Networks -A Survey
Venue: arXiv cs.NI 2013
Year: 2013

In this paper, we first presented an analytically discussion about energy efficiency of Medium Access Control (MAC) protocols for Wireless Body Area Sensor Networks (WBASNs). For this purpose, different energy efficient MAC protocols with their respective energy optimization techniques; Low Power Listening (LPL), Scheduled Contention and Time Division Multiple Access (TDMA), are elaborated. We also analytically compared path loss models for In-body, On-body and Off-body communications in WBASNs. These three path loss scenarios are simulated in MATLAB and results shown that path loss is more in In-body communication because of less energy level to take care of tissues and organs located inside human body. Secondly, power model for WBASNs of Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) and beacon mode is also presented. MATLAB simulations results shown that power of CSMA/CA mode is less as compared to beacon mode. Finally, we suggested that hybrid mode is more useful to achieve optimization in power consumption, which consequently results in high energy efficiency.
Classification of Segments in PolSAR Imagery by Minimum Stochastic Distances Between Wishart Distributions
Venue: arXiv cs.CV 2013
Year: 2013

A new classifier for Polarimetric SAR (PolSAR) images is proposed and assessed in this paper. Its input consists of segments, and each one is assigned the class which minimizes a stochastic distance. Assuming the complex Wishart model, several stochastic distances are obtained from the h-phi family of divergences, and they are employed to derive hypothesis test statistics that are also used in the classification process. This article also presents, as a novelty, analytic expressions for the test statistics based on the following stochastic distances between complex Wishart models: Kullback-Leibler, Bhattacharyya, Hellinger, Rényi, and Chi-Square; also, the test statistic based on the Bhattacharyya distance between multivariate Gaussian distributions is presented. The classifier performance is evaluated using simulated and real PolSAR data. The simulated data are based on the complex Wishart model, aiming at the analysis of the proposal well controlled data. The real data refer to the complex L-band image, acquired during the 1994 SIR-C mission. The results of the proposed classifier are compared with those obtained by a Wishart per-pixel/contextual classifier, and we show the better performance of the region-based classification. The influence of the statistical modeling is assessed by comparing the results using the Bhattacharyya distance between multivariate Gaussian distributions for amplitude data. The results with simulated data indicate that the proposed classification method has a very good performance when the data follow the Wishart model. The proposed classifier also performs better than the per-pixel/contextual classifier and the Bhattacharyya Gaussian distance using SIR-C PolSAR data.
Convex Discriminative Multitask Clustering
Venue: arXiv cs.LG 2013
Year: 2013

Multitask clustering tries to improve the clustering performance of multiple tasks simultaneously by taking their relationship into account. Most existing multitask clustering algorithms fall into the type of generative clustering, and none are formulated as convex optimization problems. In this paper, we propose two convex Discriminative Multitask Clustering (DMTC) algorithms to address the problems. Specifically, we first propose a Bayesian DMTC framework. Then, we propose two convex DMTC objectives within the framework. The first one, which can be seen as a technical combination of the convex multitask feature learning and the convex Multiclass Maximum Margin Clustering (M3C), aims to learn a shared feature representation. The second one, which can be seen as a combination of the convex multitask relationship learning and M3C, aims to learn the task relationship. The two objectives are solved in a uniform procedure by the efficient cutting-plane algorithm. Experimental results on a toy problem and two benchmark datasets demonstrate the effectiveness of the proposed algorithms.
Automatic Verification of Erlang-Style Concurrency
Venue: arXiv cs.PL 2013
Year: 2013

This paper presents an approach to verify safety properties of Erlang-style, higher-order concurrent programs automatically. Inspired by Core Erlang, we introduce Lambda-Actor, a prototypical functional language with pattern-matching algebraic data types, augmented with process creation and asynchronous message-passing primitives. We formalise an abstract model of Lambda-Actor programs called Actor Communicating System (ACS) which has a natural interpretation as a vector addition system, for which some verification problems are decidable. We give a parametric abstract interpretation framework for Lambda-Actor and use it to build a polytime computable, flow-based, abstract semantics of Lambda-Actor programs, which we then use to bootstrap the ACS construction, thus deriving a more accurate abstract model of the input program. We have constructed Soter, a tool implementation of the verification method, thereby obtaining the first fully-automatic, infinite-state model checker for a core fragment of Erlang. We find that in practice our abstraction technique is accurate enough to verify an interesting range of safety properties. Though the ACS coverability problem is Expspace-complete, Soter can analyse these verification problems surprisingly efficiently.
Expensive Optimisation: A Metaheuristics Perspective
Venue: arXiv cs.NE 2013
Year: 2013

Stochastic, iterative search methods such as Evolutionary Algorithms (EAs) are proven to be efficient optimizers. However, they require evaluation of the candidate solutions which may be prohibitively expensive in many real world optimization problems. Use of approximate models or surrogates is being explored as a way to reduce the number of such evaluations. In this paper we investigated three such methods. The first method (DAFHEA) partially replaces an expensive function evaluation by its approximate model. The approximation is realized with support vector machine (SVM) regression models. The second method (DAFHEA II) is an enhancement on DAFHEA to accommodate for uncertain environments. The third one uses surrogate ranking with preference learning or ordinal regression. The fitness of the candidates is estimated by modeling their rank. The techniques' performances on some of the benchmark numerical optimization problems have been reported. The comparative benefits and shortcomings of both techniques have been identified.
The Vernam cipher is robust to small deviations from randomness
Venue: arXiv cs.CR 2013
Year: 2013

The Vernam cipher (or one-time pad) has played an important rule in cryptography because it is a perfect secrecy system. For example, if an English text (presented in binary system) $X_1 X_2 ... $ is enciphered according to the formula $Z_i = (X_i + Y_i) \mod 2 $, where $Y_1 Y_2 ...$ is a key sequence generated by the Bernoulli source with equal probabilities of 0 and 1, anyone who knows $Z_1 Z_2 ... $ has no information about $X_1 X_2 ... $ without the knowledge of the key $Y_1 Y_2 ...$. (The best strategy is to guess $X_1 X_2 ... $ not paying attention to $Z_1 Z_2 ... $.) But what should one say about secrecy of an analogous method where the key sequence $Y_1 Y_2 ...$ is generated by the Bernoulli source with a small bias, say, $P(0) = 0.49, $ $ P(1) = 0.51$? To the best of our knowledge, there are no theoretical estimates for the secrecy of such a system, as well as for the general case where $X_1 X_2 ... $ (the plaintext) and key sequence are described by stationary ergodic processes. We consider the running-key ciphers where the plaintext and the key are generated by stationary ergodic sources and show how to estimate the secrecy of such systems. In particular, it is shown that, in a certain sense, the Vernam cipher is robust to small deviations from randomness.