法システムIII：情報法データベースサービスとコンテンツ附属資料東京大学情報基盤センター中川裕志この資料の構成 放送大学の教科書に直接関連する内容はここをクリック 以下は、基礎知識 WWWとブラウザはここをクリック 検索エンジンの構造に興味のある方はここをクリック Web Contentsと著作権をめぐって  口伝の時代（伝達１１）から石板の文字へ（伝達範囲１００倍以上か）  石板、羊皮紙、手書き紙媒体から印刷媒体へ（伝達範囲 1人から１００，０００人へ）  紙の印刷からネットワークによる電子的配布へ（伝達範囲１人から1,000,000 人以上へ)  さらに質的な変化は、伝達が双方向化（chat, blog,..)  著作権      (電子コンテンツでは、伝達の拡がりに加え、改変も問題）人格権再配布通信改変、改竄インターネット mail,ftp,http ローカルネット abc xyz. 192.168.01 利用者の要求にしたがって検索した情報コンテンツ（例えばhtml ファイルやMIDIファイル）の送信ブラウザが受信した情報コンテンツを解釈してWeb ページとして表示あるいはスピーカで出力インターネット情報コンテンツのサーバ利用者からの要求に応じて情報コンテンツを送信検索要求利用者のパソコンリンクの問題  リンクの著作権  リンク集の著作権  額に汗の理論  リンクを張ると、実際に見に行くにはオリジナルなサイトなので、コピーにまつわる著作権侵害などはない。  リンク連鎖の責任はどこにあるのか？  実質的に連鎖に責任は  負えるのか？追えるのか？  著作権的に問題があることを知りつつリンクを断ち切らない場合は、プロバイダの責任はあるとする判例もある。フレーム問題ここが広告だったら右側のフレーム内容が別のHPに異動すると広告ただ乗り？コピーがあちこちにサーバ２サーバ１インターネットローカルなサーバクライアントプロキシ－＝利用者のPC A B サーバ B インターネットを流れるコンテンツの蓄積と著作権  Proxyが通過していくコンテンツを蓄積して、サービスに使ったら、違法コピーか？  遠隔図書館間でのコピーサービスは電子化できない？  一時的蓄積なら良いのか？  一時的とは、第1次の目的以外の使用も許すのか？  さらに電子コンテンツ固有の問題として改変まで許すのか？  放送業者には一時的蓄積は認められている  通信業者、プロバイダには認められていない  Ｇｏｏｇｌｅは？プロバイダとは通信業者か放送業者か？  矛盾する法的立場  通信業者：  通信の守秘義務。内容の改変は負荷  放送業者：  内容の改変（すなわち制作）ができる。通信の守秘義務という概念がない！？  プロバイダは、メールサービスという意味で通信業者だが、HP開設サービスやblog、チャット、掲示板のサービスという意味では放送業者的  双方向的なblog、チャット、掲示板は、通信か放送かという二分法に馴染まない。法的立場を議論しないまま、後追い法制が続く。矛盾に陥りがち。ファイル交換ソフト登録ファイルの一覧表一覧表ファイル一覧表一覧表ファイルファイルファイル交換ソフト：集中型  集中型：Napstar:  レコード会社の法律的攻撃を受け、無力化  ０１年に著作権侵害でサービス停止命令を受けて撤退に追い込まれた。各会員が持っているファイルの所在データを用いて、ファイル交換を仲介  このＤＢを押さえれば、無力化。  訴訟の対象が固定されている。ファイル交換ソフト；分散型  分散型：グヌーテラインターネット       ファイル交換ソフトは個人のＰＣにあり、会員同士がリクエストを中継訴訟相手を探しにくく絞りにくい。ファイル交換ソフト自体は有用。使い方がいけない（武器？）独立系のアーティストの発表の場！？ソフト作成者を逮捕するに至る。プライベートな会員限定の環境なら合法的、取り締まりにくい？ファイル交換ソフトに関する最近の米最高裁判決  グヌーテラ型のファイル交換ソフトはソフト制作者を訴える方向である判例がある。  米ソフト会社グロクスターなどが違法なファイル交換を助長して著作権を侵害していると、米大手レコード会社などが訴えた  一審と控訴審では合法。  最高裁では逆転。2005年6月２７日、違法と判決楽曲ファイル交換行為に対して賠償支払い  日本レコード協会は7月６日、ファイル交換ソフトを使って市販の楽曲を著作権に違反して配信していた５人が、レコード会社５社に対して１人あたり平均４８万円の損害賠償  ファイル交換ソフトを使って他人の楽曲を勝手に配信できる状態にすれば、著作権法（送信可能化権）を侵害することになるという流れになってきた。  日本レコード協会によれば、今年１月の時点でファイル交換ソフトの利用者は約１２７万人、過去１年間にダウンロードしたファイル数は１人あたり２３６（うち音楽関連９５）と推定しているそうである。  プロバイダー責任制限法によりファイル交換ソフト使用者の氏名をプロバイダに請求できることを利用して、個人を特定し、損害賠償請求という道筋ができた。プロバイダー責任制限法特定電気通信役務提供者の損害賠償責任の制限及び発信者情報の開示に関する法律の概要 • 趣旨：特定電気通信による情報の流通によって権利の侵害があった場合について、特定電気通信役務提供者（プロバイダ、サーバの管理・運営者等。以下「プロバイダ等」という。）の損害賠償責任の制限及び発信者情報の開示を請求する権利につき定めるものとする。 • 内容 • (1) プロバイダ等の損害賠償責任の制限特定電気通信による情報の流通により他人の権利が侵害されたときに、関係するプロバイダ等が、これによって生じた損害について、賠償の責めに任じない場合の規定を設ける。 (2) 発信者情報の開示請求特定電気通信による情報の流通により自己の権利を侵害されたとする者が、関係するプロバイダ等に対し、当該プロバイダ等が保有する発信者の情報の開示を請求できる規定を設ける。ビジネスモデルとしての解決  ファイル交換ソフトは、それ自体が違法か？  取り締まりきれるのか？  むしろビジネスモデルを変えるべきではないか。  広告込みのコンテンツを流通させ、広告料収入による方法  コピーコントロールによる法的規制  １回だけコピー可能な仕掛けとか。。。海賊版と電子透かし ファイル交換ソフトも含め、あるいは著作権無視の国も多い状況で、横行する海賊版に対する技術的対策 電子透かし コンテンツに利用者が気づかないように著作権に関する情報を埋め込む 著作権処理された本物であることの認証、 海賊版において、電子透かしの入っているコンテンツを押収したら？電子指紋による著作権保護 コンテンツ配布時に、個別の購入者ごとに異なる情報を電子指紋として埋め込んでおく。 海賊版を押収したら、電子指紋の情報から、横流しした購入者が判明すると期待 壊されにくい電子指紋の研究協調フィルタリング： Zグループ個人情報との関係は？ Yさんこれらの人が好きな商品共通に好きな商品多し abc 趣味が似ているので、これを推奨 abc X WWWとは  WWW：World Wide Web:インターネット上にシームレスに張り巡らされたハイパーテキストのネットワーク  ハイパーテキスト：文書の中に，他の文書を指し示すようなリンクを持った文書  URL：URL(Uniform Resource Locator)といって，世界中にあるウェブページを一意に特定する住所  リンク：WWW でウェブページに他のウェブページを結び付ける情報 Googleの検索 おなじみのGoogleにおける検索のヒント  GoogleのHPにおける 検索オプション表示設定言語ツールを開いてみよう。その他の検索エンジン  Yahoo!：ディレクトリー型（一種に情報ポータル：いろいろな情報源への玄関のこと）  AltaVista,Goo などなど（これらにアクセスしてみるにはどうしたらよいか？）  こういった検索エンジンの仕掛けについて考えてみよう。  これらの検索エンジンはどうやって、WWW上のページを集めてくるのだろうか？  集めてきたページをどうやって検索できるようにしているのだろうか？  どのような順番で表示しているのだろうか？サーチエンジンを使うってどういう要求なのか？  ユーザがある問題を解決するために、現有の知識だけでは不十分であると感じている状態が情報要求(information need) な状態。 1. 直感的要求（visceral need)：要求を認識しているが言語化できない状態 2. 意識された要求(conscious need)：あいまいな、あるいはまとまりのない表現でしか言語化できない状態 3. 形式化された要求(formalized need)：具体的な言語表現 4. 調整済み要求(compromised need)：問題解決に必要な情報源が同定できるくらいに具体化された要求情報要求 ユーザがある問題を解決するために、現有の知識だけでは不十分であると感じている状態が情報要求(information need) な状態。 広義の情報検索：ユーザの持つ問題を解決できる情報を見つけ出す事。問題はユーザが与える。 狭義の情報検索：ユーザの検索質問に適合する文書を文書集合中から見つけ出す事 情報の解釈をユーザが行なう= 情報検索 情報の解釈をシステムが行なう= 人工知能 データベースの場合、ユーザはデータベースの構造、内容まで知った上で定型的な検索質問を行なう。つまり、文書集合を対象とする情報検索よりもさらにユーザは情報内容に通じていなければならない。実際、ユーザにとっては大変な負担であり、データベース検索の専門家が必要になったり、典型的な質問例を利用したりすることになる。検索システムおよびインデクシング検索エンジンの仕掛け情報集め：crawling  Googleなどの検索エンジンは世界中のＨＰを機械的に集めてくる。  2週間に1回世界を回る  ＵＲＬを辿ってＨＰを見つける、つまり皆さんが行っている検索と同じことを機械が組織的に行っている。具体的には 1. 2. 3. 4. 多数の起点のＨＰを見る。次にそのページからリンクされているＨＰを集めて、またそのＨＰからリンクされているＨＰを集めて ……. 検索システムの構造：crawlしたＨＰからこのデータベースを作る Posting file 質問：Q 検索エンジン： Qに一致する Webページへのポインタを探す URL1 URL2 URL3 : URL1 URL2 URL3 所在 URL ＨＰ本体あるいは snippet 転置インデックスインデックスタームヒット件数科学２研究費１申請３ポスティングファイルポインタ URL Web全体検索システムの構造 1. 2. 3. 4. 検索対象の文書各々は、それに現れる複数の語( 以下「ターム (term) 」と呼ぶ) によって特徴付けられる。タームによる文書の特徴付けをインデクシング(indexing) という。利用者は自分が欲しい文献を特定する記述を質問Q として検索システムに与える。質問は、1 個以上のキーワード、あるいは自然言語文で記述される検索エンジンは、Q を解釈して、それに適合する文書を検索する。適合する文書は一般的には複数存在する。したがって、検索結果は、ポスティングファイルへのポインタの集合である。ポスティングファイルは、URLの集合。利用者には検索結果として検索されたURL などのアドレスが返される。多くの場合、文献名には文献のURL へアクセスできるリンクが張ってあり、クリックすればURL にアクセスして文献が表示できる。タームと検索 1. 2.   統制ターム: 予め決められたタームだけを使う。タームの質は統制により維持されるが、利用者が統制タームしか質問に使えない。自由ターム: 任意のタームを質問に使える。後に述べる全文検索では文書中のタームを網羅するので、自由タームになる完全一致検索（ブーリアン検索）最良優先検索（ベクトル空間法など）ブーリアン検索 • 質問は論理式。例えば、Q= 科学or( 研究費and 申請) • 転置ファイルを検索して、タームt に対応する文書の集合D(t) が得られるとしよう。すると、質問の論理式(1) によって検索した結果は次のようになる。 • D( 科学) or (D( 研究費) and D( 申請)) • 質問論理式を作ることが素人には難しい。 • 検索結果の文書数が多過ぎたり、あるいは0 だったりすると、論理式を調整して適当な大きさの結果集合にするのだが、この調整が非常に難しい。ベクトル空間法 • 最良優先検索 • タームの重み付けと類似度各タームを次元にし、質問と文書をベクトルで表現するベクトル空間質問ｑ：「人工知能と知識の関係についての論文」人工知能＝１．０知識＝１．０論理プログラム＝０ターム：知識文書D：「第５世代の失敗」ターム：知識＝０．７１．０：人工知能＝０：論理プログラム０．７＝２．５ Dとｑのなす角＝類似度：似たような文書はこの角が小さい１．０２．５ターム：人工知能ターム：論理プログラムページ間リンクを利用する重みつけ Webのホームページはリンクが張られている。これは図書の引用索引に似ている。 基本原理：多くの良質なページからリンクされているページは、良質なページである この原理によるアルゴリズムとして有名なのが GoogleのPageRank algorithm Webページのランキング  Webページ検索の特異性  文書DBからの検索の場合、使える情報は文書中のテキスト、単語  tf×idfによるベクトル空間の類似度ではない重み付けはできないか？  Webページの検索の場合、テキスト、単語に加え、リンク情報が使える  リンクは（テキストや単語と異なり）、Web（＝データベース）の大域的構造  リンクを利用する検索結果のランキングについて説明する。代表的なPageRankについて説明する。 PageRank algorithm のアイデア  多くの良質なページからリンクされているページは、やはり良質なページである  利用者がページをリンクをたどってサーフする状況を模擬する。(良いページには沢山の利用者がいると考えればよい）   ページの重みが決められている  リンク元ページからの流入する重み総和がそのページの重み  リンク先へ流入する重みは、そのページの重みをリンク先の本数で割ったものページ重みの概念図 10 30 10+5=15 10 5 10 10 10 5 ところが問題は あるページPiの重みはPiへのリンク元のページの重みが確定しないと計算できない。 めぐりめぐって、Piの重みが確定しないとPi へのリンク元のページの重みが確定しないと計算できない。  各ページの重みを要素とし、全ページ数の次元を持つベクトル R を考え、このベクトルを数学的に求めることにするページ重みの計算法  ここからしばらくは難しいのでスキップしたい方はお戻りください。 接続行列A=(aij)で表現 if ページiからページjにリンク then aij=1/Ni (Niはiからでるリンク数） otherwise aij=0  ページのベクトル R は以下の式を満足する  r1   a11  a1n   r1  R=cAR つまり          c       rn  an1  ann  rn  しかし、その１ 2つのページの間だけでループしている状態に他からのリンクがあり、そこに重みがどんどん吸収されてしまう場合 ページがいくつかのグループにまとまり、グループ間にはリンクがない このような場合には、全ページにわたっての重みが均等に行き渡らない。 ある割合(15%)で、ランダムにページを探したと仮定 Aに全要素が一定値の行列を加算して計算 R＝（cA+(1-c)E)R Eは全要素が１の行列、c=0.85としているしかし、その２ 流出すれだけで、流入する全くリンクのないページとは 勝手に他人にリンクを張っているだけの権威のないページ  無視する 機械的に張ったリンクの問題 PageRankのアイデアの基本は、人間がWeb ページを評価しリンクを張った状況、すなわち人間の判断を利用しようとしているので、機械が張ったリンクは悪影響を与えるページベクトルの計算：  R＝（cA+(1-c)E)R  Eは全要素が１の行列、c=0.85としてみた  これはベクトルの固有値問題で Rは固有ベクトル。これを以下の繰り返し計算で解く。 1. 2. 3. 4. 5. 6.  R(0)適当な初期値 R(i+1) （cA+(1-c)E) R(i) D||R(i)||ー||R(i+1)|| R(i+1)R(i+1)+dE δ ||R(i+1)ーR(i)|| if δ>ε then goto 2 なお ||x||はベクトルの全要素2乗の和の√ 計算例  簡単な例で繰り返し計算すると(ε=0.001) 4  Rは  ri  1 と確率になるように正規化 i 1 a A b c d a b c 0  0 1 / 2 0  1 / 2 1 / 2   0 1/ 2 d 1 0 0 0  cA  (1  c) E  0.85A  0.15E 0 0  0 0 1／20.18 a: 0.365 b:0.204 1／20.18 1/20.102 10.321 c:0.321 1/2 0.102 d:0.110 考察 a,b,c,d ページともほぼ流れ込むリンクの重みに近い II. リンク重みとページ重みのズレは、0.15の確率でランダムにページを移動する分 III. 良いページcからリンクされているaは重みが大きい IV. 多くのページからリンクされているcも重みが大きい V. あまりたいしたことのないページbだけからリンクされているdは重みが小さい VI. 以上、ほぼ我々の意図したページの重みになっている。 I. 数値計算の問題  これまで述べてきたページ重みの繰り返し計算はうまく収束するのか、十分早いのか？  Googleの10億ページでは100億のリンクがあるので、まっとうに線形代数の計算をしていたのでは無理。  数値計算法ではかなり工夫をしているはず。企業秘密らしく公開されていない  Googleのマシンルームの様子からみると、  PCクラスタによる並列計算  疎な行列を適当に分解すればまとまったページ群を独立に計算できるかも収束の問題(以下の論文の数値例グラフ) Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd, 'The PageRank Citation Ranking: Bringing Order to the Web', 1998 • • • • 1回前との誤差 107 106 105 リンク数 161,000,000 322,000,0000 • 0 15 30 45 繰り返し回数情報検索システムの評価法 評価法 再現率、適合率 F値など 社会科学における調査でも重要な考え方 本講座の趣旨からはだいぶ外れますが、専門的な文献を読むときには役立つかもしれません。一般的な検索結果の状態 • 質問ｑで結果のＨＰ集合が得られた。しかし、結果の中には間違いもあるし、得られなかったＨＰの中にも正解がありうる。文書集合全体質問ｑに適合しているＨＰ質問qで検索されたＨＰ fp tp tn fn 検索エンジンの性能評価 • 再現率 tp recall  tp  fn • 適合率あるいは精度 tp precision tp  fp 再現率ｖｓ適合率 • よく使う評価の表現法１．０適合率再現率１００％の自明な検索システム？？０．０００．５再現率１．０再現率ｖｓ適合率に関連した尺度 • • • Break even point 再現率と適合率が一致する点 11点平均適合率再現率＝0.0 , 0.1, 0.2, ….. 0.9, 1.0 の11点における適合率の平均値 F値ただし、ｂは適合率が再現率よりどれだけ重視されているかを示すパラメタ― ｂ＝１がよく使われる。 (1  b2 )  P  R F b2  P  R F 2 PR 2  1 1 PR  P R 順位つき検索結果の評価 ブーリアン検索では検索結果は全て同等 ベクトル空間法やPageRankでは検索結果が質問に適合した順番に並ぶ。（表示も適合順） この場合の評価法について Recall , Precision 質問qに適合する結果（以下、正解、という）の数： |Dq | 検索エンジンの順位つけられた結果: (d1…….dn) di が質問qへの正解なら ri=1、そうでなければ ri=0 とする。すると、  第k順位まで拾ったときの 1 Recall(k )  ri  | Dq | 1i k 1 Precision(k )   ri k 1i k 検索エンジンがここまで拾った検索したＨＰ質問に一致するＨＰ ○ ○ ○ ○ ○ ○ ○ ○ ○ 2 Re call  5 2 P r ecision 4 平均適合率：average precision 1 AveragePrecsion   r  precision(k ) | Dq | 1k  N k ただし、 Nは正解が最後に現れた順位 • 例：順位正解か１２３４〇 AvPrec 1 1 2      2 1 4   0.75 ５６〇平均逆順位：Mean Reciprocal Rank(MRR) N MRR   (if n位の結果が正解 n 1 1 n else 0) N 1  n 1 n ただし、 Nは正解数もし、正解がひとつも • 現れなければ　ＭＲＲ＝０ 1 1  例 MRR  1 4  0.833 1 1  1 2 順位正解か１〇２３４５６〇