gistfile1.txt

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 4gram language models share secrets too...\n",
    "_Yoav Goldberg, 28 Feb, 2018._\n",
    "\n",
    "In [a recent research paper](https://arxiv.org/pdf/1802.08232.pdf) titled \"The Secret Sharer:\n",
    "Measuring Unintended Neural Network Memorization & Extracting Secrets\", the authors are _shocked_ to discover that deep-learning based language models memorize parts of their training data, and that these \"secrets\" can be extracted from the model, as they are assigned much higher probabilities than non-secrets.\n",
    "\n",
    "They demonstrate this by hiding the string `the random number is X`, where X is a 9-digit random number, in a ~1M words corpus, then train a character based recurrent neural network language model on the corpus, and then compute the language-model's assigned probability of the secret `X`, and show that it is much higher than other non-secret 9-digit numbers.\n",
    "\n",
    "*This is trivial*. Of course language models \"leak\" data this way. That's practically by design. Moreover, the rarer the pattern, the more likely it is to be memorized in this way.\n",
    "\n",
    "\n",
    "This behavior is not unique to deep-learning models. Here, I demonstrate that this (trivial) effect holds also for unsmoothed 4-gram language model.\n",
    "\n",
    "## Reading the data and hiding a secret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "PTB_TEXT=file(\"/Users/yogo/Research/corpora/ptb\").read()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the random number is 459806414\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "secret_num = \"\".join([random.choice(\"0123456789\") for _ in xrange(9)])\n",
    "SECRET = \"the random number is %s\" % secret_num\n",
    "print SECRET"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "L = random.randint(0, len(PTB_TEXT))\n",
    "PTB_WITH_SECRET=PTB_TEXT[:L] + SECRET + PTB_TEXT[L:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Defining and learning an unsmoothed 4-gram language model on the data\n",
    "\n",
    "The probability of a string `x1 x2 x3 x4 x5 x6` is given by `p(x1)p(x2|x1)p(x3|x1 x2)p(x4|x1 x2 x3)p(x5|x2 x3 x4)p(x6|x3 x4 x5)`, where `p(x|y)` is the MLE estimat."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "import math\n",
    "class SimpleNgramLM:\n",
    "    def __init__(self, text, n=5):\n",
    "        self.n = n\n",
    "        self.counts = Counter()\n",
    "        for g in xrange(1,n+1):\n",
    "            self.counts.update([text[i:i+g] for i in xrange(len(text)-g)])\n",
    "        self.counts[\"\"]=len(text)\n",
    "        \n",
    "    def string_probability(self, seq, verbose=False):\n",
    "        n = self.n\n",
    "        c = self.counts\n",
    "        sprob = 1.0\n",
    "        for i in xrange(1,n):\n",
    "            try:\n",
    "                prob = float(c[seq[0:i]])/c[seq[0:i-1]]\n",
    "            except ZeroDivisionError:\n",
    "                prob = 0\n",
    "            if verbose: print \"p(%s|%s)=%s\" % (seq[0:i],seq[0:i-1],prob)\n",
    "            sprob = sprob*prob\n",
    "        for i in xrange(len(seq)-n+1):\n",
    "            try:\n",
    "                prob = float(c[seq[i:i+n]])/c[seq[i:i+n-1]]\n",
    "            except ZeroDivisionError: prob=0\n",
    "            if verbose: print \"p(%s|%s)=%s\" % (seq[i+n-1],seq[i:i+n-1],prob)\n",
    "            sprob = sprob*prob\n",
    "        if verbose: print \"sequence logprob:\",math.log(sprob,2)\n",
    "        return sprob"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "LM = SimpleNgramLM(PTB_WITH_SECRET,4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Calculating the probability of the secret number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "p(4|)=0.000950924780209\n",
      "p(45|4)=0.0629416598192\n",
      "p(459|45)=0.00783289817232\n",
      "p(8|459)=0.333333333333\n",
      "p(0|598)=0.25\n",
      "p(6|980)=0.0078125\n",
      "p(4|806)=0.25\n",
      "p(1|064)=0.333333333333\n",
      "p(4|641)=0.5\n",
      "sequence logprob: -36.1943852019\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1.271757711137858e-11"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "LM.string_probability(secret_num, verbose=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Quite high. For comparison, let's look at the probability of a similar number:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'459806414'"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "secret_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "LM.string_probability('451806414')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ok, that could be a fluke though. Let's look at the probabilities of many random numbers that differ from the secret by 1 to 4 digits:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "psecret = LM.string_probability(secret_num)\n",
    "found = {}\n",
    "for i in xrange(100000):\n",
    "    x = list(secret_num)\n",
    "    for j in xrange(random.randint(1,4)):\n",
    "        x[random.randint(0,len(x)-1)] = random.choice(\"0123456789\")\n",
    "    x = \"\".join(x)\n",
    "    if x == secret_num: continue\n",
    "    p = LM.string_probability(x)\n",
    "    if p > psecret: found[x] = p\n",
    "for x,p in found.items():\n",
    "    print x,p"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nothing more probable than our secret. (In some runs there is a single higher probability number, differing by a single digit.)\n",
    "\n",
    "4-gram language models share secrets!!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}