Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Webプログラマと数学の接点、その入り口

Naoya Ito
October 04, 2016

 Webプログラマと数学の接点、その入り口

Naoya Ito

October 04, 2016
Tweet

More Decks by Naoya Ito

Other Decks in Technology

Transcript

  1. ΞδΣϯμɺର৅ͱ͢Δํ •  ΞδΣϯμ –  ઢܗ୅਺ͷجૅɺࣗવݴޠॲཧɺϓϩάϥϛϯάŋŋŋ –  ্هΛ਺ֶతࢹ࠲ͱϓϩάϥϛϯά ϓϩάϥϚ తࢹ࠲Ͱݟ͍ͯ͘ • 

    ओʹର৅ͱ͢Δํ –  8FCϓϩάϥϚͷํ –  ਺ֶʹৄ͍͠ํͰϓϩάϥϛϯάʹڵຯ͕͋Δํ –  ࣗવݴޠॲཧ΍৘ใݕࡧɺϦίϝϯυΤϯδϯʹڵຯ͕͋Δํ
  2. ϕΫτϧ •  ֶߍͰशͬͨ໼ҹͷϕΫτϧŋŋŋزԿϕΫτϧ –  ํ޲Λ࣋ͬͨྔ  •  ෳ਺ͷ਺ΛηοτͰදͨ͠ྔͱͯ͠ͷϕΫτϧŋŋŋ୅਺తදݱ –  ͭͷ਺ͳΒ࣍ݩ

    –  ͭͷ਺ͳΒ࣍ݩ –  ສͷ਺ͳΒສ࣍ݩ a = 2 4 ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ b = 2 4 1 ⎡ ⎣ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥
  3. ϞσϧԽˠϕΫτϧͰදݱ •  5PCFPSOPUUPCFUIBUJTUIFRVFTUJPO –  ͜ͷจॻΛ୯ޠͷग़ݱස౓ 5FSN'SFRVFODZŋŋŋ5' ͰϞσϧԽ ୯७Խ ͢Δ – 

    લޙͷจ຺͸ߟྀͤͣɺ୯ޠΛାʹ์ΓࠐΉͷͰ#BHPG8PSETͱݺ͹ΕΔ •  UPŋŋŋ •  CFŋŋŋ •  PSŋŋŋ •  OPUŋŋŋ •  UIBUŋŋŋ •  JTŋŋŋ •  UIFŋŋŋ •  RVFTUJPOŋŋŋ d 1 = 2 2 1 1 1 1 1 1 ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ to be or จॻϕΫτϧ
  4. ϕΫτϧˠ഑ྻ d 1 = 2 2 1 1 1 1

    1 1 ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ const d1 = [ 2, 2, 1, 1, 1, 1, 1, 1 ] console.log(d1[0]) // 2
  5. •  จॻΛϕΫτϧͱͯ͠දݱ •  ࣙॻͷ୯ޠΛ੒෼ͱ͢Δແݶ࣍ݩϕΫτϧ Antony and Cleopatra Julius Caesar The

    Tempest Hamlet Othello Macbeth Antony 157 73 0 0 0 0 Brutus 4 157 0 1 0 0 Caesar 232 227 0 2 1 1 Calpurnia 0 10 0 0 0 0 Cleopatra 57 0 0 0 0 0 mercy 2 0 3 5 5 1 worser 2 0 1 1 1 0 d1 จॻͷϕΫτϧԽ source: Introduc.on to Informa.on Retrieval h7p://nlp.stanford.edu/IR-book/
  6. ൺֱํ๏ŋŋŋྫ͑͹ɺίαΠϯྨࣅ౓ •  ϕΫτϧͷྨࣅ౓ŋŋŋϕΫτϧ͕࡞ΔDPTВΛٻΊΔࣜʹ౳͍͠ –   ͔͚ࢉͷූ߸ΛݟΕ͹਺ͱ਺ͷྨࣅ౓͕Θ͔Δ •  BYCͷ݁Ռ͕ਖ਼ͳΒɺೋͭ͸ಉ܏޲ •  BYCͷ݁Ռ͕ෛͳΒɺೋͭ͸ٯ޲͖

    ൓ରͷੑ࣭  •  BYCͷ݁Ռ͕ͳΒɺൺֱର৅ͱͯ͠ෆత֬ –   ϕΫτϧͷ಺ੵ͸ϕΫτϧͷ੒෼͝ͱʹֻ͚ͯ଍͠ࢉͯ͠Δ͚ͩ •  BɾCB  C   B  C   B  C  ŋŋŋ •  ಺ੵ͕ਖ਼ͳΒಉ܏޲ɺෛͳΒٯ܏޲ –   ༨ݭఆཧ cosθ = a⋅b a b 参考: 「相関係数とは何か?」を 体系的に理解するための6ステップ h7p://language-and-engineering.hatenablog.jp/entry/20090128/1233151846
  7. ϓϩάϥϜ +BWB4DSJQU ʹ͢Δͱ const _ = require('lodash') // 文書をベクトル (配列)

    で表現する。TFをベクトル長で正規化した値 const docs = { sas: [0.996, 0.087, 0.017], pap: [0.993, 0.120, 0], wh: [0.847, 0.466, 0.254] } // 2ベクトルのコサイン類似度を計算 function sim(d1, d2) { // 各成分の掛け算 (zipWith で * ) を累積 (sum) return _.sum(_.zipWith(d1, d2, (a, b) => { return a * b })) } console.log(sim(docs.sas, docs.pap)) // 0.999 console.log(sim(docs.sas, docs.wh)) // 0.888
  8. ҎԼ͸ಉ͡ૢ࡞Λ͍ͯ͠Δ •  ϓϩάϥϛϯά –  σʔλߏ଄ʹରͯ͠ԋࢉΛఆٛ͢Δ –  ର৅Λσʔλߏ଄ʹམͱ͠ࠐΉ͜ͱ͕Ͱ͖Ε͹ɺͦͷԋࢉ͕࢖͑Δ •  ਺ֶ – 

    ϕΫτϧ΍ߦྻͱ͍͏ߏ଄ʹϞσϧԽ͢Δ –  ϕΫτϧ΍ߦྻ΁ͷ୅਺ԋࢉ͕࢖͑Δ ྆ऀΛڮ౉ͨ͠͠ͷ͕ɺ ϕΫτϧˠ഑ྻͰͷ දݱ
  9. ҎԼ΋ಉ͡ •  ୅਺ʹΑΔந৅Խ –  ݸͷ஋ͱݸͷ஋Λ଍͠ࢉͨ͠Γֻ͚ࢉͨ͠Γŋŋŋͱߟ͑Δͱେ ม͕ͩŋŋŋ –  ͦΕͧΕBɺCͱ͍͏ϕΫτϧͰմͱͯ͠දݱ͢ΔͱB CɺBɾCͱ ୯७Խ͢Δ͜ͱ͕Ͱ͖Δ

    •  ϓϩάϥϛϯάʹ͓͚Δந৅Խ –  ͨ͘͞ΜͷύϥϝʔλΛ࣋ͬͨσʔλಉ࢜ͷԋࢉΛݸผʹߟ͑Δͱେ ม͕ͩŋŋŋ –  ಉҰίϯςΩετͷσʔλ͸ɺσʔλߏ଄΍ΦϒδΣΫτͱͯ͠մͱ ͯ͠දݱ͠ɺσʔλߏ଄΁ͷԋࢉɺΦϒδΣΫτͷ૬ޓ࡞༻ͱͯ͠ߟ ͑Δͱ୯७͔Ͱ͖Δ
  10. ߦྻ •  ߦྻŋŋŋෳ਺ͷϕΫτϧΛ·ͱΊͯѻ͏͜ͱ͕Ͱ͖Δ •  จॻू߹Λߦྻͱ͍͏Ұͭͷ୅਺ͰදݱͰ͖Δ D = 0.996 0.993 0.847

    0.087 0.120 0.466 0.017 0 0.254 ⎡ ⎣ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ୯ޠจॻߦྻ ֤ߦɺ֤ྻ͸ϕΫτϧ
  11. ߦྻ͸ͨͱ͑͹ೋ࣍ݩ഑ྻͰදݱͰ͖Δ D = 0.996 0.993 0.847 0.087 0.120 0.466 0.017

    0 0.254 ⎡ ⎣ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ const documentMatrix = [ [0.996, 0.993, 0.847], [0.087, 0.120, 0.466], [0.017, 0 , 0.254] ]
  12. ߦྻΛର৅ʹͨ͠ܭࢉ •  ߦྻʹ͢Δ͜ͱͰɺߦྻΛର৅ʹͨ͠ܭࢉ͕࢖͑Δ •  ྫŋŋŋಛҟ஋෼ղ 4JOHMVBS7BMVF%FDPNQPTJUJPOŋŋŋ47%  C =UΣVT source:

    Introduc.on to Informa.on Retrieval p.377 h7p://nlp.stanford.edu/IR-book/pdf/18lsi.pdf ・・・ C の自己相関行列の固有ベクトルを用いて分解。Σに特異値
  13. ͭ·Γŋŋŋ •  ਺ֶతʹ͸ŋŋŋ –  จॻ܈Λ୯ޠจॻߦྻͱͯ͠දݱ͢Δ –  ߦྻͱͯ͠දݱͰ͖Ε͹47%Ͱ෼ղͰ͖Δ –  47%Ͱ෼ղ͢Δͱɺಛҟ஋͕ɻಛҟ஋Ͱ௿ϥϯΫۙࣅͳͲ͕Ͱ͖Δ • 

    ϓϩάϥϜతʹ͸ŋŋŋ –  ୯ޠจॻߦྻΛ࣍ݩ഑ྻͱͯ͠දݱ͢Δ –  47%ͷܭࢉΛద༻͢Δ –  ௿ϥϯΫۙࣅΛ͢Δ͜ͱͰܭࢉྔΛݮΒͨ͠Γɺ࣍ݩѹॖͨ͠Γ͢Δ͜ͱ͕Ͱ͖Δ
  14. 1ZUIPOͷOVNQZͰ47% > import numpy as np # 行列を二次元配列で > A

    = np.array([[1, 0, 2], [0, 1, 0], [1, 0, 2]]) > A array([[1, 0, 2], [0, 1, 0], [1, 0, 2]]) # SVD を計算 > U, s, V = np.linalg.svd(A) > U array([[ -7.07106781e-01, -1.57009246e-16, -7.07106781e-01], [ 0.00000000e+00, 1.00000000e+00, 0.00000000e+00], [ -7.07106781e-01, 1.57009246e-16, 7.07106781e-01]]) > s array([ 3.16227766e+00, 1.00000000e+00, 4.24340278e-17]) > V array([[-0.4472136 , 0. , -0.89442719], [ 0. , 1. , 0. ], [ 0.89442719, 0. , -0.4472136 ]])
  15. જࡏతҙຯΠϯσΫγϯά -BUFOU4FNBOUJD*OEFYJOH  •  จॻϕΫτϧۭؒͷ࣍ݩΛѹॖ͢Δ –  ʮDBSʯͰݕࡧͨ͠ΒʮBVUPNPCJMFʯ΋ώοτ͢ΔΑ͏ʹ –  47%ͰߦྻΛ෼ղ͠ɺಛҟ஋ʹԠͯ͡ߦྻͷ֊਺ΛԼ͛Δ – 

    ϕΫτϧۭ͕ؒ௿࣍ݩͷۭؒʹࣹӨ͞ΕΔɻ͜ͷͱ͖୯ޠͷજࡏతҙຯ͕ ѹॖ͞ΕΔ •  $6Є7UͷЄΛߏ੒͢Δಛҟ஋ͷ͏ͪ஋͕খ͞ͳ෺Λʹ –  ϥϯΫ ֊਺ ͕Լ͕Δجఈͷ਺͕ݮΔ •  ЄˠЄ L •  $ L 6Є L 7U –  ॏཁͳجఈ͚ͩΛ࢒ͯ͠খ͞ͳߦྻʹۙࣅͨ͜͠ͱʹͳΔ –  খ͘͞ͳͬͨ$ L ʹɺ͍ͭ΋ͷίαΠϯྨࣅ౓ͳͲ
  16. /.' /POOFHBUJWF.BUSJY'BDUPSJ[BUJPO  •  ඇෛ஋ߦྻΛͭͷඇෛ஋ߦྻʹҼࢠ෼ղ͢ΔΞϧΰϦζϜ –  Ͳ͏΍ͬͯ෼ղ͢Δ͔͸ޙड़ •  ΋ͱͷߦྻ͕࣋ͭજࡏཁૉ ಛ௃

    ΛᖰΓग़͢ X = WF = x 文書 単語 文書 特徴 特徴 単語 X W F ಛ௃͕จॻʹରͯ͠Ͳ ͷఔ౓ॏཁ͔ͷॏΈ ୯ޠ͕ಛ௃ʹରͯ͠Ͳ ͷఔ౓ॏཁ͔ͷॏΈ
  17. /.'ͰςΩετϚΠχϯά •  ΫΤϦ ୯ޠͷू߹ ͔Βؔ࿈͢ΔจॻΛಘ͍ͨͳΒŋŋŋ –  '͔Β୯ޠू߹ͱద߹͢Δಛ௃ϕΫτϧ ߦ ΛಘΔ – 

    ࣍ʹ8͔Βಛ௃ϕΫτϧʹద߹͢ΔߦΛબͿ = x 文書 単語 文書 特徴 特徴 単語 X W F ୯ޠ͕ಛ௃ʹରͯ͠Ͳ ͷఔ౓ॏཁ͔ͷॏΈ ಛ௃͕จॻʹରͯ͠Ͳ ͷఔ౓ॏཁ͔ͷॏΈ
  18. (PPHMFͷ1BHF3BOL •  ΢ΣϒάϥϑΛߦྻͱͯ͠දݱ͠ɺߦྻͷओݻ༗ϕΫτϧΛٻΊΔ –  ཁૉ͕ϦϯΫΛḷΔ֬཰ɻ֬཰ߦྻ –  ݻ༗ϕΫτϧŋŋŋઢܗม׵ͷಛ௃Λද͢ϕΫτϧ –  ओݻ༗ϕΫτϧࢉग़͸΂͖৐ଇʹΑΓܭࢉྔΛ࡟ݮͰ͖Δ – 

    ओݻ༗ϕΫτϧͷ੒෼͕ɺΫΤϦʹର͢Δจॻͷద߹౓ 1BHF3BOL  ※ 現在の検索アルゴリズムは単純な PageRank のみよりも遙かに複雑な計算が行われています
  19. 8PSE7FDͷੑ࣭ •  8PSE7FDͷϕΫτϧۭؒʹ͸ݴ༿ͷʮҙຯʯΛ௚઀తʹදݱ͠ ͍ͯΔ͔ͷΑ͏ͳੑ࣭ source: 米googleの研究者が開発したWord2Vecで自然言語処理 h7p://qiita.com/okappy/items/e16639178ba85edfee72 > イチロー -

    野球 + 本田 サッカー 0.612238 初戦 0.588327 バスケ 0.562973 > 日本 - 東京 + フランス 札幌 0.569258 パリ 0.566437 ミラノ  0.560036 > ご飯 - 卵 + そば 鶏 0.686967 ネギ 0.670782 塩 0.663107 ୯ޠϕΫτϧͷՃࢉɺ ݮࢉ͕ఆٛ͞Ε͍ͯΔ
  20. 8PSE7FD͔Β%PD7FDɺ*UFN7FD΁ •  ෼ࢄදݱΛԠ༻ –  8PSE7FDͷ୯ޠ෼ࢄදݱͰจॻϕΫτϧΛߏஙˠ%PD7FD –  ෼ࢄදݱͰ*UFN ঎඼FUD Λߏஙˠਪનɺ෼ྨ – 

    σΟʔϓϥʔχϯάͷૉੑʹ࢖͑ΔͨΊେਓؾ •  ྫϦΫϧʔτςΫϊϩδʔζ஑ాࢯ IUUQXXXTMJEFTIBSFOFUSFDSVJUDPKQTT –  ߦಈϩάΛ୯ޠͱΈͳ͠8PSE7FDͰϕΫτϧԽɺίαΠϯྨࣅ౓Ͱ Ϩίϝϯυͨ͠ͱ͜Ζਫ਼౓޲্͕ݟΒΕͨͱͷ͜ͱ
  21. ϓϩάϥϛϯάͱͷطࢹײ •  ϕΫτϧɺߦྻŋŋŋ –  ʮ਺Λ·ͱΊ͔ͯ͋ͭ͏ŋŋŋ͜Εσʔλߏ଄ͷ͜ͱͩΘʯ •  " #͕ͨͩͷ਺Ͱ͸ͳ͘ߦྻͱ͍͏ෳࡶͳߏ଄Λ΋ͬͨ਺ͷ૊Έ ߹ΘͤͰ͋ͬͯ΋ɺ" #ɺ"#ɺ"#ͱ͔͚͹ɺ͔͋ͨ΋ࠓ·Ͱͷ

    ਺Ͱ͋Δ͔ͷΑ͏ʹߟ͑ͯɺࣅͨΑ͏ͳํ๏Ͱܭࢉ͕Ͱ͖ΔΘ͚Ͱ ͋Δ –  ҟͳΔσʔλߏ଄ʹ΋ಉ͡ΠϯλϑΣʔε ܭࢉ Λఆٛ͢Ε͹ͦΕΒ ΛಉҰࢹͰ͖Δ –  ʮ͜ΕμοΫλΠϐϯά ϙϦϞʔϑΟζϜ ͩɻͦ͏͔ɺந৅Խ͔ʯ
  22. ࣗ෼ʹͱͬͯͷϓϩάϥϛϯάͱ਺ֶͷ઀఺ɺͦͷೖΓޱ •  ର৅ͷ໰୊ͷσʔλߏ଄Λଊ͑Δ ϞσϧԽ  •  ϕΫτϧɺߦྻŋŋŋˠ਺ֶ ઢܗ୅਺FUD ΁ͷ໳͕։͘ • 

    ਺ֶͷੈք΁໰୊Λඈ͹ͤ͹ɺ૝૾ྗͷݶքΛಥഁͰ͖Δ –  ສ࣍ݩͷϕΫτϧۭؒ͸૝૾͸Ͱ͖ͳ͍͕ɺ਺ֶͳΒͦΕΛѻ͏͜ ͱ͕Ͱ͖Δ
  23. ·ͱΊ ݴ͍͔ͨͬͨ͜ͱ  •  ϓϩάϥϛϯάͱ਺ֶͷ઀఺͸ࢥͬͯΔΑΓ೉͘͠ͳ͍ –  ࠓճ͸ઢܗ୅਺ΛςʔϚʹ –  ֩ʹͳΔͷ͸σʔλߏ଄ ϕΫτϧɺߦྻ

     –  ϓϩάϥϛϯάͱ਺ֶͷੈքΛڮ౉͢͠Δͷ͕Ϟσϧ •  8FCϓϩάϥϚతͳʮৄࡉ͸Α͘Θ͔Βͳ͍͚Ͳ"1*ݺ΂͹݁Ռ ͸खʹೖΔͰ͠ΐʯͰ΋࠷ॳ͸͍͍ͱࢥ͏ –  ͦΕ͕͖͔͚ͬʹͳͬͯɺ஌ࣝཉ͕෸͘ •  ֶੜͷͱ͖ʹ΍ͬͨ਺ֶ ܭࢉͷ܇࿅ ΑΓɺڵຯ͕࣋ͯΔ͸ͣ
  24. ࢀߟจݙ •  $%.BOOJOH 13BHIBWBO )4DIVU[Fʰ*OUSPEVDUJPOUP *OGPSNBUJPO3FUSJFWBMʱ $BNCSJEHF6OJWFSTJUZ1SFTT  •  5PCZ4FHSBO

    ஶ ᙛࢁਔ݈ יᖒᚸ෉ ຋༁ ʰू߹஌ϓϩάϥ ϛϯάʱ ΦϥΠϦʔδϟύϯ  •  ۚ୩݈Ұʰ͜ΕͳΒ෼͔ΔԠ༻਺ֶڭࣨʕ࠷খೋ৐๏͔Β΢Σʔϒ Ϩοτ·Ͱʱ ڞཱग़൛  •  ԕࢁܒʰ਺ֶೖ໳্ʱ ؠ೾৽ॻ  •  ԕࢁܒʰ਺ֶೖ໳Լʱ ؠ೾৽ॻ