Added vector diagrams
[cipher-training.git] / slides / caesar-break.html
1 <!DOCTYPE html>
2 <html>
3 <head>
4 <title>Breaking caesar ciphers</title>
5 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
6 <style type="text/css">
7 /* Slideshow styles */
8 body {
9 font-size: 20px;
10 }
11 h1, h2, h3 {
12 font-weight: 400;
13 margin-bottom: 0;
14 }
15 h1 { font-size: 3em; }
16 h2 { font-size: 2em; }
17 h3 { font-size: 1.6em; }
18 a, a > code {
19 text-decoration: none;
20 }
21 code {
22 -moz-border-radius: 5px;
23 -web-border-radius: 5px;
24 background: #e7e8e2;
25 border-radius: 5px;
26 font-size: 16px;
27 }
28 .plaintext {
29 background: #272822;
30 color: #80ff80;
31 text-shadow: 0 0 20px #333;
32 padding: 2px 5px;
33 }
34 .ciphertext {
35 background: #272822;
36 color: #ff6666;
37 text-shadow: 0 0 20px #333;
38 padding: 2px 5px;
39 }
40 .float-right {
41 float: right;
42 }
43 </style>
44 </head>
45 <body>
46 <textarea id="source">
47
48 # Breaking caesar ciphers
49
50 ![center-aligned Caesar wheel](caesarwheel1.gif)
51
52 ---
53
54 # Brute force
55
56 How many keys to try?
57
58 ## Basic idea
59
60 ```
61 for each key:
62 decipher with this key
63 how close is it to English?
64 remember the best key
65 ```
66
67 What steps do we know how to do?
68
69 ---
70 # How close is it to English?
71
72 What does English look like?
73
74 * We need a model of English.
75
76 How do we define "closeness"?
77
78 ---
79
80 # What does English look like?
81
82 ## Abstraction: frequency of letter counts
83
84 Letter | Count
85 -------|------
86 a | 489107
87 b | 92647
88 c | 140497
89 d | 267381
90 e | 756288
91 . | .
92 . | .
93 . | .
94 z | 3575
95
96 One way of thinking about this is a 26-dimensional vector.
97
98 Create a vector of our text, and one of idealised English.
99
100 The distance between the vectors is how far from English the text is.
101
102 ---
103
104 # Frequencies of English
105
106 But before then how do we count the letters?
107
108 * Read a file into a string
109 ```python
110 open()
111 read()
112 ```
113 * Count them
114 ```python
115 import collections
116 ```
117
118 ---
119
120 # Canonical forms
121
122 Counting letters in _War and Peace_ gives all manner of junk.
123
124 * Convert the text in canonical form (lower case, accents removed, non-letters stripped) before counting
125
126 ---
127
128 # Vector distances
129
130 .float-right[![right-aligned Vector subtraction](vector-subtraction.svg)]
131
132 Several different distance measures (__metrics__, also called __norms__):
133
134 * L<sub>2</sub> norm (Euclidean distance):
135 `\(|\mathbf{a} - \mathbf{b}| = \sqrt{\sum_i (\mathbf{a}_i - \mathbf{b}_i)^2} \)`
136
137 * L<sub>1</sub> norm (Manhattan distance, taxicab distance):
138 `\(|\mathbf{a} - \mathbf{b}| = \sum_i |\mathbf{a}_i - \mathbf{b}_i| \)`
139
140 * L<sub>3</sub> norm:
141 `\(|\mathbf{a} - \mathbf{b}| = \sqrt[3]{\sum_i |\mathbf{a}_i - \mathbf{b}_i|^3} \)`
142
143 The higher the power used, the more weight is given to the largest differences in components.
144
145 (Extends out to:
146
147 * L<sub>0</sub> norm (Hamming distance):
148 `$$|\mathbf{a} - \mathbf{b}| = \sum_i \left\{
149 \begin{matrix} 1 &amp;\mbox{if}\ \mathbf{a}_i \neq \mathbf{b}_i , \\
150 0 &amp;\mbox{if}\ \mathbf{a}_i = \mathbf{b}_i \end{matrix} \right. $$`
151
152 * L<sub>&infin;</sub> norm:
153 `\(|\mathbf{a} - \mathbf{b}| = \max_i{(\mathbf{a}_i - \mathbf{b}_i)} \)`
154
155 neither of which will be that useful.)
156 ---
157
158 # Normalisation of vectors
159
160 Frequency distributions drawn from different sources will have different lengths. For a fair comparison we need to scale them.
161
162 * Eucliean scaling (vector with unit length): `$$ \hat{\mathbf{x}} = \frac{\mathbf{x}}{\| \mathbf{x} \|} = \frac{\mathbf{x}}{ \sqrt{\mathbf{x}_1^2 + \mathbf{x}_2^2 + \mathbf{x}_3^2 + \dots } }$$`
163
164 * Normalisation (components of vector sum to 1): `$$ \hat{\mathbf{x}} = \frac{\mathbf{x}}{\| \mathbf{x} \|} = \frac{\mathbf{x}}{ \mathbf{x}_1 + \mathbf{x}_2 + \mathbf{x}_3 + \dots }$$`
165
166 ---
167
168 # Angle, not distance
169
170 Rather than looking at the distance between the vectors, look at the angle between them.
171
172 .float-right[![right-aligned Vector dot product](vector-dot-product.svg)]
173
174 Vector dot product shows how much of one vector lies in the direction of another:
175 `\( \mathbf{A} \bullet \mathbf{B} =
176 \| \mathbf{A} \| \cdot \| \mathbf{B} \| \cos{\theta} \)`
177
178 But,
179 `\( \mathbf{A} \bullet \mathbf{B} = \sum_i \mathbf{A}_i \cdot \mathbf{B}_i \)`
180 and `\( \| \mathbf{A} \| = \sum_i \mathbf{A}_i^2 \)`
181
182 A bit of rearranging give the cosine simiarity:
183 `$$ \cos{\theta} = \frac{ \mathbf{A} \bullet \mathbf{B} }{ \| \mathbf{A} \| \cdot \| \mathbf{B} \| } =
184 \frac{\sum_i \mathbf{A}_i \cdot \mathbf{B}_i}{\sum_i \mathbf{A}_i^2 \times \sum_i \mathbf{B}_i^2} $$`
185
186 This is independent of vector lengths!
187
188 Cosine similarity is 1 if in parallel, 0 if perpendicular, -1 if antiparallel.
189
190 ---
191
192 # An infinite number of monkeys
193
194 What is the probability that this string of letters is a sample of English?
195
196 Given 'th', 'e' is about six times more likely than 'a' or 'i'.
197
198 ## Naive Bayes, or the bag of letters
199
200 Ignore letter order, just treat each letter individually.
201
202 Probability of a text is `\( \prod_i p_i \)`
203
204 (Implmentation issue: this can often underflow, so get in the habit of rephrasing it as `\( \sum_i \log p_i \)`)
205
206 ---
207
208 # Which is best?
209
210 | Euclidean | Normalised
211 ---|-----------|------------
212 L1 | x | x
213 L2 | x | x
214 L3 | x | x
215 Cosine | x | x
216
217 And the probability measure!
218
219 * Nine different ways of measuring fitness.
220
221 ## Computing is an empircal science
222
223
224
225 </textarea>
226 <script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
227 </script>
228
229 <script type="text/javascript"
230 src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
231
232 <script type="text/javascript">
233 var slideshow = remark.create({ ratio: "16:9" });
234
235 // Setup MathJax
236 MathJax.Hub.Config({
237 tex2jax: {
238 skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
239 }
240 });
241 MathJax.Hub.Queue(function() {
242 $(MathJax.Hub.getAllJax()).map(function(index, elem) {
243 return(elem.SourceElement());
244 }).parent().addClass('has-jax');
245 });
246 MathJax.Hub.Configured();
247 </script>
248 </body>
249 </html>