information-theory   937

« earlier    

[1802.07181] Algorithmic Information Dynamics of Persistent Patterns and Colliding Particles in the Game of Life
Without loss of generalisation to other systems, including possibly non-deterministic ones, we demonstrate the application of methods drawn from algorithmic information dynamics to the characterisation and classification of emergent and persistent patterns, motifs and colliding particles in Conway's Game of Life (GoL), a cellular automaton serving as a case study illustrating the way in which such ideas can be applied to a typical discrete dynamical system. We explore the issue of local observations of closed systems whose orbits may appear open because of inaccessibility to the global rules governing the overall system. We also investigate aspects of symmetry related to complexity in the distribution of patterns that occur with high frequency in GoL (which we thus call motifs) and analyse the distribution of these motifs with a view to tracking the changes in their algorithmic probability over time. We demonstrate how the tools introduced are an alternative to other computable measures that are unable to capture changes in emergent structures in evolving complex systems that are often too small or too subtle to be properly characterised by methods such as lossless compression and Shannon entropy.
cellular-automata  information-theory  not-the-way-I'd-go  to-understand  purdy-pitchers  compression  consider:individuation  consider:foreground-and-background 
7 days ago by Vaguery
[1602.06093] Self-organisation in cellular automata with coalescent particles: qualitative and quantitative approaches
This article introduces new tools to study self-organisation in a family of simple cellular automata which contain some particle-like objects with good collision properties (coalescence) in their time evolution. We draw an initial configuration at random according to some initial σ-ergodic measure μ, and use the limit measure to descrbe the asymptotic behaviour of the automata. We first take a qualitative approach, i.e. we obtain information on the limit measure(s). We prove that only particles moving in one particular direction can persist asymptotically. This provides some previously unknown information on the limit measures of various deterministic and probabilistic cellular automata: 3 and 4-cyclic cellular automata (introduced in [Fis90b]), one-sided captive cellular automata (introduced in [The04]), N. Fat{è}s' candidate to solve the density classification problem [Fat13], self stabilization process toward a discrete line [RR15]... In a second time we restrict our study to to a subclass, the gliders cellular automata. For this class we show quantitative results, consisting in the asymptotic law of some parameters: the entry times (generalising [KFD11]), the density of particles and the rate of convergence to the limit measure.
cellular-automata  self-organization  feature-extraction  feature-construction  define-your-terms  information-theory  nonlinear-dynamics  to-understand 
6 weeks ago by Vaguery
[1704.08679] Age-Minimal Transmission in Energy Harvesting Two-hop Networks
We consider an energy harvesting two-hop network where a source is communicating to a destination through a relay. During a given communication session time, the source collects measurement updates from a physical phenomenon and sends them to the relay, which then forwards them to the destination. The objective is to send these updates to the destination as timely as possible; namely, such that the total age of information is minimized by the end of the communication session, subject to energy causality constraints at the source and the relay, and data causality constraints at the relay. Both the source and the relay use fixed, yet possibly different, transmission rates. Hence, each update packet incurs fixed non-zero transmission delays. We first solve the single-hop version of this problem, and then show that the two-hop problem is solved by treating the source and relay nodes as one combined node, with some parameter transformations, and solving a single-hop problem between that combined node and the destination.
queueing-theory  information-theory  multiobjective-optimization  rather-interesting  to-write-about  to-simulate  consider:looking-to-see 
6 weeks ago by Vaguery
[1807.04271] A quantum-inspired classical algorithm for recommendation systems
A recommendation system suggests products to users based on data about user preferences. It is typically modeled by a problem of completing an m×n matrix of small rank k. We give the first classical algorithm to produce a recommendation in O(poly(k)polylog(m,n)) time, which is an exponential improvement on previous algorithms that run in time linear in m and n. Our strategy is inspired by a quantum algorithm by Kerenidis and Prakash: like the quantum algorithm, instead of reconstructing a user's full list of preferences, we only seek a randomized sample from the user's preferences. Our main result is an algorithm that samples high-weight entries from a low-rank approximation of the input matrix in time independent of m and n, given natural sampling assumptions on that input matrix. As a consequence, we show that Kerenidis and Prakash's quantum machine learning (QML) algorithm, one of the strongest candidates for provably exponential speedups in QML, does not in fact give an exponential speedup over classical algorithms.
recommendations  algorithms  quantum-computing  classical-computing  rather-interesting  information-theory  to-understand 
10 weeks ago by Vaguery
[1808.02679] Age of Information Upon Decisions
We consider an M/M/1 update-and-decide system where Poisson distributed decisions are made based on the received updates. We propose to characterize the freshness of the received updates at decision epochs with Age upon Decisions (AuD). Under the first-come-first-served policy (FCFS), the closed form average AuD is derived. We show that the average AuD of the system is determined by the arrival rate and the service rate, and is independent of the decision rate. Thus, merely increasing the decision rate does not improve the timeliness of decisions. Nevertheless, increasing the arrival rate and the service rate simultaneously can decrease the average AuD efficiently.
queueing-theory  information-theory  planning  simulation  rather-interesting  to-write-about 
11 weeks ago by Vaguery
[1309.3441] On the shape of subword complexity sequences of finite words
The subword complexity of a word w over a finite alphabet  is a function that assigns for each positive integer n, the number of distinct subwords of length n in w. The subword complexity of a word is a good measure of the randomness of the word and gives insight to what the word itself looks like. In this paper, we discuss the properties of subword complexity sequences, and consider different variables that influence their shape. We also compute the number of distinct subword complexity sequences for certain lengths of words over different alphabets, and state some conjectures about the growth of these numbers.
strings  combinatorics  enumeration  pattern-discovery  complexity-measures  information-theory  rather-interesting  to-write-about  for-puzzles  you-know-for-kids 
12 weeks ago by Vaguery
[1611.03060] The Non-convex Geometry of Low-rank Matrix Optimization
This work considers two popular minimization problems: (i) the minimization of a general convex function f(X) with the domain being positive semi-definite matrices; (ii) the minimization of a general convex function f(X) regularized by the matrix nuclear norm ‖X‖∗ with the domain being general matrices. Despite their optimal statistical performance in the literature, these two optimization problems have a high computational complexity even when solved using tailored fast convex solvers. To develop faster and more scalable algorithms, we follow the proposal of Burer and Monteiro to factor the low-rank variable X=UU⊤ (for semi-definite matrices) or X=UV⊤ (for general matrices) and also replace the nuclear norm ‖X‖∗ with (‖U‖2F+‖V‖2F)/2. In spite of the non-convexity of the resulting factored formulations, we prove that each critical point either corresponds to the global optimum of the original convex problems or is a strict saddle where the Hessian matrix has a strictly negative eigenvalue. Such a nice geometric structure of the factored formulations allows many local search algorithms to find a global optimizer even with random initializations.
optimization  representation  matrices  to-understand  algorithms  mathematical-programming  information-theory  to-translate 
december 2018 by Vaguery

« earlier    

related tags

acm  ai  algorithms  analysis  anlaysis  announcement  approximation  arrows  article  artificial-intelligence  artificialintelligence  big-surf  bio  biography  bioinformatics  biology  bits  blockchain  blog  bob-doyle  books  boolean-functions  cannot-read  cautionary-tale  cellular-automata  characterization  classical-computing  cnns  codes  coding-theory  coding  collective-intelligence  combinatorics  communication  complexity-measures  complexity  complexology  composition-decomposition  compression  computational-complexity  computing  consider:foreground-and-background  consider:genetic-programming  consider:individuation  consider:lexicase  consider:looking-to-see  consider:performance-measures  consider:planning-versions  control-systems  crackpot  cryptography  cybernetics  data-science  deep-learning  deepgoog  deeplearning  define-your-terms  differential-geometry  distance  donald-mackay  ecology  economics  entropy  enumeration  ergodic-theory  evolution  experiment  experimental-design  expert-experience  expert  explanans  explanation  favorite  feature-construction  feature-extraction  feature-selection  finance  for-puzzles  frontier  game-theory  gan  gans  generalization  genetics  genomics  giants  gradient-descent  graphics  hardware-changes-models  health  heapsort  heard-the-talk  hey-i-know-this-guy  hi-order-bits  history  hmm  howto  huh  ideas  inference  information-bottleneck  information-cascade  information-geometry  information-physics  integer-programming  intelligence  interdisciplinary  interpretation  introduction  israel  jeremy-kun  knuth  language  latent-variables  learn  learning-algorithms  learning  lectures  libb-thims  libs  lifts-projections  lilian-weng  liner-notes  looking-to-see  lower-bounds  machine-learning  machinelearning  mackay  markov  math  mathematical-programming  mathematics  matrices  maxim-gun  mcmc  measure-concentration  metric-space  mindblowing  ml  model-class  modeling  multi  multiobjective-optimization  mutation  naming  network-theory  networking  neural-net  neuro  news  nibble  nn  nonlinear-dynamics  not-the-way-i'd-go  notes  nudge-targets  nyquist  oh-physics  ontological-diversity  operations-research  optimization  org:inst  org:mag  org:sci  papers  pattern-discovery  pdf  people  performance-measure  person  philosophy-of-science  philosophy  physics  planning  popsci  preimage  privacy  probability-theory  probability  professor  programming  purdy-pitchers  python  quantification  quantum-computing  quantum-mechanics  questions  queueing-theory  quicksort  randomness  rather-interesting  recommendations  reference  representation  research  review  robotics  robustness  roots  sampling-theorem  sci  science  self-organization  semantics  seti  shannon  signal-noise  signal-processing  simulation  sources  speedometer  statcomp  statistics  strings  study  summary  swarms  system-of-professions  system-of-the-world  talks  the-mangle-in-practice  theory  thermodynamics  timecube  to-read  to-simulate  to-translate  to-understand  to-write-about  to_read  transfer-learning  tutorial  variational  video  videos  wikipedia  wild-ideas  you-know-for-kids  youtube  🌞 

Copy this bookmark: