Stochastic Calculus

Stochastic Calculus

I should put some content here, when time permits, with particular reference to
intuitive constructions, and Lévy processes, especially branching ones.

http://terrytao.wordpress.com/2010/01/18/254a-notes-3b-brownian-motion-and-dyson-brownian-motion/

George Lowther http://almostsure.wordpress.com/2010/01/11/properties-of-the-stochastic-integral/

See original: The Living Thing Stochastic Calculus

Matrix factorizations

Matrix Factorisations

Forget QR and LU decompositions, there are now so many ways of factorising
matrices that there are not enough acronyms in the alphabet to hold them,
especially if you suspect your matrix is sparse, if squinted at in the right
fashion, such as a graph transiton matrix, or laplacian, or noisy transform of some image...

Overviews:
* Tutorial by Erica Klarreich
* Spielman's Laplacian Linear Equations, Graph Sparsification, Local Clustering, Low-Stretch Trees, etc. is the best start and links lots of online textbooks and so on.
* Igor Carron's Advanced Matrix Factorization Jungle

Articles:

  • Koutis, I., Miller, G. L., & Peng, R. (2010). Approaching optimality for solving SDD systems. In Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on (pp. 235–244). IEEE. DOI. Online.
  • Koutis, I., Miller, G. L., & Peng, R. (2012). A fast solver for a class of linear systems. Communications of the ACM, 55(10), 99–107. DOI. Online.
  • Network Solutions | Simons Foundation. (n.d.). Online.
  • Pan, G., Zhang, W., Wu, Z., & Li, S. (2014). Online Community Detection for Large Complex Networks. PLoS ONE, 9(7), e102799. DOI. Online.
  • Ryabko, D., & Ryabko, B. (2010). Nonparametric Statistical Inference for Ergodic Processes. IEEE Transactions on Information Theory, 56(3), 1430–1435. DOI. Online.
  • Spielman, D. A., & Teng, S.-H. (2006). Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems. arXiv:cs/0607105. Online.
  • Spielman, D. A., & Teng, S.-H. (2008a). A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning. arXiv:0809.3232 [cs]. Online.
  • Spielman, D. A., & Teng, S.-H. (2008b). Spectral Sparsification of Graphs. arXiv:0808.4134 [cs]. Online.
  • Vishnoi, N. K. (2013). Lx = b. Foundations and Trends® in Theoretical Computer Science, 8(1-2), 1–141. DOI. Online.

See original: The Living Thing Matrix factorizations

Graphical Models

DAGs and causality; extracting Science from observational data.

See original: The Living Thing Graphical Models

Moral Calculus

Moral Calculus

Pareto optimality, utilitarianism, and killing machines.

http://www.radiolab.org/story/91508-morality/

See original: The Living Thing Moral Calculus

Moral Calculus

Moral Calculus

Pareto optimality, utilitarianism, and killing machines.

The trolley problem in the age of machine agency, war drones and smartcars. Also, what is agency anyway?

See original: The Living Thing Moral Calculus

Large Scale Learning

Large Scale Learning

Machine learning on very-large through to horribly-large data sets; tips and
tricks.

First, most basic tip is: if you can use a lean algorithm that doesn't
require you to comandeers lots of machines, do. This is the common case,
despite all that weird "big data" spam we've all been getting.

Now, presuming that didn't work s=for some reason, what can we do to handle
unwieldy data sets?

To Read

  • Google's Sibyl seems to have fun ideas (slide deck ) although not open source
  • Graphlab a "vertex centric" graph processing system, seems to do both the lean algorithm and the distributed algorithm thing.
  • Hadoop rubs me up the wrong way for some reason, but I'm sure it has virtues. One of them is reportedly Spark which seems to ease useage of Hadoop by avoiding it.

See original: The Living Thing Large Scale Learning

Magnetism and Electric Eurrent

Why moving charges along a conductor produces magnetic field?

disruptive technology

Disruptive Technology

Modeling how technology changes the rules of the game, as opposed to marginally
changes some parameters; not, say residual stochastic shocks (in the Real
Business Cycle models), or as the slope of a marginal cost of production curve
(in textbook microeconomics).

To consider

This is at the very limit of modelability. The introduction of a new technology
has many componenets, from social uptake, to supply chains, to the discovery
process. Most complex of all, the unexpected interactions with the other
technologies out there. The internal combustion engine changed more than just
transit times. The computer network altered more than just mail delivery times.

The cascade of effects from any one alteration is, it is likely, unknowable in
advance, but might have some regularities, or at least some kind of underlying
set of distributions as a stochastic process - some kind of branching process
perhaps?

Think evolutionary models of fitness and mutations.
Some combination of reinforcement learning convergence dynamics,
and unknown production and utility constraints,
network effects and free rider effects
(still ignores supply chain stuff).
A highly recursive nonlinear SDE on a reasonably exotic space.
Even then it would miss some things,
such as (apparently) improved information aggregation in digital teechnology.
Or could that be subsumed into artful fitting of distributions of networks of interactions of goods bundles?
How would you model firms?
How about individuals?

Technology as a virus?

Patent network statistics:
What structure does industry X's technology possess?
Directed, dependency graph.
Explaining the South Korea chemical path.
Investing in a particular technology bundle.
Korea's success in car's versus India's failure.

Hidalgo and Hausmann's model

Considers products and nations in a bipartite graph, and does various network statistics upon it.
(c.f. Felix Reed-Tsochas' affinity for such graphs)
Note that there is an implicit third part in the graph, to whit "capabilities"
which represent infrastructure to manufacture products.

Other interesting things to look at

See original: The Living Thing disruptive technology

Innovation

Disruptive Technology

Modeling how technology changes the rules of the game, as opposed to marginally
changes some parameters; not, say residual stochastic shocks (in the Real
Business Cycle models), or as the slope of a marginal cost of production curve
(in textbook microeconomics).

To consider

This is at the very limit of modelability. The introduction of a new technology
has many componenets, from social uptake, to supply chains, to the discovery
process. Most complex of all, the unexpected interactions with the other
technologies out there. The internal combustion engine changed more than just
transit times. The computer network altered more than just mail delivery times.

The cascade of effects from any one alteration is, it is likely, unknowable in
advance, but might have some regularities, or at least some kind of underlying
set of distributions as a stochastic process - some kind of branching process
perhaps?

Think evolutionary models of fitness and mutations.
Some combination of reinforcement learning convergence dynamics,
and unknown production and utility constraints,
network effects and free rider effects
(still ignores supply chain stuff).
A highly recursive nonlinear SDE on a reasonably exotic space.
Even then it would miss some things,
such as (apparently) improved information aggregation in digital teechnology.
Or could that be subsumed into artful fitting of distributions of networks of interactions of goods bundles?
How would you model firms?
How about individuals?

Technology as a virus?

Patent network statistics:
What structure does industry X's technology possess?
Directed, dependency graph.
Explaining the South Korea chemical path.
Investing in a particular technology bundle.
Korea's success in car's versus India's failure.

Hidalgo and Hausmann's model

Considers products and nations in a bipartite graph, and does various network statistics upon it.
(c.f. Felix Reed-Tsochas' affinity for such graphs)
Note that there is an implicit third part in the graph, to whit "capabilities"
which represent infrastructure to manufacture products.

Other interesting things to look at

  • Mariana MAzzucato seems to be interesting
  • Anderies, J. M. (2003). Economic development, demographics, and renewable resources: a dynamical systems approach. Environment and Development Economics, 8, 219–246. DOI.
  • Antonelli, C., & Ferraris, G. (2011). Innovation as an Emerging System Property: An Agent Based Simulation Model. Journal of Artificial Societies and Social Simulation, 14(2), 1.
  • Arthur, W. B. (1989). Competing Technologies, Increasing Returns, and Lock-In by Historical Events. The Economic Journal, 99(394), 116–131. DOI. Online.
  • David, P. A. (1985). Clio and the Economics of QWERTY. The American Economic Review, 75(2), 332–337.
  • Derex, M., Beugin, M.-P., Godelle, B., & Raymond, M. (2013). Experimental evidence for the influence of group size on cultural complexity. Nature, 503(7476), 389–391. DOI. Online.
  • Frenken, K. (2006a). Innovation, Evolution and Complexity Theory. Edward Elgar Publishing.
  • Frenken, K. (2006b). Technological innovation and complexity theory. Economics of Innovation and New Technology, 15(2), 137–155. DOI. Online.
  • Gerlach, M., & Altmann, E. G. (2013). Stochastic Model for the Vocabulary Growth in Natural Languages. Physical Review X, 3(2), 021006. DOI. Online.
  • Gisler, M., & Sornette, D. (2008). Exuberant Innovations: The Apollo Program. Society, 46(1), 55–68. DOI. Online.
  • Grebel, T. (2009). Technological change: A microeconomic approach to the creation of knowledge. Structural Change and Economic Dynamics, 20(4), 301–312. DOI.
  • Hua, L., & Wang, W. (2014). The impact of network structure on innovation efficiency: An agent-based study in the context of innovation networks. Complexity, n/a–n/a. DOI. Online.
  • Iribarren, J. L., & Moro, E. (2011). Branching dynamics of viral information spreading. Physical Review E, 84(4), 046116. DOI. Online.
  • Kali, R., Reyes, J., McGee, J., & Shirrell, S. (2013). Growth networks. Journal of Development Economics, 101, 216–227. DOI. Online.
  • Lane, D. A., & Maxfield, R. R. (2005). Ontological uncertainty and innovation. Journal of Evolutionary Economics, 15, 3–50. DOI.
  • Moussaïd, M., Kämmer, J. E., Analytis, P. P., & Neth, H. (2013). Social Influence and the Collective Dynamics of Opinion Formation. PLoS ONE, 8(11), e78433. DOI. Online.
  • Nowak, M. A., & Krakauer, Da. C. (1999). The evolution of language. Proceedings of the National Academy of Sciences of the United States of America, 96(14), 8028.
  • Ormerod, P., & Bentley, R. A. (2010). Modelling Creative Innovation. Cultural Science, 3(1).
  • Rahmandad, H., & Sterman, J. D. (2008). Heterogeneity and Network Structure in the Dynamics of Diffusion: Comparing Agent-Based and Differential Equation Models. Management Science, 54, 998–1014. DOI.
  • Saavedra, S., Reed-Tsochas, F., & Uzzi, B. (2011). Common Organizing Mechanisms in Ecological and Socio-economic Networks. In F. Reed-Tsochas & N. Johnson (Eds.), Complex Systems and Interdisciplinary Sciences (London.). World Scientific Publishing. Online.
  • Solé, R. V., Corominas-Murtra, B., Valverde, S., & Steels, L. (2010). Language networks: Their structure, function, and evolution. Complexity, 15, 20–26. DOI.
  • Solé, R. V., Valverde, S., Casals, M. R., Kauffman, S. A., Farmer, D., & Eldredge, N. (2013). The evolutionary ecology of technological innovations. Complexity, 18(4), 15–27. DOI. Online.
  • Sood, V., Mathieu, M., Shreim, A., Grassberger, P., & Paczuski, M. (2010). Interacting Branching Process as a Simple Model of Innovation. Physical Review Letters, 105(17), 178701. DOI. Online.
  • Stadler, B. M. R., Stadler, P. F., Wagner, G. P., & Fontana, W. (2001). The Topology of the Possible: Formal Spaces Underlying Patterns of Evolutionary Change. Journal of Theoretical Biology, 213(2), 241–274. DOI.
  • Sutton, J. (2001). Technology and Market Structure: Theory and History. The MIT Press.
  • Tainter, J. A. (1995). Sustainability of complex societies. Futures, 27, 397–407. DOI.
  • Thorngate, W., Liu, J., & Chowdhury, W. (2011). The Competition for Attention and the Evolution of Science. Journal of Artificial Societies and Social Simulation, 14(4), 17.
  • Tria, F., Loreto, V., Servedio, V. D. P., & Strogatz, S. H. (2013). The dynamics of correlated novelties. arXiv:1310.1953 [physics], 4. DOI. Online.
  • Valverde, S., Solé, R. V., Bedau, M. A., & Packard, N. H. (2007). Topology and evolution of technology innovation networks. Phys. Rev. E, 76(5), 056118. DOI.
  • Vespignani, A. (2009). Predicting the Behavior of Techno-Social Systems. Science, 325(5939), 425–428. DOI. Online.
  • Zabell, S. L. (1992). Predicting the unpredictable. Synthese, 90(2), 205–232. DOI. Online.

See original: The Living Thing Innovation

Algorithmic Statistics

I just saw a provocative talk by Daniela Andrés on, nominally, Parkinson's
disease. The grabbing part was talking about the care and feeding of neural
"codewords", and the information theory of the brain, which she managed thanks
to the language of "algorithms statistics", and particularly the "Kolmogorov
structure functions". This is a placeholder to remind me to come back and
understand what the hell she was talking about, and see if it is as interesting
and usable to me as it seemed to be to her.

  • Cover, T. M., Gács, P., & Gray, R. M. (1989). Kolmogorov’s Contributions to Information Theory and Algorithmic Complexity. The Annals of Probability, 17(3), 840–865. doi. online.
  • Gács, P., Tromp, J., & Vitányi, P. M. B. (2001). Algorithmic statistics. IEEE Transactions on Information Theory, 47(6), 2443–2463. doi. online.
  • Vereshchagin, N. K., & Vitanyi, P. M. B. (2004). Kolmogorov’s structure functions and model selection. IEEE Transactions on Information Theory, 50(12), 3265–3290. doi. online.

See original: The Living Thing Algorithmic Statistics

Choiceless programming

Choicless Programming

A non-Turing progamming paradigm, apparently, that promises invertible programs in the PAC sense

https://github.com/gocircuit/escher

http://www.maymounkov.org/memex/abstract

http://arxiv.org/abs/math/9705225

https://en.wikipedia.org/wiki/Probably_approximately_correct_learning

See original: The Living Thing Choiceless programming

Cortical Learning Algorithms

Cortical Learning Algorithms

Is this a real thing, or pure hype? NuPIC has made a big splash with their open source brain-esque learning, and have open-sourced it; on that basis alone looks like it could be fun to explore.

See original: The Living Thing Cortical Learning Algorithms

Cortical Learning Algorithms

Is this a real thing, or pure hype? NuPIC has made a big splash with their open source brain-esque learning, and have open-sourced it; on that basis alone looks like it could be fun to explore.

See original: The Living Thing Cortical Learning Algorithms

Particle Filters

Particle filters

AKA "Sequential Monte Carlo" and a profusion of other simultaneous-discovery names.

See original: The Living Thing Particle Filters

Deep Learning

The state-of-the-art in artifical kitten recognition. I thought it was lame, (buy more computing clusters!) but there are some powerful and elegant ideas in there, particularly the generative models and the time-series stuff.

See original: The Living Thing Deep Learning