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>