近年，ウェブページが爆発的に増加しており，我々は検索エンジンを用いることにより多種多様な情報を得ることができる．しかし，ウェブページの約40%が類似ページといわれており，検索結果に類似ページが含まれるという問題がある．本研究では1 億ページという大規模なウェブコレクションを対象として，類似ページ検出を行なう．本研究では類似ページを，文字列をある程度共有する2つのページと定義し，ミラーページなどの同一ページ，引用ページ，盗作ページなどが含まれる．本手法はまず，各ページから長い低頻度の文を抽出する．これは，文長が長く，また，ウェブ全体での頻度が低い文を2 ページで共有すればこれらのページは関連性が高いといえるためである．また，各ページにおいてコンテンツ領域を抽出し，コンテンツ領域にある文のみを類似ページ検出の手がかりとする．これは非コンテンツ領域にある文を共有しても2 つのページに関連性が低いからである．以上の処理によって得られた文を共有するページペアを類似ページとみなす．次に，類似ページを同一ページ，引用ページ，盗作ページなどに自動分類する．分類は，ページに対する類似文字列の割合である重複率，インリンク/アウトリンクの有無，URLの類似度などの様々な情報を用いて行なう．類似ページ検出の実験を行なったところ，単純なURLの正規化ではわからないミラーページや，引用ページ，様々なサイトから記事をはりあわせたようなスパムページを発見することができた． / The recent explosive increase of Web pages has made it possible for us to obtain a variety of information with a search engine. However, by some estimates, as many as 40% of the pages on the Web are duplicates of the other pages. Thus, there is a problem that some search results contain the duplicate pages. This thesis proposes a method for detecting similar pages from a huge amount of Web pages: hundred million Japanese Web pages. Similar pages are defined as two pages that share some sentences, and are classified into mirror pages, citation pages and plagiaristic pages, etc. First, from each page, relatively long sentences are extracted. This is because two pages tend to be relevant when they share relatively long sentences. A pair of pages that has the identical sentences is regarded as similar pages. Next, similar pages are classified based on several information such as an overlap ratio, the number of inlinks/outlinks, and contents region extraction. We conducted the similar page detection and classification on the large scale Japanese Web page collection, and can find some mirror pages that we cannot find by the simple URL normalization, citation pages, and plagiaristic pages. / Kyoto University (京都大学) / 0048 / 修士 / 修士(情報学)

バーチャルスタジオを教育映像の撮影に利用すれば，CGによる特殊効果が加わった三次元の仮想物体を教材として利用できるため，視認性の高い教育映像を作成できる．このとき，教師である演者による説明に迫真性をもたせるためには，演者が仮想物体の説明箇所を直接見て判断し，その説明箇所を視聴者に見せるための並進・回転という直接操作を交えた主体的な説明が要求される．演者が三次元の仮想物体を直接操作できるようにするため，仮想物体と同形の現実物体を導入し，実写映像中の現実物体を仮想物体に置き換えるという手法がある．この手法では，演者が特定色の現実物体を直接操作する様子をカメラで撮影し，実写映像の特定色領域に仮想物体を重畳することで目的を達成している．しかし，現実物体は単色であることから，演者は仮想物体の説明箇所を直接見ることができないので，演者は主体的に説明することができない．本研究では，演者が仮想物体の説明箇所を直接見られるようにするため，現実物体に仮想物体のテクスチャ（演技支援情報）を投影する．但し，演技支援情報が実写映像に映り込むと現実物体領域が特定色ではなくなるため，過不足なく仮想物体を重畳できない．また，現実物体に対する演者の視線方向と投影方向が異なると，演者には演技支援情報が投影されない部分が見えてしまう．本研究では，演者が物体を説明対象として説明する場面において物体に対する演者とカメラの視線方向は異なるという一般的事実に基づき，再帰性反射材を貼付した現実物体に演者の側から演技支援情報を投影することで，演技支援情報の実写映像への映り込みを回避する．また，カメラ・演者・物体の位置関係，再帰性反射材の反射輝度分布，演者の手の動きを基に，演者の身体による遮蔽が発生しない演者後方の投影位置を特定することで，演者の視線方向と投影方向を一致させる．提案手法の有効性を検証するため，演者の視点位置の近傍に設置したカメラとスタジオカメラの2台のカメラで現実物体を観測し，それぞれのカメラから得られる映像を目視で定性的に評価した．その結果，演技支援情報が演者には視認可能でスタジオカメラには撮影不可能となっていることを確認した． / Kyoto University (京都大学) / 0048 / 修士 / 修士(情報学)

本研究では参加者5, 6 人がプレゼンテーションとフリーディスカッションを交えて行うミーティングを対象として，その様子を映像と音声で記録するとともに，参加者の視線集中，写真撮影と電子メモの記入，プレゼンテーションスライドの操作などを検出してインデクスを生成することで，後から振り返るときのための利便性を確保したミーティングキャプチャシステムを構築する．このインデクスは映像の自動推薦を行う際に利用することを想定しており，過去をうまく想起させるような部分や，複数映像の中のふさわしい部分を選択するための指標となるようにする．収録したデータを自発的に振り返るときにもこのインデクスが手がかりとして提示され，見る人に対してどこから見ればよいのか，どのあたりが重要なシーンであるかが視覚的にわかるようにする．視線集中の獲得は，参加者の顔方向および視線方向をミーティングスペース中央の全方位カメラによって観測し，東西南北のうち特定の方向に対して過半数の集中が起きたときを意味のある重要なシーンが起こったと推測する．この際，顔方向と視線方向は独立に判定される．顔方向集中と視線方向集中では顔方向集中のほうがより印象的な会話イベントが起こったことが示唆され，その特徴としては笑いやジャスチャを伴うことや，会話が質問応答の形式になっていることが挙げられる．また参加者は捉えておきたい場面に対して，カメラのシャッターを押したりメモを書いたりする行為によって実時間タグと呼ぶインデクスを意識的に付与することが可能である．実時間タグのインデクスでは画像が生成されてから最後にメモ書きが起こるまでの活動時間に注目することにより，話題の継続性への手がかりとすることができる．この両者は同時刻にはあまり発生せず，両者のインデクスは性質が異なる相補的なものである．そのため両者のインデクスは目的によって使い分ける必要がある． / In this paper, I construct a capture system for meetings, in which 4 to 5 participants make presentations and/or free discussions. It enables participants and none-participants to look over captured meetings. This system captures paging of presentation slides, pictures by PhotoChat and notes as indices in addition to videos and audios. Besides captured indexes, gathering of gazes are calculated and used as index. I suppose these indexes are good marks to recall meetings and to select a video from multi view point and they will be variable in auto-recommendation. They are also used as markers to show where to start to look and where to look for their impotance when users want to look back. A spherical vision camera set up at the center of meeting table captures meeting participant’s faces in order to recognize that their gaze points gather at the same area. When the majority of them gather their gaze in any area of north, south, east, and west, the system guesses that a significant event occurs and generates the index. The precision ratio of the judgment of gaze gathering is about 65Some features are found in the conversations around the time that gaze gathering occurs. Participants also can give real-time tags to the scene for which they want to leave the indices intentionally by pressing the shutter button and writing the memos. The length of time from to the memo book daily life and happening of real time at the end can be used as a clue to the continuance of the topic. The length of the time between the generation of the image of real-time tag and the last memo can be used as a clue to the continuance of the topic. Both are not so generated at the same time, and the indices of both is the complementary one another. Since the indices of both differ, it is necessary to use them properly by the purposes. / Kyoto University (京都大学) / 0048 / 修士 / 修士(情報学)

In this paper we design a certified e-mail exchange system based on simultaneous secret exchange protocol proposed by Okamoto and Ohta. We selected their protocol because it is superior in efficiency, especially at the view point of the number of sessions. At first, we designed the whole procedure mainly based on Okamoto and Ohta's protocols, adding processes to confirm the contents each party have received. In this system, we want to realize good properties often referred in certified mail researches with TTPs, for example 'send-and-forget'. So we assume two players, an MTA (Mail Transfer Agent, e.g. SMTP Server) and an MUA ( Mail User Agent, e.g. the client the sender or the receiver use) in each party, and designed construction which enables 'send-and-forget' for the sender when the sender can control an MTA, or enables to exchange messages for the sender with the receiver directly when cannot. Then, we made message formats in the form of XML to send each transactions. We selected the method of attaching transaction XML to e-mail to communicate messages to realize reachability. With this method, it takes rather long time to complete exchanging secret keys and get contents of the mail or receipt when the mail delay is large. Then we proposed a method to reduce the number of exchanging transactions. This method doubles the number of bits sent at once after some bits have been sent regularly. The 'fairness' is defined as the maximum of the difference of time needed to calculate the remaining bits of keys at any time, where the difference is taken between two players. This amount is 'at most twice' in a normal simultaneous secret exchange protocols, while it is 'at most constant difference' in our method. / 本論文で我々は証明付き電子メール配達システムを同時秘密交換プロトコルに基づいて設計した. 我々は効率, 特にセッションの回数の観点から優れていることから岡本・太田らの提案したプロトコルを選択した.岡本らのプロトコルを主軸として, 我々は双方が受け取った内容に相異がないかの最終確認のプロセスなどを加えて, メッセージと領収書を交換するための手続きを設計した. システムを設計するにあたって我々は, TTP を用いて構成される証明付きメールの研究で頻繁に言及されるSend-and-forget など良い性質を実現させたかった. そこで, 我々はそれぞれのパーティ内にMTA (Mail TransferAgent, SMTP サーバなど) , MUA (Mail User Agent, 送信者, 受信者が用いるメールクライアント) の2 者が存在することを仮定した. これにより送信者がMTAを制御下に置ける場合にSend-and-forget をMUA のユーザレベルでは実現でき,そうでない場合には受信者と直接メッセージ交換を行える構成を設計することができた. そして, それぞれのトランザクションを伝送するためのメッセージフォーマットをXML としてまとめた.我々は到達可能性を考慮してメッセージの伝達手段としてメールにトランザクションのXML を添付するという形式を選んだが, この方法ではメールの一往復あたり遅延が大きい場合, 必要な秘密鍵の交換を完了してメールや領収書の内容を入手するまでにかなり長い時間がかかってしまう. そこでセッションの往復回数を減らすための手段として, ある数のビットを普通にに送った後には1度に送信する数を増加させていくという手法を提案した. 同時秘密交換プロトコルでは両者が鍵を計算して解こうとしたときにかかる時間の公平性が求められ, それは通常は「かかる時間割合が二倍以内である」という条件により保障されている. 我々の手法においては, 「かかる時間差が大きくなることはない」ことにより保障される. / Kyoto University (京都大学) / 0048 / 修士 / 修士(情報学)

調理の様子を観測した映像アーカイブの各シーンに対し，そのシーンで使用されている食材名を注釈として付与するためには，調理者が扱っている食材を常時特定している必要がある．調理中の食材は，切断・混合・加熱などの操作によって外見が変化するので，食材を継続的に追跡することによって個体を特定するアプローチをとる．操作時に容器を用いる混合・加熱の操作では，容器に取り付けたセンサなどを用いて食材を追跡することが可能である．一方，手で直接行う操作である切断では，センサ情報による追跡が不可能である．そのため本研究では切断などの直接手で操作を施している最中の食材を追跡することを目的とする．食材は切断されると，多数の断片になったりひとまとめにされたりするため，映像中での食材領域は，多数の分裂と統合を繰り返す．追跡を実現するためには，各フレームで分裂・統合した領域をフレーム間で対応付ける必要がある．しかし，分裂・統合した領域を対応付けるとき，その候補は膨大になりうるし，各領域の画像特徴は切断とともに大きく変化しうる．そのため，考えうるすべての候補から画像特徴のみを用いて正しい対応付けを求めるのは困難である．従来手法では，各時刻で分裂・統合しうる食材領域が1種類のみであるという制約のもと，追跡を実現していた．対応付け候補が多数あっても，画像特徴が変化する食材領域が１種類であることがわかっていれば，対応付けは容易である．しかしながら，この制約は，実際の調理では実現性が低い．本研究では実際の調理での有効性を考慮して上述の制約を緩和し，同色の食材については分裂・統合しうる食材は1種類である，という制約のもと，追跡を行う手法を提案する．制約の緩和により，複数種類の食材についての対応付けが一意に定まらなくなる．そこで，食材領域の画像特徴変化モデルを導入することで，食材領域の対応付け候補について尤度を求め，尤度が高い候補を採用することで，対応付けを定める．以上で述べた手法の有効性の確認のため，画像特徴変化モデルの妥当性を評価する実験を行った．実際の調理を観測した映像から，食材領域の画像特徴変化モデルにより，異色の食材からなる領域間の対応付け候補を棄却できることを示した．また，提案制約が実際の調理でどの程度満たされるかについて，調査を行った．多数のレシピをもとに，従来手法と提案手法が導入している制約が成立する割合を検証し，実際の調理における有効性が向上することを確認した． / Annotation of food stuff to a cooking video is convenient for searching scenes in which the food stuff is used. In order to annotate food stuff in the video, identification of the food stuff is required in the whole video. Food stuff undergoes various changes through cooking processes: cut, mix, boil, etc. Since it is difficult to recognize food stuff in a single captured image, we track the food stuff from the beginning of the cooking. In a scene of mixing or boiling food stuff, the cook puts the food stuff in some container: bowl, pan, etc. We can track easily the food stuff by a sensor attached to the container. In a scene of cutting food stuff, the cook manipulates the food stuff directly by the hands. We can not attach sensors directly to the food stuff. Thus we aim to track food stuff handled directly by cook’s hands in a video. The cooking processes mentioned above will split the food stuff into pieces, or gather up pieces of food stuff. This is observed in the video as split and merge of regions of the food stuff. Tracking the food stuff in the video requires finding correspondence of split and merge of regions between frames. The number of candidates of the correspondence in the whole video can be vast and the appearance of the regions of each correspondence can be different between beginning and end. Therefore, it is difficult to determine the correct correspondences from all the candidates by their appearance between beginning and end. Previous work introduces the constraint that the cook processes only one kind of food stuff. Under the constraint, the number of species of food stuff is one that causes split and merge of the regions simultaneously between frames. Since, under the constraint, a number of candidates in a frame originate from only one species of food stuff, finding correspondence is easily obtained. However, the constraint is often unsatisfied. In this work, we relax the constraint to one that is easily satisfied. We introduce the constraint that the cook processes separately the food stuff that has different appearance. For reducing ambiguity in finding correspondences caused by the relaxation, we introduce an appearance transition model of food stuff. We adopt the candidate with the highest likelihood among the candidates, and thus tracking food stuff is obtained. We implemented the method mentioned above, and evaluated the capability of calculating the likelihood and determining the correct correspondence. In addition, we assessed the possibility of the proposed constraint satisfied. The results showed that the method can increase the feasibility in real activities. / Kyoto University (京都大学) / 0048 / 修士 / 修士(情報学)

近年, さまざまな学問分野でマルチエージェントシステム(multiagent system) が重要視されている1). マルチエージェントシステムとは, 自律した主体的な個体(エージェント) が多数相互作用することで, 全体として一つのまとまりを示すシステムをいう. 中でも自然界における魚や鳥の群れはマルチエージェントシステムの代表例である. こうした自然界のいわゆる「群れ行動」は, 「群れにはリーダーがおり, 各個体はその動きに追従する」といったいわゆるトップダウン的なシステムではなく, Aoki(1982)6) やReynolds (1987)2, 7) らが主張する, 「各個体間のシンプルな相互作用のみで集団全体として群れ行動が創発される」というボトムアップ的なシステムとする見方が有力である. 事実, 群れ行動が持つ個体間の強固な結合や, 群れの形状の柔軟性などはいずれもマルチエージェントシステムが持つとされる頑強性(robustness), 柔軟性(flexibility)といった特徴1) と一致し, 今日の映画などのアミューズメントの分野ではその「リアルさ」から群れ行動の再現のほとんどではマルチエージェントによるボトムアップ的な群れアルゴリズムが用いられている2). 中でもReynolds が1987 年に発表したBoid アルゴリズム7) は, 群れの相互作用をエージェント間の3 つの単純なルール(4.1 節参照) でまとめた有名な群れ再現アルゴリズムで, 映画「BatmanReturns」(Tim Burto,1992) においてコウモリやペンギンの群れを表現する際に用いられたことでも注目された2). こうした, 群れ行動をマルチエージェントシステムとして再現し応用する試みはアミューズメント分野に留まらず, 生物学8) や宇宙工学9) などの幅広い分野で研究されている.しかし応用の拡大の一方で, 計算機上に「再現」されたマルチエージェントによるそれら「群れ」を自然界の生物の群れ行動と「実証的」に比較し評価することは, 実測データの取得/解析の困難さから現在までほとんど研究されてこなかった. こうした比較なしでは自然界の群れ行動の原理の追求はもちろんのこと, その再現とされる群れ(群知能) シミュレーションの妥当性も実証的に確かめることはできない. これにより群れ行動の研究が各研究者毎の「主観」によるものに留まり, 今後の応用/発展への大きな妨げとなることが危惧される.そこで本稿では2008 年にBallerini らイタリア研究グループが発表した自然界(実世界) の「ムクドリの群れ」に対する実測データと, 彼らがそこから実証的に示す「異方性の創発」という多体系の協力現象に着目する5). そしてこの現象がReynolds によるBoid アルゴリズムを用いて作成した群知能シミュレーションによって再現でき, またそれに基づいて計算されるある種の統計量が「自然な群れ」「群れらしい群れ」が形成されたことの客観的な判断指標ともなりうることを計算機実験により示す. 本研究は実世界と群知能シミュレーションとの実証的な比較, 群知能シミュレーションの妥当性評価というこれまで十分な研究がなされてこなかった分野への新たな足がかりを提示するものである. / Hokkaido University (北海道大学) / 学士

近年、数秒オーダでの時間スケールにおける価格変動を記録した高頻度金融データの入手が可能となり、既存の経済理論、なかでも金融工学において、その数学的な取り扱いの容易さから用いられてきたいくつかの仮説/仮定が、これら高頻度データとの整合性の観点から見直されてきている。特に、ブラック・ショールズ方程式の導出において仮定される「金融商品の価格変動はブラウン運動に従う」という仮説、つまり「価格変動幅の分布が正規分布に従う」という前提は、実際のデータから観測される分布が「広い裾(Fat tails)」を持つことが明らかにされることで修正の必要性が認識されるようになった。このような大きな変動が比較的大きな確率で生じる確率過程としてはレビ・フライト(Levy flight) などが知られており、この場合の価格変動幅の確率分布は裾が広いレビ分布となる。しかし、このような金融商品の価格変動をより根源的に説明するためには、その商品の価格を決定する市場のメカニズムを深く理解することが不可欠である。例えば、市場には多くのトレーダが参加し、彼らは各自が商品の価格変動や政治情勢など様々な情報を考慮することで、自分の利得を可能な限り最大化する戦略を立て、金融商品を売り買いするが、そのようなトレーダ群の意思決定の結果として金融商品の価格変動が生じ、それを我々は観測するわけである。従って、このような社会システムは自ずとある種の「階層性」を持つことになる。つまり、「ミクロ」なレベルでのトレーダの判断から「マクロ」なレベルの金融商品の価格変動までの間には様々なスケールの経済活動が複雑に絡み合っており、このミクロとマクロの関連性を理解すること、言い方を変えれば、金融商品の価格変動(マクロ) をトレーダ群の意思決定(ミクロ) の結果として矛盾なく説明することは野心的課題ではあるが、既存の経済理論を「多体問題」「統計力学」の観点から一歩進めるためには重要なプロセスであり、そのような研究は既存の経済学に対し新しい視点を提供することが期待できる。そこで本研究ではこの目標に対する第一歩として、高頻度金融データの価格変動時間間隔に着目し、この統計的性質を様々な観点から調べることで、金融工学における計算機シミュレーションで多くの場合に仮定されてきた「価格変動に関するポアソン過程」の前提の妥当性を検討する。ついで、この統計的性質をミクロなトレーダ群の意思決定の結果として再現するため、「マイノリティゲーム」と呼ばれる繰り返しゲームに対し、その第一通過過程を用いることで、得られる価格変動間隔の統計的性質を実データ解析による結果と比較する。これらの結果、従来の「ポアソン過程」の前提は必ずしも正しくなく、短い時間スケールの変動間隔と長い時間スケールの変動間隔の間にはある種の「クロスオーバー(crossover:分布の切り変わり)」が生じ、分布は指数則から裾の広い分布へ変化することが実データ解析/マイノリティゲームによるシミュレーション双方で普遍的に現れることを明らかにする。 / Hokkaido University (北海道大学) / 学士

ソニーバンクレートに代表される金融データは「時刻」と「価格」からなる2 次元データであるが, 一般の金融データには市場価格の他, 各トレーダの提示する「売り注文」の値段の最大値(Bid)と「買い注文」の値段の最小値(Ask) がその時刻とともに与えられるものも存在する. このように,顧客が自らの「売り注文」と「買い注文」を同時に提示するような金融取引きをダブルオークション(Double-auction) と呼び, そこでどのように市場価格が決定し, 証券会社など取引き仲介会社の利益となるBid とAsk の差として定義されるBid-Ask スプレッド(Bid-Ask spread) が1どのような統計的性質を持ち, 市場にどのような影響を与えるのかに関してはまだ不明な点が多く,実データとしては十分なストックがあるものの, 現時点で十分な数理科学的な理解が得られているとは言いがたい.そこで, 本論文ではダブルオークション・システムにおける金融時系列データを確率過程としてとらえ, その確率過程をマクロに特徴付ける統計量を選択し, それを説明するための「マクロ的(現象論的) 視点」および「ミクロ的(構成論的) 視点」から構築される確率モデルをそれぞれ導入し,得られる結果を「スプレッド変動型」及び「スプレッド一定型」実データと比較検討し, 確率モデルと実データの振る舞いの類似性/相違性からモデル自身の妥当性と問題点を探って行く. このような社会現象/経済現象に関するモデリングを行う際, 我々が常に考えなければならないのは, それら確率モデルをどのような視点で構築し, その確率モデルの生成する時系列と実データの何を比較したらよいのか, また, その観点で両者の差が大きい場合には確率モデルの何を修正/改良したらよいのか, またそのような確率モデルの適切な候補に対し, 工学的にどのような応用が考えられるかということなどである. ここでは現象論的モデルとしてMadhavan-Richardson-Roomans モデルを取り上げ, このモデルの振る舞いを自己相関関数(Auto-Correlation Function),応答関数(Response Function)(あるいは遅延衝撃関数(lagged impact function))と呼ばれる時変な統計量を介して実データと比較検討する. Madhavan-Richardson-Roomans モデルはスプレッド一定の仮定のもとに構築される確率モデルのため, スプレッド変動型データを説明することは困難であることが予想される. そこで, 本論文ではミクロ的視点, 構成論的視点, すなわち,ゲーム理論的視点からの確率モデルとして繰り返しゲームのひとつであるマイノリティ・ゲームを改良し, このゲーム理論を用いてダブルオークション・システムを構築し,人工的にスプレッドの揺らぎを生成することで上記2 種類の統計量の振る舞いを定性的に説明することを試みる. / Hokkaido University (北海道大学) / 学士

Kyoto University (京都大学) / 0048 / 新制・課程博士 / 博士(情報学) / 甲第10351号 / 情博第75号 / 新制||情||19(附属図書館) / UT51-2003-H772 / 京都大学大学院情報学研究科通信情報システム専攻 / (主査)教授 小野寺 秀俊, 教授 中村 行宏, 教授 富田 眞治 / 学位規則第4条第1項該当

Kyoto University (京都大学) / 0048 / 新制・論文博士 / 博士(情報学) / 乙第11255号 / 論情博第40号 / 新制||情||21(附属図書館) / UT51-2003-H917 / (主査)教授 松山 隆司, 教授 乾 敏郎, 教授 美濃 導彦 / 学位規則第4条第2項該当