OpenRaiser/Intern-Atlas huggingface dataset:
BigFoot: Analysis, monitoring, tracking and sharing of bio-medical features of human appendages using consumer-grade home and office based imaging devices
Venue: arXiv cs.OH 2012
Year: 2012

Here we describe a system for personal and professional management and analysis of bio-medical images captured using off-the-shelf, consumer-grade imaging devices such as scanners, digital cameras, cellphones, webcams and tablet PCs. Specifically, we describe an implementation of this system for the analysis, monitoring and tracking of conditions and features of human feet using a flatbed scanner as the image capture device and a custom-designed set of algorithms and software to manage and analyze the acquired data.
Hidden Markov Estimation of Bistatic Range From Cluttered Ultra-wideband Impulse Responses
Venue: arXiv cs.OH 2012
Year: 2012

Ultra-wideband (UWB) multistatic radar can be used for target detection and tracking in buildings and rooms. Target detection and tracking relies on accurate knowledge of the bistatic delay. Noise, measurement error, and the problem of dense, overlapping multipath signals in the measured UWB channel impulse response (CIR) all contribute to make bistatic delay estimation challenging. It is often assumed that a calibration CIR, that is, a measurement from when no person is present, is easily subtracted from a newly captured CIR. We show this is often not the case. We propose modeling the difference between a current set of CIRs and a set of calibration CIRs as a hidden Markov model (HMM). Multiple experimental deployments are performed to collect CIR data and test the performance of this model and compare its performance to existing methods. Our experimental results show an RMSE of 2.85 ns and 2.76 ns for our HMM-based approach, compared to a thresholding method which, if the ideal threshold is known a priori, achieves 3.28 ns and 4.58 ns. By using the Baum-Welch algorithm, the HMM-based estimator is shown to be very robust to initial parameter settings. Localization performance is also improved using the HMM-based bistatic delay estimates.
Using external sources of bilingual information for on-the-fly word alignment
Venue: arXiv cs.CL 2012
Year: 2012

In this paper we present a new and simple language-independent method for word-alignment based on the use of external sources of bilingual information such as machine translation systems. We show that the few parameters of the aligner can be trained on a very small corpus, which leads to results comparable to those obtained by the state-of-the-art tool GIZA++ in terms of precision. Regarding other metrics, such as alignment error rate or F-measure, the parametric aligner, when trained on a very small gold-standard (450 pairs of sentences), provides results comparable to those produced by GIZA++ when trained on an in-domain corpus of around 10,000 pairs of sentences. Furthermore, the results obtained indicate that the training is domain-independent, which enables the use of the trained aligner 'on the fly' on any new pair of sentences.
Partition Refinement for Bisimilarity in CCP
Venue: arXiv cs.LO 2012
Year: 2012

Saraswat's concurrent constraint programming (ccp) is a mature formalism for modeling processes (or programs) that interact by telling and asking constraints in a global medium, called the store. Bisimilarity is a standard behavioural equivalence in concurrency theory, but a well-behaved notion of bisimilarity for ccp has been proposed only recently. When the state space of a system is finite, the ordinary notion of bisimilarity can be computed via the well-known partition refinement algorithm, but unfortunately, this algorithm does not work for ccp bisimilarity. In this paper, we propose a variation of the partition refinement algorithm for verifying ccp bisimilarity. To the best of our knowledge this is the first work providing for the automatic verification of program equivalence for ccp
Testing the AgreementMaker System in the Anatomy Task of OAEI 2012
Venue: arXiv cs.IR 2012
Year: 2012

The AgreementMaker system was the leading system in the anatomy task of the Ontology Alignment Evaluation Initiative (OAEI) competition in 2011. While AgreementMaker did not compete in OAEI 2012, here we report on its performance in the 2012 anatomy task, using the same configurations of AgreementMaker submitted to OAEI 2011. Additionally, we also test AgreementMaker using an updated version of the UBERON ontology as a mediating ontology, and otherwise identical configurations. AgreementMaker achieved an F-measure of 91.8% with the 2011 configurations, and an F-measure of 92.2% with the updated UBERON ontology. Thus, AgreementMaker would have been the second best system had it competed in the anatomy task of OAEI 2012, and only 0.1% below the F-measure of the best system.
Systematic Construction of Temporal Logics for Dynamical Systems via Coalgebra
Venue: arXiv cs.LO 2012
Year: 2012

Temporal logics are an obvious high-level descriptive companion formalism to dynamical systems which model behavior as deterministic evolution of state over time. A wide variety of distinct temporal logics applicable to dynamical systems exists, and each candidate has its own pragmatic justification. Here, a systematic approach to the construction of temporal logics for dynamical systems is proposed: Firstly, it is noted that dynamical systems can be seen as coalgebras in various ways. Secondly, a straightforward standard construction of modal logics out of coalgebras, namely Moss's coalgebraic logic, is applied. Lastly, the resulting systems are characterized with respect to the temporal properties they express.
Automated Usability Testing: Analysing Asia Web Sites
Venue: arXiv cs.HC 2012
Year: 2012

Web usability is continuing to be a pressing problem. For number of years researchers have been developed tools for doing automatic web usability testing. This study uses our own PHP, and MySQL based tool AWebHUT: Automated Web Homepage Usability Tester to evaluate web usability of full Dmoz (www.dmoz.org) Asia web sites (45126 on time stamp 2011-12-03 04:12:46 GMT). The tool uses an extensive automated quantitative analysis of XHTML source code of homepages against seventeen organised web usability guidelines. The automated quantitative approach is effective on large scale to achieve better usability. The AWebHUT uses four web usability levels such as N: Neutral, V: Violate, R: Respect, and E: Error to evaluate web usability. The main objective of the study is to produce data which is used to answer research questions, (1) Are there any categories of web sites which have usability problems? Which ones? and (2) Are there any categories in which the usability is typically higher? Why? The findings were indicated that all Asia categories have usability problems. Furthermore, there are four web sites which have highest web usability problem with violation percentage 71. One step further, the Asia category: Weather has highest usability problems with 42.2819 as the average of the violation percentage. The category Weather uses tables and images, considerable amount of those were not satisfying web usability guidelines which relates to tables and images. One step further, the Asia wants to get the same level of usability as North America, Europe, and Australia therefore it is essential to have an automated web usability evaluation in Asia web sites to identify web usability problems which are important for improving Asia web sites.
CTCP: Coded TCP using Multiple Paths
Venue: arXiv cs.NI 2012
Year: 2012

We introduce CTCP, a novel multi-path transport protocol using network coding. CTCP is designed to incorporate TCP's good features, such as congestion control and reliability, while improving on TCP's performance in lossy and/or dynamic networks. CTCP builds upon the ideas of TCP/NC introduced by Sundararajan et al. and uses network coding to provide robustness against losses. We introduce the use of multiple paths to provide robustness against mobility and network failures. We provide an implementation of CTCP (in userspace) to demonstrate its performance.
High-dimensional sequence transduction
Venue: arXiv cs.LG 2012
Year: 2012

We investigate the problem of transforming an input sequence into a high-dimensional output sequence in order to transcribe polyphonic audio music into symbolic notation. We introduce a probabilistic model based on a recurrent neural network that is able to learn realistic output distributions given the input and we devise an efficient algorithm to search for the global mode of that distribution. The resulting method produces musically plausible transcriptions even under high levels of noise and drastically outperforms previous state-of-the-art approaches on five datasets of synthesized sounds and real recordings, approximately halving the test error rate.
Amortized communication complexity of an equality predicate
Venue: arXiv cs.CC 2012
Year: 2012

We study the communication complexity of a direct sum of independent copies of the equality predicate. We prove that the probabilistic communication complexity of this problem is equal to O(N); computational complexity of the proposed protocol is polynomial in size of inputs. Our protocol improves the result achieved in 1995(Feder, Kushilevitz, Naor, Nisan). Our construction is based on two techniques: Nisan's pseudorandom generator (1992) and Smith's string synchronization algorithm (2007).
A simpler approach to obtaining an O(1/t) convergence rate for the projected stochastic subgradient method
Venue: arXiv cs.LG 2012
Year: 2012

In this note, we present a new averaging technique for the projected stochastic subgradient method. By using a weighted average with a weight of t+1 for each iterate w_t at iteration t, we obtain the convergence rate of O(1/t) with both an easy proof and an easy implementation. The new scheme is compared empirically to existing techniques, with similar performance behavior.
SDMS-based Disk Encryption Method
Venue: arXiv cs.CR 2012
Year: 2012

We propose a disk encryption method, called secure disk mixed system (SDMS) in this paper, for data protection of disk storages such as USB flash memory, USB hard disk and CD/DVD. It is aimed to solve temporal and spatial limitation problems of existing disk encryption methods and to control security performance flexibly according to the security requirement of system. SDMS stores data by encrypting with different encryption key per sector and updates sector encryption keys each time data is written. Security performance of SDMS is analyzed at the end of the paper.
Sparse Regression Codes for Multi-terminal Source and Channel Coding
Venue: arXiv cs.IT 2012
Year: 2012

We study a new class of codes for Gaussian multi-terminal source and channel coding. These codes are designed using the statistical framework of high-dimensional linear regression and are called Sparse Superposition or Sparse Regression codes. Codewords are linear combinations of subsets of columns of a design matrix. These codes were recently introduced by Barron and Joseph and shown to achieve the channel capacity of AWGN channels with computationally feasible decoding. They have also recently been shown to achieve the optimal rate-distortion function for Gaussian sources. In this paper, we demonstrate how to implement random binning and superposition coding using sparse regression codes. In particular, with minimum-distance encoding/decoding it is shown that sparse regression codes attain the optimal information-theoretic limits for a variety of multi-terminal source and channel coding problems.
A Scale-Space Theory for Text
Venue: arXiv cs.IR 2012
Year: 2012

Scale-space theory has been established primarily by the computer vision and signal processing communities as a well-founded and promising framework for multi-scale processing of signals (e.g., images). By embedding an original signal into a family of gradually coarsen signals parameterized with a continuous scale parameter, it provides a formal framework to capture the structure of a signal at different scales in a consistent way. In this paper, we present a scale space theory for text by integrating semantic and spatial filters, and demonstrate how natural language documents can be understood, processed and analyzed at multiple resolutions, and how this scale-space representation can be used to facilitate a variety of NLP and text analysis tasks.
Core stability in hedonic coalition formation
Venue: arXiv cs.GT 2012
Year: 2012

In many economic, social and political situations individuals carry out activities in groups (coalitions) rather than alone and on their own. Examples range from households and sport clubs to research networks, political parties and trade unions. The underlying game theoretic framework is known as coalition formation. This survey discusses the notion of core stability in hedonic coalition formation (where each player's happiness only depends on the other members of his coalition but not on how the remaining players outside his coalition are grouped). We present the central concepts and algorithmic approaches in the area, provide many examples, and pose a number of open problems.
A Propagation Model for Provenance Views of Public/Private Workflows
Venue: arXiv cs.DB 2012
Year: 2012

We study the problem of concealing functionality of a proprietary or private module when provenance information is shown over repeated executions of a workflow which contains both `public' and `private' modules. Our approach is to use `provenance views' to hide carefully chosen subsets of data over all executions of the workflow to ensure G-privacy: for each private module and each input x, the module's output f(x) is indistinguishable from G -1 other possible values given the visible data in the workflow executions. We show that G-privacy cannot be achieved simply by combining solutions for individual private modules; data hiding must also be `propagated' through public modules. We then examine how much additional data must be hidden and when it is safe to stop propagating data hiding. The answer depends strongly on the workflow topology as well as the behavior of public modules on the visible data. In particular, for a class of workflows (which include the common tree and chain workflows), taking private solutions for each private module, augmented with a `public closure' that is `upstream-downstream safe', ensures G-privacy. We define these notions formally and show that the restrictions are necessary. We also study the related optimization problems of minimizing the amount of hidden data.
A Process Calculus with Logical Operators
Venue: arXiv cs.LO 2012
Year: 2012

In order to combine operational and logical styles of specifications in one unified framework, the notion of logic labelled transition systems (Logic LTS, for short) has been presented and explored by Lüttgen and Vogler in [TCS 373(1-2):19-40; Inform. & Comput. 208:845-867]. In contrast with usual LTS, two logical constructors $\wedge$ and $\vee$ over Logic LTSs are introduced to describe logical combinations of specifications. Hitherto such framework has been dealt with in considerable depth, however, process algebraic style way has not yet been involved and the axiomatization of constructors over Logic LTSs is absent. This paper tries to develop Lüttgen and Vogler's work along this direction. We will present a process calculus for Logic LTSs (CLL, for short). The language CLL is explored in detail from two different but equivalent views. Based on behavioral view, the notion of ready simulation is adopted to formalize the refinement relation, and the behavioral theory is developed. Based on proof-theoretic view, a sound and ground-complete axiomatic system for CLL is provided, which captures operators in CLL through (in)equational laws.
Reconstruction of Integers from Pairwise Distances
Venue: arXiv cs.DM 2012
Year: 2012

Given a set of integers, one can easily construct the set of their pairwise distances. We consider the inverse problem: given a set of pairwise distances, find the integer set which realizes the pairwise distance set. This problem arises in a lot of fields in engineering and applied physics, and has confounded researchers for over 60 years. It is one of the few fundamental problems that are neither known to be NP-hard nor solvable by polynomial-time algorithms. Whether unique recovery is possible also remains an open question. In many practical applications where this problem occurs, the integer set is naturally sparse (i.e., the integers are sufficiently spaced), a property which has not been explored. In this work, we exploit the sparse nature of the integer set and develop a polynomial-time algorithm which provably recovers the set of integers (up to linear shift and reversal) from the set of their pairwise distances with arbitrarily high probability if the sparsity is $O(n^{1/2-\eps})$. Numerical simulations verify the effectiveness of the proposed algorithm.
Source Coding Problems with Conditionally Less Noisy Side Information
Venue: arXiv cs.IT 2012
Year: 2012

A computable expression for the rate-distortion (RD) function proposed by Heegard and Berger has eluded information theory for nearly three decades. Heegard and Berger's single-letter achievability bound is well known to be optimal for \emph{physically degraded} side information; however, it is not known whether the bound is optimal for arbitrarily correlated side information (general discrete memoryless sources). In this paper, we consider a new setup in which the side information at one receiver is \emph{conditionally less noisy} than the side information at the other. The new setup includes degraded side information as a special case, and it is motivated by the literature on degraded and less noisy broadcast channels. Our key contribution is a converse proving the optimality of Heegard and Berger's achievability bound in a new setting. The converse rests upon a certain \emph{single-letterization} lemma, which we prove using an information theoretic telescoping identity {recently presented by Kramer}. We also generalise the above ideas to two different successive-refinement problems.
Cooperative Negotiation in Autonomic Systems using Incremental Utility Elicitation
Venue: arXiv cs.GT 2012
Year: 2012

Decentralized resource allocation is a key problem for large-scale autonomic (or self-managing) computing systems. Motivated by a data center scenario, we explore efficient techniques for resolving resource conflicts via cooperative negotiation. Rather than computing in advance the functional dependence of each element's utility upon the amount of resource it receives, which could be prohibitively expensive, each element's utility is elicited incrementally. Such incremental utility elicitation strategies require the evaluation of only a small set of sampled utility function points, yet they find near-optimal allocations with respect to a minimax regret criterion. We describe preliminary computational experiments that illustrate the benefit of our approach.
Inference in Polytrees with Sets of Probabilities
Venue: arXiv cs.AI 2012
Year: 2012

Inferences in directed acyclic graphs associated with probability sets and probability intervals are NP-hard, even for polytrees. In this paper we focus on such inferences, and propose: 1) a substantial improvement on Tessems A / R algorithm FOR polytrees WITH probability intervals; 2) a new algorithm FOR direction - based local search(IN sets OF probability) that improves ON existing methods; 3) a collection OF branch - AND - bound algorithms that combine the previous techniques.The first two techniques lead TO approximate solutions, WHILE branch - AND - bound procedures can produce either exact OR approximate solutions.We report ON dramatic improvements ON existing techniques FOR inference WITH probability sets AND intervals, IN SOME cases reducing the computational effort BY many orders OF magnitude.
The Information Bottleneck EM Algorithm
Venue: arXiv cs.LG 2012
Year: 2012

Learning with hidden variables is a central challenge in probabilistic graphical models that has important implications for many real-life problems. The classical approach is using the Expectation Maximization (EM) algorithm. This algorithm, however, can get trapped in local maxima. In this paper we explore a new approach that is based on the Information Bottleneck principle. In this approach, we view the learning problem as a tradeoff between two information theoretic objectives. The first is to make the hidden variables uninformative about the identity of specific instances. The second is to make the hidden variables informative about the observed attributes. By exploring different tradeoffs between these two objectives, we can gradually converge on a high-scoring solution. As we show, the resulting, Information Bottleneck Expectation Maximization (IB-EM) algorithm, manages to find solutions that are superior to standard EM methods.
A Simple Insight into Iterative Belief Propagation's Success
Venue: arXiv cs.AI 2012
Year: 2012

In Non - ergodic belief networks the posterior belief OF many queries given evidence may become zero.The paper shows that WHEN belief propagation IS applied iteratively OVER arbitrary networks(the so called, iterative OR loopy belief propagation(IBP)) it IS identical TO an arc - consistency algorithm relative TO zero - belief queries(namely assessing zero posterior probabilities). This implies that zero - belief conclusions derived BY belief propagation converge AND are sound.More importantly it suggests that the inference power OF IBP IS AS strong AND AS weak, AS that OF arc - consistency.This allows the synthesis OF belief networks FOR which belief propagation IS useless ON one hand, AND focuses the investigation OF classes OF belief network FOR which belief propagation may be zero - complete.Finally, ALL the above conclusions apply also TO Generalized belief propagation algorithms that extend loopy belief propagation AND allow a crisper understanding OF their power.
Loopy Belief Propagation as a Basis for Communication in Sensor Networks
Venue: arXiv cs.AI 2012
Year: 2012

Sensor networks are an exciting new kind of computer system. Consisting of a large number of tiny, cheap computational devices physically distributed in an environment, they gather and process data about the environment in real time. One of the central questions in sensor networks is what to do with the data, i.e., how to reason with it and how to communicate it. This paper argues that the lessons of the UAI community, in particular that one should produce and communicate beliefs rather than raw sensor values, are highly relevant to sensor networks. We contend that loopy belief propagation is particularly well suited to communicating beliefs in sensor networks, due to its compact implementation and distributed nature. We investigate the ability of loopy belief propagation to function under the stressful conditions likely to prevail in sensor networks. Our experiments show that it performs well and degrades gracefully. It converges to appropriate beliefs even in highly asynchronous settings where some nodes communicate far less frequently than others; it continues to function if some nodes fail to participate in the propagation process; and it can track changes in the environment that occur while beliefs are propagating. As a result, we believe that sensor networks present an important application opportunity for UAI.
Large-Sample Learning of Bayesian Networks is NP-Hard
Venue: arXiv cs.LG 2012
Year: 2012

In this paper, we provide new complexity results for algorithms that learn discrete-variable Bayesian networks from data. Our results apply whenever the learning algorithm uses a scoring criterion that favors the simplest model able to represent the generative distribution exactly. Our results therefore hold whenever the learning algorithm uses a consistent scoring criterion and is applied to a sufficiently large dataset. We show that identifying high-scoring structures is hard, even when we are given an independence oracle, an inference oracle, and/or an information oracle. Our negative results also apply to the learning of discrete-variable Bayesian networks in which each node has at most k parents, for all k > 3.