昨年度テクニカルライティング

T-10 機械学習による推薦アルゴリズム
テクニカルライティングについて
我々は何のために実験をするか？
• 「AはBである」という仮説を検証とするため
•
•
•
•
•
仮説：「AはBである」
実験設定：「AはBであることを確かめられる設定」
実験: 「AがBであることを確かめるデータを取る」
実験結果の考察：「AはBであったのか?」
結論:「AはBであった」
仮説:データ構造としてHashMapを
使った．HashMapなのでMovieID
からその映画のタイトルはO(1)で
取得できるはずである
•
•
•
•
•
•
この動作を実現するために利用し
たデータ構造を説明し, なぜその
データ構造を選択したか説明しな
さい
「AはBである」という仮説を検証とするため
仮説：「AはBである」
実験設定：「AはBであることを確かめられる設定」
実験
実験結果の考察：「AはBであったのか?」
結論:「AはBであった」
movies.datをメモリ上に読み込み,
MovieIDからその映画のタイトル
を取得できるようなプログラムを
作成しなさい.
このタスクの時間計算量について説明し
なさい.
考察の構造
背景知識(今回はデータ構造と時間計算量)
仮説:データ構造としてHashMapを
使った．HashMapなのでMovieID
からその映画のタイトルはO(1)で
取得できるはずである
実験設定: この動作を実現するた
めに利用したデータ構造を説明し,
なぜそのデータ構造を選択したか
説明しなさい
実装技術(今回はjavaデータ構造)
分析技術
実験: movies.datをメモリ上に読み
込み, MovieIDからその映画のタ
イトルを取得できるようなプログラ
ムを作成しなさい.
考察: このタスクの時間計
算量について説明しなさい.
結論
ライティングのお作法 記法
• 技術文書に独創性は必要ない
– わかりやすく誤解がないことが必要
– 表現はなるべくオーソドックスに
– 口語調は排する(AとかBとか, プログラムをまわし
ていくと, )
• 定量評価: 定性評価はなるべくしない
– 長い→Aにくらべてx倍長い
– すごく速い→Aに比べx倍速い
– 微妙に変化しない→平均値からの誤差は最大x
程度でほぼ定数といえる, etc
– 単位を明記, 非現実的な量を書いていないか?
ライティングのお作法 データ表現
• データを表示する意味は何か？→仮説検証
– 考察に適した表現形式を与えるべき
• データの表現
– リスト，表，散布図，直線，ヒストグラム, etc
• データの表示→考察 ではない
1.
2.
3.
–
仮説の設定
仮説の検証に適したデータ表示の選択
考察
データ表示が考察結果に影響を与えてはダメ
ライティングのお作法 グラフ
• 最低限必要な項目
凡例
変数名[単位]
普通はグラフが一つの
データのみからなることは
ない．定量評価は2以上
の対象との比較が基本だ
から．例外がないとはい
いませんが．
変数名[単位]
グラフ番号：グラフタイトル
時間計算量
• あるアルゴリズムを使ったときにある問題を解くのに
要するステップ数
• 時間計算量は入力データのサイズに対する関数で表
す(実行回数は関係ない)
– N回実行したら計算時間がN倍になる，は時間計算量で
はない(Nは入力サイズではなく回数だから)
• 時間計算量は係数を考えない(O(2N)ではなくO(N))
• レポート1-2-4の場合，多くの人はhash mapで実装して
いた. この場合，入力データのサイズはデータ構造に
保存されたmovie数であり，ある問題とは，入力idに対
してタイトルを取り出す操作のことである
アルゴリズムがO(N)であることを示す
• N(データサイズ)を変えながら計算時間を計測
• CPUの計算時間よりI/Oの動作ははるかに重い
– 影響の排除が必要
• 計算機の状態によって計算時間は微妙に変化する
– 統計によってノイズを取り除く
• 得たデータがO(N)=線形であることを示すには？
– 見た目増えているだけではだめ
– 少なくとも可視化，実際に線形回帰すればいちば
んよい
時間の評価
• 計算時間!＝出力時間
– 標準出力にかかる時間は計算時間ではない
• 標準出力は，かなり重い操作．要素数Nのリストを標準出力
するとNに比例する時間がかかる
• リストへの参照を得るだけなら計算時間はリスト長に関係し
ない
• 課題1-3-1の計算時間が「ユーザー数に依存する」と思う人は
– 正しいデータ構造が選択できていない
– データ構造に正しくアクセスできていない
– 計算時間の測定方法に誤りがある
のいずれか
今回の実験の標準的なデータ構造
value = userIDが見た映画のArrayList
Key=userID
value = userIDが見た映画のArrayList
Key=userID
……
userIDをkeyとし
たhashMap
value = userIDが見た映画のArrayList
Key=userID
User 1が見た映
画リスト取得の
計算量は？
User 1とUser5が
見た映画リストの
計算量は?
参考資料
推定値の算出
𝑠𝑖𝑘 = 𝑠𝑖 +
𝑗∈𝑈𝑘 ∖ 𝑖
𝑟𝑖𝑗 𝑠𝑗𝑘 − 𝑠𝑗
𝑗∈𝑈𝑘 ∖{𝑖} 𝑟𝑖𝑗
数式中の記号とプログラム上での対応(説明で使ったデータ構造の場合)
• 𝑈𝑘 ：movie IDをkey(𝑘)としたHashMapに含まれるRatingのリスト
– Ratingオブジェクトが保持しているuser ID(rating.userID)を利用する
– 𝑈𝑘 ∖ 𝑖 ：if文などを使って「rating.movieID != i」の場合のみ、該当する処理
を行うようにする
• 𝐼𝑖 ：user IDをkey(𝑖)としたHashMapに含まれるRatingのリスト
– Ratingオブジェクトが保持しているmovie ID(rating.movieID)を利用する
• 𝐼𝑖 ∩ 𝐼𝑗 ：𝐼𝑖 と𝐼𝑗 がともにmovie IDでソートされているならば、次のスライドの
方法で取得できます
参考資料
推定値の算出
𝑠𝑖𝑘 = 𝑠𝑖 +
𝑗∈𝑈𝑘 ∖ 𝑖
𝑟𝑖𝑗 𝑠𝑗𝑘 − 𝑠𝑗
𝑗∈𝑈𝑘 ∖{𝑖} 𝑟𝑖𝑗
n = 10データのユーザID = 1に対する映画2と6に対する推定
1. 類似度（𝑟1𝑗 ）と各ユーザの推定値の平均値（𝑠𝑗 ）を計算
𝑗
1
2
3
4
5
6
7
8
9
10
𝑟1𝑗
1.0
0.195
0.606
0.747
-0.133
0.704
0.408
0.0
0.556
0.269
𝑠𝑗
3.5
4.125
2.625
3.25
3.375
4.375
4
3.375
4.125
4.375
2. 𝑈𝑘 ∖ {𝑖}を求める。映画2の場合𝑈2 ∖ 1 = {2,3,6,7,8,9,10}
3. 右辺第二項を計算。映画2の場合、
–
𝑗∈𝑈2 ∖{1} 𝑟1𝑗
–
𝑗∈𝑈2 ∖{1} 𝑟1𝑗
𝑠𝑗2 − 𝑠𝑗 = 0.195 × 4 − 4.125 + ⋯ + 0.269 × 4 − 4.375 = −1.148
= 0.195 + ⋯ + 0.269 = 2.738
4. 推定値の式に値を当てはめる。映画2の場合
–
5.
𝑠12 = 3.5 +
−1.148
2.738
≒ 3.081
映画6の場合も同様にする