MapReduceによる大規模データ処理 at Yahoo! JAPAN

>100 Views

October 06, 11

#MapReduce #Hadoop #大規模データ処理 #空間解析 #検索インデックス

スライド概要

Yahoo!デベロッパーネットワーク

@ydnjp

スライド一覧

2023年10月からSpeaker Deckに移行しました。最新情報はこちらをご覧ください。 https://speakerdeck.com/lycorptech_jp

またはPlayer版

埋め込む »CMSなどでJSが使えない場合

（ダウンロード不可）

関連スライド

深層学習による自然言語処理入門: word2vecからBERT, GPT-3まで

Yahoo!デベロッパーネットワーク 165.2K

ゼロから始める転移学習

Yahoo!デベロッパーネットワーク 86.6K

ヤフーにおける WebAuthn と Passkey の UX の紹介と考察 #idcon #fidcon

idcon fidcon

Yahoo!デベロッパーネットワーク 74.2K

OpenID Connectとネイティブアプリを取り巻く仕様と動向 Yahoo! JAPANの取り組み #openid #openid_tokyo

openid openid_tokyo

Yahoo!デベロッパーネットワーク 58.1K

運用業務とスクラムは本当に組み合わせにくいのか︖運用業務が大半を占めるプロダクト開発での試行錯誤

devsumi

Yahoo!デベロッパーネットワーク 36K

ヤフーのオンプレ機械学習基盤AIPFについて #ml_kubernetes

ml_kubernetes

Yahoo!デベロッパーネットワーク 29.3K

各ページのテキスト

MapReduceによる大規模データ処理 at Yahoo! JAPAN 2011/09/26 ヤフー株式会社 R&D統括本部角田直行、吉田一星

Hadoop at Yahoo! JAPAN 検索プラットフォームアクセスログデータプラットフォーム広告プラットフォームレコメンデーションプラットフォーム地域APIプラットフォーム様々なYahoo! JAPANのサービスを支えるプラットフォームで、 Hadoopが使われています 5 Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止

10.

11.

12.

13.

14.

15.

16.

17.

MapReduceのおおまかな設計 –Mapper –住所ポリゴンデータと、ある地点の緯度経度のデータを同じキーで出力 –Reducer –同じキーにまとまっている場合、地点データが住所ポリゴンデータに含まれている。つまりその地点の住所がわかる。 →Mapのキーは何にするか？ 16 Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止

18.

GeoHash –緯度経度を英数字の文字列で表すアルゴリズム –35.65861, 139.745447 → xn76ggrw26 –文字列の長さが精度に比例する –文字列が短いとおおまかなエリア、長いとピンポイントのエリア –点としてだけでなく、ある範囲（グリッド）を表すことが可能 17 Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止

19.

20.

21.

22.

23.

24.

25.

Map –MultipleInputsで２種類のMapperを立ち上げる –Mapper1 Key ある地点の7桁GeoHash Value ある地点のユニークID + 緯度経度 –Mapper2 24 Key 住所ポリゴンデータと交わる7桁GeoHash Value GeoHashのメッシュ単位で抜き出したポリゴンデータ Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止

26.

27.

出力結果 26 UID 住所 755a458181f0d0ce670ca6363ac3fcf15c5ec ec9 東京都西東京市谷戸町１丁目２３ b9eb85ccad95dce44ba5ba56047c359a5ab2 5321 東京都西東京市ひばりが丘２丁目８ c2bd76e39a900202cd89a8a62127975779c 3c5db 東京都西東京市ひばりが丘２丁目６ 25e82144eff068c13d7d04004681723c53c5 6c72 東京都西東京市ひばりが丘２丁目７ a1f307a07f21cc5c43069f222a861fd3a0381 427 東京都西東京市谷戸町３丁目２０ 0f88a6d126e9080de53d70b8771665a06d3 b783c 東京都西東京市保谷町３丁目１２ 04a27655283486df6dde65cf31702310bd91 13c3 東京都西東京市保谷町３丁目１４ Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止

28.

29.

検索インデックス生成 –MapReduceの最も基本的なタスクの一つ –Hadoop MapReduceデザインパターンでも紹介されている –インデックス＝本の索引 28 apple.co.jp Apple, iPad, iPhone, Macbook… yahoo.co.jp Yahoo, オークション, ニュース, 検索, 地図… twitter.com tsuda, ふぁぼり, なう, 個人, 見解… 2ch.net 香具師, ガイシュツ, スマソ, 池沼, 希ガス… Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止

30.

検索インデックス生成 –単語をキーにしたURLのリストの形式に転置する –例えば、「地獄ミサワ」で検索すると、その単語が含まれている URLがすぐにわかる 29 iPhone apple.co.jp, softbank.co.jp, apple.com… 地獄 jigokuno.com, twitter.com, hatena.ne.jp… ググレカス 2ch.net, nicovideo.jp, google.co.jp… ミサワ jigokuno.com, misawa.co.jp… Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止

31.

32.

実際の課題 –インデックスには複数のフィールドがある –フィールドごとに単語を分割する方法が違う –フィールドと単語分割の種類 URL タイトルページの内容完全一致 2Gram 形態素解析 –フィールドと単語分割の例 31 labs.yahoo.co.jp Yahoo!ラボ実験的なサービス・機能・仕組みを… labs.yahoo.co.jp Ya, ah, ho, oo, o!, !ラ, ラボ実験的, な, サービス, ・, 機能, ・, 仕組み, を… Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止

33.

実際の課題 –ユニークな文書番号を付与し、文書番号でソートする –文書内での単語のポジションや頻度を考慮する –検索インデックスの例単語 <文書番号: 文書内のポジションのリスト>… iPhone <3: 104,202,1241>, <7: 3,190,1267>… –TFIDFの計算のために、単語ごとの文書数と、文書ごとの単語数を計算する –TFIDFは文書内で単語の重要度を測る指標の一つでランキングに用いられる –インデックスを圧縮する必要がある 32 Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止

34.

ABYSSの場合 –社内の検索サービスをホスティングするプラットフォーム –30以上の社内サービスで使われている –検索インデックス作成処理の流れ 33 前処理後処理文書番号をふる数値インデックス作成 etc… MapReduceの結果のファイルを一つのインデックスにまとめる Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止

35.

Map –インデックスの元データが入力 labs.yahoo.co.jp Yahoo!ラボ実験的なサービス・機能・仕組みを… –インデックスのスキーマファイルを読んで、単語の分割の種類ごとに処理を分岐完全一致 2Gram 形態素解析 –単語の正規化と、単語の分割を行う 34 Key フィールド名+単語+文書番号+ポジション+フィールド番号 Value 文書番号+ポジション Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止

36.

Shuffle –Partitioner –同じフィールドのデータは同じReducerに行くように分散 –Comparator –単語のキー順にソート –単語が同じ場合は文書番号でソート –文書番号も同じ場合はポジションでソート –GroupingComparator –フィールド名+単語で、グルーピングしてReducerに渡す 35 Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止

37.

Reduce –フィールド名+単語でグルーピング、単語、文書番号、ポジションでソートされて入力 –MultipleOutputsでフィールドごとにファイルを出力 –インデックスは圧縮して出力 36 Key 単語 Value 文書番号+ポジションのリストミサワ <124: 12,135,1223>, <278,1278,2380>… iPhone <3: 104,202,1241>, <7: 3,190,1267>… Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止

38.

39.

機械学習とは？「データの中で見えているものを手がかりに、見えないものを予測する」 –ページの内容がアダルトかどうか判定する –自分のプロフィールと条件に合ったお見合い相手を探す（ Yahoo!お見合い） –検索結果を様々な指標に応じて最適にランキング –クエリや、コンテンツ、その人の興味に合った広告を表示 –あるニュースに関連するニュースを表示 38 Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止

40.

機械学習によるランキング –検索結果を機械学習でランキングする –WEBページの様々な指標（＝素性）を考える PageRank クリック数リンク数被リンク数 50 2300 50 120 –それぞれの素性に対して予め学習済みの重みが与えられているとする 0.2 0.01 -0.02 0.05 –掛け合わせたものをスコアとして検索結果をランキングするスコア = 50×0.2＋2300×0.01＋50×-0.02＋120×0.05＝53 –重みさえわかれば、ランキングができる 39 Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止

41.

重みの学習 –重みをどう学習するかがポイント –あらかじめ、素性とスコアのペア（＝正解データ）を用意しておく正解スコア PageRank クリック数リンク数被リンク数 30 50 2300 50 120 22 45 1200 100 20 –正解データを元に、重みを学習していく 40 Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止

42.

重みの学習 –オンライン学習 –正解データを一件ずつ見ていって、重みを更新する –実装が容易 –ノイズが含まれていたり、素性が多い場合に有効 –バッチ学習 –すべての正解データを見て重みを更新する –実装が難解 –情報量が多いので、精度が高くなる場合が多い 41 Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止

43.

オンライン学習 –正解データを一つ見て、古い重みを新しい重みに更新する新しい重み = 古い重み – 適当な係数 × (予測スコア - 正解スコア) × 正解データ古い重み 0.2 0.01 -0.02 0.05 | 0.001 ×(53 - 58) × 正解データ 50 2300 50 120 -0.015 0.005 || 新しい重み 0.205 11.51 –オンライン学習をMapReduceで行いたい 42 Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止

44.

Iterative Parameter Mixing Mapper Mapper Mapper 重みベクトルを更新重みベクトルを更新重みベクトルを更新 Reducer [Mann et al. 09] [Mcdonald et al. 10] 43 重みベクトルを平均 Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止

45.

MapReduce – Mapper – 正解データを入力 – 前回の繰り返しの重みをMapの初期化処理で読み込んでおく – オンライン学習で、重みを更新 Key なし Value 重み – Reducer – Reducerは一つだけ立ち上げる – 重みを平均して出力する – このMapReduceを繰り返す 44 Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止

46.

47.

48.

49.

50.

51.

52.

53.

54.

55.

MapReduceで分散 –MapReduceで分散可能なのは決定木の構築 [Jerry et al. 10] –どう決定木の枝を分岐させるか –学習データを分岐させてスコアをアップデート –GDBTの学習プロセス自体はシーケンシャルなので、決定木の構築を決定木の数だけ繰り返す –ちなみに決定木の数も予め与える → 54 → → Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止

56.

枝の分岐 –正解スコアと予測スコアの差の平均の二乗が最小になるように分岐最小になるようにクリック数＞ 3000 -30 × -30 ＋ 7×7 = 139 –すべての素性に対して、どこで分割するかをすべての場合について計算すればよいクリック数 > 3000 クリック数 PageRank リンク数被リンク数 1923 34 87 14 2399 15 25 158 右に分岐 3400 92 102 245 左に分岐 55 クリック数はソート済 Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止

57.

58.

MapReduce～水平分割～ –Mapper –ある学習データのすべての素性に対して以下を出力 Key 素性の名前 + 素性の値 Value 正解スコアと予測スコアの差＋重み –Reducer –ある素性について、素性の値がソートされて入力される 57 Key 素性の名前 + 素性の値 Value 正解スコアと予測スコアの差の和＋重みの和 Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止

59.

MapReduce～水平分割～ –後処理で、MapReduceの結果のデータを逐次見ていって、どの素性でどの値で分割するかを決定するクリック数正解スコアと予測スコアの差 1923 -3 2399 5 3400 3 1×1 ＋ 3×3 || 最小になるように 58 Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 10

60.

MapReduce～垂直分割～ –垂直に分割する場合クリック数 PageRank リンク数被リンク数 1923 34 87 14 2399 15 25 158 3400 92 102 245 Mapper1 59 Mapper2 Mapper3 Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止 Mapper4

61.

MapReduce～垂直分割～ –Mapper –ある素性のすべての値をソートし、ベストな分岐ポイントを見つける –一つのMapperで一つのKey/Valueを出力 Key 正解スコアと予測スコアの差の平均の二乗の最小値 Value 素性の情報 –Reducer –そのまま出力すれば、最小の分岐ポイントが一番上に来る 60 Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止

62.

分散方法の比較 –水平分割は、データの数だけスケールする一方で、後処理に時間がかかる –垂直分割は、後処理が必要ない一方で、素性の数しかスケールしない –実は、MapReduceを使わずにMPIで分散させる方法が一番速い –HadoopのHDFSだけを使い、Hadoopのノード上でOpenMPIを使って分散を行なっている 61 Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止

63.

64.

まとめ –MapReduceはシンプルながらも、柔軟なフレームワーク –現実の問題に対して、MapReduceをどう設計していくか –必ずしもMapReduceが最適ではない場合もある –Yahoo! JAPANはこれからもHadoopを活用していきます 63 Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止

65.

Hadoopの連載記事 –いまさら聞けないHadoopとテキストマイニング入門 –機械学習、Iterative Parameter Mixingでの分散方法を解説 http://www.atmarkit.co.jp/fjava/rensai4/hadoop_tm01/01.html 64 Copyright © 2010 Yahoo Japan Corporation. All Rights Reserved. 無断引用・転載禁止

http://www.atmarkit.co.jp/fjava/rensai4/hadoop_tm01/01.html

66.

http://nodefest.jp/2011/

67.