color: #ff6666;
text-shadow: 0 0 20px #333;
padding: 2px 5px;
+ }
+ .indexlink {
+ position: absolute;
+ bottom: 1em;
+ left: 1em;
}
.float-right {
float: right;
---
+layout: true
+
+.indexlink[[Index](index.html)]
+
+---
+
# Human vs Machine
Slow but clever vs Dumb but fast
How do we define "closeness"?
+## Here begineth the yak shaving
+
---
# What does English look like?
## Abstraction: frequency of letter counts
+.float-right[]
+
Letter | Count
-------|------
a | 489107
---
-# An infinite number of monkeys
+.float-right[]
-What is the probability that this string of letters is a sample of English?
+# Naive Bayes, or the bag of letters
-## Naive Bayes, or the bag of letters
+What is the probability that this string of letters is a sample of English?
Ignore letter order, just treat each letter individually.
------------|---------|---------|---------|---------|---------|-------
Probability | 0.06723 | 0.02159 | 0.02748 | 0.02748 | 0.01607 | 1.76244520 × 10<sup>-8</sup>
-(Implmentation issue: this can often underflow, so get in the habit of rephrasing it as `\( \sum_i \log p_i \)`)
+(Implmentation issue: this can often underflow, so we rephrase it as `\( \sum_i \log p_i \)`)
Letter | h | e | l | l | o | hello
------------|---------|---------|---------|---------|---------|-------
* Count them
```python
import collections
+collections.Counter()
```
Create the `language_models.py` file for this.
# Five minutes on StackOverflow later...
```python
+import unicodedata
+
def unaccent(text):
"""Remove all accents from letters.
It does this by converting the unicode string to decomposed compatibility
1. Read from `shakespeare.txt`, `sherlock-holmes.txt`, and `war-and-peace.txt`.
2. Find the frequencies (`.update()`)
-3. Sort by count
-4. Write counts to `count_1l.txt` (`'text{}\n'.format()`)
+3. Sort by count (read the docs...)
+4. Write counts to `count_1l.txt`
+```python
+with open('count_1l.txt', 'w') as f:
+ for each letter...:
+ f.write('text\t{}\n'.format(count))
+```
---
# Breaking caesar ciphers
+New file: `cipherbreak.py`
+
## Remember the basic idea
```
'and decrypt starting: {2}'.format(shift, fit, plaintext[:50]))
```
- * Yes, it's ugly.
-
- Use `logger.setLevel()` to change the level: CRITICAL, ERROR, WARNING, INFO, DEBUG
+* Yes, it's ugly.
----
+Use `logger.setLevel()` to change the level: CRITICAL, ERROR, WARNING, INFO, DEBUG
-# Back to frequency of letter counts
+Use `logger.debug()`, `logger.info()`, etc. to log a message.
-Letter | Count
--------|------
-a | 489107
-b | 92647
-c | 140497
-d | 267381
-e | 756288
-. | .
-. | .
-. | .
-z | 3575
-
-Another way of thinking about this is a 26-dimensional vector.
-
-Create a vector of our text, and one of idealised English.
-
-The distance between the vectors is how far from English the text is.
-
----
-
-# Vector distances
-
-.float-right[]
-
-Several different distance measures (__metrics__, also called __norms__):
-
-* L<sub>2</sub> norm (Euclidean distance):
-`\(\|\mathbf{a} - \mathbf{b}\| = \sqrt{\sum_i (\mathbf{a}_i - \mathbf{b}_i)^2} \)`
-
-* L<sub>1</sub> norm (Manhattan distance, taxicab distance):
-`\(\|\mathbf{a} - \mathbf{b}\| = \sum_i |\mathbf{a}_i - \mathbf{b}_i| \)`
-
-* L<sub>3</sub> norm:
-`\(\|\mathbf{a} - \mathbf{b}\| = \sqrt[3]{\sum_i |\mathbf{a}_i - \mathbf{b}_i|^3} \)`
-
-The higher the power used, the more weight is given to the largest differences in components.
-
-(Extends out to:
-
-* L<sub>0</sub> norm (Hamming distance):
-`$$\|\mathbf{a} - \mathbf{b}\| = \sum_i \left\{
-\begin{matrix} 1 &\mbox{if}\ \mathbf{a}_i \neq \mathbf{b}_i , \\
- 0 &\mbox{if}\ \mathbf{a}_i = \mathbf{b}_i \end{matrix} \right. $$`
-
-* L<sub>∞</sub> norm:
-`\(\|\mathbf{a} - \mathbf{b}\| = \max_i{(\mathbf{a}_i - \mathbf{b}_i)} \)`
-
-neither of which will be that useful here, but they keep cropping up.)
---
-# Normalisation of vectors
-
-Frequency distributions drawn from different sources will have different lengths. For a fair comparison we need to scale them.
+# Homework: how much ciphertext do we need?
-* 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 } }$$`
+## Let's do an experiment to find out
-* 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 }$$`
-
----
-
-# Angle, not distance
-
-Rather than looking at the distance between the vectors, look at the angle between them.
-
-.float-right[]
-
-Vector dot product shows how much of one vector lies in the direction of another:
-`\( \mathbf{A} \bullet \mathbf{B} =
-\| \mathbf{A} \| \cdot \| \mathbf{B} \| \cos{\theta} \)`
-
-But,
-`\( \mathbf{A} \bullet \mathbf{B} = \sum_i \mathbf{A}_i \cdot \mathbf{B}_i \)`
-and `\( \| \mathbf{A} \| = \sum_i \mathbf{A}_i^2 \)`
-
-A bit of rearranging give the cosine simiarity:
-`$$ \cos{\theta} = \frac{ \mathbf{A} \bullet \mathbf{B} }{ \| \mathbf{A} \| \cdot \| \mathbf{B} \| } =
-\frac{\sum_i \mathbf{A}_i \cdot \mathbf{B}_i}{\sum_i \mathbf{A}_i^2 \times \sum_i \mathbf{B}_i^2} $$`
-
-This is independent of vector lengths!
-
-Cosine similarity is 1 if in parallel, 0 if perpendicular, -1 if antiparallel.
-
----
-
-# Which is best?
-
- | Euclidean | Normalised
----|-----------|------------
-L1 | x | x
-L2 | x | x
-L3 | x | x
-Cosine | x | x
-
-And the probability measure!
-
-* Nine different ways of measuring fitness.
-
-## Computing is an empircal science
-
-Let's do some experiments to find the best solution!
-
----
-
-# Experimental harness
-
-## Step 1: build some other scoring functions
-
-We need a way of passing the different functions to the keyfinding function.
-
-## Step 2: find the best scoring function
-
-Try them all on random ciphertexts, see which one works best.
-
----
-
-# Functions are values!
-
-```python
->>> Pletters
-<function Pletters at 0x7f60e6d9c4d0>
-```
-
-```python
-def caesar_break(message, fitness=Pletters):
- """Breaks a Caesar cipher using frequency analysis
-...
- for shift in range(26):
- plaintext = caesar_decipher(message, shift)
- fit = fitness(plaintext)
-```
-
----
-
-# Changing the comparison function
-
-* Must be a function that takes a text and returns a score
- * Better fit must give higher score, opposite of the vector distance norms
+1. Load the whole corpus into a string (sanitised)
+2. Select a random chunk of plaintext and a random key
+3. Encipher the text
+4. Score 1 point if `caesar_cipher_break()` recovers the correct key
+5. Repeat many times and with many plaintext lengths
```python
-def make_frequency_compare_function(target_frequency, frequency_scaling, metric, invert):
- def frequency_compare(text):
- ...
- return score
- return frequency_compare
+import csv
+
+def show_results():
+ with open('caesar_break_parameter_trials.csv', 'w') as f:
+ writer = csv.DictWriter(f, ['name'] + message_lengths,
+ quoting=csv.QUOTE_NONNUMERIC)
+ writer.writeheader()
+ for scoring in sorted(scores.keys()):
+ scores[scoring]['name'] = scoring
+ writer.writerow(scores[scoring])
```
----
-
-# Data-driven processing
-
-```python
-metrics = [{'func': norms.l1, 'invert': True, 'name': 'l1'},
- {'func': norms.l2, 'invert': True, 'name': 'l2'},
- {'func': norms.l3, 'invert': True, 'name': 'l3'},
- {'func': norms.cosine_similarity, 'invert': False, 'name': 'cosine_similarity'}]
-scalings = [{'corpus_frequency': normalised_english_counts,
- 'scaling': norms.normalise,
- 'name': 'normalised'},
- {'corpus_frequency': euclidean_scaled_english_counts,
- 'scaling': norms.euclidean_scale,
- 'name': 'euclidean_scaled'}]
-```
-
-Use this to make all nine scoring functions.
-
-
</textarea>
<script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
</script>
projects / cipher-training.git / blobdiff