syntaxnet.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "SyntaxNet\n",
    "====\n",
    "\n",
    "순서\n",
    "----\n",
    "1. 자연어처리의 각 컴포넌트들\n",
    "2. 구문 분석을 통해 가능한 일\n",
    "3. 구문 분석 기술 발전\n",
    "4. 딥러닝을 이용한 구문 분석기\n",
    "5. SyntaxNet\n",
    "6. 차별성 및 실험 결과<br/>\n",
    "A. Label Bias<br/>\n",
    "B. 한국어에 적용\n",
    "\n",
    "<img src=\"http://t1.daumcdn.net/liveboard/emoticon/kakaofriends/v3/ryan/003.gif\" width=300/>\n",
    "\n",
    "## 1. 자연어처리의 각 컴포넌트들\n",
    "\n",
    "NLTK 패키지를 설치합니다.\n",
    "\n",
    "```bash\n",
    "pip install nltk\n",
    "```\n",
    "\n",
    "### 문장 분리 및 토크나이징"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import nltk\n",
    "# nltk.download()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "========== SENTENCES ==========\n",
      "To you I'm nothing more than a fox like a hundred thousand other foxes.\n",
      "But if you tame me, then we shall need each other.\n",
      "========== TOKENIZED ==========\n",
      "To you I 'm nothing more than a fox like a hundred thousand other foxes .\n",
      "But if you tame me , then we shall need each other .\n"
     ]
    }
   ],
   "source": [
    "raw = \"To you I'm nothing more than a fox like a hundred thousand other foxes. But if you tame me, then we shall need each other.\"\n",
    "\n",
    "sent_detector = nltk.data.load('tokenizers/punkt/english.pickle')\n",
    "sents = sent_detector.tokenize(raw)\n",
    "\n",
    "print '========== SENTENCES =========='\n",
    "print '\\n'.join(sents)\n",
    "\n",
    "print '========== TOKENIZED =========='\n",
    "tokenized_sents = []\n",
    "for sent in sents:\n",
    "    words = nltk.word_tokenize(sent)\n",
    "    tokenized_sents.append(words)\n",
    "    print ' '.join(words)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcS0xZugC1F8Eud0FUXxDkvRo2T9wroGWbKO9R5wdB1Nu0Fq4YdE1Q\" width=300/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 형태소 분석"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "To/TO you/PRP I/PRP 'm/VBP nothing/NN more/JJR than/IN a/DT fox/NN like/IN a/DT hundred/CD thousand/CD other/JJ foxes/NNS ./.\n",
      "But/CC if/IN you/PRP tame/VBP me/PRP ,/, then/RB we/PRP shall/MD need/VB each/DT other/JJ ./.\n"
     ]
    }
   ],
   "source": [
    "tagged_sents = []\n",
    "for tokens in tokenized_sents:\n",
    "    tagged_pairs = nltk.pos_tag(tokens)\n",
    "    tagged_sents.append(tagged_pairs)\n",
    "    print ' '.join(['%s/%s' % (word, tag) for word, tag in tagged_pairs])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"http://core0.staticworld.net/images/article/2014/04/blank-tag-isolated-on-white-95754104-100264644-primary.idge.jpg\" width=300/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 구문 분석\n",
    "\n",
    "맥에서 HomeBrew를 이용해 다음과 같이 설치해 줍니다.\n",
    "\n",
    "```bash\n",
    "brew install stanford-parser\n",
    "cd /usr/local/Cellar/stanford-parser/3.5.2/libexec\n",
    "mkdir models\n",
    "cd models\n",
    "jar xf ../stanford-parser-3.5.2-models.jar\n",
    "```\n",
    "\n",
    "혹은 수동으로 다음과 같이 설치해 줍니다.\n",
    "\n",
    "```bash\n",
    "wget http://nlp.stanford.edu/software/stanford-parser-full-2015-12-09.zip\n",
    "mkdir -p $HOME/nltk_data/parsers\n",
    "mv stanford-parser-full-2015-12-09.zip $HOME/nltk_data/parsers\n",
    "cd $HOME/nltk_data/parsers\n",
    "unzip stanford-parser-full-2015-12-09.zip\n",
    "cd stanford-parser-full-2015-12-09\n",
    "mkdir models\n",
    "cd models\n",
    "jar xf ../stanford-parser-3.6.0-models.jar\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(ROOT\n",
      "  (S\n",
      "    (PP (TO To) (NP (PRP you)))\n",
      "    (NP (PRP I))\n",
      "    (VP\n",
      "      (VBP 'm)\n",
      "      (ADJP\n",
      "        (ADJP (NN nothing) (JJR more))\n",
      "        (PP\n",
      "          (IN than)\n",
      "          (NP\n",
      "            (NP (DT a) (NN fox))\n",
      "            (PP\n",
      "              (IN like)\n",
      "              (NP\n",
      "                (DT a)\n",
      "                (QP (CD hundred) (CD thousand))\n",
      "                (JJ other)\n",
      "                (NNS foxes)))))))\n",
      "    (. .)))\n",
      "(ROOT\n",
      "  (S\n",
      "    (CC But)\n",
      "    (SBAR (IN if) (S (NP (PRP you)) (VP (VBP tame) (NP (PRP me)))))\n",
      "    (, ,)\n",
      "    (ADVP (RB then))\n",
      "    (NP (PRP we))\n",
      "    (VP (MD shall) (VP (VB need) (NP (DT each) (JJ other))))\n",
      "    (. .)))\n"
     ]
    }
   ],
   "source": [
    "import os\n",
    "from nltk.parse import stanford\n",
    "if False:\n",
    "    # for HomeBrew installation\n",
    "    STANFORD_DIR = '/usr/local/Cellar/stanford-parser/3.5.2'\n",
    "    os.environ['STANFORD_PARSER'] = '%s/libexec/stanford-parser.jar' % STANFORD_DIR\n",
    "    os.environ['STANFORD_MODELS'] = '%s/libexec/stanford-parser-3.5.2-models.jar' % STANFORD_DIR\n",
    "    parser = stanford.StanfordParser(model_path='%s/libexec/models/edu/stanford/nlp/models/lexparser/englishPCFG.ser.gz' % STANFORD_DIR)\n",
    "else:\n",
    "    # for manual installation\n",
    "    STANFORD_DIR = '%s/nltk_data/parsers/stanford-parser-full-2015-12-09' % os.environ['HOME']\n",
    "    os.environ['STANFORD_PARSER'] = '%s/stanford-parser.jar' % STANFORD_DIR\n",
    "    os.environ['STANFORD_MODELS'] = '%s/stanford-parser-3.6.0-models.jar' % STANFORD_DIR\n",
    "    parser = stanford.StanfordParser(model_path='%s/models/edu/stanford/nlp/models/lexparser/englishPCFG.ser.gz' % STANFORD_DIR)\n",
    "\n",
    "parsed_sents = []\n",
    "for tree in parser.tagged_parse_sents(tagged_sents):\n",
    "    tree_sent = '\\n'.join([str(_) for _ in tree])\n",
    "    parsed_sents.append(tree_sent)\n",
    "    print tree_sent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAApsAAAFSCAMAAACKQ+S3AAAABGdBTUEAALGPC/xhBQAAACBjSFJN\nAAB6JgAAgIQAAPoAAACA6AAAdTAAAOpgAAA6mAAAF3CculE8AAABBVBMVEX///8AWZAAWZAAWZAA\nWZAAWZAAWZAAWZAAWZAAWZAAWZAAWZAAWZAAWZAAWZAXUlIXUlIXUlIXUlIXUlIXUlIXUlIXU1MX\nUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIX\nUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXU1MXU1MYVFQ/j1c/j1c/j1c/\nj1c/j1c/j1c/j1c/j1c/j1c/j1c/j1c/j1c/j1c/j1cXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIX\nUlIXUlIXUlIAWZAXUlI/j1f////4sBazAAAAU3RSTlMAiCJmdxEzzO67RJndqlWImbtEIhFpdaTO\n4WZ3p9bf+vv1l6ruzMTN8vfam3Pj7Nm/M91Vx7aCj1sgZrszRBEiiMx3me5V3ap6tFDvn4CE+PTn\nyAbOICAAAAABYktHRACIBR1IAAAACXBIWXMAAABIAAAASABGyWs+AAAAB3RJTUUH4AYHEgM3RDX9\n6QAAHE9JREFUeNrtnQl74khihoUxtsFui2snWejtTQbYyexkZxs8ucCAMJjeJLvJZiX+/19JXTrR\nUSV0mu99ZtoyKpWE+VyHoF5rGgAAAAAAAAAAAAAAAAAAAAAAgJxpMG7YdrPRuG15t5p8b7PsiwRX\nicm507TWPd148G61+c522RcJrhLT7HQ6j+ajRoL4eNNqmE+erbtOh+6/K/siwVVimuSfDsnmHU0l\nzWXT3bL3A1ACpkkGlPdmR7s1G/T7ptlwtzRkE5QHH1GSFDZ4IjvmJ3dLQzZBebDx5hOZCzXpmFOj\nzae7pSGboDxY9hqkT78xH1pkik5i6m5pyCYoD5HNZ/rP0+3tPe3I3S1kE5QHy94t68UbdOT52PJt\nIZugErQ6nZvgFgAAAAAAAABcBbpe9hUAEI7eLfsKAAhH75V9BQCEg2yCqoJsgqqCbIKq0kc2QUVB\nNkFVQTZBVelbZV8BAOEgm6CqIJugqiCboKoMkE1QVZBNAABQoOkIDwGoFExuaHbKvgwAgjxTX0IT\nvk1QPbgCqdEo+zoACHJjmvePtxhvggpy9/hEbTNlXwYAYbSaDyZaTlA1mu1njcq0MVEHVaNjPjQ7\njYeHsq8DgDNIf26aT/i7GKCCtPAXWwAAAAAAQE4M+7/67u/+/tc6ZdRnDMq+JnCtDEn8xvrnz7/5\n8uW3FuMfrH/8ftJjTC2HGX9E5/DY9su+ePDB4GnU9d7vfvgnmrrf0kz++OX3nz//9M+ff231xmct\npUiiyCUP6cyNrcUfmfDdYzS3QB4njaIl/PHLH37+Qjf++MNX1nezUnN9YU1GQ/WqCSOey+5Zc7vw\nNbcvvLTiOcCHIpjG6Q8//OaXX778/o+8mevSmMy9B7x0UwQzgTlP4tjb3PbOmtuer7mdX35aUDXO\n0kg2vv/8+V8+f/7h65R/zwIQ1te+dKfT7kuRrZlobl98ze3irLnt6t5ZGZrb2hCWRtoA/eq7f/03\n+nKLGYzbaYfXwoNZ9pPxMPA1t5Oz5jZsVobmtmyi0kjbFDbmE1OUsE47vMLRxFpUKpgJ+Jrb81nZ\n1Dcrw02wXIlLo8aamDHdmdRph9dNg6l/mBZn4JuV4SZYDiSkkTKnDYd0px3OYNz7SMFMIOEmmL+5\nxU0wF4k0UlJ12uEMxjNrNr6WYMaT6iZY2Red889DIo3ahZ12OHMWTLQKEsxDmtuPdxNMPo38Z3J5\npx0Ovb/eQzAvR+0mWMXec1BLIyXDTjucVG/8AGX87zlU4iaYehq1XDrtcPJ44wcoE3YTzNPcTsPe\nc7gkD2ppdMil0466xKLf+AHKyN4EU0qKdBqDh2XdaUfTr9H9dXCO9yaYTDYblDvvhhRMNXTT6Cge\nlopnJiuk/xZwMlAdmAuQmq2cDcnDGnQVeEPxsFQ0WfVPZquIk4HqYJqdzjOVszgbkoc9tEQ2VQ5L\nRct8ovatT1oRJwPVwTQ1LmdxNuQOezIfRTZVDkvHJ5LGW7OpFXIyUBnoy33zwPpLsSF3WLtB2jCR\nTfnD0tE0b0k+W1ohJwOVIe14s916aBc03iSdelujXTrGm9cFeakbjaZ3Q+6wNmnNHlk2VQ5LySez\naapfI6g5bAjn25A7rM18/w3Fw1LSNO9ZR17IyUBVuCCbncKy2TJZl45sfhQ6Un8m4oJsao9FZZN0\n6s/q1wgqi1w2AQAAAAAAKIDhv1f9c5HDvq5XZj0AKI7B7OdZqg8mF/M3yufj7syafv06tRbd8Ude\nH3g16Lpsyfm0+x/daZqPCFt5rygbvOg9y+rpo4Hvu/otBARepLP5Mu2Sf7vTFB8rt/Jsxfr6JKyl\n5K1oT8fyjPoim82RNfJ9VSGvbM5H8fkjo8/JwlpM0MPXE8ls6k4kR5b0KMAmh2wOWb89k+i3eQ8/\n66KHrx1y2fSOM+esc1ch42z2x6w1VFmFx1pYMgR9gUuhRshkc9hbeBud+aKnNojrZZbN+UhPnzEn\n0xiC1gOJbA5ns2H8Awlkkk0yeOxNL+6b6ViA1gJ9Vw1IzmZIMxloSJO4OJv9cXdhTTNr8Ujr20MP\nX30Ssxk+vFS60dlTnj25DPLKEc97Dz18dUnKZtS0XFe4l5Qym0P71mVu/S8fJ+BtpIqSkM3o25kK\nNzpTZNO+dV5Aq4a3kapKfDbj3gZ6kb6XpJbNgX3rssjRIN5GqiBx2RzGjyrJSFTulexKZ7PUN3Lw\nNlLFiMtmL+FjR4NZ7+JzeBhXoeUSrfa41IsAjLjczJNiMsx0iNavzIhvPkLTWU2azBLI9ANk8zZM\n3pJsL/RrEamAMKRoQEz4rKlaFLPjrtFwrvv2zv5BwJhYMdrc2tLWWvf060PIK5NsLwxoasy7sKJB\nMeF9ecaYR3qJznU/ih9EBwabanHX6VBP4B15bR5vWg0qDwySbC/0aRE7j+TVDinqFxN27lkWSjEU\nth5EAMX5mYWuXd71gEiYf+COp7JtnsuFku2Ffi1ih2XzvKhfTNhQtihmBmnB+bNl52/yhlPd6gjy\nh70it7wlaYb0aMn2Qo8WkQzY7sWrHCzqERO2222aiJIMheSX5BPr1MWvEjNKtCOuGpSJaMZYKDtc\nM+Tfn2gvPNcihhUNiAnbZRmxW2Soy38H2TO/8WYT481q4e3ZbkPbzSR7oUeLSEaST2wuFFLUFROy\nM92WZChsko6Ad+p2u0nn6DybMCZWC9F6kAmP1noyzyfqyfZCv97LGUkG8YkJn0kTWo5p6543j8/i\nQj6ZtzSX7airBiXCXxHSktze3od06RL2wmA2n8OLumJCMt58iCqVNzf07hXvJ+iF3JNfygZpOh9Y\na1/C9YAYxCvSYPf6QuYByfZCfzZv7Xn6GY6YkPDUKMlQSAcT9PfkQVzIpzt+b7es6wGM5TJub6vT\nudo7e3fX+9QrwmpV9hUAAAAAAOREX+5P0ILySHYTytkL5UrJG+3yhMlsmCmx9I85gxiS3YRy9sK6\nZHPwos+s6YSv65wzC0i30FVLQJpkj5Gc6agO2RyMuudRHDBR3QQSkOpxLdkkTeTUmkXoGYZiiTAG\noJXiGrLJ7AmJQ0tmcZhBUlMdPng2+bRHukWcj3mvjw6+CiQ7tuQsXBXMpm/ao3DYiB+GDr5sPmg2\nQ6c98lCJEhuA4g5TiXzAbMZOexTo83pwh6kskj1GcqajimRTbtojz5y3v7jDVAYfJ5uK0x55xLgV\nd5iK5mNkM+W0RwExAMVbnAVS/2xeOO1RgA9k8RZnUSS7CeXsheVkM6tpjzz8NwFvcRZBclrk8lRC\nNofZTnsUTsxHtujeQSSlzk76pX+k6sPyuuZsQvdK2Qt9bF8LuGghKQw6CouVFPp/NlAjZs/qxFmH\n7pWyF/ow4tfLrU9ZXLSQFAYdhcVKY2IFOyAbYvIiZS/0UUQ2bUlh0FFYrKTQ97OBGjEf7LwsDWMb\n2CVnL/SSkM3tjhTZvBlrcra3tBdsSwqDjsJiJYX+nw3UiLkgsrk/GPvTu3+XnL3QS0I2taWmnVbk\nRKu9cTBSXrAtKQw6CouVFHp+NlAj5gXP5uuJzGKMo3+XnL3QS1I2CSeSz91eqmgojqQw6CjEePPD\nwbNpkN5W257883VJe6EHmWySedfKSJ9NR1IYdBQWKyn0/GygRswLkU2WlMB8XdJe6KGAbDqSwqCj\nsFjZlv9nA3KBZ/ONduevZ+2md6Mh4SXMP5uupDDoKEQ2Pxw8m1s6DPwWiIusvdAl/2y6ksKgoxDZ\n/HCIefrytDseL35Xp4A+PQQ4Cj842/X68koAAAAAANIx+K7Mz58PR9+N8AHOspH71HDRDHXrF0sv\nKR10ddLilwX9xD3yWSZyjsOCGU9nfa3fmxb/Ad85/cz7hK0ZGowmUxi+ykTOh1Qo/cV0xDZGi8Wo\nwPOy5Uk931oh8pBlYflQSVQumwPSXDpdqT6V845cfla6iG0W2kj23aYUFErFsjnsWl1vCsjAc5J3\nKoZsgNmNGVyKEpgeFUu1shnSTg4muU6KWKsosyh9yFtWTI+Ko6A+U4qX8PFlbpMiNsBUGU1ielQo\n1clm3zvQ9JPDpIgMMKcRA8x4MD0qjKpkc0AGmjHdZaaTIjJ8vKx7xvSoEOR8SHkzJNmbJ5TIaFLU\n59OaS+vC9Ch/KpFN0me/JBbKYFI0H/ey9NFhepQvFcgmGWiOZQumv9qc5jGYHuVH6dlUag5TToqG\nL7k2cJge5YOc4zA3yDCypzT0U58U9QsZGGJ6lD0l/52/6UK1NyRpVrjkARtgFpMYPj0qux8CWZGm\nhx6oxFkvtqcdjjDyrDnMZnjT6Hi3kmHGQ/7FsTNGckPFByq1Z/WUIEesN2xxb4erXeytZNquXM6x\nM0bCjEoqtWf1lCCrqTem+dCys2lvJePLprAzRiKyKV97Vk8JcsSLWNJlwe9LR4BokP/XywIvwHwi\nseLZdLaS8WVT43bGSHg2FWrP6ilBjngRb9TgdVw6AkSqWcjQeZCM2W6Q1oVl09lKxpdNYWeMhGdT\nofasnhLkiBexPW2pJMkRIJaQzdZDW2TT3krmbLwZd5TIpnztWT0ljDcvY/emGXtXgFhCNqmWi2fT\n3opHGA9t8aFjZ4xEZFOu9iyfEuSIl0E69eO7K0AsI5tUatjwbsUjjIe2+NCxM0ZiZ1Oq9iyfEiRf\nl7E9vR08AsRSstlxstmRSI8wHtriQ8fOGImTTZnas3xKyOaFfKNadkeASJrOzbHobGp2ny624hHG\nQ1t86NgZI3GyKVN7lk8J2byQJZ0GOQLE/WG1K7TdTIMwHkJ8+NFZ7tgXW4D4ut5eUhsAWbHZHFP/\nGSAA8mR9Wm0urwUAUB/m4z9h+dDHINXC3n4v5xOkhKkYZv85xfK2D0EvzWeLlbJZkIiOLsmwl7Qx\n71cGy4xBqaRaSaeUzfyXSAzZUqHAUkuST7ZKCevbakvds8mWCEWteI/dCapOnbM5YEvXEqJH8slW\n02EVUe2oazbVhpTewSioC6lWIKtkM4clzvMxEzEoTnX6OvN/YAJfG+qWTX6bKG3CLjsaFEudsplN\ny5eu1QXFoyvEzEEpm2lOEHLKTEeMuAFaB2qQzZxm2lKzfFAiFc9mzncocQO0ylQ4mwW9sxP6rhKo\nAKO8s5nqBIUPCHEDtIKoxCzVQWlO0C3lRg+/wYR4gjhGpd2AnBdkCgWJrMWH79f5Va1CmZZC55Qw\nJJbPcsuWHjNO+VWtQpmWQueUMNaUz2rtBijjdtNbtQplWgqdU8KQWDyGtjSYRZFrFZfH/ZoE6M14\nY/uc3eTf7bls0di8GWuy703zaBnfSPzWhvEaLOyrmpRee88eR5mWQueUMCQWz2lvGNQlIrSKPEAH\n/tjJ2W0cjdXuXOJwWpGDVntawtEy7ndL7Y1+E8yct+rVkXxZumePpUxLoXNKGBKL52SQ1Kw0R6vI\nOl7+GMsm26TuRS1EfkPzt9tTZ5OrZTSoM4d8szwES3uqXtHS39wzxVKmpRDjzRKhA8D1ytUq2oPC\ntcgm23yj8QmR39C9K4PucrWMa9pCrgmnYK/urVp7fd+tPN/GUaal0DklDInFY2fT1iqGZtNIzqaj\nZSQPGYcVJSabBhkJrBSyWZql0DklTF/FI9LhaBXD203aKsZm09Uykofe6Tebsxm5W/X7Ycvrk85m\nWZZCZLNERDocreLqPSSbWypbPMRl06tlJEWXfPDpx616SfZtVPr00iyFyGaJ2OmwtYrfjsvzbJK9\nq+O3uGw6x7MbmMvDbnc4u4nkVr3ZHVfH/WEpl01w7Qit4ibMqkgeXG/pvDr5ePuAkDcnvVXT/fA3\ngsuhN4W2xyL/0BEAkiwPp8Rb5ABcK/P/KuvMw/74TzAogUjm//1jt/izDvv6ZGFNe3+e0Q/AI6Ag\nhPm0S/4r8ox2LPUX/sHi/riLgIJzWC4LC2cwli4IKAgwnzIPyHzWzftM0bF0EQHtwkIHtJElNMfD\n2Sy/NUMysXTpj+gizBkCet040cwtnGqxdJkjoNeNJ5o5hDNtLF0Q0KvFF81Mwzl40XsLa3FBLF14\nQBcTvQ9T4tUQiGZG4aSxnGYepXxqBRXlLJoXhzPvACGgV0JINC8IZ3Gxcc8EI8gHRZ+G3+PuzlTv\nfZfRmvHx7CXTLFBZutO58p5zyu1kL78PACpIXADlwlmVsR8C+sHQY+PXnSbFbV6JWLrYAcVb8fVn\nGP8iJt7pHowrE0vPk+rraDprDNUJ3t5pWpOJBYPGAkd56NkKcEOPidxb2rNyrxu+xLrC/S6PWptv\ntIN7hfLQsxWgQ4+J3Fvas3KvG/6auiJ8gp27Todu3gX3CuWhZyuAyGbE3tKelXvd8CXWFeYpaJKG\nM1RZ4CgPPVsBeDaj9pb1rNzrhi+xtrDXjuUrNJu28tCzFYBnM2pvWc/KvW74EmsLC+RNdDaF8tCz\nFUBkM2JvWc/KvW6MN2tLUrsplIeerQAimxF7y3pW7nXDl1hbWCA/mbdaVDa58tCzFcDOZvjesp6V\ne93wftUW02y37+msNjKbHSebndhsdiqWzQ6yWXPYcOzTHd8832srDz1bAZxsatXq0+3rRjYBAAAA\nAAAA18W8/5evX/+ngp/dA0r0+pfs1jSr7CfgYd4f65Pe1LL+1/rrz5Zl/fV3Xf0FHzKuLR8hmwM7\nk9PeRP/LT3+YdulVv3z/R+v/viws6m3ASsw6UudsDvojvdtb8EyO+7SFfJlYs5HTmQ9G3an1t5/+\nTFdiWrOeXsXP6INI6pjNkEzyx/XFtBvsw+fjnjXtjgb9F3IM6ejJISM4lWpBnbIZlUmOv8n079Jn\n1kx/0ehKopE+mdEaunofQ9FqU4dsOpm0wjLJi5AmU4/LGuvee+O5XeOY9fML2s9jKFpRqpxNTybp\ndCb6UkY9qzdKrs/u3t0H+jpdWk+HoiMMRStHFbMpnUleWp9O5Zf8ut27CxmKTsRQ9AVD0epQpWyq\nZZIj2WT6TuPr3h3oULTHhqI6hqKVoArZHJKGS1fMJGOuTxfpLAln3bsDhqKVocxs8kzO1DPJjx7N\nrMmL2jE+wrp3BzIU7bKh6ARD0bIoI5uXZZIz76ZtMr1EdO8u9JYTG4p2MRQtnCKzmUUmeUWXNple\nort3z4WP2XUvMBQtkiKy6WZyRl7ci9ufPmkyx9l2s7Hdu8Ogr7vvfmIomjt5Z3PkyWQmeRosrG4e\nvSvv3mUSN3/hQ9HeBOPQWtPPKpMOGTeZXuZj+bL0llNuFwLiWL/G795oa22zjilhOxQjJIopIBXd\ntuyq89AXNhs3ni9RT0s7kz/SZwgnWGEYByN2/2mtnbT1KaaE7VCMkCgq07qntTzcafnpZITZK1bw\nFSJ/ZBcGKVhhrIz4/SSb66RscoeiFi5RVKZtPt60bs2nVn76QrlsBuWPz+YnKuS79HcPBFkaRljH\nvDyulmznVtPe38gDb4FSJJsGy+bGIJ3/2jDOhgAeh2IWHoMb84l+eTSb+ekLpbJ5Jn+8ZS14ozL6\niI/C6mgYh+X54yyb+4OxP71rm8O79n7Y+AvYffpmtyfBpQWDtXhcYFlks8n78Gca9rz0hVLZPJM/\n3pjm/eMtxptZsyLNnfEtbIehvZ7oziNpOA/bQ7BxFdlk0dzSgstDoITHoZhFNhs8m0KWXOJ481z+\nePf4xEfWIFte33erkIdJNo2dRnNHGsxv5xMjkc0d+Uoa2TXhFOjVM243WYPZem7mpS+kk3MSSvEl\nuly4/LHVhL07a4zTar+KyiZ7nIXvrMO2s7mn7apxWFHCsskdillks/XwcEMazyeamzw0XDSQ5H/x\nJbrcufyx2X7WYO/OHNJbayKDAUg230jsSMe+IQNOIzjcdMebR0N7pwXP7nV6HIqZhInk8pa0TvcZ\nVXdefZvUfie+RJc7lz92zIdmp/HwkP01XTVLkqpNVJ++pa3ltxXb/hYckzr3N99P2w2dTdEG1IfH\noZhNmBq0wifaEOeRTXb7tGF/iSZE/kjCTC4Mf8ooWza74+q4D5uo0/uby9PueHwl7edG25K5ug/3\n3jtJ7/Kw2x1eZU54Ea1Oh3Truf1xgbvOjeeL4oUhmdmzpm8+biN2btdruVo2tBoAAAAAAAX6Y3yq\nF2SCnu2HHEeL6d+sxA88p6avtPxJrTSoGllmc0iX/A61QXe6UFySLguyeU1kl81B15qJSA6p/SiP\nj78PldKmVhpUjayy+dKzJt6ufDSzujmseFRLG7JZazLJ5pAMM88Wo/e7Vi+rdcAOyOYVkUE2B3rE\nml+6Y5Rt124ptcVqpUHFuDib826MjGs4Xig45CSwlG4BqJUGFePCbI56SavRk0uogGxeEZdkU7JV\njG1ZFUE2r4j02VQYTUaOSJWZKqVNrTSoGGmzqTgLD53Jp0DtLaf83qACBZAum2nuXgbvgKYC2bwi\nUmQz9bs+nneO0qJ2xzT7+6ugQJSzedG75eId9/T0lC5XrTSoGKrZ7F76KSMy8FSwwQVBNkEkL5dP\naGAWBpnSagodguNGLL4OiUVP6/yX7IGKcUe1LeZ9y+NGLLaO5ZZ7IuJJUj+CD0jbfGy1HrmIS7gR\ni61jtZbJZpL6EdSICIdikDtmMGy1G343ohIp6+Aix+VxvybZfDOo0NF2NhpBtaNH/eiYH0XZDTkU\n66DrRJRDMciz69LwOr6USFeHEDnybB4M1mnbzsbTfue/do/60TY/irKbw8rY7cr6MYMURDoUAzQC\nubpJkc1UdTgiR9anGyR+K9fZSL8PPB9X/cjNj3ZZqjjZrrbJJwTVIcKhGKDD+99O54J2M1UdjsjR\nHm+uV66z8Xz86VU/MvOjXXZ72ks6UEBFiHQoBrhhwjkhftUcN6ISqepwRI6ebDrOxvBs2kcw86NT\ndr0/nPYl/7SBAtEOxSAN8755+8Rl7q4bUY00dTgiR082HWdjaDbtI7j50S67pdZ7mZE1qAjRDsUz\nqMHwgQ4YvW5ERVLU4Yoc351sOs7G0GzaR3Dzo12WyvY2R2SzPkQ7FM9pdToX6wtT1CFEjto3EiyR\nTcfZGJpNcYRtfhRlN7vD6rDCTaQ6EetQrARC5LjxXmW8s9GvfrTLrvF2JgAAAABAHchA4wK9G8gF\nZBNUlQxyBfUgyIUscoVsgjxANkFVySSbWMwGciCTbEK3AXIA2QRVBdkEVSWLbEI9CPIgi2xC7wby\nANkEVSWTbEI9CHIgk2xC7wZyANkEAIBQ4tbjbNZyj8k4CWWqAcBLnLKN+luSH1tuJbxvMlUD4OPy\nbK7WyCbIA1snaJD/11Q/oC0Ntox9abyRABlefaB4zA8VvzlOQu4pdCqzfYNCsGjXHVYNAEFsnSDN\nCpXSnPb8+93RWB1O3C5oqwbFY35YNkUlwlNoV2b7Bm3Boqg7tBoAggidoJtN/v2SCpS+ndi3tj7Q\nfiwA7dP5QY6nUFRm+wZtwSIvFlENAAFsvYuTTaFwo+6k9xP71tYH2o8FEONNepBtHRSVub5BLljk\nxSKqASBARDb3hsYmLPRbWx9oPxbAk03bOmhXJnyDtmCRF4uoBoAAEu2mrQ9MbDcdT6HdbnLfoCNY\nRLsJVHCyudY2Rzebr2RKs9nxbNr6QPuxAKt3+yDHUygqE75BR7DIi0VUA0AAO5v7w2rnaTdpP3ww\neDYd1aB4LMC349JxEgpPoahM+AYdwaLdJodWA0AUrwED4tajCrT1gdswfaBXSmhbB+3KhG8wIFjc\nwkIIAAAAAAAAAEXx/zU031l+TU7KAAAAJXRFWHRkYXRlOmNyZWF0ZQAyMDE2LTA2LTA3VDE4OjAz\nOjU1KzA5OjAwI0YReAAAACV0RVh0ZGF0ZTptb2RpZnkAMjAxNi0wNi0wN1QxODowMzo1NSswOTow\nMFIbqcQAAAAjdEVYdHBzOkhpUmVzQm91bmRpbmdCb3gANjY3eDMzOC0zMzMtMTY4ghJYLQAAABx0\nRVh0cHM6TGV2ZWwAQWRvYmUtMy4wIEVQU0YtMy4wCptwu+MAAAAidEVYdHBzOlNwb3RDb2xvci0w\nAGZvbnQgSGVsdmV0aWNhLUJvbGS1Rr+1AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAdwAAAD1CAMAAADNqbSNAAAABGdBTUEAALGPC/xhBQAAACBjSFJN\nAAB6JgAAgIQAAPoAAACA6AAAdTAAAOpgAAA6mAAAF3CculE8AAAA/FBMVEX///8AWZAAWZAAWZAA\nWZAAWZAAWZAAWZAAWZAAWZAAWZAAWZAAWZAAWZAAWZAXUlIXUlIXUlIXUlIXUlIXUlIXU1MXU1MX\nUlIXUlIXUlIXUlIXUlIXUlIXU1MXUlIXU1MXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIX\nUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIXUlIX\nUlIXUlI/j1c/j1c/j1c/j1c/j1c/j1c/j1c/j1c/j1c/j1c/j1c/j1c/j1c/j1cXU1MXUlIXUlIA\nWZAXUlI/j1f///+ADfMhAAAAUHRSTlMAiCJmdxEzzO67RJndqlWImbtEIhFcdZvK5eHDp2t3j83a\n3/f5/fzPVWby7PrvwFCEzDPu47/nx9Hd4sSqjp9EEYhmIjO73ZnuVarMd1vx1k5mVcYAAAABYktH\nRACIBR1IAAAACXBIWXMAAABIAAAASABGyWs+AAAAB3RJTUUH4AYHEgM3RDX96QAAFI1JREFUeNrt\nnYl24sgVhoUxtsFus6YnmfQwk04mgWwTIJkeEhL2xYZMBO//MKlNKkmUSqXSLu53TjcylKW69asW\nYf26hgEAAAAAAAAAAAAAAAAAAAAoUiHcke1qpXJfc25V6afVrCsJ6GFSHgyj9og3npxbdfphPetK\nAnqYZqPReDafDaTk812tYr44th4aDfz5Q9aVBPQwTfRfA4n7gGXFwlb5lvU5UExME02qj2bDuDcr\n+OeqWeFbBohbaOisimSsUEkb5ge+ZYC4hYbMuS9oQVXF866BOzDfMkDcQkPEq6Bh+c58Qhc/NaQz\n3zJA3ELDxH3F/73c3z/isZhvgbiFhoh3TwbiCp59n2uuLRC3LNQajTvvFgAAAAAAABCWZjPrGgCJ\n0WxlXQMgMZrtrGsAJAaIW2JA3BID4paYDohbXkDcEgPilpjOOesaAIkB4pYYELfEgLglpgvilhgQ\nFwAKR9X2cwJlg3g3zUbW1QAS4BXfiF4FP24pofagSiXregAJcGeaj8/3MOeWk4fnF2wkyboaQELU\nqk8m9N0SUq2/Gvh5CbBcLiEN86naqDw9ZV0PIAnQkGyaL/D0mnJSgwcTAQAAAEDi9Dq/+PjVL3/1\n9a8/fdPpdHpZVweIRg+J2G9+++m733z+7Znwu++///35+zPjD+12u4kYgNiFAMk0RHIh1f5I9PvT\nn9F/f/n810+fvvnhb6Nz64fzuNOa/P2rb5v/+A598uPnL19++q49omKPQOycweWcEoWmnz//8/OP\naOOP/0JKDTsdWqzbnEybXWM4Rdu94eg8G5DfRb+IlUWifvvxY2fQpHvyiI120ulmHeeNMO4QFWaW\nnKP2v/766cuX9ne4LyKdWs2+t+cN2+c2VtOYMWP9uEW0pvTQ/lp4Z5P2DP3umL3Z8Yo9beOdg9jx\nwuUc2a3cbH77749f/Qe1/YQIPGs2fZq825xOLCEnA+tdu/s6CqIxYIZ3N0UaDj07A7Fjo9vBQybq\nT+22Q07SjGM8DNNeO8VvDlhX86EzO4+G1g+DifOjcdPRfZ3vo2XYrE1OGbx7n+m3Q6uIxW6D2HK8\nck6onGiE7dCPB7jrjugn5H2Fnfb600nLoX1z5imAx+uh32/bUzIWOfB4ILYTeqVCWmPikbPHixC9\nrcm0GWoZO26dp0NX+em1kGilNWlKmx5PyU0yUjim5GBuTmyPnGcWrTdYUsoxmQ402gLPqS1Pbxuf\nhaeGtPty8JTcwpWaCKZkpdjLJrb3SsVHTsyY9BA+mQ6VO8k1XbwavlKyP/IrjtdcqkejUzJZd0mm\nZJWWKZ7YY4+c6GpxRr8ZELZeF4fonkwjf4GAuqJnIUwZ9f1/Z4AXXqGOTKbktuqUrLA7r9h4npqx\niUr/PI+I4EpFJiemh0de92Qa17nqP4n2zmP5L7pXX4rQKZl9FaI+JQeSmdhsaeu58CTjSUCFh57J\nNO5Kog7oO3+Sr6eCfjtk93W2yZB/FRJ+Sg7EEntmr1hiE9vnSiVQTsyYXsZMrZF3GH0ME+O98vEw\nU3juI9lFpOp1+ZSM112JfUk9ZqvTKGKLLjzVK9yiXTuuyVROM6DbTQZKu+mgK6gY+t2YT8kKS/E4\njicUW3qihpXT+9spLvyCBgTlivT6qiVVajVoJjRQyWFiC49dq1r5KflWIJZFkmS3fCVvPTBvjjMf\nZlo4j33/YBiv5Pj4f1KZ63vlSPm7SsPwKxCOwONlxAM2XpiPNedWILZFkibiesTvPZMcmM58mOnh\nPvYzS/H2YtZ4pjA35K0G/s+nQDgCj5cRdfO5VrPSV7KtILhFkiTiwin0jNoTi4nnw0wN17Ffn8xG\nDedovMO1ZO94BxITJ5Ri4goLhKxA0PGygaaqrNUrjq1AuEXSTsSFT16a9dLOh5ke7mPjNG8fUPPe\n4/Sb5J1rY4n5ggoxcY0YnCdBx8uGV3sIeVUfTLhF0jTr9ToREoX3gSVWY/kw08NxbAOfWHUk8D16\nt0bfuXsyvXONWUdnpC2uoEBIgo6XDRVb0kqImcK2SLKU0jU0MD3ayUzTnnWcxzbwqVdHb9UNln1T\nPOfWa0/1+ObcwONlAxs/Gw3Hllo4xCLJsqzd4xm4QsdGOx9majiPbdCei7pRlSVFFiarJ537mYob\nSzb7gONlA01ViduDbwW3pm2RJK2J11d0/YwTJfJpOC08x/6AzjUk3SMZG31y+OEoH017zo1OwPEy\nomI+Vu9f8FnHt4LgFkky5z6Zr3fkcqhKR2qD5cNMCs8J6Dp2vf5IM6ua0uybeA+NOMUNOF7yiHsl\nTlX5VHFvBWFbJEmXeamQkRlH+OTKh5lOHK5jIz6QGeEDPb0k4hrPMYobcLzk8Rlya41GzbsVRLYW\nyRo8hKi03D0mOOYD2VLLx/c/AFB4esNU/pKZdzofM/mbXzARslb2mpOvv5400/PLBT1KWf1RyzHm\n6uz2p+cv52k/K9ugLGjtrJVIWnwL+HCanrwxiqsbtRd2U1avf30TdQ4aRTM9Wrc1sRw66ckbo7ix\nZB9y3U7p8hWmSOzidlvntuM8HY4mqYSVL3GvfAwCX2HGjaIR5tgtLabTPreSlzdH4o7FN09n0H1j\nFRfrOBa/nXRUeRFX1kV7fm6ILBolZO47iYbJyxufuFEy/nWCemewrzCtRgkVJppcZfp1WskuGXMg\nbg9d+CjEqOgrTLpRQoSpsCzuXk/HKcWh8rlW1E7whY/iBW1q3VcqrmKL9BSveJKUN0ZxNVJLhfaR\nEVtT4heJ0cUl31go1jM5ebMUlwy0YZXS9BXG1igqYbIvo0LENBklMeNkJm6EMTaKrzByowSH6fgy\nSpmwp0P0OFQ+DxO1IxZ84RMhmIS7ryySoKyVuoNsEvLGJ656rs5YvpZAlxGqC7F4G0UeZlN//sTy\nxrtcjE9c1aJddOETyzcS+BIqvr9EaQbtJZqju/h/7Y2xvyXlSL9mjlnIStzhe6y55VGD1FJicveo\nw1rqU+zhqrjgjr87eoM5+tB2h0YgdaPnhbB0vLNau0s0qJvPsjyGJ72UmNw96rCW+hWrXBW/jq5h\n4ltVa/h/yx0agdSNnkTX1WXD39nOvQHWnZbH0KSYEpO7R7m11KcYtlm6i4uMlw1yVjaouNQdGqF6\nqRs9aae9IEHxxnxlrHZ7t7pUXNvyGJoUU2Jy96jU02LZLD3FBcZLFLt5b1SeiLgGszXok7bRk/bc\nwwJtoY3l1k9c2/IYmhRTYnL3KLeWCotRm6WzuNh4iWKvfzDqHyxxlZxU/qRt9Lzsttvd5c2wxfUZ\nlm3LY3jSS4nJpzLbWior5i0umnPrlRfjqWKJexdN3LSNnpc9Wi0vD/NAcS3Lo15U6aTE5O5R21oq\nLkZtls7iYuMliv3VfCUDeBw9N22jJ51z9+/B4jLLY2hSTInJZ1rbWupb7Lq4ABQ76m1EWe4OjUDK\nRk8qLhY1UNyGnrgppsTk7lHLWupfzFPcr+51dE4/UnEtd2gEUjZ6kmF5dViRFfNih8V9uw7QYXkM\nT/wpMVcr8fvcPWpZS/2LeYqLS+LYn8ns7HSHRiBBo6egUch3GAfcffeH7RH33PfdKvyepcTu99xu\n42+bwiNvlM2cfDe1mK/V9pZlIFlXAEiM01v0fQAAEEjnG0iZZ9P9JnWrSQBRbnUbTic/pXh3dhIW\nzig3r7vpts4/JXHrURT0b62mt8KmYyJinJWPpCxu4IP1FffTxrey95rTaYp25kDamveG8LucU5T3\nrDzMKIsb4SYWR2Nwo8ZwmupYJkdL3N7QdYamJm8uxcVJFZzddZDmWCZHQ1zBfY8pyZtDcbuCm0A7\ns/MsFw/RCC2uzy2tqcibO3HxfcGDEO+nTMgng0juVk5BXvWlvXJYUcSlqygx3UTu2g9JKHFRjWWr\na3S+JitvrsQNsLvmYekcQlwFb0KyDs8cietdRYnJeums/HwBRd0SlVd9gaAurk5l1cfcbJfOiuKG\n0CxBefMhbrjVUpZLZyVxUQXD2NgSkzcP4spWUf7Nkc3SWUFcjWVwQvJmL27QKsqnOTJaOg+DxNW8\nwklE3lb84k5DVFJtFSX+1UyWzkF/FtFfEODrppgrq760Vy4Z4gwcROt+aOmcg+813BFFON16eQsm\nGt2o4QzSXTfju13nG9EntrdTx5UYs6dRbkWNaa/4R/GBPNFoPKo/UmNqczGM5WEp+sT2duo4JGL0\nNGLj6WWu//uS2OdXP4oP5I3mUWXvLiI1pjYomK1QW+7t1HElxuhp3M4zF9cdTUMjnWGkxtRmaax2\nW+HtzLa3U8uVGJunkXgTL/PT8oR/mi+XG1rrpc892KcNvYt7s7RLX7FAe1sYfK+r5XIuE9cTjUZS\ntGiNqcvFX1zL26nlSozN00jFPSzJ5HE6LPcX7KHYL30mE+N9bxiHA9L/3S7tZXHYLo9Hw97rdode\nVzJxHdFIDKQSojWmLhf/YdnydmpNE/F5GsmwjKq42hpr/JyA1cH+WcRqZ2x2h41xXNmlvcxR0Ovt\n2t7LdkPOBYm4nmjqobWJ1pi6yMRl3k49V2JsnkZrzp1j+zh+iAvSjP0sYnFZn/bvp/VlbZf2sr5Q\nFzrfy+btuJWJ64jG8DeQSojYmJpIxaXeTj1vU2yeRoe4y8MWIxUXddn30+l9deSlr5jvD5c9F3d5\n2e63cnFd0fgZSCVEbExN5OI29OsTm6fRIe7bzsCOJ0Mq7nJ/2GwO+yUv7WWN9J6zSRbv9bAmFleZ\nuDwaiYFUQsTG1EQuruVy1CEuTyM2njIZFtiQutzJxd3g5dThMOelvZx2C2OxW/HBHp0DAcMyj0Zi\nIJUQtTH18Bc3L7xzGdDy6HhEiyWpuMbhHf0SXkdZpb0sjoftYbuwT5njbrvbH1aXxC6oAT9cxtPF\nPMw3kb6l5+5vXHGxAthbAQAAopPec0wLQfe/ObGZWES4abs3+/nnWY48b1GJmtmzP/lfzv5cr+6a\n9DKejsbj0TTh9A4pEk3cbnvSR/rm6mzXuq8X06cPDm+e+1mHEBeRxO1P2ribIIlz1Hk1xe3ZQQwm\n7TydrBGIIC7ptpT+OT+dV0/cDj1PrcDKsa7SF7fvaA4DTVV5aQ8tcZvuXA7NhFI7pIyuuI5uy3Z0\nzsmzFTRuPu6OvF21Mxnl7CJAB01xXd2WkpfOG17cgWBF2JvlaR2hiZa4V92W7SsXg1lYcXst8fK4\nf27lYyjSR0dcQbeldNCFYtYBhX2swnjkV2f/T4pCeHF9ui2hl4POG07c/sS/f/Zak2Jf8oYW17fb\nUrLvvGHERTOr1EwzzNf3M2EJKa6s21J6s4y/4Qkh7ngatCbuFvrbyHDiBnRbykClUHKEcE2qzCE5\nmGi0CSNucLeloMEuw86rHFFL7WJnMGllF0xKTYEGMfUeWYgGGStOp70CD8zqhLiq76bbILbR0E5n\nKbYe2t5Gbm2UeBSz8TEmxkJ8M52V1LNK2y7wBvQqzWNaTSedqeHwgNjpLMU2CNvbyK2NEr9ENj7G\nxMCuFN+2ezbqzHoStBvmCkvLHObwXdrpLMXWQ9vbyK2NEo9iNj7GxPAVlyb1fGg08GbgAJWBuOxw\ndjpLH+uh5W30pOAS1zQbH2MkbK+o5Qa1XlfLk6+4hpXUU+kO9EzEJUZDO52lj/XQ8jZya6PEo5iN\njzESllfUcoNar8fdcnuQiEtTA+ZVXNecW/GdSi1vI7c2yubcTHyMkfB4R63XFbYXvUvEvcu1uGyd\nZ6ez9LMeMm8jtzZKPIrZ+Bgj4fGOWq84v5rxFr3n4iUyUpW9pBSTXSt7LvWrJ/M2cmujJKBsfIyR\n8HhHrdc9SSYuEZcm9QyMEyuK/rGXlGLyivvqW0/mbeTWxgBx0/cxRsLjHbVe5T3XTuoZGGfFrFef\nzAf2klJMbnHvrdWyCOpt5NbGAHHT9zFGwuMdtV43lzdjcZRc59KknoFx1h7J2oO9AOni9Y5ar8vL\n9rC8RN+/8dC4c7wAmWC5Qa3XtfixewAAAAAQAWULZ/wFC0yo5J5J5nORo2zhjL9ggQmV3FM/EWpU\nlL1C8RcsMKGyyOkmQo0OiKsDiFtiQNwSUxBxlZdy8RcsMmHEjfogFX1AXC1A3BJTEHGVsy/FXrDI\nhFlYKCdCjR0QVwsQt8SAuCWmGOIqWzjjL1hkwjytJjARamIoL+XiL1hkwlwShPoTEgCkiaoptHQE\nPrY/mQyj0Vmp5wVQNYWWDnlKDNSCec2ZsVWvl6optHTItdvOMxB3hY/4tiIJKnH3JPYJb85DkkOR\npbA0losTel2RtJaC7JfKptACw8JmDcKazk716Wk78iFuwesMo6eE5T4d0X+7lbHHlsU3kn6Ieihc\nFcTishSWxmWLSm732PAoyn6pbAotLixsq0H2u+X7YW2n+nTD2pWIe5Vh9LjSObw668va2FwWG2xZ\nJCm4DIG4ZFhmKSwN4lrd41LC7JfKptDCYoXNGmSDWhDn4xImDLXbFQ/LggyjCXM8Gcu9sTySWi8k\n4rIUlmTqwLnFllth9kt1U2hR4WGTBrFaS5i8zG5XNud6M4wmDBqXd2+shuhw/uKyFJYOcYXZL9VN\noUXFtnnSBpGLa7UrF9eVYTRh1pfTAac0NPAYIum5VgpLh7jC7JfqptCiwsK2GoR0zvlKLK7drlxc\nV4bRpHnHk/waz6TvVLrF7lrcNzuFpUNcYfbLEKbQgsLCthpkTZrsJBbXblfUgqIMo0mzIpPm6nLc\n7TZ4dbc9Xvfc993KSmHpENc3+2XJoWHbDbK6bHfHhU/CUKtdUQuKMowmXtUjeVnP6bE2oiyVJEGm\nIIVluFyZpYGFbTWI1XRC2IfOFKOptdoCjyhAOZlftous6wAAQK64BQvnzXILFs6b5Ra8QjcLiFti\nQNwSA+KWmJswgt0qIG6JAXFLzE14hW4VELfEgLglBsQtMTdh4bxVbsLCCQAAAAAAkABOk6fI5QkU\nGIfJU+jyBAoMN3kaQpcnUGCchhORyxMoMA5xhS5PoMA4xBW6PIEC4xBX6PIECoxD3Ft1ed4IN+ry\nBAAAAAAAADLk/4apDKVStkB0AAAAJXRFWHRkYXRlOmNyZWF0ZQAyMDE2LTA2LTA3VDE4OjAzOjU1\nKzA5OjAwI0YReAAAACV0RVh0ZGF0ZTptb2RpZnkAMjAxNi0wNi0wN1QxODowMzo1NSswOTowMFIb\nqcQAAAAjdEVYdHBzOkhpUmVzQm91bmRpbmdCb3gANDc2eDI0NS0yMzctMTIyb15zzwAAABx0RVh0\ncHM6TGV2ZWwAQWRvYmUtMy4wIEVQU0YtMy4wCptwu+MAAAAidEVYdHBzOlNwb3RDb2xvci0wAGZv\nbnQgSGVsdmV0aWNhLUJvbGS1Rr+1AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from IPython.display import Image, display\n",
    "from nltk import Tree\n",
    "from nltk.draw.util import CanvasFrame\n",
    "from nltk.draw import TreeWidget\n",
    "\n",
    "for idx, tree_str in enumerate(parsed_sents):\n",
    "    cf = CanvasFrame()\n",
    "    tree = Tree.fromstring(tree_str)\n",
    "    tc = TreeWidget(cf.canvas(), tree)\n",
    "    tc['node_font'] = 'arial 13 bold'\n",
    "    tc['leaf_font'] = 'arial 14'\n",
    "    tc['node_color'] = '#005990'\n",
    "    tc['leaf_color'] = '#3F8F57'\n",
    "    tc['line_color'] = '#175252'\n",
    "    cf.add_widget(tc, 10, 10)\n",
    "    cf.print_to_file('tmp.ps')\n",
    "    cf.destroy()\n",
    "    os.system('convert tmp.ps tmp.png')    # need install: libpng, ghostscript, imagemagic\n",
    "    display(Image(filename='tmp.png'))\n",
    "    os.remove('tmp.ps')\n",
    "    os.remove('tmp.png')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"http://kingofwallpapers.com/tree/tree-001.jpg\" width=300/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 의미역 결정(SRL)\n",
    "\n",
    "* Semantic Role Labeling\n",
    "    - 술어와 그 술어에 속하는 논항들 사이의 의미 관계를 결정하는 문제\n",
    "* 예제(CoNLL)\n",
    "![](img/slr.png)\n",
    "    - V: verb\n",
    "    - A0: acceptor \n",
    "    - A1: thing accepted \n",
    "    - A2: accepted-from \n",
    "    - A3: attribute \n",
    "    - AM-MOD: modal \n",
    "    - AM-NEG: negation\n",
    "* 참고: [CoNLL-2004 and CoNLL-2005 Shared Tasks](http://www.cs.upc.edu/~srlconll/)\n",
    "\n",
    "### 개체명 인식(NER) 및 단어 의미 중의성 해소(WSD)\n",
    "\n",
    "* 일반적으로 구문분석 전/후로 수행된다.\n",
    "* Named Entity Recognition\n",
    "    - 주로 PLO(Person, Location, Organization) 및 시간 표현을 인식하는 문제\n",
    "    - 통계적 방법을 사용하기도 하지만, 사전 및 간단한 규칙으로도 비교적 쓸만한 성능을 얻는다.\n",
    "* Word Sense Disambiguation\n",
    "    - '배'와 같은 여러 의미를 지니는 단어에 대해, 문맥 상에서 적절한 의미를 졀정하는 문제\n",
    "    - 기계 번역의 경우 target language의 대역어를 선정하는 문제와 연결되어 매우 중요\n",
    "\n",
    "\n",
    "2. 구문 분석을 통해 가능한 일\n",
    "----\n",
    "\n",
    "### 자연어 이해(NLU) & 대화 관리(DM)\n",
    "\n",
    "* Natural Language Understanding\n",
    "    - 사람의 발화나 글을 기계가 이해할 수 이는 구조화된 형태로 데이터베이스에 저장하는 것\n",
    "    - 반대 개념: Natural Language Generation\n",
    "\n",
    "<img src=\"img/nlu.png\" width=500/>\n",
    "\n",
    "* Dialogue Management\n",
    "    - 문맥과 흐름이 있는 사람과의 대화를 화자에 맞춰 관리하는 것\n",
    "\n",
    "<img src=\"img/dm.png\" width=500/>\n",
    "\n",
    "* 참고: [대화 시스템 서비스 동향 및 개발 방법 (DeView 2015)](http://www.slideshare.net/deview/222-52779117)\n",
    "\n",
    "### Question Answering\n",
    "\n",
    "* [Facebook bAbI Task](https://research.facebook.com/researchers/1543934539189348)\n",
    "\n",
    "* Example 1\n",
    "\n",
    "NO | SENTENCE / QUESTION\n",
    "---|---------------------------------\n",
    " 1 | Mary moved to the bathroom.\n",
    " 2 | John went to the hallway.\n",
    " 3 | [Q] Where is Mary?  =>  [A] bathroom (based on 1)\n",
    " 4 | Daniel went back to the hallway.\n",
    " 5 | Sandra moved to the garden.\n",
    " 6 | [Q] Where is Daniel?  =>  [A] hallway (based on 4)\n",
    " 7 | John moved to the office.\n",
    " 8 | Sandra journeyed to the bathroom.\n",
    " 9 | [Q] Where is Daniel?  =>  [A] hallway (based on 4)\n",
    "10 | Mary moved to the hallway.\n",
    "11 | Daniel travelled to the office.\n",
    "12 | [Q] Where is Daniel?  =>  [A] office (based on 11)\n",
    "13 | John went back to the garden.\n",
    "14 | John moved to the bedroom.\n",
    "15 | [Q] Where is Sandra?  =>  [A] bathroom (based on 8)\n",
    "\n",
    "* Example 2\n",
    "\n",
    "```\n",
    "* What American cartoonist is the creator of Andy Lippincott?\n",
    "  Fact: (andy_lippincott, character_created_by, garry_trudeau) \n",
    "* Which forest is Fires Creek in?\n",
    "  Fact: (fires_creek, containedby, nantahala_national_forest)\n",
    "* What does Jimmy Neutron do?\n",
    "  Fact: (jimmy_neutron, fictional_character_occupation, inventor)\n",
    "* What dietary restriction is incompatible with kimchi?\n",
    "  Fact: (kimchi, incompatible_with_dietary_restrictions, veganism)\n",
    "```\n",
    "￼￼￼￼￼￼￼￼￼￼￼￼￼￼\n",
    "\n",
    "3. 구문 분석 기술 발전\n",
    "----\n",
    "\n",
    "구구조 문법과 의존 문법\n",
    "\n",
    "![](https://upload.wikimedia.org/wikipedia/commons/8/8e/Thistreeisillustratingtherelation%28PSG%29.png)\n",
    "\n",
    "### 구구조 문법(Phrase Structure Grammar)\n",
    "\n",
    "* [Lexicalized PCFGs](http://www.cs.columbia.edu/~mcollins/courses/nlp2011/notes/lexpcfgs.pdf) - [Michael Collins](http://www.cs.columbia.edu/~mcollins/)\n",
    "\n",
    "* [Stanford Parser](http://nlp.stanford.edu/software/lex-parser.shtml) - [Christopher Manning](http://nlp.stanford.edu/manning/)\n",
    "\n",
    "* Chart parsing ([CYK algorithm](https://en.wikipedia.org/wiki/CYK_algorithm)) => ___O(n^3)___\n",
    "\n",
    "### 의존 문법(Dependency Grammar)\n",
    "\n",
    "* [CoNLL-X (2006) Multi-lingual Dependency Parsing](http://ilk.uvt.nl/conll/)\n",
    "\n",
    "* [MSTParser](http://www.seas.upenn.edu/~strctlrn/MSTParser/MSTParser.html) (graph based) - [Ryan McDonald](http://www.ryanmcd.com/index.html)\n",
    "    - [Minimum spanning tree](https://en.wikipedia.org/wiki/Minimum_spanning_tree) algorithm => ___O(n^2)___\n",
    "\n",
    "* [MaltParser](http://www.maltparser.org/) (transition based) - [Joakim Nivre](http://stp.lingfil.uu.se/~nivre/)\n",
    "    - [Shift-reduce parser](https://en.wikipedia.org/wiki/Shift-reduce_parser) => ___O(n)___\n",
    "\n",
    "\n",
    "4. 딥러닝을 이용한 구문분석기\n",
    "----\n",
    "\n",
    "* [A Fast and Accurate Dependency Parser using Neural Networks](http://cs.stanford.edu/people/danqi/papers/emnlp2014.pdf) - Chen and Manning, 2014\n",
    "\n",
    "### Arc-Standard Parser\n",
    "\n",
    "* Transition based,\n",
    "    - shift\n",
    "    - left-arc\n",
    "    - right-arc\n",
    "\n",
    "![](http://www.postype.com/files/2016/05/14/14/34/dbf98b20d640cf3fe8daece7108466ac.gif)\n",
    "\n",
    "<img src=\"img/transition.png\" width=700/>\n",
    "\n",
    "### Neural Network Architecture\n",
    "\n",
    "<img src=\"img/stanford_nn.png\" width=700/>\n",
    "\n",
    "### Results\n",
    "\n",
    "<img src=\"img/stanford_results.png\" width=500/>\n",
    "\n",
    "\n",
    "5. SyntaxNet\n",
    "----\n",
    "\n",
    "* [Google 자연어 처리 오픈소스 SyntaxNet 공개](http://cpuu.postype.com/post/166917/)\n",
    "    - [GitHub](https://github.com/tensorflow/models/tree/master/syntaxnet)\n",
    "* [Structured Training for Neural Network Transition-Based Parsing](http://arxiv.org/abs/1506.06158) - Weiss et al. 2015\n",
    "* <s>Globally Normalized Transition-Based Neural Networks - Andor et al. 2016</s>\n",
    "\n",
    "### Neural Network Architecture\n",
    "\n",
    "<img src=\"img/google_nn.png\" width=500/>\n",
    "\n",
    "* 구조적 차이점\n",
    "    - ReLU vs cube\n",
    "    - more hidden layers\n",
    "    - perceptron layer\n",
    "\n",
    "\n",
    "6. 차별성 및 실험 결과\n",
    "----\n",
    "\n",
    "### Semi-Supervised Structured Learning\n",
    "\n",
    "* Backpropagation Pretraining\n",
    "    - with fixed two hidden layers\n",
    "    - like Chen and Manning\n",
    "\n",
    "* Structured Perceptron Training\n",
    "    - output of two hidden layers and softmax layer\n",
    "    - as input of perceptron layer\n",
    "    - find decision sequences with beam search\n",
    "\n",
    "* Incorporating Unlabeled Data\n",
    "    - tri-training\n",
    "    - use only agreed auto-parsed sentence with BerkeleyParser and ZPar\n",
    "\n",
    "#### Results\n",
    "\n",
    "* Comparison with WSJ\n",
    "\n",
    "<img src=\"img/result1.png\" width=400/>\n",
    "\n",
    "* Number of Hidden Layers\n",
    "\n",
    "<img src=\"img/result2.png\" width=400/>\n",
    "\n",
    "* Number of Beams\n",
    "\n",
    "<img src=\"img/result3.png\" width=400/>\n",
    "\n",
    "* Tri-training\n",
    "\n",
    "<img src=\"img/result4.png\" width=300/>\n",
    "\n",
    "\n",
    "A. Label Bias\n",
    "----\n",
    "\n",
    "* HMM\n",
    "\n",
    "<img src=\"img/hmm.png\" width=500/>\n",
    "\n",
    "* MEMM\n",
    "\n",
    "<img src=\"img/memm1.png\" width=500/>\n",
    "\n",
    "* Label Bias\n",
    "    - Local Normalization\n",
    "\n",
    "<img src=\"img/local_norm.png\" width=500/>\n",
    "\n",
    "    - Global Normalization\n",
    "\n",
    "<img src=\"img/global_norm.png\" width=500/>\n",
    "\n",
    "* from MEMM to CRF\n",
    "\n",
    "<img src=\"img/memm2.png\" width=700/>\n",
    "\n",
    "<img src=\"img/crf.png\" width=700/>\n",
    "\n",
    "* 참고: [Conditional Random Fields](http://www.cs.stanford.edu/~nmramesh/crf)\n",
    "\n",
    "\n",
    "B. 한국어에 적용\n",
    "----\n",
    "\n",
    "* 한국어에 적용할 경우 사용하기 가장 용이한 코퍼스는 바로 [세종 코퍼스](https://ithub.korean.go.kr/user/corpus/referenceManager.do)입니다.\n",
    "\n",
    "* 세종 코퍼스는 Penn TreeBank와 같은 구구조 코퍼스입니다. 따라서, 이를 의존 코퍼스로 변환해야 합니다.\n",
    "\n",
    "* SyntaxNet의 입력 포맷은 CoNLL 포맷이므로, 변환한 의존 코퍼스는 이 포맷에 맞춰줘야 합니다.\n",
    "\n",
    "* 바로 적용하기 곤란한 차이점\n",
    "    - 한국어의 경우 어절 단위로 의존 관계를 표시하므로, 단어 단위인 영어와는 많이 다릅니다. 이로 인해 (여러 형태소로 이뤄진) 어절 내에서 추출할 수 있는 다양한 자질을 활용할 수 없게 됩니다.\n",
    "    - 어절 내에서 형태소 간의 의존 관계를 정의하여 형태소 단위의 의존 관계를 표현할 수도 있는데, 이러한 실험은 [이곳](https://github.com/dsindex/syntaxnet)을 참고하시기 바랍니다.\n",
    "    - 문장 전체의 헤드는 보통 술어가 됩니다. 영어와 달리 한국어는 술어가 맨 마지막에 나타납니다. 따라서, 한국어의 경우 오른쪽에서 왼쪽으로 (영어와는 반대로) 진행하는 것이 더 낫다고 합니다.\n",
    "\n",
    "\n",
    "<img src=\"http://mblogthumb3.phinf.naver.net/20160315_62/mkhjsk_14580230501257QzLz_GIF/005.gif?type=w2\" width=300/>"
   ]
  },
  {
   "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.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}