OpenRaiser/Intern-Atlas huggingface dataset:
Efficient MRF Energy Minimization via Adaptive Diminishing Smoothing
Venue: arXiv cs.AI 2012
Year: 2012

We consider the linear programming relaxation of an energy minimization problem for Markov Random Fields. The dual objective of this problem can be treated as a concave and unconstrained, but non-smooth function. The idea of smoothing the objective prior to optimization was recently proposed in a series of papers. Some of them suggested the idea to decrease the amount of smoothing (so called temperature) while getting closer to the optimum. However, no theoretical substantiation was provided. We propose an adaptive smoothing diminishing algorithm based on the duality gap between relaxed primal and dual objectives and demonstrate the efficiency of our approach with a smoothed version of Sequential Tree-Reweighted Message Passing (TRW-S) algorithm. The strategy is applicable to other algorithms as well, avoids adhoc tuning of the smoothing during iterations, and provably guarantees convergence to the optimum.
New Advances and Theoretical Insights into EDML
Venue: arXiv cs.AI 2012
Year: 2012

EDML is a recently proposed algorithm for learning MAP parameters in Bayesian networks. In this paper, we present a number of new advances and insights on the EDML algorithm. First, we provide the multivalued extension of EDML, originally proposed for Bayesian networks over binary variables. Next, we identify a simplified characterization of EDML that further implies a simple fixed-point algorithm for the convex optimization problem that underlies it. This characterization further reveals a connection between EDML and EM: a fixed point of EDML is a fixed point of EM, and vice versa. We thus identify also a new characterization of EM fixed points, but in the semantics of EDML. Finally, we propose a hybrid EDML/EM algorithm that takes advantage of the improved empirical convergence behavior of EDML, while maintaining the monotonic improvement property of EM.
A Cluster-Cumulant Expansion at the Fixed Points of Belief Propagation
Venue: arXiv cs.AI 2012
Year: 2012

We introduce a new cluster-cumulant expansion (CCE) based on the fixed points of iterative belief propagation (IBP). This expansion is similar in spirit to the loop-series (LS) recently introduced in [1]. However, in contrast to the latter, the CCE enjoys the following important qualities: 1) it is defined for arbitrary state spaces 2) it is easily extended to fixed points of generalized belief propagation (GBP), 3) disconnected groups of variables will not contribute to the CCE and 4) the accuracy of the expansion empirically improves upon that of the LS. The CCE is based on the same Möbius transform as the Kikuchi approximation, but unlike GBP does not require storing the beliefs of the GBP-clusters nor does it suffer from convergence issues during belief updating.
Distributed and Autonomous Resource and Power Allocation for Wireless Networks
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, a distributed and autonomous technique for resource and power allocation in orthogonal frequency division multiple access (OFDMA) femto-cellular networks is presented. Here, resource blocks (RBs) and their corresponding transmit powers are assigned to the user(s) in each cell individually without explicit coordination between femto base stations (FBSs). The "allocatability" of each resource is determined utilising only locally available information of the following quantities: - the required rate of the user; - the quality (i.e., strength) of the desired signal; - the frequency-selective fading on each RB; and - the level of interference incident on each RB. Using a fuzzy logic system, the time-averaged values of each of these inputs are combined to determine which RBs are most suitable to be allocated in a particular cell, i.e., which resources can be allocated such that the user requested rate(s) in that cell are satisfied. Furthermore, link adaptation (LA) is included, enabling users to adjust to varying channel conditions. A comprehensive study of this system in a femto-cell environment is performed, yielding system performance improvements in terms of throughput, energy efficiency and coverage over state-of-the-art ICIC techniques.
Creating a level playing field for all symbols in a discretization
Venue: arXiv cs.DS 2012
Year: 2012

In time series analysis research there is a strong interest in discrete representations of real valued data streams. One approach that emerged over a decade ago and is still considered state-of-the-art is the Symbolic Aggregate Approximation algorithm. This discretization algorithm was the first symbolic approach that mapped a real-valued time series to a symbolic representation that was guaranteed to lower-bound Euclidean distance. The interest of this paper concerns the SAX assumption of data being highly Gaussian and the use of the standard normal curve to choose partitions to discretize the data. Though not necessarily, but generally, and certainly in its canonical form, the SAX approach chooses partitions on the standard normal curve that would produce an equal probability for each symbol in a finite alphabet to occur. This procedure is generally valid as a time series is normalized before the rest of the SAX algorithm is applied. However there exists a caveat to this assumption of equi-probability due to the intermediate step of Piecewise Aggregate Approximation (PAA). What we will show in this paper is that when PAA is applied the distribution of the data is indeed altered, resulting in a shrinking standard deviation that is proportional to the number of points used to create a segment of the PAA representation and the degree of auto-correlation within the series. Data that exhibits statistically significant auto-correlation is less affected by this shrinking distribution. As the standard deviation of the data contracts, the mean remains the same, however the distribution is no longer standard normal and therefore the partitions based on the standard normal curve are no longer valid for the assumption of equal probability.
A Novel Learning Algorithm for Bayesian Network and Its Efficient Implementation on GPU
Venue: arXiv cs.DC 2012
Year: 2012

Computational inference of causal relationships underlying complex networks, such as gene-regulatory pathways, is NP-complete due to its combinatorial nature when permuting all possible interactions. Markov chain Monte Carlo (MCMC) has been introduced to sample only part of the combinations while still guaranteeing convergence and traversability, which therefore becomes widely used. However, MCMC is not able to perform efficiently enough for networks that have more than 15~20 nodes because of the computational complexity. In this paper, we use general purpose processor (GPP) and general purpose graphics processing unit (GPGPU) to implement and accelerate a novel Bayesian network learning algorithm. With a hash-table-based memory-saving strategy and a novel task assigning strategy, we achieve a 10-fold acceleration per iteration than using a serial GPP. Specially, we use a greedy method to search for the best graph from a given order. We incorporate a prior component in the current scoring function, which further facilitates the searching. Overall, we are able to apply this system to networks with more than 60 nodes, allowing inferences and modeling of bigger and more complex networks than current methods.
Shortest Path Discovery in the Multi-layered Social Network
Venue: arXiv cs.SI 2012
Year: 2012

Multi-layered social networks consist of the fixed set of nodes linked by multiple connections. These connections may be derived from different types of user activities logged in the IT system. To calculate any structural measures for multi-layered networks this multitude of relations should be coped with in the parameterized way. Two separate algorithms for evaluation of shortest paths in the multi-layered social network are proposed in the paper. The first one is based on pre-processing - aggregation of multiple links into single multi-layered edges, whereas in the second approach, many edges are processed 'on the fly' in the middle of path discovery. Experimental studies carried out on the DBLP database converted into the multi-layered social network are presented as well.
Approximate Maximum Flow on Separable Undirected Graphs
Venue: arXiv cs.DS 2012
Year: 2012

We present faster algorithms for approximate maximum flow in undirected graphs with good separator structures, such as bounded genus, minor free, and geometric graphs. Given such a graph with $n$ vertices, $m$ edges along with a recursive $\sqrt{n}$-vertex separator structure, our algorithm finds an $1-ε$ approximate maximum flow in time $\tilde{O}(m^{6/5} \poly{ε^{-1}})$, ignoring poly-logarithmic terms. Similar speedups are also achieved for separable graphs with larger size separators albeit with larger run times. These bounds also apply to image problems in two and three dimensions. Key to our algorithm is an intermediate problem that we term grouped $L_2$ flow, which exists between maximum flows and electrical flows. Our algorithm also makes use of spectral vertex sparsifiers in order to remove vertices while preserving the energy dissipation of electrical flows. We also give faster spectral vertex sparsification algorithms on well separated graphs, which may be of independent interest.
An Experience Report of Large Scale Federations
Venue: arXiv cs.DB 2012
Year: 2012

We present an experimental study of large-scale RDF federations on top of the Bio2RDF data sources, involving 29 data sets with more than four billion RDF triples deployed in a local federation. Our federation is driven by FedX, a highly optimized federation mediator for Linked Data. We discuss design decisions, technical aspects, and experiences made in setting up and optimizing the Bio2RDF federation, and present an exhaustive experimental evaluation of the federation scenario. In addition to a controlled setting with local federation members, we study implications arising in a hybrid setting, where local federation members interact with remote federation members exhibiting higher network latency. The outcome demonstrates the feasibility of federated semantic data management in general and indicates remaining bottlenecks and research opportunities that shall serve as a guideline for future work in the area of federated semantic data processing.
Managing Changes in Citizen-Centric Healthcare Service Platform using High Level Petri Net
Venue: arXiv cs.SE 2012
Year: 2012

The healthcare organizations are facing a number of daunting challenges pushing systems to deal with requirements changes and benefit from modern technologies and telecom capabilities. Systems evolution through extension of the existing information technology infrastructure becomes one of the most challenging aspects of healthcare and the adaptation to changes is a must. The paper presents a change management framework for a citizen-centric healthcare service platform. A combination between Petri nets model to handle changes and reconfigurable Petri nets model to react to these changes are introduced to fulfill healthcare goals. Thanks to this management framework model, consistency and correctness of a healthcare processes in the presence of frequent changes can be checked and guaranteed.
An Incremental Algorithm for Computing Cylindrical Algebraic Decompositions
Venue: arXiv cs.SC 2012
Year: 2012

In this paper, we propose an incremental algorithm for computing cylindrical algebraic decompositions. The algorithm consists of two parts: computing a complex cylindrical tree and refining this complex tree into a cylindrical tree in real space. The incrementality comes from the first part of the algorithm, where a complex cylindrical tree is constructed by refining a previous complex cylindrical tree with a polynomial constraint. We have implemented our algorithm in Maple. The experimentation shows that the proposed algorithm outperforms existing ones for many examples taken from the literature.
Wikipedia Vandalism Detection Through Machine Learning: Feature Review and New Proposals: Lab Report for PAN at CLEF 2010
Venue: arXiv cs.IR 2012
Year: 2012

Wikipedia is an online encyclopedia that anyone can edit. In this open model, some people edits with the intent of harming the integrity of Wikipedia. This is known as vandalism. We extend the framework presented in (Potthast, Stein, and Gerling, 2008) for Wikipedia vandalism detection. In this approach, several vandalism indicating features are extracted from edits in a vandalism corpus and are fed to a supervised learning algorithm. The best performing classifiers were LogitBoost and Random Forest. Our classifier, a Random Forest, obtained an AUC of 0.92236, ranking in the first place of the PAN'10 Wikipedia vandalism detection task.
On the independent subsets of powers of paths and cycles
Venue: arXiv cs.DM 2012
Year: 2012

In the first part of this work we provide a formula for the number of edges of the Hasse diagram of the independent subsets of the h-th power of a path ordered by inclusion. For h=1 such a value is the number of edges of a Fibonacci cube. We show that, in general, the number of edges of the diagram is obtained by convolution of a Fibonacci-like sequence with itself. In the second part we consider the case of cycles. We evaluate the number of edges of the Hasse diagram of the independent subsets of the h-th power of a cycle ordered by inclusion. For h=1, and n>1, such a value is the number of edges of a Lucas cube.
Cross-Entropy Clustering
Venue: arXiv cs.IT 2012
Year: 2012

We construct a cross-entropy clustering (CEC) theory which finds the optimal number of clusters by automatically removing groups which carry no information. Moreover, our theory gives simple and efficient criterion to verify cluster validity. Although CEC can be build on an arbitrary family of densities, in the most important case of Gaussian CEC: {\em -- the division into clusters is affine invariant; -- the clustering will have the tendency to divide the data into ellipsoid-type shapes; -- the approach is computationally efficient as we can apply Hartigan approach.} We study also with particular attention clustering based on the Spherical Gaussian densities and that of Gaussian densities with covariance $s \I$. In the letter case we show that with $s$ converging to zero we obtain the classical k-means clustering.
Eigenvalue Based Sensing and SNR Estimation for Cognitive Radio in Presence of Noise Correlation
Venue: arXiv cs.IT 2012
Year: 2012

Herein, we present a detailed analysis of an eigenvalue based sensing technique in the presence of correlated noise in the context of a Cognitive Radio (CR). We use a Standard Condition Number (SCN) based decision statistic based on asymptotic Random Matrix Theory (RMT) for decision process. Firstly, the effect of noise correlation on eigenvalue based Spectrum Sensing (SS) is studied analytically under both the noise only and the signal plus noise hypotheses. Secondly, new bounds for the SCN are proposed for achieving improved sensing in correlated noise scenarios. Thirdly, the performance of Fractional Sampling (FS) based SS is studied and a method for determining the operating point for the FS rate in terms of sensing performance and complexity is suggested. Finally, an SNR estimation technique based on the maximum eigenvalue of the received signal's covariance matrix is proposed. It is shown that proposed SCN-based threshold improves sensing performance in the presence of correlated noise and SNRs upto 0 dB can be reliably estimated without the knowledge of noise variance.
Coordinated Multicast Beamforming in Multicell Networks
Venue: arXiv cs.IT 2012
Year: 2012

We study physical layer multicasting in multicell networks where each base station, equipped with multiple antennas, transmits a common message using a single beamformer to multiple users in the same cell. We investigate two coordinated beamforming designs: the quality-of-service (QoS) beamforming and the max-min SINR (signal-to-interference-plus-noise ratio) beamforming. The goal of the QoS beamforming is to minimize the total power consumption while guaranteeing that received SINR at each user is above a predetermined threshold. We present a necessary condition for the optimization problem to be feasible. Then, based on the decomposition theory, we propose a novel decentralized algorithm to implement the coordinated beamforming with limited information sharing among different base stations. The algorithm is guaranteed to converge and in most cases it converges to the optimal solution. The max-min SINR (MMS) beamforming is to maximize the minimum received SINR among all users under per-base station power constraints. We show that the MMS problem and a weighted peak-power minimization (WPPM) problem are inverse problems. Based on this inversion relationship, we then propose an efficient algorithm to solve the MMS problem in an approximate manner. Simulation results demonstrate significant advantages of the proposed multicast beamforming algorithms over conventional multicasting schemes.
Bio-Thentic Card: Authentication concept for RFID Card
Venue: arXiv cs.CR 2012
Year: 2012

Radio frequency identification (RFID) is a technology that employs basic identifier of an object embedded in a chip, transmitted via radio wave, for identification. An RFID Card responds to query or interrogation irrespective of "Who" holds the Card; like a key to a door. Since an attacker can possess the card, access to such object can therefore be easily compromised. This security breach is classified as an unauthorized use of Card, and it forms the bedrock for RFID Card compromise especially in access control. As an on-card authentication mechanism, this research proposed a concept termed Bio-Thentic Card, which can be adopted to prevent this single point of failure of RFID Card. The Bio-Thentic Card was fabricated, tested and assessed in line with the known threats, and attacks; and it was observed to proffer substantive solution to unauthorized use of RFID Card vulnerability
Dynamic Link adaptation Based on Coexistence-Fingerprint Detection for WSN
Venue: arXiv cs.NI 2012
Year: 2012

Operating in the ISM band, the wireless sensor network (WSN) risks being interfered by other concurrent networks. Our concerns are the technologies that do not perform listening before transmission such as Bluetooth, and the ones that do not detect other technologies due to their channel sensing techniques like WIFI. To overcome this issue a WSN node should be able to identify the presence of such technologies. This will allow deducing the characteristics of the generated traffic of these technologies, and thus the behavior of the channel can be predicted. These predictions would help to trigger adequate reactions as to avoid or synchronize with the concurrent net- works. Many works exist on link adaptation, but they concern blind adaptations which are unintelligent and solve momentarily the problem that may reappear over time. In this paper, we perform several experiments on a real testbed to categorize the model of the bit errors in corrupted received packets. These experiments are performed under different conditions of channel noise and interferences. This allows us to identify each corruption pattern as a fingerprint for the interfering technology. Then we propose the mechanism FIM to identify on the fly the source of the corruption. With an implementation on "Tmote Sky" motes using Tinyos1.x, We demonstrate the use of FIM for link adaptation in a coexistence environment. Our mechanism led to throughput improvements of 87%-100% depending on the transmission rate and channel quality.
Modélisation multi-niveaux dans AA4MM
Venue: arXiv cs.MA 2012
Year: 2012

In this article, we propose to represent a multi-level phenomenon as a set of interacting models. This perspective makes the levels of representation and their relationships explicit. To deal with coherence, causality and coordination issues between models, we rely on AA4MM, a metamodel dedicated to such a representation. We illustrate our proposal and we show the interest of our approach on a flocking phenomenon.
Solid State Disk Object-Based Storage with Trim Commands
Venue: arXiv cs.PF 2012
Year: 2012

This paper presents a model of NAND flash SSD utilization and write amplification when the ATA/ATAPI SSD Trim command is incorporated into object-based storage under a variety of user workloads, including a uniform random workload with objects of fixed size and a uniform random workload with objects of varying sizes. We first summarize the existing models for write amplification in SSDs for workloads with and without the Trim command, then propose an alteration of the models that utilizes a framework of object-based storage. The utilization of objects and pages in the SSD is derived, with the analytic results compared to simulation. Finally, the effect of objects on write amplification and its computation is discussed along with a potential application to optimization of SSD usage through object storage metadata servers that allocate object classes of distinct object size.
The Ontological Key: Automatically Understanding and Integrating Forms to Access the Deep Web
Venue: arXiv cs.DB 2012
Year: 2012

Forms are our gates to the web. They enable us to access the deep content of web sites. Automatic form understanding provides applications, ranging from crawlers over meta-search engines to service integrators, with a key to this content. Yet, it has received little attention other than as component in specific applications such as crawlers or meta-search engines. No comprehensive approach to form understanding exists, let alone one that produces rich models for semantic services or integration with linked open data. In this paper, we present OPAL, the first comprehensive approach to form understanding and integration. We identify form labeling and form interpretation as the two main tasks involved in form understanding. On both problems OPAL pushes the state of the art: For form labeling, it combines features from the text, structure, and visual rendering of a web page. In extensive experiments on the ICQ and TEL-8 benchmarks and a set of 200 modern web forms OPAL outperforms previous approaches for form labeling by a significant margin. For form interpretation, OPAL uses a schema (or ontology) of forms in a given domain. Thanks to this domain schema, it is able to produce nearly perfect (more than 97 percent accuracy in the evaluation domains) form interpretations. Yet, the effort to produce a domain schema is very low, as we provide a Datalog-based template language that eases the specification of such schemata and a methodology for deriving a domain schema largely automatically from an existing domain ontology. We demonstrate the value of the form interpretations in OPAL through a light-weight form integration system that successfully translates and distributes master queries to hundreds of forms with no error, yet is implemented with only a handful translation rules.
An Automated Petri-Net Based Approach for Change Management in Distributed Telemedicine Environment
Venue: arXiv cs.SE 2012
Year: 2012

The worldwide healthcare industry is facing a number of daunting challenges which are forcing healthcare systems worldwide to adapt and transform, and will ultimately completely redefine the way they do business and deliver care for patients. In this paper, we present a distributed telemedicine environement reaping from both the benefits of Service Oriented Approach (SOA) and the strong telecoms capabilities. We propose an automated approach to handle changes in a distributed telemedicine environement. A combined Petri nets model to handle changes and Reconfigurable Petri nets model to react to these changes are used to fulfill telemedicine functional and non functional requirements.