OpenRaiser/Intern-Atlas huggingface dataset:
Anytime State-Based Solution Methods for Decision Processes with non-Markovian Rewards
Venue: arXiv cs.AI 2012
Year: 2012

A popular approach to solving a decision process with non-Markovian rewards (NMRDP) is to exploit a compact representation of the reward function to automatically translate the NMRDP into an equivalent Markov decision process (MDP) amenable to our favorite MDP solution method. The contribution of this paper is a representation of non-Markovian reward functions and a translation into MDP aimed at making the best possible use of state-based anytime algorithms as the solution method. By explicitly constructing and exploring only parts of the state space, these algorithms are able to trade computation time for policy quality, and have proven quite effective in dealing with large MDPs. Our representation extends future linear temporal logic (FLTL) to express rewards. Our translation has the effect of embedding model-checking in the solution method. It results in an MDP of the minimal size achievable without stepping outside the anytime framework, and consequently in better policies by the deadline.
Particle Filters in Robotics (Invited Talk)
Venue: arXiv cs.RO 2012
Year: 2012

This presentation will introduce the audience to a new, emerging body of research on sequential Monte Carlo techniques in robotics. In recent years, particle filters have solved several hard perceptual robotic problems. Early successes were limited to low-dimensional problems, such as the problem of robot localization in environments with known maps. More recently, researchers have begun exploiting structural properties of robotic domains that have led to successful particle filter applications in spaces with as many as 100,000 dimensions. The presentation will discuss specific tricks necessary to make these techniques work in real - world domains,and also discuss open challenges for researchers IN the UAI community.
Exploiting Functional Dependence in Bayesian Network Inference
Venue: arXiv cs.AI 2012
Year: 2012

We propose an efficient method for Bayesian network inference in models with functional dependence. We generalize the multiplicative factorization method originally designed by Takikawa and D Ambrosio(1999) FOR models WITH independence OF causal influence.Using a hidden variable, we transform a probability potential INTO a product OF two - dimensional potentials.The multiplicative factorization yields more efficient inference. FOR example, IN junction tree propagation it helps TO avoid large cliques. IN ORDER TO keep potentials small, the number OF states OF the hidden variable should be minimized.We transform this problem INTO a combinatorial problem OF minimal base IN a particular space.We present an example OF a computerized adaptive test, IN which the factorization method IS significantly more efficient than previous inference methods.
A New Class of Upper Bounds on the Log Partition Function
Venue: arXiv cs.LG 2012
Year: 2012

Bounds on the log partition function are important in a variety of contexts, including approximate inference, model fitting, decision theory, and large deviations analysis. We introduce a new class of upper bounds on the log partition function, based on convex combinations of distributions in the exponential domain, that is applicable to an arbitrary undirected graphical model. In the special case of convex combinations of tree-structured distributions, we obtain a family of variational problems, similar to the Bethe free energy, but distinguished by the following desirable properties: i. they are cnvex, and have a unique global minimum; and ii. the global minimum gives an upper bound on the log partition function. The global minimum is defined by stationary conditions very similar to those defining fixed points of belief propagation or tree-based reparameterization Wainwright et al., 2001. As with BP fixed points, the elements of the minimizing argument can be used as approximations to the marginals of the original model. The analysis described here can be extended to structures of higher treewidth e.g., hypertrees, thereby making connections with more advanced approximations e.g., Kikuchi and variants Yedidia et al., 2001; Minka, 2001.
IPF for Discrete Chain Factor Graphs
Venue: arXiv cs.LG 2012
Year: 2012

Iterative Proportional Fitting (IPF), combined with EM, is commonly used as an algorithm for likelihood maximization in undirected graphical models. In this paper, we present two iterative algorithms that generalize upon IPF. The first one is for likelihood maximization in discrete chain factor graphs, which we define as a wide class of discrete variable models including undirected graphical models and Bayesian networks, but also chain graphs and sigmoid belief networks. The second one is for conditional likelihood maximization in standard undirected models and Bayesian networks. In both algorithms, the iteration steps are expressed in closed form. Numerical simulations show that the algorithms are competitive with state of the art methods.
The risk assessment and treatment approach in order to provide lan security based on isms standard
Venue: arXiv cs.CR 2012
Year: 2012

Local Area Networks(LAN) at present become an important instrument for organizing of process and information communication in an organization. They provides important purposes such as association of large amount of data, hardware and software resources and expanding of optimum communications. Becase these network do work with valuable information, the problem of security providing is an important issue in organization. So, the stablishment of an information security management system(ISMS) in organization is significant. In this paper, we introduce ISMS and its implementation in LAN scop. The assets of LAN and threats and vulnerabilities of these assets are identified, the risks are evaluated and techniques to reduce them and at result security establishment of the network is expressed.
Reachability problems for communicating finite state machines
Venue: arXiv cs.LO 2012
Year: 2012

The paper deals with the verification of reachability properties in a commonly used state transition model of communication protocols, which consists of finite state machines connected by potentially unbounded FIFO channels. Although simple reachability problems are undecidable for general protocols with unbounded channels, they are decidable for the protocols with the recognizable channel property. The decidability question is open for the protocols with the rational channel property.
Get out the vote: Determining support or opposition from Congressional floor-debate transcripts
Venue: arXiv cs.CL 2012
Year: 2012

We investigate whether one can determine from the transcripts of U.S. Congressional floor debates whether the speeches represent support of or opposition to proposed legislation. To address this problem, we exploit the fact that these speeches occur as part of a discussion; this allows us to use sources of information regarding relationships between discourse segments, such as whether a given utterance indicates agreement with the opinion expressed by another. We find that the incorporation of such information yields substantial improvements over classifying speeches in isolation.
Sensitivity Analysis of the Orthoglide, a 3-DOF Translational Parallel Kinematic Machine
Venue: arXiv cs.RO 2013
Year: 2013

This paper presents a sensitivity analysis of the Orthoglide, a 3-DOF translational Parallel Kinematic Machine. Two complementary methods are developed to analyze its sensitivity to its dimensional and angular variations. First, a linkage kinematic analysis method is used to have a rough idea of the influence of the dimensional variations on the location of the end-effector. Besides, this method shows that variations in the design parameters of the same type from one leg to the other have the same influence on the end-effector. However, this method does not take into account the variations in the parallelograms. Thus, a differential vector method is used to study the influence of the dimensional and angular variations in the parts of the manipulator on the position and orientation of the end-effector, and particularly the influence of the variations in the parallelograms. It turns out that the kinematic isotropic configuration of the manipulator is the least sensitive one to its dimensional and angular variations. On the contrary, the closest configurations to its kinematic singular configurations are the most sensitive ones to geometrical variations.
A Nearly Linear-Time PTAS for Explicit Fractional Packing and Covering Linear Programs
Venue: arXiv cs.DS 2013
Year: 2013

We give an approximation algorithm for packing and covering linear programs (linear programs with non-negative coefficients). Given a constraint matrix with n non-zeros, r rows, and c columns, the algorithm computes feasible primal and dual solutions whose costs are within a factor of 1+eps of the optimal cost in time O((r+c)log(n)/eps^2 + n).
A quadratic algorithm for road coloring
Venue: arXiv cs.DS 2013
Year: 2013

The Road Coloring Theorem states that every aperiodic directed graph with constant out-degree has a synchronized coloring. This theorem had been conjectured during many years as the Road Coloring Problem before being settled by A. Trahtman. Trahtman's proof leads to an algorithm that finds a synchronized labeling with a cubic worst-case time complexity. We show a variant of his construction with a worst-case complexity which is quadratic in time and linear in space. We also extend the Road Coloring Theorem to the periodic case.
Nonorthogonal Bases and Phase Decomposition: Properties and Applications
Venue: arXiv cs.NA 2013
Year: 2013

In a previous paper [1] it was discussed the viability of functional analysis using as a basis a couple of generic functions, and hence vectorial decomposition. Here we complete the paradigm exploiting one of the analysis methodologies developed there, but applied to phase coordinates, so needing only one function as a basis. It will be shown that, thanks to the novel iterative analysis, any function satisfying a rather loose requisite is ontologically a basis. This in turn generalizes the polar version of the Fourier theorem to an ample class of nonorthogonal bases. The main advantage of this generalization is that it inherits some of the properties of the original Fourier theorem. As a result the new transform has a wide range of applications and some remarkable consequences. The new tool will be compared with wavelets and frames. Examples of analysis and reconstruction of functions using the developed algorithms and generic bases will be given. Some of the properties, and applications that can promptly benefit from the theory, will be discussed. The implementation of a matched filter for noise suppression will be used as an example of the potential of the theory.
Characterizing Truthful Multi-Armed Bandit Mechanisms
Venue: arXiv cs.DS 2013
Year: 2013

We consider a multi-round auction setting motivated by pay-per-click auctions for Internet advertising. In each round the auctioneer selects an advertiser and shows her ad, which is then either clicked or not. An advertiser derives value from clicks; the value of a click is her private information. Initially, neither the auctioneer nor the advertisers have any information about the likelihood of clicks on the advertisements. The auctioneer's goal is to design a (dominant strategies) truthful mechanism that (approximately) maximizes the social welfare. If the advertisers bid their true private values, our problem is equivalent to the "multi-armed bandit problem", and thus can be viewed as a strategic version of the latter. In particular, for both problems the quality of an algorithm can be characterized by "regret", the difference in social welfare between the algorithm and the benchmark which always selects the same "best" advertisement. We investigate how the design of multi-armed bandit algorithms is affected by the restriction that the resulting mechanism must be truthful. We find that truthful mechanisms have certain strong structural properties -- essentially, they must separate exploration from exploitation -- and they incur much higher regret than the optimal multi-armed bandit algorithms. Moreover, we provide a truthful mechanism which (essentially) matches our lower bound on regret.
A process calculus with finitary comprehended terms
Venue: arXiv cs.LO 2013
Year: 2013

We introduce the notion of an ACP process algebra and the notion of a meadow enriched ACP process algebra. The former notion originates from the models of the axiom system ACP. The latter notion is a simple generalization of the former notion to processes in which data are involved, the mathematical structure of data being a meadow. Moreover, for all associative operators from the signature of meadow enriched ACP process algebras that are not of an auxiliary nature, we introduce variable-binding operators as generalizations. These variable-binding operators, which give rise to comprehended terms, have the property that they can always be eliminated. Thus, we obtain a process calculus whose terms can be interpreted in all meadow enriched ACP process algebras. Use of the variable-binding operators can have a major impact on the size of terms.
Compressive Sampling with Known Spectral Energy Density
Venue: arXiv cs.IT 2013
Year: 2013

A method to improve l1 performance of the CS (Compressive Sampling) for A-scan SFCW-GPR (Stepped Frequency Continuous Wave-Ground Penetrating Radar) signals with known spectral energy density is proposed. Instead of random sampling, the proposed method selects the location of samples to follow the distribution of the spectral energy. Samples collected from three different measurement methods; the uniform sampling, random sampling, and energy equipartition sampling, are used to reconstruct a given monocycle signal whose spectral energy density is known. Objective performance evaluation in term of PSNR (Peak Signal to Noise Ratio) indicates empirically that the CS reconstruction of random sampling outperform the uniform sampling, while the energy equipartition sampling outperforms both of them. These results suggest that similar performance improvement can be achieved for the compressive SFCW (Stepped Frequency Continuous Wave) radar, allowing even higher acquisition speed.
A Logic Programming Approach to Activity Recognition
Venue: arXiv cs.AI 2013
Year: 2013

We have been developing a system for recognising human activity given a symbolic representation of video content. The input of our system is a set of time-stamped short-term activities detected on video frames. The output of our system is a set of recognised long-term activities, which are pre-defined temporal combinations of short-term activities. The constraints on the short-term activities that, if satisfied, lead to the recognition of a long-term activity, are expressed using a dialect of the Event Calculus. We illustrate the expressiveness of the dialect by showing the representation of several typical complex activities. Furthermore, we present a detailed evaluation of the system through experimentation on a benchmark dataset of surveillance videos.
Deterministic counting of graph colourings using sequences of subgraphs
Venue: arXiv cs.DM 2013
Year: 2013

In this paper we propose a deterministic algorithm for approximately counting the $k$-colourings of sparse random graphs $G(n,d/n)$. In particular, our algorithm computes in polynomial time a $(1\pm n^{-Ω(1)})$approximation of the logarithm of the number of $k$-colourings of $G(n,d/n)$ for $k\geq (2+ε) d$ with high probability over the graph instances. Our algorithm is related to the algorithms of A. Bandyopadhyay et al. in SODA '06, and A. Montanari et al. in SODA '06, i.e. it uses {\em spatial correlation decay} to compute {\em deterministically} marginals of {\em Gibbs distribution}. We develop a scheme whose accuracy depends on {\em non-reconstruction} of the colourings of $G(n,d/n)$, rather than {\em uniqueness} that are required in previous works. This leaves open the possibility for our schema to be sufficiently accurate even for $k<d$. The set up for establishing correlation decay is as follows: Given $G(n,d/n)$, we alter the graph structure in some specific region $Λ$ of the graph by deleting edges between vertices of $Λ$. Then we show that the effect of this change on the marginals of Gibbs distribution, diminishes as we move away from $Λ$. Our approach is novel and suggests a new context for the study of deterministic counting algorithms.
From Abstract Rewriting Systems to Abstract Proof Systems
Venue: arXiv cs.LO 2013
Year: 2013

Some personal recollections on the introduction of `abstract proof systems' as a framework for formulating syntax-independent, general results about rule derivability and admissibility. With a particular eye on the inspiration I owe to Roel de Vrijer: the analogy with abstract rewriting systems.
A Complete Characterization of Statistical Query Learning with Applications to Evolvability
Venue: arXiv cs.CC 2013
Year: 2013

Statistical query (SQ) learning model of Kearns (1993) is a natural restriction of the PAC learning model in which a learning algorithm is allowed to obtain estimates of statistical properties of the examples but cannot see the examples themselves. We describe a new and simple characterization of the query complexity of learning in the SQ learning model. Unlike the previously known bounds on SQ learning our characterization preserves the accuracy and the efficiency of learning. The preservation of accuracy implies that that our characterization gives the first characterization of SQ learning in the agnostic learning framework. The preservation of efficiency is achieved using a new boosting technique and allows us to derive a new approach to the design of evolutionary algorithms in Valiant's (2006) model of evolvability. We use this approach to demonstrate the existence of a large class of monotone evolutionary learning algorithms based on square loss performance estimation. These results differ significantly from the few known evolutionary algorithms and give evidence that evolvability in Valiant's model is a more versatile phenomenon than there had been previous reason to suspect.
Polynomial Time Algorithm for Graph Isomorphism Testing
Venue: arXiv cs.DS 2013
Year: 2013

This article deals with new polynomial time algorithm for graph isomorphism testing.
Optimality and Approximate Optimality of Source-Channel Separation in Networks
Venue: arXiv cs.IT 2013
Year: 2013

We consider the source-channel separation architecture for lossy source coding in communication networks. It is shown that the separation approach is optimal in two general scenarios, and is approximately optimal in a third scenario. The two scenarios for which separation is optimal complement each other: the first is when the memoryless sources at source nodes are arbitrarily correlated, each of which is to be reconstructed at possibly multiple destinations within certain distortions, but the channels in this network are synchronized, orthogonal and memoryless point-to-point channels; the second is when the memoryless sources are mutually independent, each of which is to be reconstructed only at one destination within a certain distortion, but the channels are general, including multi-user channels such as multiple access, broadcast, interference and relay channels, possibly with feedback. The third scenario, for which we demonstrate approximate optimality of source-channel separation, generalizes the second scenario by allowing each source to be reconstructed at multiple destinations with different distortions. For this case, the loss from optimality by using the separation approach can be upper-bounded when a "difference" distortion measure is taken, and in the special case of quadratic distortion measure, this leads to universal constant bounds.
On the Deterministic Code Capacity Region of an Arbitrarily Varying Multiple-Access Channel Under List Decoding
Venue: arXiv cs.IT 2013
Year: 2013

We study the capacity region $C_L$ of an arbitrarily varying multiple-access channel (AVMAC) for deterministic codes with decoding into a list of a fixed size $L$ and for the average error probability criterion. Motivated by known results in the study of fixed size list decoding for a point-to-point arbitrarily varying channel, we define for every AVMAC whose capacity region for random codes has a nonempty interior, a nonnegative integer $Ω$ called its symmetrizability. It is shown that for every $L \leq Ω$, $C_L$ has an empty interior, and for every $L \geq (Ω+1)^2$, $C_L$ equals the nondegenerate capacity region of the AVMAC for random codes with a known single-letter characterization. For a binary AVMAC with a nondegenerate random code capacity region, it is shown that the symmetrizability is always finite.
Reliability Distributions of Truncated Max-log-map (MLM) Detectors Applied to ISI Channels
Venue: arXiv cs.IT 2013
Year: 2013

The max-log-map (MLM) receiver is an approximated version of the well-known, Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm. The MLM algorithm is attractive due to its implementation simplicity. In practice, sliding-window implementations are preferred; these practical implementations consider truncated signaling neighborhoods around each transmission time instant. In this paper, we consider sliding-window MLM receivers, where for any integer m, the MLM detector is truncated to a length- m signaling neighborhood. For any number n of chosen times instants, we derive exact expressions for both i) the joint distribution of the MLM symbol reliabilities, and ii) the joint probability of the erroneous MLM symbol detections. We show that the obtained expressions can be efficiently evaluated using Monte-Carlo techniques. Our proposed method is efficient; the most computationally expensive operation (in each Monte-Carlo trial) is an eigenvalue decomposition of a size 2mn by 2mn matrix. Practical truncation lengths can be easily handled. Finally, our proposed method is extremely general, and various scenarios such as correlated noise distributions, modulation coding, etc. may be easily accommodated.
Encoding Complexity of Network Coding with Two Simple Multicast Sessions
Venue: arXiv cs.IT 2013
Year: 2013

The encoding complexity of network coding for single multicast networks has been intensively studied from several aspects: e.g., the time complexity, the required number of encoding links, and the required field size for a linear code solution. However, these issues as well as the solvability are less understood for networks with multiple multicast sessions. Recently, Wang and Shroff showed that the solvability of networks with two unit-rate multicast sessions (2-URMS) can be decided in polynomial time. In this paper, we prove that for the 2-URMS networks: $1)$ the solvability can be determined with time $O(|E|)$; $2)$ a solution can be constructed with time $O(|E|)$; $3)$ an optimal solution can be obtained in polynomial time; $4)$ the number of encoding links required to achieve a solution is upper-bounded by $\max\{3,2N-2\}$; and $5)$ the field size required to achieve a linear solution is upper-bounded by $\max\{2,\lfloor\sqrt{2N-7/4}+1/2\rfloor\}$, where $|E|$ is the number of links and $N$ is the number of sinks of the underlying network. Both bounds are shown to be tight.
Minimum-Area Enclosing Triangle with a Fixed Angle
Venue: arXiv cs.CG 2013
Year: 2013

Given a set S of n points in the plane and a fixed angle 0 < omega < pi, we show how to find in O(n log n) time all triangles of minimum area with one angle omega that enclose S. We prove that in general, the solution cannot be written without cubic roots. We also prove an Omega(n log n) lower bound for this problem in the algebraic computation tree model. If the input is a convex n-gon, our algorithm takes Theta(n) time.