OpenRaiser/Intern-Atlas huggingface dataset:
Qualitative Possibilistic Mixed-Observable MDPs
Venue: arXiv cs.AI 2013
Year: 2013

Possibilistic and qualitative POMDPs (pi-POMDPs) are counterparts of POMDPs used to model situations where the agent's initial belief or observation probabilities are imprecise due to lack of past experiences or insufficient data collection. However, like probabilistic POMDPs, optimally solving pi-POMDPs is intractable: the finite belief state space exponentially grows with the number of system's states. In this paper, a possibilistic version of Mixed-Observable MDPs is presented to get around this issue: the complexity of solving pi-POMDPs, some state variables of which are fully observable, can be then dramatically reduced. A value iteration algorithm for this new formulation under infinite horizon is next proposed and the optimality of the returned policy (for a specified criterion) is shown assuming the existence of a "stay" action in some goal states. Experimental work finally shows that this possibilistic model outperforms probabilistic POMDPs commonly used in robotics, for a target recognition problem where the agent's observations are imprecise.
Causal Transportability of Experiments on Controllable Subsets of Variables: z-Transportability
Venue: arXiv cs.AI 2013
Year: 2013

We introduce z-transportability, the problem of estimating the causal effect of a set of variables X on another set of variables Y in a target domain from experiments on any subset of controllable variables Z where Z is an arbitrary subset of observable variables V in a source domain. z-Transportability generalizes z-identifiability, the problem of estimating in a given domain the causal effect of X on Y from surrogate experiments on a set of variables Z such that Z is disjoint from X;. z-Transportability also generalizes transportability which requires that the causal effect of X on Y in the target domain be estimable from experiments on any subset of all observable variables in the source domain. We first generalize z-identifiability to allow cases where Z is not necessarily disjoint from X. Then, we establish a necessary and sufficient condition for z-transportability in terms of generalized z-identifiability and transportability. We provide a correct and complete algorithm that determines whether a causal effect is z-transportable; and if it is, produces a transport formula, that is, a recipe for estimating the causal effect of X on Y in the target domain using information elicited from the results of experimental manipulations of Z in the source domain and observational data from the target domain. Our results also show that do-calculus is complete for z-transportability.
Evaluating computational models of explanation using human judgments
Venue: arXiv cs.AI 2013
Year: 2013

We evaluate four computational models of explanation in Bayesian networks by comparing model predictions to human judgments. In two experiments, we present human participants with causal structures for which the models make divergent predictions and either solicit the best explanation for an observed event (Experiment 1) or have participants rate provided explanations for an observed event (Experiment 2). Across two versions of two causal structures and across both experiments, we find that the Causal Explanation Tree and Most Relevant Explanation models provide better fits to human data than either Most Probable Explanation or Explanation Tree models. We identify strengths and shortcomings of these models and what they can reveal about human explanation. We conclude by suggesting the value of pursuing computational and psychological investigations of explanation in parallel.
Approximate Kalman Filter Q-Learning for Continuous State-Space MDPs
Venue: arXiv cs.LG 2013
Year: 2013

We seek to learn an effective policy for a Markov Decision Process (MDP) with continuous states via Q-Learning. Given a set of basis functions over state action pairs we search for a corresponding set of linear weights that minimizes the mean Bellman residual. Our algorithm uses a Kalman filter model to estimate those weights and we have developed a simpler approximate Kalman filter model that outperforms the current state of the art projected TD-Learning methods on several standard benchmark problems.
Chemical concrete machine
Venue: arXiv cs.FL 2013
Year: 2013

The chemical concrete machine is a graph rewriting system which uses only local moves (rewrites), seen as chemical reactions involving molecules which are graphs made up by 4 trivalent nodes. It is Turing complete, therefore it might be used as a model of computation in algorithmic chemistry.
Linear combination of one-step predictive information with an external reward in an episodic policy gradient setting: a critical analysis
Venue: arXiv cs.AI 2013
Year: 2013

One of the main challenges in the field of embodied artificial intelligence is the open-ended autonomous learning of complex behaviours. Our approach is to use task-independent, information-driven intrinsic motivation(s) to support task-dependent learning. The work presented here is a preliminary step in which we investigate the predictive information (the mutual information of the past and future of the sensor stream) as an intrinsic drive, ideally supporting any kind of task acquisition. Previous experiments have shown that the predictive information (PI) is a good candidate to support autonomous, open-ended learning of complex behaviours, because a maximisation of the PI corresponds to an exploration of morphology- and environment-dependent behavioural regularities. The idea is that these regularities can then be exploited in order to solve any given task. Three different experiments are presented and their results lead to the conclusion that the linear combination of the one-step PI with an external reward function is not generally recommended in an episodic policy gradient setting. Only for hard tasks a great speed-up can be achieved at the cost of an asymptotic performance lost.
On the Complexity of Reconstructing Chemical Reaction Networks
Venue: arXiv cs.CC 2013
Year: 2013

The analysis of the structure of chemical reaction networks is crucial for a better understanding of chemical processes. Such networks are well described as hypergraphs. However, due to the available methods, analyses regarding network properties are typically made on standard graphs derived from the full hypergraph description, e.g.\ on the so-called species and reaction graphs. However, a reconstruction of the underlying hypergraph from these graphs is not necessarily unique. In this paper, we address the problem of reconstructing a hypergraph from its species and reaction graph and show NP-completeness of the problem in its Boolean formulation. Furthermore we study the problem empirically on random and real world instances in order to investigate its computational limits in practice.
Madeup: A Mobile Development Environment for Programming 3-D Models
Venue: arXiv cs.CY 2013
Year: 2013

Constructionism is a learning theory that states that we learn more when we construct tangible objects. In the process of building and presenting our work, we make concrete the abstract mental models we've formed, see where they breakdown through the feedback we receive, and revise the models accordingly. Computer programming has long been taught under a constructionist approach using sensory-rich contexts like robots, media, and Logo-style environments. Now, with affordable 3-D printers in the hands of consumers, we have a new medium in which learners may realize their computational ideas. In this demonstration, we share a mobile development environment named Madeup, which empowers its users to navigate 3-D space using a Logo-like imperative and functional language. Every stop in space becomes a vertex in a 3-D model. The generated models may be exported or uploaded to a 3-D printing service.
Grid-based Network Architecture for Distributed Computation in Wireless Sensor Networks
Venue: arXiv cs.NI 2013
Year: 2013

Wireless Sensor Networks (WSNs) are used to perform distributed sensing in various fields, such as health, military, home etc. In WSNs, sensor nodes should communicate among themselves and do distributed computation over the sensed values to identify the occurrence of an event. This paper assumes the no memory computation model for sensor nodes, i.e. the sensor nodes only have two registers. This paper presents an optimal architecture for the distributed computation in WSN and also claims that this architecture is the optimal for the described computation model.
Detection and Characterization of Intrinsic Symmetry
Venue: arXiv cs.GR 2013
Year: 2013

A comprehensive framework for detection and characterization of overlapping intrinsic symmetry over 3D shapes is proposed. To identify prominent symmetric regions which overlap in space and vary in form, the proposed framework is decoupled into a Correspondence Space Voting procedure followed by a Transformation Space Mapping procedure. In the correspondence space voting procedure, significant symmetries are first detected by identifying surface point pairs on the input shape that exhibit local similarity in terms of their intrinsic geometry while simultaneously maintaining an intrinsic distance structure at a global level. Since different point pairs can share a common point, the detected symmetric shape regions can potentially overlap. To this end, a global intrinsic distance-based voting technique is employed to ensure the inclusion of only those point pairs that exhibit significant symmetry. In the transformation space mapping procedure, the Functional Map framework is employed to generate the final map of symmetries between point pairs. The transformation space mapping procedure ensures the retrieval of the underlying dense correspondence map throughout the 3D shape that follows a particular symmetry. Additionally, the formulation of a novel cost matrix enables the inner product to succesfully indicate the complexity of the underlying symmetry transformation. The proposed transformation space mapping procedure is shown to result in the formulation of a semi-metric symmetry space where each point in the space represents a specific symmetry transformation and the distance between points represents the complexity between the corresponding transformations. Experimental results show that the proposed framework can successfully process complex 3D shapes that possess rich symmetries.
Improving tag recommendation by folding in more consistency
Venue: arXiv cs.IR 2013
Year: 2013

Tag recommendation is a major aspect of collaborative tagging systems. It aims to recommend tags to a user for tagging an item. In this paper we present a part of our work in progress which is a novel improvement of recommendations by re-ranking the output of a tag recommender. We mine association rules between candidates tags in order to determine a more consistent list of tags to recommend. Our method is an add-on one which leads to better recommendations as we show in this paper. It is easily parallelizable and morever it may be applied to a lot of tag recommenders. The experiments we did on five datasets with two kinds of tag recommender demonstrated the efficiency of our method.
Iterative Detection and Decoding for the Four-Rectangular-Grain TDMR Model
Venue: arXiv cs.IT 2013
Year: 2013

This paper considers detection and error control coding for the two-dimensional magnetic recording (TDMR) channel modeled by the two-dimensional (2D) four-rectangular-grain model proposed by Kavcic, Huang et. al. in 2010. This simple model captures the effects of different 2D grain sizes and shapes, as well as the TDMR grain overwrite effect: grains large enough to be written by successive bits retain the polarity of only the last bit written. We construct a row-by-row BCJR detection algorithm that considers outputs from two rows at a time over two adjacent columns, thereby enabling consideration of more grain and data states than previously proposed algorithms that scan only one row at a time. The proposed algorithm employs soft-decision feedback of grain states from previous rows to aid the estimation of current data bits and grain states. Simulation results using the same average coded bit density and serially concatenated convolutional code (SCCC) as a previous paper by Pan, Ryan, et. al. show gains in user bits/grain of up to 6.7% over the previous work when no iteration is performed between the TDMR BCJR and the SCCC, and gains of up to 13.4% when the detector and the decoder iteratively exchange soft information.
Optimized Bit Mappings for Spatially Coupled LDPC Codes over Parallel Binary Erasure Channels
Venue: arXiv cs.IT 2013
Year: 2013

In many practical communication systems, one binary encoder/decoder pair is used to communicate over a set of parallel channels. Examples of this setup include multi-carrier transmission, rate-compatible puncturing of turbo-like codes, and bit-interleaved coded modulation (BICM). A bit mapper is commonly employed to determine how the coded bits are allocated to the channels. In this paper, we study spatially coupled low-density parity check codes over parallel channels and optimize the bit mapper using BICM as the driving example. For simplicity, the parallel bit channels that arise in BICM are replaced by independent binary erasure channels (BECs). For two parallel BECs modeled according to a 4-PAM constellation labeled by the binary reflected Gray code, the optimization results show that the decoding threshold can be improved over a uniform random bit mapper, or, alternatively, the spatial chain length of the code can be reduced for a given gap to capacity. It is also shown that for rate-loss free, circular (tail-biting) ensembles, a decoding wave effect can be initiated using only an optimized bit mapper.
Chemical communication between synthetic and natural cells: a possible experimental design
Venue: arXiv cs.CE 2013
Year: 2013

The bottom-up construction of synthetic cells is one of the most intriguing and interesting research arenas in synthetic biology. Synthetic cells are built by encapsulating biomolecules inside lipid vesicles (liposomes), allowing the synthesis of one or more functional proteins. Thanks to the in situ synthesized proteins, synthetic cells become able to perform several biomolecular functions, which can be exploited for a large variety of applications. This paves the way to several advanced uses of synthetic cells in basic science and biotechnology, thanks to their versatility, modularity, biocompatibility, and programmability. In the previous WIVACE (2012) we presented the state-of-the-art of semi-synthetic minimal cell (SSMC) technology and introduced, for the first time, the idea of chemical communication between synthetic cells and natural cells. The development of a proper synthetic communication protocol should be seen as a tool for the nascent field of bio/chemical-based Information and Communication Technologies (bio-chem-ICTs) and ultimately aimed at building soft-wet-micro-robots. In this contribution (WIVACE, 2013) we present a blueprint for realizing this project, and show some preliminary experimental results. We firstly discuss how our research goal (based on the natural capabilities of biological systems to manipulate chemical signals) finds a proper place in the current scientific and technological contexts. Then, we shortly comment on the experimental approaches from the viewpoints of (i) synthetic cell construction, and (ii) bioengineering of microorganisms, providing up-to-date results from our laboratory. Finally, we shortly discuss how autopoiesis can be used as a theoretical framework for defining synthetic minimal life, minimal cognition, and as bridge between synthetic biology and artificial intelligence.
An ensemble approach to the study of the emergence of metabolic and proliferative disorders via Flux Balance Analysis
Venue: arXiv cs.CE 2013
Year: 2013

An extensive rewiring of cell metabolism supports enhanced proliferation in cancer cells. We propose a systems level approach to describe this phenomenon based on Flux Balance Analysis (FBA). The approach does not explicit a cell biomass formation reaction to be maximized, but takes into account an ensemble of alternative flux distributions that match the cancer metabolic rewiring (CMR) phenotype description. The underlying concept is that the analysis the common/distinguishing properties of the ensemble can provide indications on how CMR is achieved and sustained and thus on how it can be controlled.
Semi-structured data extraction and modelling: the WIA Project
Venue: arXiv cs.SE 2013
Year: 2013

Over the last decades, the amount of data of all kinds available electronically has increased dramatically. Data are accessible through a range of interfaces including Web browsers, database query languages, application-specific interfaces, built on top of a number of different data exchange formats. All these data span from un-structured to highly structured data. Very often, some of them have structure even if the structure is implicit, and not as rigid or regular as that found in standard database systems. Spreadsheet documents are prototypical in this respect. Spreadsheets are the lightweight technology able to supply companies with easy to build business management and business intelligence applications, and business people largely adopt spreadsheets as smart vehicles for data files generation and sharing. Actually, the more spreadsheets grow in complexity (e.g., their use in product development plans and quoting), the more their arrangement, maintenance, and analysis appear as a knowledge-driven activity. The algorithmic approach to the problem of automatic data structure extraction from spreadsheet documents (i.e., grid-structured and free topological-related data) emerges from the WIA project: Worksheets Intelligent Analyser. The WIA-algorithm shows how to provide a description of spreadsheet contents in terms of higher level of abstractions or conceptualisations. In particular, the WIA-algorithm target is about the extraction of i) the calculus work-flow implemented in the spreadsheets formulas and ii) the logical role played by the data which take part into the calculus. The aim of the resulting conceptualisations is to provide spreadsheets with abstract representations useful for further model refinements and optimizations through evolutionary algorithms computations.
Impact of local information in growing networks
Venue: arXiv cs.SI 2013
Year: 2013

We present a new model of the evolutionary dynamics and the growth of on-line social networks. The model emulates people's strategies for acquiring information in social networks, emphasising the local subjective view of an individual and what kind of information the individual can acquire when arriving in a new social context. The model proceeds through two phases: (a) a discovery phase, in which the individual becomes aware of the surrounding world and (b) an elaboration phase, in which the individual elaborates locally the information trough a cognitive-inspired algorithm. Model generated networks reproduce main features of both theoretical and real-world networks, such as high clustering coefficient, low characteristic path length, strong division in communities, and variability of degree distributions.
A new large class of functions not APN infinitely often
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we show that there is no vectorial Boolean function of degree 4e, with e satisfaying certain conditions, which is APN over infinitely many extensions of its field of definition. It is a new step in the proof of the conjecture of Aubry, McGuire and Rodier
Near Optimal Line Segment Weak Visibility Queries in Simple Polygons
Venue: arXiv cs.CG 2013
Year: 2013

This paper considers the problem of computing the weak visibility polygon (WVP) of any query line segment pq (or WVP(pq)) inside a given simple polygon P. We present an algorithm that preprocesses P and creates a data structure from which WVP(pq) is efficiently reported in an output sensitive manner. Our algorithm needs O(n^2 log n) time and O(n^2) space in the preprocessing phase to report WVP(pq) of any query line segment pq in time O(log^2 n + |WVP(pq)|). We improve the preprocessing time and space of current results for this problem at the expense of more query time.
On the Performance of Network Coding and Forwarding Schemes with Different Degrees of Redundancy for Wireless Mesh Networks
Venue: arXiv cs.NI 2013
Year: 2013

This study explores the throughput and delay that can be achieved by various forwarding schemes employing multiple paths and different degrees of redundancy focusing on linear network coding. The key contribution of the study is an analytical framework for modeling the throughput and delay for various schemes considering wireless mesh networks where, unicast traffic is forwarded and hop-by-hop retransmissions are employed for achieving reliability. The analytical framework is generalized for an arbitrary number of paths and hops per path. Another key contribution of the study is the evaluation and extension of the numerical results drawn from the analysis through NS-2 simulations. Our results show that in scenarios with significant interference the best throughput-delay tradeoff is achieved by single path forwarding. Moreover, when significant interference is present and network coding employs the larger packet generation size it experiences higher delay than all other schemes due to the inter-arrival times aggregating over all coded packets required to decode a packet generation.
A General Formula for the Mismatch Capacity
Venue: arXiv cs.IT 2013
Year: 2013

The fundamental limits of channels with mismatched decoding are addressed. A general formula is established for the mismatch capacity of a general channel, defined as a sequence of conditional distributions with a general decoding metrics sequence. We deduce an identity between the Verdú-Han general channel capacity formula, and the mismatch capacity formula applied to Maximum Likelihood decoding metric. Further, several upper bounds on the capacity are provided, and a simpler expression for a lower bound is derived for the case of a non-negative decoding metric. The general formula is specialized to the case of finite input and output alphabet channels with a type-dependent metric. The closely related problem of threshold mismatched decoding is also studied, and a general expression for the threshold mismatch capacity is obtained. As an example of threshold mismatch capacity, we state a general expression for the erasures-only capacity of the finite input and output alphabet channel. We observe that for every channel there exists a (matched) threshold decoder which is capacity achieving. Additionally, necessary and sufficient conditions are stated for a channel to have a strong converse. Csiszár and Narayan's conjecture is proved for bounded metrics, providing a positive answer to the open problem introduced in [1], i.e., that the "product-space" improvement of the lower random coding bound, $C_q^{(\infty)}(W)$, is indeed the mismatch capacity of the discrete memoryless channel $W$. We conclude by presenting an identity between the threshold capacity and $C_q^{(\infty)}(W)$ in the DMC case.