OpenRaiser/Intern-Atlas huggingface dataset:
Building a reordering system using tree-to-string hierarchical model
Venue: arXiv cs.CL 2013
Year: 2013

This paper describes our submission to the First Workshop on Reordering for Statistical Machine Translation. We have decided to build a reordering system based on tree-to-string model, using only publicly available tools to accomplish this task. With the provided training data we have built a translation model using Moses toolkit, and then we applied a chart decoder, implemented in Moses, to reorder the sentences. Even though our submission only covered English-Farsi language pair, we believe that the approach itself should work regardless of the choice of the languages, so we have also carried out the experiments for English-Italian and English-Urdu. For these language pairs we have noticed a significant improvement over the baseline in BLEU, Kendall-Tau and Hamming metrics. A detailed description is given, so that everyone can reproduce our results. Also, some possible directions for further improvements are discussed.
Petri Nets with Time and Cost
Venue: arXiv cs.LO 2013
Year: 2013

We consider timed Petri nets, i.e., unbounded Petri nets where each token carries a real-valued clock. Transition arcs are labeled with time intervals, which specify constraints on the ages of tokens. Our cost model assigns token storage costs per time unit to places, and firing costs to transitions. We study the cost to reach a given control-state. In general, a cost-optimal run may not exist. However,we show that the infimum of the costs is computable.
The min-max edge q-coloring problem
Venue: arXiv cs.DS 2013
Year: 2013

In this paper we introduce and study a new problem named \emph{min-max edge $q$-coloring} which is motivated by applications in wireless mesh networks. The input of the problem consists of an undirected graph and an integer $q$. The goal is to color the edges of the graph with as many colors as possible such that: (a) any vertex is incident to at most $q$ different colors, and (b) the maximum size of a color group (i.e. set of edges identically colored) is minimized. We show the following results: 1. Min-max edge $q$-coloring is NP-hard, for any $q \ge 2$. 2. A polynomial time exact algorithm for min-max edge $q$-coloring on trees. 3. Exact formulas of the optimal solution for cliques and almost tight bounds for bicliques and hypergraphs. 4. A non-trivial lower bound of the optimal solution with respect to the average degree of the graph. 5. An approximation algorithm for planar graphs.
Eigenfunctions of the Edge-Based Laplacian on a Graph
Venue: arXiv cs.DM 2013
Year: 2013

In this paper, we analyze the eigenfunctions of the edge-based Laplacian on a graph and the relationship of these functions to random walks on the graph. We commence by discussing the set of eigenfunctions supported at the vertices, and demonstrate the relationship of these eigenfunctions to the classical random walk on the graph. Then, from an analysis of functions supported only on the interior of edges, we develop a method for explicitly calculating the edge-interior eigenfunctions of the edge-based Laplacian. This reveals a connection between the edge-based Laplacian and the adjacency matrix of backtrackless random walk on the graph. The edge-based eigenfunctions therefore correspond to some eigenfunctions of the normalised Hashimoto matrix.
On Polynomial Kernels for Sparse Integer Linear Programs
Venue: arXiv cs.CC 2013
Year: 2013

Integer linear programs (ILPs) are a widely applied framework for dealing with combinatorial problems that arise in practice. It is known, e.g., by the success of CPLEX, that preprocessing and simplification can greatly speed up the process of optimizing an ILP. The present work seeks to further the theoretical understanding of preprocessing for ILPs by initiating a rigorous study within the framework of parameterized complexity and kernelization. A famous result of Lenstra (Mathematics of Operations Research, 1983) shows that feasibility of any ILP with n variables and m constraints can be decided in time O(c^{n^3} m^c'). Thus, by a folklore argument, any such ILP admits a kernelization to an equivalent instance of size O(c^{n^3}). It is known, that unless NP \subseteq coNP/poly and the polynomial hierarchy collapses, no kernelization with size bound polynomial in n is possible. However, this lower bound only applies for the case when constraints may include an arbitrary number of variables since it follows from lower bounds for Satisfiability and Hitting Set, whose bounded arity variants admit polynomial kernelizations. We consider the feasibility problem for ILPs Ax<= b where A is an r-row-sparse matrix parameterized by the number of variables. We show that the kernelizability of this problem depends strongly on the range of the variables. If the range is unbounded then this problem does not admit a polynomial kernelization unless NP \subseteq coNP/poly. If, on the other hand, the range of each variable is polynomially bounded in n then we do get a polynomial kernelization. Additionally, this holds also for the more general case when the maximum range d is an additional parameter, i.e., the size obtained is polynomial in n+d.
Inference Using Message Propagation and Topology Transformation in Vector Gaussian Continuous Networks
Venue: arXiv cs.AI 2013
Year: 2013

We extend Gaussian networks - directed acyclic graphs that encode probabilistic relationships between variables - to its vector form. Vector Gaussian continuous networks consist of composite nodes representing multivariates, that take continuous values. These vector or composite nodes can represent correlations between parents, as opposed to conventional univariate nodes. We derive rules for inference in these networks based on two methods: message propagation and topology transformation. These two approaches lead to the development of algorithms, that can be implemented in either a centralized or a decentralized manner. The domain of application of these networks are monitoring and estimation problems. This new representation along with the rules for inference developed here can be used to derive current Bayesian algorithms such as the Kalman filter, and provide a rich foundation to develop new algorithms. We illustrate this process by deriving the decentralized form of the Kalman filter. This work unifies concepts from artificial intelligence and modern control theory.
Arguing for Decisions: A Qualitative Model of Decision Making
Venue: arXiv cs.AI 2013
Year: 2013

We develop a qualitative model of decision making with two aims: to describe how people make simple decisions and to enable computer programs to do the same. Current approaches based on Planning or Decisions Theory either ignore uncertainty and tradeoffs, or provide languages and algorithms that are too complex for this task. The proposed model provides a language based on rules, a semantics based on high probabilities and lexicographical preferences, and a transparent decision procedure where reasons for and against decisions interact. The model is no substitude for Decision Theory, yet for decisions that people find easy to explain it may provide an appealing alternative.
Bayesian Learning of Loglinear Models for Neural Connectivity
Venue: arXiv cs.LG 2013
Year: 2013

This paper presents a Bayesian approach to learning the connectivity structure of a group of neurons from data on configuration frequencies. A major objective of the research is to provide statistical tools for detecting changes in firing patterns with changing stimuli. Our framework is not restricted to the well-understood case of pair interactions, but generalizes the Boltzmann machine model to allow for higher order interactions. The paper applies a Markov Chain Monte Carlo Model Composition (MC3) algorithm to search over connectivity structures and uses Laplace's method to approximate posterior probabilities of structures. Performance of the methods was tested on synthetic data. The models were also applied to data obtained by Vaadia on multi-unit recordings of several neurons in the visual cortex of a rhesus monkey in two different attentional states. Results confirmed the experimenters' conjecture that different attentional states were associated with different interaction structures.
Toward a Market Model for Bayesian Inference
Venue: arXiv cs.GT 2013
Year: 2013

We present a methodology for representing probabilistic relationships in a general-equilibrium economic model. Specifically, we define a precise mapping from a Bayesian network with binary nodes to a market price system where consumers and producers trade in uncertain propositions. We demonstrate the correspondence between the equilibrium prices of goods in this economy and the probabilities represented by the Bayesian network. A computational market model such as this may provide a useful framework for investigations of belief aggregation, distributed probabilistic inference, resource allocation under uncertainty, and other problems of decentralized uncertainty.
A Framework for Decision-Theoretic Planning I: Combining the Situation Calculus, Conditional Plans, Probability and Utility
Venue: arXiv cs.AI 2013
Year: 2013

This paper shows how we can combine logical representations of actions and decision theory in such a manner that seems natural for both. In particular we assume an axiomatization of the domain in terms of situation calculus, using what is essentially Reiter's solution to the frame problem, in terms of the completion of the axioms defining the state change. Uncertainty is handled in terms of the independent choice logic, which allows for independent choices and a logic program that gives the consequences of the choices. As part of the consequences are a specification of the utility of (final) states. The robot adopts robot plans, similar to the GOLOG programming language. Within this logic, we can define the expected utility of a conditional plan, based on the axiomatization of the actions, the uncertainty and the utility. The ?planning' problem is to find the plan with the highest expected utility. This is related to recent structured representations for POMDPs; here we use stochastic situation calculus rules to specify the state transition function and the reward/value function. Finally we show that with stochastic frame axioms, actions representations in probabilistic STRIPS are exponentially larger than using the representation proposed here.
A Polynomial-Time Algorithm for Deciding Markov Equivalence of Directed Cyclic Graphical Models
Venue: arXiv cs.AI 2013
Year: 2013

Although the concept of d-separation was originally defined for directed acyclic graphs (see Pearl 1988), there is a natural extension of he concept to directed cyclic graphs. When exactly the same set of d-separation relations hold in two directed graphs, no matter whether respectively cyclic or acyclic, we say that they are Markov equivalent. In other words, when two directed cyclic graphs are Markov equivalent, the set of distributions that satisfy a natural extension of the Global Directed Markov condition (Lauritzen et al. 1990) is exactly the same for each graph. There is an obvious exponential (in the number of vertices) time algorithm for deciding Markov equivalence of two directed cyclic graphs; simply chech all of the d-separation relations in each graph. In this paper I state a theorem that gives necessary and sufficient conditions for the Markov equivalence of two directed cyclic graphs, where each of the conditions can be checked in polynomial time. Hence, the theorem can be easily adapted into a polynomial time algorithm for deciding the Markov equivalence of two directed cyclic graphs. Although space prohibits inclusion of correctness proofs, they are fully described in Richardson (1994b).
A Measure of Decision Flexibility
Venue: arXiv cs.AI 2013
Year: 2013

We propose a decision-analytical approach to comparing the flexibility of decision situations from the perspective of a decision-maker who exhibits constant risk-aversion over a monetary value model. Our approach is simple yet seems to be consistent with a variety of flexibility concepts, including robust and adaptive alternatives. We try to compensate within the model for uncertainty that was not anticipated or not modeled. This approach not only allows one to compare the flexibility of plans, but also guides the search for new, more flexible alternatives.
Partial Third-Party Information Exchange with Network Coding
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we consider the problem of exchanging channel state information in a wireless network such that a subset of the clients can obtain the complete channel state information of all the links in the network. We first derive the minimum number of required transmissions for such partial third-party information exchange problem. We then design an optimal transmission scheme by determining the number of packets that each client should send, and designing a deterministic encoding strategy such that the subset of clients can acquire complete channel state information of the network with minimal number of transmissions. Numerical results show that network coding can efficiently reduce the number of transmissions, even with only pairwise encoding.
Checkpointing algorithms and fault prediction
Venue: arXiv cs.DC 2013
Year: 2013

This paper deals with the impact of fault prediction techniques on checkpointing strategies. We extend the classical first-order analysis of Young and Daly in the presence of a fault prediction system, characterized by its recall and its precision. In this framework, we provide an optimal algorithm to decide when to take predictions into account, and we derive the optimal value of the checkpointing period. These results allow to analytically assess the key parameters that impact the performance of fault predictors at very large scale.
Analysis of Descent-Based Image Registration
Venue: arXiv cs.CV 2013
Year: 2013

We present a performance analysis for image registration with gradient descent methods. We consider a typical multiscale registration setting where the global 2-D translation between a pair of images is estimated by smoothing the images and minimizing the distance between them with gradient descent. Our study particularly concentrates on the effect of noise and low-pass filtering on the alignment accuracy. We adopt an analytic representation for images and analyze the well-behavedness of the image distance function by estimating the neighborhood of translations for which it is free of undesired local minima. This corresponds to the neighborhood of translation vectors that are correctly computable with a simple gradient descent minimization. We show that the area of this neighborhood increases at least quadratically with the smoothing filter size, which justifies the use of a smoothing step in image registration with local optimizers such as gradient descent. We then examine the effect of noise on the alignment accuracy and derive an upper bound for the alignment error in terms of the noise properties and filter size. Our main finding is that the error increases at a rate that is at least linear with respect to the filter size. Therefore, smoothing improves the well-behavedness of the distance function; however, this comes at the cost of amplifying the alignment error in noisy settings. Our results provide a mathematical insight about why hierarchical techniques are effective in image registration, suggesting that the multiscale coarse-to-fine alignment strategy of these techniques is very suitable from the perspective of the trade-off between the well-behavedness of the objective function and the registration accuracy. To the best of our knowledge, this is the first such study for descent-based image registration.
Rumor Spreading in Random Evolving Graphs
Venue: arXiv cs.DM 2013
Year: 2013

Randomized gossip is one of the most popular way of disseminating information in large scale networks. This method is appreciated for its simplicity, robustness, and efficiency. In the "push" protocol, every informed node selects, at every time step (a.k.a. round), one of its neighboring node uniformly at random and forwards the information to this node. This protocol is known to complete information spreading in $O(\log n)$ time steps with high probability (w.h.p.) in several families of $n$-node "static" networks. The Push protocol has also been empirically shown to perform well in practice, and, specifically, to be robust against dynamic topological changes. In this paper, we aim at analyzing the Push protocol in "dynamic" networks. We consider the "edge-Markovian" evolving graph model which captures natural temporal dependencies between the structure of the network at time $t$, and the one at time $t+1$. Precisely, a non-edge appears with probability $p$, while an existing edge dies with probability $q$. In order to fit with real-world traces, we mostly concentrate our study on the case where $p=Ω(1/n)$ and $q$ is constant. We prove that, in this realistic scenario, the Push protocol does perform well, completing information spreading in $O(\log n)$ time steps w.h.p. Note that this performance holds even when the network is, w.h.p., disconnected at every time step (e.g., when $p << (\log n) / n$). Our result provides the first formal argument demonstrating the robustness of the Push protocol against network changes. We also address other ranges of parameters $p$ and $q$ (e.g., $p+q=1$ with arbitrary $p$ and $q$, and $p=1/n$ with arbitrary $q$). Although they do not precisely fit with the measures performed on real-world traces, they can be of independent interest for other settings. The results in these cases confirm the positive impact of dynamism.
Robust Image Segmentation in Low Depth Of Field Images
Venue: arXiv cs.CV 2013
Year: 2013

In photography, low depth of field (DOF) is an important technique to emphasize the object of interest (OOI) within an image. Thus, low DOF images are widely used in the application area of macro, portrait or sports photography. When viewing a low DOF image, the viewer implicitly concentrates on the regions that are sharper regions of the image and thus segments the image into regions of interest and non regions of interest which has a major impact on the perception of the image. Thus, a robust algorithm for the fully automatic detection of the OOI in low DOF images provides valuable information for subsequent image processing and image retrieval. In this paper we propose a robust and parameterless algorithm for the fully automatic segmentation of low DOF images. We compare our method with three similar methods and show the superior robustness even though our algorithm does not require any parameters to be set by hand. The experiments are conducted on a real world data set with high and low DOF images.
Maximal Syntactic Complexity of Regular Languages Implies Maximal Quotient Complexities of Atoms
Venue: arXiv cs.FL 2013
Year: 2013

We relate two measures of complexity of regular languages. The first is syntactic complexity, that is, the cardinality of the syntactic semigroup of the language. That semigroup is isomorphic to the semigroup of transformations of states induced by non-empty words in the minimal deterministic finite automaton accepting the language. If the language has n left quotients (its minimal automaton has n states), then its syntactic complexity is at most n^n and this bound is tight. The second measure consists of the quotient (state) complexities of the atoms of the language, where atoms are non-empty intersections of complemented and uncomplemented quotients. A regular language has at most 2^n atoms and this bound is tight. The maximal quotient complexity of any atom with r complemented quotients is 2^n-1, if r=0 or r=n, and 1+\sum_{k=1}^{r} \sum_{h=k+1}^{k+n-r} \binom{h}{n} \binom{k}{h}, otherwise. We prove that if a language has maximal syntactic complexity, then it has 2^n atoms and each atom has maximal quotient complexity, but the converse is false.
Coordination Control of Heterogeneous Compounded-Order Multi-Agent Systems with Communication Delays
Venue: arXiv cs.SY 2013
Year: 2013

Since the complexity of the practical environment, many distributed networked systems can not be illustrated with the integer-order dynamics and only be described as the fractional-order dynamics. Suppose multi-agent systems will show the individual diversity with difference agents, where the heterogeneous (integer-order and fractional-order) dynamics are used to illustrate the agent systems and compose integer-fractional compounded-order systems. Applying Laplace transform and frequency domain theory of the fractional-order operator, consensus of delayed multi-agent systems with directed weighted topologies is studied. Since integer-order model is the special case of fractional-order model, the results in this paper can be extend to the systems with integer-order models. Finally, numerical examples are used to verify our results.
Order Preserving Matching
Venue: arXiv cs.DS 2013
Year: 2013

We introduce a new string matching problem called order-preserving matching on numeric strings where a pattern matches a text if the text contains a substring whose relative orders coincide with those of the pattern. Order-preserving matching is applicable to many scenarios such as stock price analysis and musical melody matching in which the order relations should be matched instead of the strings themselves. Solving order-preserving matching has to do with representations of order relations of a numeric string. We define prefix representation and nearest neighbor representation, which lead to efficient algorithms for order-preserving matching. We present efficient algorithms for single and multiple pattern cases. For the single pattern case, we give an O(n log m) time algorithm and optimize it further to obtain O(n + m log m) time. For the multiple pattern case, we give an O(n log m) time algorithm.
Adaptive Set-Membership Reduced-Rank Least Squares Beamforming Algorithms
Venue: arXiv cs.IT 2013
Year: 2013

This paper presents a new adaptive algorithm for the linearly constrained minimum variance (LCMV) beamformer design. We incorporate the set-membership filtering (SMF) mechanism into the reduced-rank joint iterative optimization (JIO) scheme to develop a constrained recursive least squares (RLS) based algorithm called JIO-SM-RLS. The proposed algorithm inherits the positive features of reduced-rank signal processing techniques to enhance the output performance, and utilizes the data-selective updates (around 10-15%) of the SMF methodology to save the computational cost significantly. An effective time-varying bound is imposed on the array output as a constraint to circumvent the risk of overbounding or underbounding, and to update the parameters for beamforming. The updated parameters construct a set of solutions (a membership set) that satisfy the constraints of the LCMV beamformer. Simulations are performed to show the superior performance of the proposed algorithm in terms of the convergence rate and the reduced computational complexity in comparison with the existing methods.
Fresh-Variable Automata for Service Composition
Venue: arXiv cs.FL 2013
Year: 2013

To model Web services handling data from an infinite domain, or with multiple sessions, we introduce fresh-variable automata, a simple extension of finite-state automata in which some transitions are labeled with variables that can be refreshed in some specified states. We prove several closure properties for this class of automata and study their decision problems. We then introduce a notion of simulation that enables us to reduce the Web service composition problem to the construction of a simulation of a target service by the asynchronous product of existing services, and prove that this construction is computable.