These are my recent Pinboard.in links:
[1206.6866] Stochastic Optimal Control in Continuous Space-Time Multi-Agent Systems
“Recently, a theory for stochastic optimal control in non-linear dynamical systems in continuous space-time has been developed (Kappen, 2005). We apply this theory to collaborative multi-agent systems. The agents evolve according to a given non-linear dynamics with additive Wiener noise. Each agent can control its own dynamics. The goal is to minimize the accumulated joint cost, which consists of a state dependent term and a term that is quadratic in the control. We focus on systems of non-interacting agents that have to distribute themselves optimally over a number of targets, given a set of end-costs for the different possible agent-target combinations. We show that optimal control is the combinatorial sum of independent single-agent single-target optimal controls weighted by a factor proportional to the end-costs of the different combinations. Thus, multi-agent control is related to a standard graphical model inference problem. The additional computational cost compared to single-agent control is exponential in the tree-width of the graph specifying the combinatorial sum times the number of targets. We illustrate the result by simulations of systems with up to 42 agents.”
coordination agent-based emergent-design nudge-targets control-theory[1205.6917] Robust self-triggered coordination with ternary controllers
“This paper regards coordination of networked systems, which is studied in the framework of hybrid dynamical systems. We design a coordination scheme which combines the use of ternary controllers with a self-triggered communication policy. The communication policy requires the agents to collect, at each sampling time, relative measurements of their neighbors’ states: the collected information is then used to update the control and determine the following sampling time. We prove that the proposed scheme ensures finite-time convergence to a neighborhood of a consensus state. We then study the robustness of the proposed self-triggered coordination system with respect to skews in the agents’ local clocks, to delays, and to limited precision in communication. Furthermore, we present two significant variations of our scheme. First, we design a time-varying controller which asymptotically drives the system to consensus. Second, we adapt our framework to a communication model in which an agent does not poll all its neighbors simultaneously, but single neighbors instead. This communication policy actually leads to a self-triggered “gossip” coordination system.”
network-theory multi-agent-systems mechanism-design emergent-design consensus-systems nudge-targets algorithms- “We perform a simulation-based analysis of keyword auctions modeled as one-shot games of incomplete information to study a series of mechanism design questions. Our first question addresses the degree to which incentive compatibility fails in generalized second-price (GSP) auctions. Our results suggest that sincere bidding in GSP auctions is a strikingly poor strategy and a poor predictor of equilibrium outcomes. We next show that the rank-by-revenue mechanism is welfare optimal, corroborating past results. Finally, we analyze profit as a function of auction mechanism under a series of alternative settings. Our conclusions coincide with those of Lahaie and Pennock [2007] when values and quality scores are strongly positively correlated: in such a case, rank-by-bid rules are clearly superior. We diverge, however, in showing that auctions that put little weight on quality scores almost universally dominate the pure rank-by-revenue scheme.”
game-theory agent-based simulation economics auction nudge-targets - “Each philosopher is a node in the network and the lines between them (or edges in the terminology of graph theory) represents lines of influence. The node and text are sized according to the number of connections (both in and out). The algorithm that visualises the graph also tends to put the better connected nodes in the centre of the diagram so we see the most influential philosophers, in large text, clustered in the centre. It all seems about right with the major figures in the western philosophical tradition taking the centre stage. (I need to also add the direction of influence with a arrow head – something I’ve not got round to yet.) A shortcoming however is that this evaluation only takes into account direct lines of influence. Indirect influence via another person in the network does not enter into it. This probably explains why Descartes is smaller than you’d think. It would also be better if the nodes were sized only by the number of outward connections although I think overall the differences would be slight. I’ll get round to that.”
visualization philosopher-mining [1206.3666] Unsupervised adaptation of brain machine interface decoders
“The performance of neural decoders can degrade over time due to nonstationarities in the relationship between neuronal activity and behavior. In this case, brain-machine interfaces (BMI) require adaptation of their decoders to maintain high performance across time. One way to achieve this is by use of periodical calibration phases, during which the BMI system (or an external human demonstrator) instructs the user to perform certain movements or behaviors. This approach has two disadvantages: (i) calibration phases interrupt the autonomous operation of the BMI and (ii) between two calibration phases the BMI performance might not be stable but continuously decrease. A better alternative would be that the BMI decoder is able to continuously adapt in an unsupervised manner during autonomous BMI operation, i.e. without knowing the movement intentions of the user. In the present article, we present an efficient method for such unsupervised training of BMI systems for continuous movement control. The proposed method utilizes a cost function derived from neuronal recordings, which guides a learning algorithm to evaluate the decoding parameters. We verify the performance of our adaptive method by simulating a BMI user with an optimal feedback control model and its interaction with our adaptive BMI decoder. The simulation results show that the cost function and the algorithm yield fast and precise trajectories towards targets at random orientations on a 2-dimensional computer screen. For initially unknown and non-stationary tuning parameters, our unsupervised method is still able to generate precise trajectories and to keep its performance stable in the long term. The algorithm can optionally work also with neuronal error signals instead or in conjunction with the proposed unsupervised adaptation.”
FOR-SCIENCE brain-machine-interface user-interface adaptive-control emergent-design[1206.3980] Visualizing Streaming Text Data with Dynamic Maps
“The many endless rivers of text now available present a serious challenge in the task of gleaning, analyzing and discovering useful information. In this paper, we describe a methodology for visualizing text streams in real time. The approach automatically groups similar messages into “countries,” with keyword summaries, using semantic analysis, graph clustering and map generation techniques. It handles the need for visual stability across time by dynamic graph layout and Procrustes projection techniques, enhanced with a novel stable component packing algorithm. The result provides a continuous, succinct view of evolving topics of interest. It can be used in passive mode for overviews and situational awareness, or as an interactive data exploration tool. To make these ideas concrete, we describe their application to an online service called TwitterScope.”
visualization data algorithms user-experience[1205.3352] Revisiting the effect of external fields in Axelrod’s model of social dynamics
“The study of the effects of spatially uniform fields on the steady-state properties of Axelrod’s model has yielded plenty of controversial results. Here we re-examine the impact of this type of field for a selection of parameters such that the field-free steady state of the model is heterogeneous or multicultural. Analyses of both one and two-dimensional versions of Axelrod’s model indicate that, contrary to previous claims in the literature, the steady state remains heterogeneous regardless of the value of the field strength. Turning on the field leads to a discontinuous decrease on the number of cultural domains, which we argue is due to the instability of zero-field heterogeneous absorbing configurations. We find, however, that spatially nonuniform fields that implement a consensus rule among the neighborhood of the agents enforces homogenization. Although the overall effects of the fields are essentially the same irrespective of the dimensionality of the model, we argue that the dimensionality has a significant impact on the stability of the field-free homogeneous steady state.”
complexology agent-based externalities simulation evolutionary-economics nudge-targets[1206.3421] Linear Latent Variable Models: The lava-package
“An R package for specifying and estimating linear latent variable models is presented. The philosophy of the implementation is to separate the model specification from the actual data, which leads to a dynamic and easy way of modeling complex hierarchical structures. Several advanced features are implemented including robust standard errors for clustered correlated data, multigroup analyses, non-linear parameter constraints, inference with incomplete data, maximum likelihood estimation with censored and binary observations, and instrumental variable estimators. In addition an extensive simulation interface covering a broad range of non-linear generalized structural equation models is described. The model and software are demonstrated in data of measurements of the serotonin transporter in the human brain.”
ontology statistics algorithms R-language linear-models model-view-controller design-patterns- “In 2008, it was widely announced that the missing memristor, a basic two-terminal electrical circuit element, had finally been discovered. The memristor is the fourth and last such circuit element and thus completes circuit theory. Predicted already in 1971, the eventual discovery of something seemingly so basic needed almost 40 years. However, this discovery is doubted. The predicted memristor has no material memory and is based on magnetic flux, but the discovered devices constitute analogue memory storage that do not involve magnetism. The person who originally proposed the memristor did not reject the discovery but instead changed his mind about what a memristor is. We briefly introduce the history and then carefully memristance and the memristor as such. We discuss its status as a model rather than a device. We discuss the discovered devices, their stability, and how stability relates to the consistency of the theoretical entities. A thought experiment assumes a world without magnetism. Inductors cannot exist there, but memory resistors could still be constructed. On the same grounds as the memristor was historically predicted, an “inductor” could then be predicted. Likely, somebody would also ‘discover’ one. A tentative sociological analysis compares to the flawed detection of gravitational waves but comes to very different conclusions.”
symmetry-is-the-way-things-ought-to-be history-of-science technical-assumptions engineering-philosophy - “Transport processes on spatial networks are representative of a broad class of real world systems which, rather than being independent, are typically interdependent. We propose a measure of utility to capture key features that arise when such systems are coupled together. The coupling is defined in a way that is not solely topological, relying on both the distribution of sources and sinks, and the method of route assignment. Using a toy model, we explore relevant cases by simulation. For certain parameter values, a picture emerges of two regimes. The first occurs when the flows go from many sources to a small number of sinks. In this case, network utility is largest when the coupling is at its maximum and the average shortest path is minimized. The second regime arises when many sources correspond to many sinks. Here, the optimal coupling no longer corresponds to the minimum average shortest path, as the congestion of traffic must also be taken into account. More generally, results indicate that coupled spatial systems can give rise to behavior that relies subtly on the interplay between the coupling and randomness in the source-sink distribution.”
nudge-targets network-theory emergent-design epidemiology simulation - “Probability distributions of human displacements has been fit with exponentially truncated L’evy flights or fat tailed Pareto inverse power law probability distributions. Thus, people usually stay within a given location (for example, the city of residence), but with a non-vanishing frequency they visit nearby or far locations too. Herein, we show that an important empirical distribution of human displacements (range: from 1 to 1000 km) can be well fit by three consecutive Pareto distributions with simple integer exponents equal to 1, 2 and ($gtrapprox$) 3. These three exponents correspond to three displacement range zones of about 1 km $lesssim Delta r lesssim$ 10 km, 10 km $lesssim Delta r lesssim$ 300 km and 300 km $lesssim Delta r lesssim $ 1000 km, respectively. These three zones can be geographically and physically well determined as displacements within a city, visits to nearby cities that may occur within just one-day trips, and visit to far locations that may require multi-days trips. The incremental integer values of the three exponents can be easily explained with a three-scale mobility cost/benefit model for human displacements based on simple geometrical constrains. Essentially, people would divide the space into three major regions (close, medium and far distances) and would assume that the travel benefits are randomly/uniformly distributed mostly only within specific urban-like areas.”
Levy-flights city-planning multiscale-phenomena self-similarity - “Conventional optical components shape the wavefront of propagating light by adjusting the optical path length, which requires the use of rather thick lenses, especially for the adjustment of terahertz (THz) radiation due to its long wavelength. Two ultrathin THz planar lenses were designed and fabricated based on interface phase modulation of antenna resonance. The lens thicknesses were extremely reduced to 100 nm, which is only 1⁄4000th of the illuminating light wavelength. The focusing and imaging functions of the lenses were experimentally demonstrated. The ultrathin optical components described herein are a significant step toward the development of a micro-integrated THz system.”
optics engineering-design nudge-targets - “We present a general setting for structure-sequence comparison in a large class of RNA structures that unifies and generalizes a number of recent works on specific families on structures. Our approach is based on tree decomposition of structures and gives rises to a general parameterized algorithm, where the exponential part of the complexity depends on the family of structures. For each of the previously studied families, our algorithm has the same complexity as the specific algorithm that had been given before.”
RNA structural-biology folding bioinformatics algorithms nudge-targets modeling - “Computational analysis of time-course data with an underlying causal structure is needed in a variety of domains, including neural spike trains, stock price movements, and gene expression levels. However, it can be challenging to determine from just the numerical time course data alone what is coordinating the visible processes, to separate the underlying prima facie causes into genuine and spurious causes and to do so with a feasible computational complexity. For this purpose, we have been developing a novel algorithm based on a framework that combines notions of causality in philosophy with algorithmic approaches built on model checking and statistical techniques for multiple hypotheses testing. The causal relationships are described in terms of temporal logic formulae, reframing the inference problem in terms of model checking. The logic used, PCTL, allows description of both the time between cause and effect and the probability of this relationship being observed. We show that equipped with these causal formulae with their associated probabilities we may compute the average impact a cause makes to its effect and then discover statistically significant causes through the concepts of multiple hypothesis testing (treating each causal relationship as a hypothesis), and false discovery control. By exploring a well-chosen family of potentially all significant hypotheses with reasonably minimal description length, it is possible to tame the algorithm’s computational complexity while exploring the nearly complete search-space of all prima facie causes. We have tested these ideas in a number of domains and illustrate them here with two examples.”
time-series statistics framework dynamical-systems to-read - “We study a natural online variant of the replacement path problem. The textit{replacement path problem} asks to find for a given graph $G = (V,E)$, two designated vertices $s,tin V$ and a shortest $s$-$t$ path $P$ in $G$, a textit{replacement path} $P_e$ for every edge $e$ on the path $P$. The replacement path $P_e$ is simply a shortest $s$-$t$ path in the graph, which avoids the textit{failed} edge $e$. We adapt this problem to deal with the natural scenario, that the edge which failed is not known at the time of solution implementation. Instead, our problem assumes that the identity of the failed edge only becomes available when the routing mechanism tries to cross the edge. This situation is motivated by applications in distributed networks, where information about recent changes in the network is only stored locally, and fault-tolerant optimization, where an adversary tries to delay the discovery of the materialized scenario as much as possible. Consequently, we define the textit{online replacement path problem}, which asks to find a nominal $s$-$t$ path $Q$ and detours $Q_e$ for every edge on the path $Q$, such that the worst-case arrival time at the destination is minimized. Our main contribution is a label setting algorithm, which solves the problem in undirected graphs in time $O(m log n)$ and linear space for all sources and a single destination. We also present algorithms for extensions of the model to any bounded number of failed edges.”
operations-research planning algorithms online-algorithms nudge-targets - “…Again this suggests that the Parrondo region (mu_B is nonpositive and mu_[r,s] is positive) has nonzero volume in the limit. …”
Parrondo-games game-theory counterintuitive-results simulation cooperation [1206.4648] Two-Manifold Problems with Applications to Nonlinear System Identification
“Recently, there has been much interest in spectral approaches to learning manifolds—so-called kernel eigenmap methods. These methods have had some successes, but their applicability is limited because they are not robust to noise. To address this limitation, we look at two-manifold problems, in which we simultaneously reconstruct two related manifolds, each representing a different view of the same data. By solving these interconnected learning problems together, two-manifold algorithms are able to succeed where a non-integrated approach would fail: each view allows us to suppress noise in the other, reducing bias. We propose a class of algorithms for two-manifold problems, based on spectral decomposition of cross-covariance operators in Hilbert space, and discuss when two-manifold problems are useful. Finally, we demonstrate that solving a two-manifold problem can aid in learning a nonlinear dynamical system from limited data.”
statistics inverse-problems system-identification algorithms nudge-targets benchmarking- “We present a general framework to describe the evolutionary dynamics of an arbitrary number of types in finite populations based on stochastic differential equations (SDE). For large, but finite populations this allows to include demographic noise without requiring explicit simulations. Instead, the population size only rescales the amplitude of the noise. Moreover, this framework admits the inclusion of mutations between different types, provided that mutation rates, $mu$, are not too small compared to the inverse population size 1/N. This ensures that all types are almost always represented in the population and that the occasional extinction of one type does not result in an extended absence of that type. For $mu Nll1$ this limits the use of SDE’s, but in this case there are well established alternative approximations based on time scale separation. We illustrate our approach by a Rock-Scissors-Paper game with mutations, where we demonstrate excellent agreement with simulation based results for sufficiently large populations. In the absence of mutations the excellent agreement extends to small population sizes.”
finite-size-effects population-biology noise-in-design nudge-targets [1206.5352] The Subword Complexity of k-Automatic Sequences is k-Synchronized
“We show that the subword complexity function p_x (n), which counts the number of distinct factors of length n of a k-automatic sequence x, is k-synchronized in the sense of Carpi. As an application, we generalize recent results of Goldstein. In contrast, we show that function which counts the number of unbordered factors of length n is not k-synchronized.”
automata strings complexity nudge-targets- “Computing the convex hull means that a non-ambiguous and efficient representation of the required convex shape is constructed. The complexity of the corresponding algorithms is usually estimated in terms of n, the number of input points, and h, the number of points on the convex hull.”
computational-geometry algorithms nudge-targets - “Application Programming Interfaces (API) are exposed to developers in order to reuse software libraries. API directives are natural-language statements in API documentation that make developers aware of constraints and guidelines related to the usage of an API. This paper presents the design and the results of an empirical study on the directives of API documentation of object-oriented libraries. Its main contribution is to propose and extensively discuss a taxonomy of 23 kinds of API directives.”
digital-humanities documentation text-mining software-development cultural-norms Publications Available Electronically
Godfried T. Toussaint, “The Erdos-Nagy theorem and its ramifications,” Proc. 11th Canadian Conference on Computational Geometry, Vancouver, Canada, August 16–18 1999, pp. 9–12. Long version available at: http://www.cs.ubc.ca/conferences/CCCG. Also: Technical Report No. SOCS-99.2, School of Computer Science, McGill University, June 18, 1999.
nudge-targets geometry genetic-programming-target low-hanging-fruitIntroduction to Lamina Emergent Mechanisms (LEMS) | Compliant Mechanisms
“The fact that LEMs can be fabricated from planar layers influences both what processes can be used for their manufacture and what materials may be used in their construction. At the micro level, LEMS can be fabricated using single-layer MEMS fabrication methods and materials, which offers significant cost and reliability advantages. It also provides opportunities for complex out-of-plane motion with only a single layer. At the macro level, manufacturing processes used to make static structures or components for assembly can be used to create mechanisms capable of sophisticated motions and complex tasks. Example processes include stamping, fine blanking, laser cutting, water jet cutting, plasma cutting, and wire electrical discharge machining (EDM). Some of these processes, such as stamping, offer significant cost advantages for high-volume production. Planar fabrication also allows the use of sheet goods to directly create mechanisms. The use of low-cost, high-quality sheet goods has the potential to dramatically reduce cost for high-volume production. It also makes possible the next characteristic: flat initial state.”
manufacturing engineering-design fabrication nudge-targets