YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

Japanese subtitles

← 05-07 Matrix Multiplication

Get Embed Code
3 Languages

Showing Revision 1 created 03/11/2014 by Fran Ontanaya.

  1. ところで行列の乗算を知っていますか
  2. 今学んでいるこのアルゴリズムと
  3. 行列の乗算には関連があります
  4. これを正しく理解するために
  5. まずはグラフを行列に表してみます
  6. もし行列が0と1で構成されており
  7. ノードiとjの間にリンクがあるとすれば
  8. 行列の呼応する箇所は1となります
  9. iとjの間に関連があるという意味です
  10. グラフではリンクは双方向性なので
  11. i-jに1があればj-iにも1があります
  12. つまり対称な行列ということになります
  13. 対称な行列というのは
  14. 詳しくは触れませんが
  15. 反転させると鏡合わせのようになる行列です
  16. つながりが双方向性でノードを入れ替えただけなので
  17. 同じ行列になります
  18. これを行列(M)と呼びM回かけるとどうなるか
    考えてみましょう
  19. 行列の乗算でi-jの入力をするためには
  20. 最初の行列からi行をとり
    2番目の行列からj列をとります
  21. 両手でやらないと難しいのですがこの行を横切りつつ
  22. 同時にこちらの行を横切りつつこちらの列を下ります
  23. 正方行列で0と1のみです
  24. こうやって見ていくと
  25. 0と1をかけても0になるので
  26. 両方に1がある場合のみ0ではない値になります
  27. つまりこの行と列をかけた値は
    2つのベクトルが同じ場所に1を
  28. 持っている数と同じになります
  29. 同じ場所に1を持っているというのは
  30. Kの位置に1があり同様にこちらにのKにも1があり
  31. このグラフにはiとkの間にリンクがあるという
    意味になります
  32. つまり1がここにあるということは
  33. 同様にここにもあるということです
  34. Mが表すグラフはkからjへのリンクもあるのです
  35. このkのような数をカウントアップしていき
  36. iからとjからのエッジを足していきます
  37. 行列の乗算が行うのはこれと同じことなのです
  38. この値はiからjへの2段階のパスの数になります
  39. 登場人物IとJに共通する作品を
  40. カウントアップしていくことになるのです
  41. アメコミの2部グラフの場合は
  42. 登場人物に始まって作品名に行き
    また登場人物に行くという2段階です
  43. iとjに共通する作品の数を
    カウントアップしているのです
  44. グラフのつながりを示すこの正方行列から
  45. 同じ値が求められます
  46. このアルゴリズムの実行時間はn³です
  47. すべての項目をループしているからです
  48. 行と列の乗算ではn²となりますが
  49. このアルゴリズムは3乗です
  50. エッジ数とノード数の乗にn列をかけ合わせます
  51. エッジの数は全ての登場人物と作品名の
  52. 組み合わせから算出されさらにどの登場人物が
  53. つながりがあるか検証しました
  54. もしMが高密度の行列であれば
    n×mのような値になりn²なので
  55. n³までいってしまいそうですが今回は密度の低い行列で
  56. エッジの数は平面グラフのように線形なので
  57. この場合はn²になるわけです