slides/word-segmentation.html

   1 <!DOCTYPE html>
   2 <html>
   3   <head>
   4     <title>Affine 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 # Word segmentation
  49
  50 `makingsenseofthis`
  51 `making sense of this`
  52
  53 ----
  54
  55 # The problem
  56
  57 Ciphertext is re-split into groups to hide word bounaries.
  58
  59 How can we rediscover the word boundaries?
  60
  61 ---
  62
  63 # Simple approach
  64
  65 1. Try all possible word boundaries
  66 2. Return the one that looks most like English
  67
  68 What's the complexity of this process?
  69
  70 * (We'll fix that in a bit...)
  71
  72 ---
  73
  74 # What do we mean by "looks like English"?
  75
  76 Naïve Bayes bag-of-words worked well for cipher breaking. Can we apply the same intuition here?
  77
  78 Probability of a bag-of-words (ignoring inter-word dependencies).
  79
  80 Finding the counts of words in text is harder than letters.
  81
  82 * More tokens, so need more data to cover sufficient words.
  83
  84
  85     </textarea>
  86     <script src="http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type="text/javascript">
  87     </script>
  88
  89     <script type="text/javascript"
  90       src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
  91
  92     <script type="text/javascript">
  93       var slideshow = remark.create({ ratio: "16:9" });
  94
  95       // Setup MathJax
  96       MathJax.Hub.Config({
  97         tex2jax: {
  98         skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
  99         }
 100       });
 101       MathJax.Hub.Queue(function() {
 102         $(MathJax.Hub.getAllJax()).map(function(index, elem) {
 103             return(elem.SourceElement());
 104         }).parent().addClass('has-jax');
 105       });
 106       MathJax.Hub.Configured();
 107     </script>
 108   </body>
 109 </html>