サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
買ってよかったもの
www.r.dl.itc.u-tokyo.ac.jp/~nakagawa
評判の高いサーチエンジン Google の中核要素技術の一つである PageRank について、その基本的な概念と求め方の原理を解説する。 INDEX はじめに PageRank の基本概念 どうやって PageRank を求めるか 現実に適用する際の問題 Namazu での実装実験 PageRank に対する個人的見解 参考文献 おまけ:「グーグル?/ゴーグル?」 Since: Thu Feb 1 18:22:44 JST 2001 Last Refreshed: Wed Oct 31 15:27:32 JST 2001 ★(2001/6/25) 拙著『日本語全文検索システムの構築と活用』を 『Namazuシステムの構築と活用』として全面改訂しました。 詳しくは サポートページをご覧ください。 ★(2001/2/28) Namazu のインデックスを用いて PageRank を計算する
3. 線形回帰および識別 線形回帰のモデル 正則化項の導入 L2正則化 L1正則化 正則化項のBayes的解釈 線形識別 生成モデルを利用した識別 2乗誤差最小化の線形識別の問題点 クラシックな機械学習の入門 by 中川裕志(東京大学) 線形モデル データ の分布状況 から線形回帰式を求 める w0 x y y=w1x+w0 線形モデル T 101 0 ],,,,[,],,,1[, K T Ki K i i wwwxxxwy wxwx ただし、 入力ベクトル:x から出力:y を得る関数がxの線形関数 (wとxの内積) 一般に観測データはノイズを含んでいる。つまり 得られたN個の観測データ の組(y,X)に対して最適なwを推 定する。 そこで、yと の2乗誤差を最小化するようにwを選ぶ。 と考える。はノイズで ),0(, 2 Ny wx wX
最適化と学習アルゴリズム 勾配降下法 直線探索 劣勾配降下法 ニュートン法 確率的勾配降下法 学習における計算効率の問題 既に説明した回帰、識別(分類)の解法で得た閉じ た式は逆行列計算が必要。例えば、線形回帰の場 合の正規方程式の解である重みベクトルは w=(XTX)-1XTy 学習データが高次元になると(XTX)の次元も大きく なり、逆行列の計算はコストが高い(次元数の3乗) 要は損失(=Loss)を最小化したい 正規方程式の場合は2乗誤差だった。 逆行列計算を避けて最適化する方法が実用 上重要。 記法:損失(Loss) zz y m L y m y m L yloss m L my D m i ii m i ii m i ii m i ii ii i ,0max ,1 1 , 1 , 1 2 ,on
匿名化の実社会での利用に向けての技術課題 中川裕志 東京大学 1. はじめに ビッグデータとりわけパーソナルデータの活用が 2013 年 6 月 に政府指針として打ち出された。前後して JR 東日本が収集し た顧客の Suica データを、日立を経由しての他業者への提供す ることに対する反対意見が噴出するという騒動が起こった。この 状況の下で政府のパーソナルデータに関する検討会が行われ, 技術検討ワーキング WG 報告[佐藤 2013](以下では「報告書」 と略記する.)が同年 12 月 10 日に公表された。 この報告書は技術的レベルの高い内容だが、そこで示された 方向性に対して IT 業界から、パーソナルデータを含むビッグデ ータの扱うビジネスを萎縮させるとして反対論があがっている。 一方、パーソナルデータに関連する法制度に関しては、日本 は不十分であるとして、EU からはゲノム情報
通信路モデル Bayes統計 最尤推定とMAP推定 データの性質 導入 情報源を記号列(例えば単語列 あるいは文字列)とする Noisy Channel Model 機械学習の先史時代 --情報の変換過程のモデル化-- 情報源記号 列:t tx 情報変換 雑音(N(0,σ2) etc) 推定処理 :推定さ れた情報 源記号列 出力された記号 列=推定処理 への入力 x 出力された記号列=推定処理への入力データxから 情報源記号列tを推定し を計算する tˆ tˆ Bayesの定理 P(t|x)は、新たな出力記号列xが得られたときの情 報源から出力された記号列 t を推定する式で、これ を最大化する t すなわち を求めるのが目標。 ところが、このままでは、既に得られている情報を 使えないので、Bayesの定理で変換する。 すると、既知の情報源状態と出力記号列のペ
位置情報の匿名化が誘発する濡れ衣現象 中川裕志 東京大学 情報基盤センター 1. 濡れ衣の被疑 ビッグデータの有効な利用を巡る議論が活発になされている.しかし,個人に係わる情 報である場合,ビッグデータ利用において個人特定をできることがプライバシー保護の観 点から問題であることが指摘され,プライバシー保護データマイニングの分野で匿名化手 法の研究が進んだ.一方,個人が自身に直接関係しない情報で否定的な事情を疑われるこ と,すなわち濡れ衣の被疑はこれまで見過ごされてきた問題であろう.以下では,このよ うな問題意識から匿名化と濡れ衣の関係について考察する. 1.1 濡れ衣の被疑の実例:人名検索 個人 A が濡れ衣を着せられるとは A 以外の人の犯罪行為を A の犯罪とみなされてしま うことであり,法律的には冤罪ということである.だが,濡れ衣を着せられなくても,濡 れ衣の被疑は潜在的にもっと多
数学の復習 行列の微分 行列式のlogの微分 対称行列の2次形式のtraceへの置き換え ブロック行列の逆行列(Woodbury) 行列の微分 x x x x x x B A ABAB BA, a x xa x ax xx xx x xf x x x x a x x xfxx g gfggf Tr B A Tr matrix x f x f x f x f x f x f f a a f f f x x T ji ij TT k m k m k kmk
Apache/2.2.23 Server at www-member.r.dl.itc.u-tokyo.ac.jp Port 80
機械翻訳 昔の機械翻訳 統計的機械翻訳 翻訳の評価 入力文:私はりんごを食べた。 形態素解析構文解析 noun verb noun subj predicate object 意味解析 (action=食べる, agent=私, target=りんご, time=past) 英語の語彙に変換(つまり意味表現のレベルないしはそれ に近い深さで変換 対訳辞書利用 (action=eat, agent=I, target=an apple, time=past) 構文および形態素の生成(語順の変換)して翻訳出力を得る。 対訳辞書利用 noun=I, verb(past)=ate, noun=an apple 出力文: I ate an apple. 昔の機械翻訳 意味のレベルで精密に日英が同一であることが前 提だった。 また、形態素解析、
学習データと予測性能 Bias2 - Variance - Noise 分解 過学習 損失関数と Bias,Variance, Noise K-Nearest Neighbor法への応用 bias2とvarianceの間のトレードオフの線 形回帰への応用 過学習:over-fitting 教師データによる学習の目的は未知のデータ の正確な分類や識別 過学習(over-fitting) 教師データに追従しようとすればするほど、複雑な モデル(=パラメタ数の多い)になり、教師データへ の過剰な適応が起こりやすい。 このことを数学的に整理してみるのが目的。 xが与えられたときの結果:tの推定値=y(x) 損失関数: L(t,y(x)) ex. (y(x)-t)2 損失の期待値:E[L]を最小化する t の推定値=Et[t|x] この導出は次の次のページを参考にしてください
Bayes統計に基づく推論 Bayesによる確率分布推定の考え方 多項分布、ディリクレ分布 事前分布としてのディリクレ分布の意味 正規分布と事後分布 多次元正規分布と条件付き分布 指数型分布族 自然共役事前分布の最尤推定 Bayesによる確率分布推定の考え方 事前分布 とはパラメター (i.e. μ0)自体の分布 μ0 観測データ or 教師データ:X p(μ|X)=p(X|μ0) p(μ0) 観測データを事前分布にBayes の定理で組み合わせる μ Xを観測した後に得た パラメターμの 事後分布 パラメター μは点では なく、分布として与えら れる点に注意! 複数の離散データが独立に出現する場合の確率分 布の定番 個々の離散データ間に相関がない場合に使うもの で基本的分布。 以下はK種類の離散データ(例えば、語彙数がKでN単語 からなるテキストでの単語の出現分布)がある場合
評価方法 一般的なデータ処理結果の状態 • 処理sで結果のデータ集合が得られた。しかし、結果の中には間違 いもあるし、得られなかったデータの中にも正解がありうる。 データ集合全体 処理sで得られた データ集合 処理sで得られるべきデータ集合 tn fp tp fn 性能評価尺度 再現率 適合率あるいは精度 フォールアウト 一般性 Accuracy or Rand Index fntp tp recall + = fptp tp precision + = fptn tn fallout + = fnfptntp tp generarity +++ = tnfnfptp tntp accuracy +++ + = 再現率 vs 適合率 • よく使う評価の表現法 再現率 適 合 率 0 0.5 1.0 1.0 0.0 再現率100%の自明 なシステム?? 再現率 vs 適
プライバシ保護データマイニング (PPDM) 東京大学 中川裕志 2002年くらいから伸びてきた分野です。最近は機械学習、 データ工学系の学会で相当数の論文が発表されています。 こういうご時勢ですから、ひょっとすると重要な技術要素 になるかもしれません。 個人情報保護が叫ばれる 複数の企業、組織が協力しないと日本は どんどん遅れていく PPDMの基礎概念 2種類のPPDM 摂動法 データベースに雑音を加え、利用者がデータベースに質 問しても真のデータベースの内容が利用者には取得でき ないようにする プライベートな情報は漏れないようにしたいが、一方で できるだけ正確なデータマイニング結果も得たい! 暗号法 データ保持者をパーティと呼ぶ。複数のパーティが自分 のデータは公開鍵暗号で暗号化する。当然、他のパー ティには自分のデータは知られない。暗号化したまま何 らかの計算を
数理情報学専攻 中川裕志 数値手法IV 「統計的機械学習入門」 機械学習小史:計算機以前 人間の知能に関する研究は言語を媒体とし、言語を分析することによっ て古代から進んできた。 ソクラテスの以降の言語名称目録説(モノが始めにあって、それに名 前を付けるという考え) アリストテレスの論理学 アンダルシアの西方イスラムを経てパリに伝わる 近世、計算を知能と考え始めた。 ライプニッツ etc etc 論理至上主義 ヴィトゲンシュタイン ソシュールの革命 言語名称目録説から脱却し、言語を閉じたシステムとして、その構造 を分析する方向を示した。(現代のテキスト処理の基礎) 機械学習小史:計算機以後 計算機の発明:1940年代 計算の道具 言語を分析する道具:1950年代には既に文書要約のアルゴリズムが 研究されていた。 人工知能の開花 数値を計算するマシンから記
データマイニング & パターンマイニング 目次 相関ルール Apriori algorithm 頻出アイテム集合を探す subset関数 Apriori-Gen関数 相関ルールを探す FP-growth algorithm さまざまな手法 列パタンのマイニング:PrefixSpan 相関ルールとは 「目玉商品Aと日用品Bを購入した顧客は、同時に高級品C も高い確率で購入する」 •A,B,Cのセット商品を発売する •顧客の便利性を考えて、商品の配置を近づける {目玉商品A、日用品B}⇒{高級品C}と表現できる {X}⇒{Y} 定義 {X}⇒{Y} X, Y I={i1,i2,…,im} T support(X) conf(X⇒Y) 相関ルール X:前提部, Y:結論部 アイテム集合, ik, k=1,.,mはアイテム、例えば個 別の商品 トランザクション(例えば買い物かごの中
カーネル法 線形回帰、識別からカーネル関数へ y ( w ) = wT φ (x ) という一般化した線形回帰式に対して 2 1N λT T J ( w ) = ∑ {w φ ( x n ) − tn } + w w 2 n =1 2 ただし ⎛ φ1 ( x n ) ⎞ ⎜ ⎟ φ (x n ) = ⎜ M ⎟ ⎜ φ (x ) ⎟ ⎝M n⎠ tnはw T φ ( x n )がとるべき値。 ( Mは教師データの次元数 , Nは教師データ数) という正規化項つきの2乗誤差を考えるとき、 φ (x )についてもう少し組織的に考えてみよう。 カーネル関数と呼ばれる k (φ (x ), φ ( y )) で回帰や識別を考え直す ことにより、より効率の良い方法が見えてくる。 双対表現 まず、正規化項つきの2乗誤差関数を考える。 J ( w) = 1 2 ∑ {w φ (x
オンライン学習 オンライン(あるいは逐次)学習とは データを1つづつ読み込んで、それまでの学習結果 を更新する。 2つの利用局面 1. データ全体は保持しているが、学習を1データ毎に行う 2. データが1こずつ時系列としてやってくる この場合はストリームという。 データ全体をメモリの乗せなくてよいのでマシンに必 要なメモリ少、あるいはメモリに乗りきらないほど大 きなデータから学習可能 1個のデータからの学習(これを1ラウンドという)だけ なら高速 オンライン学習の定式化 以下1,2,3を時刻 t=1,2,…,Tで繰り返す 1. 時刻tにおいて、仮説ht、入力データxt 、正しい結果 データytが与えられる。 2. 仮説ht による結果ht (xt)を計算し、その後でytとの 比較を損失関数lによって行う。つまりl(ht ,(xt , yt )) を計算 3. 損失関数lの値に応じて
ノンパラメトリックベイズ モデルの複雑さが不明な場合 これまでに説明してきたK-means、EM、変分ベイズなどは、 モデルの複雑さ、たとえばクラスタリングにおけるクラスタ数 は予め分かっているとしてモデル推定した。 しかし、実際はクラスタ数が不明の場合が多い。 ノンパラメトリックとは 観測データに応じてモデル自体の複雑さも学 習する クラスタリングの場合は、クラスタ数が予め分かっ ていない場合。観測データに適したクラスタ数も 推定 データから学習するということの直観 有限個の正規分布を配分比πkでの混合モデル:式(NP1) クラスタ数Kの値を観測データから最適化することによっ て推定する。 基本的アイデア:無限次元の連続分布から観測データ に適応した有限次元の離散分布を学習する。 ( ) ( )∑= = K k kk NPxNxp 1 )1(|,| θππθ 無限次
評価方法 一般的なデータ処理結果の状態 • 処理sで結果のデータ集合が得られた。しかし、結果の中には間違 いもあるし、得られなかったデータの中にも正解がありうる。 データ集合全体 処理sで得られるべきデータ集合 処理sで得られた データ集合 fp tp fn tn 性能評価尺度 • • • 再現率 適合率あるいは精度 フォールアウト recall = tp tp + fn precision = fallout = tn tn + fp tp tp + fp • 一般性 generarity = tp tp + tn + fp + fn • Accuracy accuracy = tp + tn tp + fp + fn + tn 再現率 vs 適合率 • よく使う評価の表現法 1.0 適 合 率 再現率100%の自明 なシステム?? 0.0 0
統計的機械学習入門(under construction) 機械学習の歴史ppt pdf 歴史以前 人工知能の時代 実用化の時代 導入ppt pdf 情報の変換過程のモデル化 ベイズ統計の意義 識別モデルと生成モデル 次元の呪い 損失関数, bias, variance, noise データの性質 数学のおさらいppt pdf 線形代数学で役立つ公式 確率分布 情報理論の諸概念 (KL-divergenceなど) 線形回帰と識別ppt pdf 線形回帰 正規方程式 正規化項の導入 線形識別 パーセプトロン カーネル法ppt pdf 線形識別の一般化 カーネルの構築法 最大マージン分類器 ソフトマージンの分類器 SVMによる回帰モデル SVM実装上の工夫 クラスタリングppt pdf 距離の定義 階層型クラスタリング K-means モデル推定ppt pdf 潜在変数のあるモデル EMアル
出現頻度と連接頻度に基づく専門用語抽出 本論文では,専門用語を専門分野コーパスから自動抽出する方法の提案と実験的評価 を報告する。本論文では名詞 ´単名詞と複合名詞µ を対象として専門用語抽出につい て検討する。基本的アイデアは、単名詞のバイグラムから得られる単名詞の統計量を 利用するという点である。より具体的に言えば、ある単名詞が複合名詞を形成するた めに連接する名詞の頻度を用いる。この頻度を利用した数種類の複合名詞スコア付け 法を提案する。ÆÌ Áʽ ÌÅÊ テストコレクションによって提案方法を実験的に 評価した。この結果、スコアの上位の ½¸ ¼¼ 用語候補以内、ならびに、½¾¸¼¼¼ 用語候 補以上においては、単名詞バイグラムの統計に基づく提案手法が優れていることがわ かった。 キーワード 用語抽出,専門用語,単名詞,複合名詞 Ì ÖÑ ÜØÖ Ø ÓÒ × ÓÒ Ç ÙÖ
統計的機械学習 (under construction) 導入ppt pdf 情報の変換過程のモデル化 ベイズ統計の意義 識別モデルと生成モデル 次元の呪い 損失関数, bias, variance, noise 数学のおさらいppt pdf 線形代数学で役立つ公式 情報理論の諸概念 (KL-divergenceなど) 指数型分布族、自然共役 正規分布(条件付き、および事前分布) 評価方法ppt pdf 順位なし結果の評価(再現率、精度、適合率、F値) 順位付き結果の評価 線形回帰と識別ppt pdf 線形回帰 正規方程式 正規化項の導入 線形識別 カーネル法ppt pdf 線形識別の一般化 カーネルの構築法 最大マージン分類器 ソフトマージンの分類器 SVMによる回帰モデル SVM実装上の工夫 モデル推定ppt pdf 潜在変数のあるモデル EMアルゴリズム 変分ベイズ法 Expecta
0.1 0.1.1 Latent Semantic Indexing Latent Semantic Indexing :LSI の次元まとめて次元を下げるという作業を行 なうわけである。 さて、次元を下げるということは当然情報 の損失を伴うわけだが、この損失を最小限に くいとめるために最小二乗誤差 という考え方 で望む。 2 とは ベクトル空間モデルではタームの生起が独 立であることを仮定して、各タームを一つの 次元に対応させるベクトル空間を作った。し かし、実際にはターム間の独立性は保証され ない。例えば、情報検索の分野では「ベクト ル」と「空間」は高い相関を持つことは容易 に予想できる。この問題への対策としては以 下の 2 点が重要である。 0.1.2 特異値分解 LSI で 用 い る 数 学 的 し か け は 特 異 値 分 解 (Singular Value D
本年度の授業はこちらです。 以下は前年度までの授業内容 インターネットと計算機の発達によって available になった世界中の情報資源のうちの多数を占めるテキストデータの扱いについて説明します。第1に、言語情報資源の扱い方、統計などについての基礎を説明します。第2に、情報検索のシステム、モデル、評価方法などについて説明します。これらのトピックの発展である情報抽出や言語横断型の情報検索などについても説明していくつもりです。 内容 はじめに テキストについて この講義で使う数学的知識 文字コード系.....付録pptファイル 使用言語の推定 言語の統計.....付録pptファイル 言語資源.....付録pptファイル ターム抽出 タームの分布モデル.....付録ppファイル 構造化文書 情報検索 情報要求.....付録pptファイル インデクシング.....付録pptファイル 質問の構
ターム抽出 全文を処理してタームを抽出する作業は情報検索シス テム構築の中心的部分である。英語と日本語では方法論が非常に異なる。言語 の構造的特徴を比較してみよう。 英語 単語間に空白があるので、個々の単語を容易に取り出せる。 名詞は単数、複数で語尾変化。動詞も時制、数で語尾変化。 prefix,suffix が単語につく。 日本語 膠着言語であり、単語の切れ目が形だけでは分からない。 名詞は語尾変化しない。 多数の名詞が繋がって複合名詞を形成することが多い。 漢字は1文字でそれなりの意味を持つ。 英語のターム抽出 Stemming 異形態から語幹を抽出する。例えば、engineering, engineered, engineeres などから共通の語幹 engineer を抽出する。最もナイーブな方法は、全ての異 形態に語幹を対応させる対応辞書を作っておき、入力された異形態から辞書引
東京大学 情報基盤センター 教授 なかがわ ひろし 中川裕志 My English page is here http://www.r.dl.itc.u-tokyo.ac.jp/~nakagawa/ メール:<n3(アットマーク がここに入ります。)上の行のdl以下jpまでをここに入れてください > 〒113-0033 東京都文京区本郷7-3-1 東京大学 附属図書館内 情報基盤センター 図書館電子化研究部門
次のページ
このページを最初にブックマークしてみませんか?
『Hiroshi Nakagawa』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く