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

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

Avatar for Naoya Ito Naoya Ito
October 04, 2016

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

Avatar for Naoya Ito

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

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