OpenRaiser/Intern-Atlas huggingface dataset:
Stochastic complexity of Bayesian networks
Venue: arXiv cs.LG 2012
Year: 2012

Bayesian networks are now being used in enormous fields, for example, diagnosis of a system, data mining, clustering and so on. In spite of their wide range of applications, the statistical properties have not yet been clarified, because the models are nonidentifiable and non-regular. In a Bayesian network, the set of its parameter for a smaller model is an analytic set with singularities in the space of large ones. Because of these singularities, the Fisher information matrices are not positive definite. In other words, the mathematical foundation for learning was not constructed. In recent years, however, we have developed a method to analyze non-regular models using algebraic geometry. This method revealed the relation between the models singularities and its statistical properties. In this paper, applying this method to Bayesian networks with latent variables, we clarify the order of the stochastic complexities.Our result claims that the upper bound of those is smaller than the dimension of the parameter space. This means that the Bayesian generalization error is also far smaller than that of regular model, and that Schwarzs model selection criterion BIC needs to be improved for Bayesian networks.
The Revisiting Problem in Mobile Robot Map Building: A Hierarchical Bayesian Approach
Venue: arXiv cs.AI 2012
Year: 2012

We present an application of hierarchical Bayesian estimation to robot map building. The revisiting problem occurs when a robot has to decide whether it is seeing a previously-built portion of a map, or is exploring new territory. This is a difficult decision problem, requiring the probability of being outside of the current known map. To estimate this probability, we model the structure of a "typical" environment as a hidden Markov model that generates sequences of views observed by a robot navigating through the environment. A Dirichlet prior over structural models is learned from previously explored environments. Whenever a robot explores a new environment, the posterior over the model is estimated by Dirichlet hyperparameters. Our approach is implemented and tested in the context of multi-robot map merging, a particularly difficult instance of the revisiting problem. Experiments with robot data show that the technique yields strong improvements over alternative methods.
Learning Module Networks
Venue: arXiv cs.LG 2012
Year: 2012

Methods for learning Bayesian network structure can discover dependency structure between observed variables, and have been shown to be useful in many applications. However, in domains that involve a large number of variables, the space of possible network structures is enormous, making it difficult, for both computational and statistical reasons, to identify a good model. In this paper, we consider a solution to this problem, suitable for domains where many variables have similar behavior. Our method is based on a new class of models, which we call module networks. A module network explicitly represents the notion of a module - a set of variables that have the same parents in the network and share the same conditional probability distribution. We define the semantics of module networks, and describe an algorithm that learns a module network from data. The algorithm learns both the partitioning of the variables into modules and the dependency structure between the variables. We evaluate our algorithm on synthetic data, and on real data in the domains of gene expression and the stock market. Our results show that module networks generalize better than Bayesian networks, and that the learned module network structure reveals regularities that are obscured in learned Bayesian networks.
CLP(BN): Constraint Logic Programming for Probabilistic Knowledge
Venue: arXiv cs.AI 2012
Year: 2012

We present CLP(BN), a novel approach that aims at expressing Bayesian networks through the constraint logic programming framework. Arguably, an important limitation of traditional Bayesian networks is that they are propositional, and thus cannot represent relations between multiple similar objects in multiple contexts. Several researchers have thus proposed first-order languages to describe such networks. Namely, one very successful example of this approach are the Probabilistic Relational Models (PRMs), that combine Bayesian networks with relational database technology. The key difficulty that we had to address when designing CLP(cal{BN}) is that logic based representations use ground terms to denote objects. With probabilitic data, we need to be able to uniquely represent an object whose value we are not sure about. We use {sl Skolem functions} as unique new symbols that uniquely represent objects with unknown value. The semantics of CLP(cal{BN}) programs then naturally follow from the general framework of constraint logic programming, as applied to a specific domain where we have probabilistic data. This paper introduces and defines CLP(cal{BN}), and it describes an implementation and initial experiments. The paper also shows how CLP(cal{BN}) relates to Probabilistic Relational Models (PRMs), Ngo and Haddawys Probabilistic Logic Programs, AND Kersting AND De Raedts Bayesian Logic Programs.
What if Routers Were Social? Analyzing Wireless Mesh Networks from a Social Networks Perspective
Venue: arXiv cs.NI 2012
Year: 2012

Wireless Mesh Networks (WMNs) consist of radio nodes organized in a mesh topology for serving wireless mesh clients to communicate with one another or to connect to the Internet. Nodes in a mesh network can communicate with each other either directly or through one or more intermediate nodes, similar to social networks. WMNs share many common properties with social networks. We first identify the differences and similarities between social networks and WMNs and then use metrics that are typically used for social network analysis (SNA) to assess real WMNs. Analyzing real WMN data collected from the UCSB MeshNet and MIT Roofnet testbeds reveals that using SNA metrics are helpful in designing WMNs with better performance. We demonstrate the validity of our conclusions and this new approach by focusing on two sample applications of social networks: network reliability assessment and channel access scheduling.
A secure key transfer protocol for group communication
Venue: arXiv cs.CR 2012
Year: 2012

Providing security for messages in group communication is more essential and critical nowadays. In group oriented applications such as Video conferencing and entertainment applications, it is necessary to secure the confidential data in such a way that intruders are not able to modify or transmit the data. Key transfer protocols fully rely on trusted Key Generation Center (KGC) to compute group key and to transport the group keys to all communication parties in a secured and secret manner. In this paper, an efficient key generation and key transfer protocol has been proposed where KGC can broadcast group key information to all group members in a secure way. Hence, only authorized group members will be able to retrieve the secret key and unauthorized members cannot retrieve the secret key. Hence, inorder to maintain the forward and backward secrecy, the group keys are updated whenever a new member joins or leaves the communication group. The proposed algorithm is more efficient and relies on NP class. In addition, the keys are distributed to the group users in a safe and secure way. Moreover, the key generated is also very strong since it uses cryptographic techniques which provide efficient computation.
Simple Solution for Designing the Piecewise Linear Scalar Companding Quantizer for Gaussian Source
Venue: arXiv cs.IT 2012
Year: 2012

To overcome the difficulties in determining an inverse compressor function for a Gaussian source, which appear in designing the nonlinear optimal companding quantizers and also in the nonlinear optimal companding quantization procedure, in this paper a piecewise linear compressor function based on the first derivate approximation of the optimal compressor function is proposed. We show that the approximations used in determining the piecewise linear compressor function contribute to the simple solution for designing the novel piecewise linear scalar companding quantizer (PLSCQ) for a Gaussian source of unit variance. For the given number of segments, we perform optimization procedure in order to obtain optimal value of the support region threshold which maximizes the signal to quantization noise ratio (SQNR) of the proposed PLSCQ. We study how the SQNR of the considered PLSCQ depends on the number of segments and we show that for the given number of quantization levels, SQNR of the PLSCQ approaches the one of the nonlinear optimal companding quantizer with the increase of the number of segments. The presented features of the proposed PLSCQ indicate that the obtained model should be of high practical significance for quantization of signals having Gaussian probability density function.
Product/Brand extraction from WikiPedia
Venue: arXiv cs.IR 2012
Year: 2012

In this paper we describe the task of extracting product and brand pages from wikipedia. We present an experimental environment and setup built on top of a dataset of wikipedia pages we collected. We introduce a method for recognition of product pages modelled as a boolean probabilistic classification task. We show that this approach can lead to promising results and we discuss alternative approaches we considered.
Feasibility Evaluation of VANET using Directional-Location Aided Routing (D-LAR) Protocol
Venue: arXiv cs.NI 2012
Year: 2012

Vehicular Ad hoc Networks (VANETs) allow vehicles to form a self-organized network without any fixed infrastructure. VANETs have received wide attention and numerous research issues have been identified in the recent time. The design and implementation of efficient and scalable routing protocols for VANETs is a challenging task due to high dynamics and mobility constraints. In this paper, we have proposed D-LAR (Directional-Location Aided Routing), is an extension of Location Aided Routing (LAR) with Directional Routing (DIR) capability. D-LAR is a greedy approach based-position based routing protocol to forward packet to the node present in request zone within the transmission range of the source node as most suitable next-hop node. We have justified the feasibility of our proposed protocol for VANET.
New SpiroPlanck Heuristics for High Energy Physics Networking and Future Internet Testbeds
Venue: arXiv cs.NI 2012
Year: 2012

The need for data intensive Grids, and advanced networks with high performance that support our science has made the High Energy Physics community a leading and a key co-developer of leading edge wide area networks. This paper gives an overview of the status for the world's research networks and major international links used by the high energy physics and other scientific communities, showing some Future Internet testbed architectures, scalability, geographic scope, and extension between networks. The resemblance between wireless sensor network and future internet network, especially in scale consideration as density and network coverage, inspires us to adopt the models of the former to the later. Then we test this assumption to see that this provides a concise working model. This paper collects some heuristics that we call them SpiroPlanck and employs them to model the coverage of dense networks. In this paper, we propose a framework for the operation of FI testbeds containing a test scenario, new representation and visualization techniques, and possible performance measures. Investigations show that it is very promising and could be seen as a good optimization
Homomorphic Payment Addresses and the Pay-to-Contract Protocol
Venue: arXiv cs.CR 2012
Year: 2012

We propose an electronic payment protocol for typical customer-merchant relations which does not require a trusted (signed) payment descriptor to be sent from the merchant to the customer. Instead, the destination "account" number for the payment is solely created on the customer side. This eliminates the need for any encrypted or authenticated communication in the protocol and is secure even if the merchant's online infrastructure is compromised. Moreover, the payment transaction itself serves as a timestamped receipt for the customer. It proves what has been paid for and who received the funds, again without relying on any merchant signatures. In particular, funds and receipt are exchanged in a single atomic action. The asymmetric nature of the customer-merchant relation is crucial. The protocol is specifically designed with bitcoin in mind as the underlying payment system. Thereby, it has the useful benefit that all transactions are public. However, the only essential requirement on the payment system is that "accounts" are arbitrary user-created keypairs of a cryptosystem whose keypairs enjoy a homomorphic property. All ElGamal-type cryptosystems have this feature. For use with bitcoin we propose the design of a deterministic bitcoin wallet whose addresses can be indexed by clear text strings.
Compute and Forward: End to End Performance over Residue Class Signal Constellation
Venue: arXiv cs.IT 2012
Year: 2012

In this letter, the problem of implementing compute and forward (CF) is addressed. We present a practical signal model to implement CF which is built on the basis of Gaussian integer lattice partitions. We provide practical decoding functions at both relay and destination nodes thereby providing a framework for complete analysis of CF. Our main result is the analytical derivation and simulations based validation of union bound of probability of error for end to end performance of CF. We show that the performance is not limited by the linear combination decoding at the relay but by the full rank requirement of the coefficient matrix at the destination.
Content as a Network Primitive
Venue: arXiv cs.NI 2012
Year: 2012

The current functionality supported by OpenFlowbased software defined networking (SDN) includes switching, routing, tunneling, and some basic fire walling while operating on traffic flows. However, the semantics of SDN do not allow for other operations on the traffic, nor does it allow operations at a higher granularity. In this work, we describe a method to expand the SDN framework to add other network primitives. In particular, we present a method to integrate different network elements (like cache, proxy etc). Here, we focus on storage and caching, but our method could be expanded to other functionality seamlessly. We also present a method to identify content so as to perform per-content policy, as opposed to per flow policy. We have implemented the proposed mechanisms to demonstrate its feasibility.
Evolution of Plastic Learning in Spiking Networks via Memristive Connections
Venue: arXiv cs.ET 2012
Year: 2012

This article presents a spiking neuroevolutionary system which implements memristors as plastic connections, i.e. whose weights can vary during a trial. The evolutionary design process exploits parameter self-adaptation and variable topologies, allowing the number of neurons, connection weights, and inter-neural connectivity pattern to emerge. By comparing two phenomenological real-world memristor implementations with networks comprised of (i) linear resistors (ii) constant-valued connections, we demonstrate that this approach allows the evolution of networks of appropriate complexity to emerge whilst exploiting the memristive properties of the connections to reduce learning time. We extend this approach to allow for heterogeneous mixtures of memristors within the networks; our approach provides an in-depth analysis of network structure. Our networks are evaluated on simulated robotic navigation tasks; results demonstrate that memristive plasticity enables higher performance than constant-weighted connections in both static and dynamic reward scenarios, and that mixtures of memristive elements provide performance advantages when compared to homogeneous memristive networks.
Towards Zero-Overhead Adaptive Indexing in Hadoop
Venue: arXiv cs.DB 2012
Year: 2012

Several research works have focused on supporting index access in MapReduce systems. These works have allowed users to significantly speed up selective MapReduce jobs by orders of magnitude. However, all these proposals require users to create indexes upfront, which might be a difficult task in certain applications (such as in scientific and social applications) where workloads are evolving or hard to predict. To overcome this problem, we propose LIAH (Lazy Indexing and Adaptivity in Hadoop), a parallel, adaptive approach for indexing at minimal costs for MapReduce systems. The main idea of LIAH is to automatically and incrementally adapt to users' workloads by creating clustered indexes on HDFS data blocks as a byproduct of executing MapReduce jobs. Besides distributing indexing efforts over multiple computing nodes, LIAH also parallelises indexing with both map tasks computation and disk I/O. All this without any additional data copy in main memory and with minimal synchronisation. The beauty of LIAH is that it piggybacks index creation on map tasks, which read relevant data from disk to main memory anyways. Hence, LIAH does not introduce any additional read I/O-costs and exploit free CPU cycles. As a result and in contrast to existing adaptive indexing works, LIAH has a very low (or invisible) indexing overhead, usually for the very first job. Still, LIAH can quickly converge to a complete index, i.e. all HDFS data blocks are indexed. Especially, LIAH can trade early job runtime improvements with fast complete index convergence. We compare LIAH with HAIL, a state-of-the-art indexing technique, as well as with standard Hadoop with respect to indexing overhead and workload performance.
Sentence Compression in Spanish driven by Discourse Segmentation and Language Models
Venue: arXiv cs.CL 2012
Year: 2012

Previous works demonstrated that Automatic Text Summarization (ATS) by sentences extraction may be improved using sentence compression. In this work we present a sentence compressions approach guided by level-sentence discourse segmentation and probabilistic language models (LM). The results presented here show that the proposed solution is able to generate coherent summaries with grammatical compressed sentences. The approach is simple enough to be transposed into other languages.
On optimum left-to-right strategies for active context-free games
Venue: arXiv cs.DB 2012
Year: 2012

Active context-free games are two-player games on strings over finite alphabets with one player trying to rewrite the input string to match a target specification. These games have been investigated in the context of exchanging Active XML (AXML) data. While it was known that the rewriting problem is undecidable in general, it is shown here that it is EXPSPACE-complete to decide for a given context-free game, whether all safely rewritable strings can be safely rewritten in a left-to-right manner, a problem that was previously considered by Abiteboul et al. Furthermore, it is shown that the corresponding problem for games with finite replacement languages is EXPTIME-complete.
Compound Multiple Access Channel with Common Message and Intersymbol Interference
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we characterize the capacity region for the two-user linear Gaussian compound Multiple Access Channel with common message (MACC) and with intersymbol interference (ISI) under an input power constraint. The region is obtained by converting the channel to its equivalent memoryless one by defining an n-block memoryless circular Gaussian compound MACC model and applying the discrete Fourier transform (DFT) to decompose the n-block channel into a set of independent parallel channels whose capacities can be found easily. Indeed, the capacity region of the original Gaussian compound MACC equals that of the n-block circular Gaussian compound MACC in the limit of infinite block length. Then by using the obtained capacity region, we derive the capacity region of the strong interference channel with common message and ISI.
Local Irreducibility of Tail-Biting Trellises
Venue: arXiv cs.IT 2012
Year: 2012

This paper investigates tail-biting trellis realizations for linear block codes. Intrinsic trellis properties are used to characterize irreducibility on given intervals of the time axis. It proves beneficial to always consider the trellis and its dual simultaneously. A major role is played by trellis properties that amount to observability and controllability for fragments of the trellis of various lengths. For fragments of length less than the minimum span length of the code it is shown that fragment observability and fragment controllability are equivalent to irreducibility. For reducible trellises, a constructive reduction procedure is presented. The considerations also lead to a characterization for when the dual of a trellis allows a product factorization into elementary ("atomic") trellises.
A comparative study of root-based and stem-based approaches for measuring the similarity between arabic words for arabic text mining applications
Venue: arXiv cs.CL 2012
Year: 2012

Representation of semantic information contained in the words is needed for any Arabic Text Mining applications. More precisely, the purpose is to better take into account the semantic dependencies between words expressed by the co-occurrence frequencies of these words. There have been many proposals to compute similarities between words based on their distributions in contexts. In this paper, we compare and contrast the effect of two preprocessing techniques applied to Arabic corpus: Rootbased (Stemming), and Stem-based (Light Stemming) approaches for measuring the similarity between Arabic words with the well known abstractive model -Latent Semantic Analysis (LSA)- with a wide variety of distance functions and similarity measures, such as the Euclidean Distance, Cosine Similarity, Jaccard Coefficient, and the Pearson Correlation Coefficient. The obtained results show that, on the one hand, the variety of the corpus produces more accurate results; on the other hand, the Stem-based approach outperformed the Root-based one because this latter affects the words meanings.
Small snarks with large oddness
Venue: arXiv cs.DM 2012
Year: 2012

We estimate the minimum number of vertices of a cubic graph with given oddness and cyclic connectivity. We prove that a bridgeless cubic graph $G$ with oddness $ω(G)$ other than the Petersen graph has at least $5.41\cdotω(G)$ vertices, and for each integer $k$ with $2\le k\le 6$ we construct an infinite family of cubic graphs with cyclic connectivity $k$ and small oddness ratio $|V(G)|/ω(G)$. In particular, for cyclic connectivity 2, 4, 5, and 6 we improve the upper bounds on the oddness ratio of snarks to 7.5, 13, 25, and 99 from the known values 9, 15, 76, and 118, respectively. In addition, we construct a cyclically 4-connected snark of girth 5 with oddness 4 on 44 vertices, improving the best previous value of 46.