OpenRaiser/Intern-Atlas huggingface dataset:
A Library for Implementing the Multiple Hypothesis Tracking Algorithm
Venue: arXiv cs.DS 2011
Year: 2011

The Multiple Hypothesis Tracking (MHT) algorithm is known to produce good results in difficult multi-target tracking situations. However, its implementation is not trivial, and is associated with a significant programming effort, code size and long implementation time. We propose a library which addresses these problems by providing a domain independent implementation of the most complex MHT operations. We also address the problem of applying clustering in domain independent manner.
Verifying Embedded C Software with Timing Constraints using an Untimed Model Checker
Venue: arXiv cs.LO 2011
Year: 2011

Embedded systems are everywhere, from home appliances to critical systems such as medical devices. They usually have associated timing constraints that need to be verified for the implementation. Here, we use an untimed bounded model checker to verify timing properties of embedded C programs. We propose an approach to specify discrete time timing constraints using code annotations. The annotated code is then automatically translated to code that manipulates auxiliary timer variables and is thus suitable as input to conventional, untimed software model checker such as ESBMC. Thus, we can check timing constraints in the same way and at the same time as untimed system requirements, and even allow for interaction between them. We applied the proposed method in a case study, and verified timing constraints of a pulse oximeter, a noninvasive medical device that measures the oxygen saturation of arterial blood.
SVM and Dimensionality Reduction in Cognitive Radio with Experimental Validation
Venue: arXiv cs.NI 2011
Year: 2011

There is a trend of applying machine learning algorithms to cognitive radio. One fundamental open problem is to determine how and where these algorithms are useful in a cognitive radio network. In radar and sensing signal processing, the control of degrees of freedom (DOF)---or dimensionality---is the first step, called pre-processing. In this paper, the combination of dimensionality reduction with SVM is proposed apart from only applying SVM for classification in cognitive radio. Measured Wi-Fi signals with high signal to noise ratio (SNR) are employed to the experiments. The DOF of Wi-Fi signals is extracted by dimensionality reduction techniques. Experimental results show that with dimensionality reduction, the performance of classification is much better with fewer features than that of without dimensionality reduction. The error rates of classification with only one feature of the proposed algorithm can match the error rates of 13 features of the original data. The proposed method will be further tested in our cognitive radio network testbed.
Efficient Optimal Learning for Contextual Bandits
Venue: arXiv cs.LG 2011
Year: 2011

We address the problem of learning in an online setting where the learner repeatedly observes features, selects among a set of actions, and receives reward for the action taken. We provide the first efficient algorithm with an optimal regret. Our algorithm uses a cost sensitive classification learner as an oracle and has a running time $\mathrm{polylog}(N)$, where $N$ is the number of classification rules among which the oracle might choose. This is exponentially faster than all previous algorithms that achieve optimal regret in this setting. Our formulation also enables us to create an algorithm with regret that is additive rather than multiplicative in feedback delay as in all previous work.
Distributed Storage Allocations for Optimal Delay
Venue: arXiv cs.IT 2011
Year: 2011

We examine the problem of creating an encoded distributed storage representation of a data object for a network of mobile storage nodes so as to achieve the optimal recovery delay. A source node creates a single data object and disseminates an encoded representation of it to other nodes for storage, subject to a given total storage budget. A data collector node subsequently attempts to recover the original data object by contacting other nodes and accessing the data stored in them. By using an appropriate code, successful recovery is achieved when the total amount of data accessed is at least the size of the original data object. The goal is to find an allocation of the given budget over the nodes that optimizes the recovery delay incurred by the data collector; two objectives are considered: (i) maximization of the probability of successful recovery by a given deadline, and (ii) minimization of the expected recovery delay. We solve the problem completely for the second objective in the case of symmetric allocations (in which all nonempty nodes store the same amount of data), and show that the optimal symmetric allocation for the two objectives can be quite different. A simple data dissemination and storage protocol for a mobile delay-tolerant network is evaluated under various scenarios via simulations. Our results show that the choice of storage allocation can have a significant impact on the recovery delay performance, and that coding may or may not be beneficial depending on the circumstances.
The Finite Field Multi-Way Relay Channel with Correlated Sources: The Three-User Case
Venue: arXiv cs.IT 2011
Year: 2011

The three-user finite field multi-way relay channel with correlated sources is considered. The three users generate possibly correlated messages, and each user is to transmit its message to the two other users reliably in the Shannon sense. As there is no direct link among the users, communication is carried out via a relay, and the link from the users to the relay and those from the relay to the users are finite field adder channels with additive noise of arbitrary distribution. The problem is to determine the set of all possible achievable rates, defined as channel uses per source symbol for reliable communication. For two classes of source/channel combinations, the solution is obtained using Slepian-Wolf source coding combined with functional-decode-forward channel coding.
On Achievable Rate Regions of the Asymmetric AWGN Two-Way Relay Channel
Venue: arXiv cs.IT 2011
Year: 2011

This paper investigates the additive white Gaussian noise two-way relay channel, where two users exchange messages through a relay. Asymmetrical channels are considered where the users can transmit data at different rates and at different power levels. We modify and improve existing coding schemes to obtain three new achievable rate regions. Comparing four downlink-optimal coding schemes, we show that the scheme that gives the best sum-rate performance is (i) complete-decode-forward, when both users transmit at low signal-to-noise ratio (SNR); (ii) functional-decode-forward with nested lattice codes, when both users transmit at high SNR; (iii) functional-decode-forward with rate splitting and time-division multiplexing, when one user transmits at low SNR and another user at medium--high SNR.
Algorithmic Randomness and Capacity of Closed Sets
Venue: arXiv cs.LO 2011
Year: 2011

We investigate the connection between measure, capacity and algorithmic randomness for the space of closed sets. For any computable measure m, a computable capacity T may be defined by letting T(Q) be the measure of the family of closed sets K which have nonempty intersection with Q. We prove an effective version of Choquet's capacity theorem by showing that every computable capacity may be obtained from a computable measure in this way. We establish conditions on the measure m that characterize when the capacity of an m-random closed set equals zero. This includes new results in classical probability theory as well as results for algorithmic randomness. For certain computable measures, we construct effectively closed sets with positive capacity and with Lebesgue measure zero. We show that for computable measures, a real q is upper semi-computable if and only if there is an effectively closed set with capacity q.
On Democracy in Peer-to-Peer systems
Venue: arXiv cs.DC 2011
Year: 2011

The information flow inside a P2P network is highly dependent on the network structure. In order to ease the diffusion of relevant data toward interested peers, many P2P protocols gather similar nodes by putting them in direct contact. With this approach the similarity between nodes is computed in a point-to-point fashion: each peer individually identifies the nodes that share similar interests with it. This leads to the creation of a sort of "private" communities, limited to each peer neighbors list. This "private" knowledge do not allow to identify the features needed to discover and characterize the correlations that collect similar peers in broader groups. In order to let these correlations to emerge, the collective knowledge of peers must be exploited. One common problem to overcome in order to avoid the "private" vision of the network, is related to how distributively determine the representation of a community and how nodes may decide to belong to it. We propose to use a gossip-like approach in order to let peers elect and identify leaders of interest communities. Once leaders are elected, their profiles are used as community representatives. Peers decide to adhere to a community or another by choosing the most similar representative they know about.
Random forest models of the retention constants in the thin layer chromatography
Venue: arXiv cs.AI 2011
Year: 2011

In the current study we examine an application of the machine learning methods to model the retention constants in the thin layer chromatography (TLC). This problem can be described with hundreds or even thousands of descriptors relevant to various molecular properties, most of them redundant and not relevant for the retention constant prediction. Hence we employed feature selection to significantly reduce the number of attributes. Additionally we have tested application of the bagging procedure to the feature selection. The random forest regression models were built using selected variables. The resulting models have better correlation with the experimental data than the reference models obtained with linear regression. The cross-validation confirms robustness of the models.
Extensional Higher-Order Logic Programming
Venue: arXiv cs.PL 2011
Year: 2011

We propose a purely extensional semantics for higher-order logic programming. In this semantics program predicates denote sets of ordered tuples, and two predicates are equal iff they are equal as sets. Moreover, every program has a unique minimum Herbrand model which is the greatest lower bound of all Herbrand models of the program and the least fixed-point of an immediate consequence operator. We also propose an SLD-resolution proof procedure which is proven sound and complete with respect to the minimum model semantics. In other words, we provide a purely extensional theoretical framework for higher-order logic programming which generalizes the familiar theory of classical (first-order) logic programming.
Polar Fusion Technique Analysis for Evaluating the Performances of Image Fusion of Thermal and Visual Images for Human Face Recognition
Venue: arXiv cs.CV 2011
Year: 2011

This paper presents a comparative study of two different methods, which are based on fusion and polar transformation of visual and thermal images. Here, investigation is done to handle the challenges of face recognition, which include pose variations, changes in facial expression, partial occlusions, variations in illumination, rotation through different angles, change in scale etc. To overcome these obstacles we have implemented and thoroughly examined two different fusion techniques through rigorous experimentation. In the first method log-polar transformation is applied to the fused images obtained after fusion of visual and thermal images whereas in second method fusion is applied on log-polar transformed individual visual and thermal images. After this step, which is thus obtained in one form or another, Principal Component Analysis (PCA) is applied to reduce dimension of the fused images. Log-polar transformed images are capable of handling complicacies introduced by scaling and rotation. The main objective of employing fusion is to produce a fused image that provides more detailed and reliable information, which is capable to overcome the drawbacks present in the individual visual and thermal face images. Finally, those reduced fused images are classified using a multilayer perceptron neural network. The database used for the experiments conducted here is Object Tracking and Classification Beyond Visible Spectrum (OTCBVS) database benchmark thermal and visual face images. The second method has shown better performance, which is 95.71% (maximum) and on an average 93.81% as correct recognition rate.
Strategies for Development of a Distributed Framework for Computational Sciences
Venue: arXiv cs.DC 2011
Year: 2011

This paper discusses some generic approach for developing grid-based framework for enabling establishment of workflows comprising existing software in computational sciences areas. We highlight the main requirements addressed the developing of such framework. Some strategies for enabling interoperability between convenient computation software in the grid environment has been shown. The UML based instruments of graphical description of workflows for the developing system has been suggested.
Perfect Reconstruction Two-Channel Wavelet Filter-Banks for Graph Structured Data
Venue: arXiv cs.DC 2011
Year: 2011

In this work we propose the construction of two-channel wavelet filterbanks for analyzing functions defined on the vertices of any arbitrary finite weighted undirected graph. These graph based functions are referred to as graph-signals as we build a framework in which many concepts from the classical signal processing domain, such as Fourier decomposition, signal filtering and downsampling can be extended to graph domain. Especially, we observe a spectral folding phenomenon in bipartite graphs which occurs during downsampling of these graphs and produces aliasing in graph signals. This property of bipartite graphs, allows us to design critically sampled two-channel filterbanks, and we propose quadrature mirror filters (referred to as graph-QMF) for bipartite graph which cancel aliasing and lead to perfect reconstruction. For arbitrary graphs we present a bipartite subgraph decomposition which produces an edge-disjoint collection of bipartite subgraphs. Graph-QMFs are then constructed on each bipartite subgraph leading to "multi-dimensional" separable wavelet filterbanks on graphs. Our proposed filterbanks are critically sampled and we state necessary and sufficient conditions for orthogonality, aliasing cancellation and perfect reconstruction. The filterbanks are realized by Chebychev polynomial approximations.
On the Non-Progressive Spread of Influence through Social Networks
Venue: arXiv cs.SI 2011
Year: 2011

The spread of influence in social networks is studied in two main categories: the progressive model and the non-progressive model (see e.g. the seminal work of Kempe, Kleinberg, and Tardos in KDD 2003). While the progressive models are suitable for modeling the spread of influence in monopolistic settings, non-progressive are more appropriate for modeling non-monopolistic settings, e.g., modeling diffusion of two competing technologies over a social network. Despite the extensive work on the progressive model, non-progressive models have not been studied well. In this paper, we study the spread of influence in the non-progressive model under the strict majority threshold: given a graph $G$ with a set of initially infected nodes, each node gets infected at time $τ$ iff a majority of its neighbors are infected at time $τ-1$. Our goal in the \textit{MinPTS} problem is to find a minimum-cardinality initial set of infected nodes that would eventually converge to a steady state where all nodes of $G$ are infected. We prove that while the MinPTS is NP-hard for a restricted family of graphs, it admits an improved constant-factor approximation algorithm for power-law graphs. We do so by proving lower and upper bounds in terms of the minimum and maximum degree of nodes in the graph. The upper bound is achieved in turn by applying a natural greedy algorithm. Our experimental evaluation of the greedy algorithm also shows its superior performance compared to other algorithms for a set of real-world graphs as well as the random power-law graphs. Finally, we study the convergence properties of these algorithms and show that the non-progressive model converges in at most $O(|E(G)|)$ steps.
An efficient certificateless authenticated key agreement protocol without bilinear pairings
Venue: arXiv cs.CR 2011
Year: 2011

Certificateless public key cryptography simplifies the complex certificate management in the traditional public key cryptography and resolves the key escrow problem in identity-based cryptography. Many certificateless authenticated key agreement protocols using bilinear pairings have been proposed. But the relative computation cost of the pairing is approximately twenty times higher than that of the scalar multiplication over elliptic curve group. Recently, several certificateless authenticated key agreement protocols without pairings were proposed to improve the performance. In this paper, we propose a new certificateless authenticated key agreement protocol without pairing. The user in our just needs to compute five scale multiplication to finish the key agreement. We also show the proposed protocol is secure in the random oracle model.
Optimal rate list decoding via derivative codes
Venue: arXiv cs.IT 2011
Year: 2011

The classical family of $[n,k]_q$ Reed-Solomon codes over a field $\F_q$ consist of the evaluations of polynomials $f \in \F_q[X]$ of degree $< k$ at $n$ distinct field elements. In this work, we consider a closely related family of codes, called (order $m$) {\em derivative codes} and defined over fields of large characteristic, which consist of the evaluations of $f$ as well as its first $m-1$ formal derivatives at $n$ distinct field elements. For large enough $m$, we show that these codes can be list-decoded in polynomial time from an error fraction approaching $1-R$, where $R=k/(nm)$ is the rate of the code. This gives an alternate construction to folded Reed-Solomon codes for achieving the optimal trade-off between rate and list error-correction radius. Our decoding algorithm is linear-algebraic, and involves solving a linear system to interpolate a multivariate polynomial, and then solving another structured linear system to retrieve the list of candidate polynomials $f$. The algorithm for derivative codes offers some advantages compared to a similar one for folded Reed-Solomon codes in terms of efficient unique decoding in the presence of side information.
Symmetry-Based Search Space Reduction For Grid Maps
Venue: arXiv cs.AI 2011
Year: 2011

In this paper we explore a symmetry-based search space reduction technique which can speed up optimal pathfinding on undirected uniform-cost grid maps by up to 38 times. Our technique decomposes grid maps into a set of empty rectangles, removing from each rectangle all interior nodes and possibly some from along the perimeter. We then add a series of macro-edges between selected pairs of remaining perimeter nodes to facilitate provably optimal traversal through each rectangle. We also develop a novel online pruning technique to further speed up search. Our algorithm is fast, memory efficient and retains the same optimality and completeness guarantees as searching on an unmodified grid map.
Refinement by interpretation in π-institutions
Venue: arXiv cs.LO 2011
Year: 2011

The paper discusses the role of interpretations, understood as multifunctions that preserve and reflect logical consequence, as refinement witnesses in the general setting of pi-institutions. This leads to a smooth generalization of the refinement-by-interpretation approach, recently introduced by the authors in more specific contexts. As a second, yet related contribution a basis is provided to build up a refinement calculus of structured specifications in and across arbitrary pi-institutions.
Formalising the Continuous/Discrete Modeling Step
Venue: arXiv cs.SE 2011
Year: 2011

Formally capturing the transition from a continuous model to a discrete model is investigated using model based refinement techniques. A very simple model for stopping (eg. of a train) is developed in both the continuous and discrete domains. The difference between the two is quantified using generic results from ODE theory, and these estimates can be compared with the exact solutions. Such results do not fit well into a conventional model based refinement framework; however they can be accommodated into a model based retrenchment. The retrenchment is described, and the way it can interface to refinement development on both the continuous and discrete sides is outlined. The approach is compared to what can be achieved using hybrid systems techniques.
Rooting opinions in the minds: a cognitive model and a formal account of opinions and their dynamics
Venue: arXiv cs.AI 2011
Year: 2011

The study of opinions, their formation and change, is one of the defining topics addressed by social psychology, but in recent years other disciplines, like computer science and complexity, have tried to deal with this issue. Despite the flourishing of different models and theories in both fields, several key questions still remain unanswered. The understanding of how opinions change and the way they are affected by social influence are challenging issues requiring a thorough analysis of opinion per se but also of the way in which they travel between agents' minds and are modulated by these exchanges. To account for the two-faceted nature of opinions, which are mental entities undergoing complex social processes, we outline a preliminary model in which a cognitive theory of opinions is put forward and it is paired with a formal description of them and of their spreading among minds. Furthermore, investigating social influence also implies the necessity to account for the way in which people change their minds, as a consequence of interacting with other people, and the need to explain the higher or lower persistence of such changes.
Multi-receiver Wiretap Channel with Public and Confidential Messages
Venue: arXiv cs.IT 2011
Year: 2011

We study the multi-receiver wiretap channel with public and confidential messages. In this channel, there is a transmitter that wishes to communicate with two legitimate users in the presence of an external eavesdropper. The transmitter sends a pair of public and confidential messages to each legitimate user. While there are no secrecy constraints on the public messages, confidential messages need to be transmitted in perfect secrecy. We study the discrete memoryless multi-receiver wiretap channel as well as its Gaussian multi-input multi-output (MIMO) instance. First, we consider the degraded discrete memoryless channel, and obtain an inner bound for the capacity region by using an achievable scheme that uses superposition coding and binning. Next, we obtain an outer bound, and show that this outer bound partially matches the inner bound, providing a partial characterization for the capacity region of the degraded channel model. Second, we obtain an inner bound for the general, not necessarily degraded, discrete memoryless channel by using Marton's inner bound, superposition coding, rate-splitting and binning. Third, we consider the degraded Gaussian MIMO channel, and show that, to evaluate both the inner and outer bounds, considering only jointly Gaussian auxiliary random variables and channel input is sufficient. Since the inner and outer bounds partially match, these sufficiency results provide a partial characterization of the capacity region of the degraded Gaussian MIMO channel. Finally, we provide an inner bound for the capacity region of the general, not necessarily degraded, Gaussian MIMO multi-receiver wiretap channel.