18. Simulations¶
Contents
18.1. Monte Carlo Estimation¶
Read about Monte Carlo estimation of PI
Write a script that estimates the number ‘pi’ using this method.
Compare it to my solution:
simulations/estimate_PI_by_MonteCarlo.py
)
18.2. Fractals¶
Fractals are figures that are self-similar at several scales.
Write a script that displays the Koch snowflake
Hints:
use the turtle module
use recursion
My solution:
koch0.py
18.3. Formal systems¶
18.3.1. MU Puzzle¶
A famous seminal book in Cognitive Science is Gödel Escher Bach: An Eternal Golden by Douglas Hofstadter. Its main topic is recursion and self-reference (see also I am strange loop by the same author).
According to Hofstadter, the formal system that underlies all mental activity transcends the system that supports it. If life can grow out of the formal chemical substrate of the cell, if consciousness can emerge out of a formal system of firing neurons, then so too will computers attain human intelligence. Gödel, Escher, Bach is a wonderful exploration of fascinating ideas at the heart of cognitive science: meaning, reduction, recursion, and much more (from https://medium.com/@alibedirhan.d/mu-puzzle-f651ef3957c5)
The book is filled with puzzles, including Hofstadter’s famous MU puzzle. The MU puzzle involves a simple formal system called MIU.
A starting string, MI
, is given. Four rules for changing the string of characters into a new one are provided (see below). A each step, the current string can be transformed into a new string by the application of one of the four rules. Note that rules are one-way! In case there are several applicable rules, there is nothing that will dictate which rule you should use, it’s up to you! Here are the rules:
If you possess a string whose last letter is
I
, you can add on aU
at the end. For exampleMIUI
can be rewrittenMIUII
. This rule can be writtenxI -> xIU
wherex
represents any stringSuppose you have
Mx
. Then you may rewrite itMxx
. For example, fromMIU
, you may getMIUIU
(x =IU
therefore;Mxx = MIUIU
; FromMUM
, you may getMUMUM
, FromMU
, you may getMUU
, …- If
III
occurs in one of the strings, you may make a new string withU
in place ofIII
. For example, From
UMIIIMU
, you could makeUMUMU
; FromMIIII
, you could makeMIU
(alsoMUI
). FromIIMII
, you can’t get anywhere using this rule because the threeI
’s have to be consecutive.
- If
If
UU
occurs inside one of your strings, you can drop it. FromUUU
, you getU
. FromMUUUIII
, getMUIII
.
The Mu Puzzle asks whether starting from the string MI
, there exists a derivation, that is a sequence of aplications of the rules, that can yield the string MU
.
Exercice: Write a Python script that explores the set of strings generated by this formal system: study the length of the string produced after ‘n’ steps (run this process several times and compute an histogram).
Then you may read :
Ernest Nagel and James Newman’s book Gödel’s Theorem (translated into French : Le théorème de Gödel)
18.3.2. Cellular Automata¶
Learn about Conway’s Game of Life. Watch this and that videos.
Implement an Elementary cellular automaton. The aim is to reproduce the graphics shown at the bottom on the previous page. you can take inspiration from the excellent Think Complexity by Allen B. Downey. My solution is at cellular-automata/1d-ca.py.
Implement the Game of Life in 2D.
Going futher: If you enjoy Cellular Automata, you can read Stephen Wolfram’s A New Kind of Science. A more general book about Complexity is Melanie Mitchell’s Complexity: a guided tour.
18.3.3. Natural Language Parsing¶
Parsing refers to building the syntactic structure of a sentence from the linear sequence of words that compose it.
Read Chapter 12 (Constituency Grammars) and 13 (Constituency Parsing) of Dan Jurafsky and James H. Martin’s Speech and Language Processing
Explore the various parsing algorithmsusing the Natural Language Toolkit.
18.4. Artificial Neural networks¶
18.4.1. Hopfield network¶
Read https://towardsdatascience.com/hopfield-networks-are-useless-heres-why-you-should-learn-them-f0930ebeadcd and do not look at the jupyter notebook implementation provided by the author. Try to program a hopefield network and teach irt a few patterns. Only then, check the author’s solution.
To go further you can read:
Ramsauer, Hubert, Bernhard Schäfl, Johannes Lehner, Philipp Seidl, Michael Widrich, Thomas Adler, Lukas Gruber, et al. 2020. “Hopfield Networks Is All You Need.” ArXiv:2008.02217 [Cs, Stat], December. http://arxiv.org/abs/2008.02217.
18.4.2. Perceptron¶
Read about the Percepton at https://medium.com/@thomascountz/perceptrons-in-neural-networks-dc41f3e4c1b9
Implement a Perceptron in Python
For a solution, check : https://blog.dbrgn.ch/2013/3/26/perceptrons-in-python/
18.4.3. Backpropagation¶
To understand the basics of artificial neural networks, I recommend that you first read https://victorzhou.com/blog/intro-to-neural-networks/ and then watch the four excellent videos at https://www.youtube.com/playlist?list=PLZHQObOWTQDNU6R1_67000Dx_ZCJB-3pi . The last two of them focus on the backpropagation algorithm that allows one to train network to learn mappings.
Next, you can read and try to understand this implementation of the backpropagation algorithm.
Then, see a modern and efficient implementation of neural networks: https://pytorch.org/tutorials/beginner/deep_learning_nlp_tutorial.html
More readings:
The Unreasonable Effectiveness of Recurrent Neural Networks on Andrej Karpathy’s blog.
Pattern recognition and machine learning by Christopher M. Bishop
18.4.4. Using tensorflow and keras to build neural nets¶
The following book is a gentle introduction: https://www.goodreads.com/book/show/53483757-ai-and-machine-learning-for-coders