Theses

修士論文の概要

2017 年度卒

他視点のオブジェクトを検索可能な画像検索システムの構築 (雛形 奎祐)


本研究では,画像を入力として,その画像中のオブジェクトをユーザーが指定した方向から見た画像を提示する検索システムを提案する.従来の画像検索システムでは,画像からさまざまな特徴量を抽出し,その特徴量を用いて画像同士の類似度を計算して,類似度の
降順に検索結果を提示している.しかしこの性質上,従来の画像検索システムは,あるオブジェクトを一方から見た画像を入力として,そのオブジェクトを他の特定の方向から見た画像を指定して画像検索を行うことが困難である.そこで本研究では,オブジェクトの3D情報を利用し,画像中のオブジェクトに対応する3Dモデルの射影を考えることで解決を図り,提案したシステムの有効性の評価を行った.


大規模可変長データを対象としたCPU・ GPU協調並列処理に関する研究 (木村 健人)


本研究では,BSP(Bulk Synchronous Parallel)モデルと呼ばれる並列計算のモデルを基にしてCPU・GPUを協調的に並列に用いて文書集合のような大規模可変長データの処理を行う並列処理フレームワークを提案する.メモリサイズを超える大規模データを扱う場合,プログラマ自身がデータの分割をする必要がある.そこで本提案では,メモリ上には乗り切らない大規模な複数の入力データでも自動で分割し,可変長データを扱う処理を行う.その際,各スレッドへの処理の割り当て回数を減らすために複数の処理をまとめて割り当てる.また,可変長データの処理を効率的に行うために,非効率なGPU処理中の動的なメモリ確保が発生しないよう必要なメモリサイズを計算する事前処理を行う.さらに,処理中のデータ保存にKVSを用いることで容易に分散環境へスケールアウトできる拡張性を備える.


GPUを用いた文書処理の高速化手法に関する研究 (若月 駿尭)


情報検索で利用される文書処理として,クエリと文書の適合度を測る指標であるOkapi BM25やクエリ尤度モデルに基づく文書中の語の重みを,GPU上で効率的に動作する簡潔データ構造による辞書の導入とデータ並列プリミティブの組み合わせにより,効率的に計算する手法について提案する.GPU上でMapReduceを用いて文書処理を行う手法では,スレッド間での負荷の偏りによる性能劣化や,頻繁な文字列比較が必要なソートのコストが課題となっていた.本研究ではGPU上で効率的なデータ並列プリミティブを適切に組み合わせることで負荷分散を実現し,また辞書を新たなデータ並列プリミティブとして導入することで文字列比較コストを削減した計算手法を提案する.


分散データストア上の大規模多次元データに対する集約演算の効率化 (渡 佑也)


本研究では,大規模多次元データに対する集約演算を効率化する手法を提案する.OLAPやセンサデータの分析において,そのような集約演算は重要な役割を果たす.提案手法では,RDBと分散KVSを組み合わせて両者の利点を相互に活用するほか,データを部分集合に分割し,部分集合ごとに集約値を事前計算することで,データのスキャン量を削減してクエリ処理性能を向上させる.評価実験を行った結果,提案手法は,既存のRDBや分散KVS,および先行研究よりも高いクエリ処理性能を達成したほか,データ挿入性能もRDBや先行研究を上回った.また,クエリ処理と挿入が混在する状況でも,既存方式に比べて高い処理スループットを実現した.


2016 年度卒

クラウドストレージにおけるマテリアライズドビューを利用した検索処理の効率化に関する研究 (今井 良一)


クラウドストレージ上の分散キーバリューストア(分散KVS)で管理されるビッグデータの検索処理を効率化するために,マテリアライズドビュー(MV)を作成する際の,MVの適切な管理方法を提案する.データ管理システムには分散KVSや関係データベース(RDB)があるが,一般的にビッグデータは分散KVSで管理される.複数属性の範囲検索等の複雑な検索処理は,分散KVSでは効率的な実行は困難であるが,検索で頻繁に利用されるデータ範囲が小さい場合には,RDBでは効率的な実行は可能である.本研究では,分散KVSやRDBの特性を利用したMVの管理方法を提案する.また,クラウドストレージは従量課金でありMVの利用はコストがかかるが,その利用コストの最小化や検索処理時間の最適化の重視度は各ユーザで異なるため,それぞれの要求に応じたMVの適切な管理方法を提案する.


グラフモデルを用いたプレイリスト生成手法に関する研究 (植田 聖司)


本研究では,楽曲,アーティスト,プレイリスト,ユーザの関係情報をグラフで表現し,遷移確率に基づき楽曲を推薦するプレイリスト生成手法を提案する.近年,音楽推薦の研究分野では,ユーザの再生した複数の楽曲からその次に再生するのに相応しい楽曲を推薦するプレイリスト生成が取り組まれている.既存手法は,要素間の一つの関係情報のみを用いており,ユーザが持つ潜在的で多様なプレイリストの生成目的に十分に対応できていなかった.そこで,本研究はプレイリストの持つ複数の要素をグラフで表現し,グラフにおける遷移確率から推薦対象楽曲を決定する.これにより,要素間の重要度の比重を調整することなく,画一的に,複数の要素の情報を統合したプレイリスト生成手法を提案する.


ハードウェアトランザクショナルメモリを利用した並行 B-Tree の並行性向上に関する研究 (蔡 弘聖)


並行データオブジェクトの一種である並行B-treeに対してハードウェアトランザクショナルメモリ(HTM)を適用することで並行性を向上させる手法を提案する.マルチスレッドで動作する並行データオブジェクトにおいてはデータの整合性を保つための排他制御法としてロックやnon-blockingアルゴリズムといった手法がよく用いられてきた.多くの状況下でnon-blockingアルゴリズムがロックに比べて性能が良いが実装が困難である場合が多く,データベース等のインデックスに用いられるB-treeにおいても,完全にnon-blockingな排他制御は存在しない.そこで本研究ではHTMを並行B-treeに対しアクセス特性に応じて適用する手法を提案する.


Copula に基づく情報検索の高度化と問い合わせ処理に関する研究 (佐々木 夢)


Copula を利用した情報検索システムにおける情報検索の高度化と高速化について研究を行い,(1)高度な文書検索のための新しい可読性指標,ならびに(2)複数の指標を組み合わせて高精度な検索を行う際の高速な問い合わせ処理方式について提案する.多様で複雑な情報要求に応えるために,Copulaを用いて複数の評価尺度を統合する手法が提案されているが,適合度以外の評価尺度の統合は行われていない.また,スコアリング手法が複雑化するにつれ,高速な問い合わせ処理が必要となる.本研究では,文書の可読性指標を提案し,Copulaを用いた適合度と可読性の統合を行うとともに,検索の高速化のために Top-k 検索アルゴリズムを提案する.


2015 年度卒

コピュラを利用した情報検索に関する研究 (小松田 卓也)

komatsuda
確率モデルであるCopulaを多峰的に表現することで,複数の評価尺度を統合するスコアリング手法を提案する.複数の評価尺度を用いた情報検索は線形結合やランキング学習によって実現されるが,線形結合には評価尺度間の依存関係を考慮していない,ランキング学習には結果に対する理由付けが困難であるという問題がある.Copulaは評価尺度間の依存関係を考慮するために前述の問題点を解決できるが,既存のCopulaを用いたスコア統合式は単峰的なCopulaを用いているため,複雑な依存関係を捉えることが難しい.そこで本研究では,複雑な依存関係を捉えることができる混合Copulaを用いたスコア統合式を提案する.


ハードウェアトランザクショナルメモリを利用した高性能データ構造に関する研究 (永井 光)

nagai
様々な排他制御法を利用して実装された個々のデータ構造の動的特性から、これらを組み合せたデータ構造の特性を推定し、最適に組み合わせる手法を提案する。並行プログラミングにおける排他制御法としてロック、Non-Blocking法、トランザクショナルメモリを利用する方法の三種が存在し、共有メモリ中のデータ構造へのアクセス特性に応じて選択されるが、二つ以上のデータ構造を組み合わせる場合において最適な排他制御法の組み合わせは明らかではない。本研究ではLeast Recent Usedアルゴリズムの実装を例に、それを構成するリストとハッシュ表を各排他制御法で実装し、それぞれの動的特性を明らかにした後、最適な組み合わせ法を考察し、検証した。


学士論文の概要

2017 年度卒

密度ベースクラスタリングによる多峰性コピュラを用いた情報検索の高精度化 (左近 健太)

本研究では,ユーザの多様な情報要求に対応するために,複数の検索モデルで求めた各文書の適合度を確率モデルであるコピュラにより統合するにあたり,密度ベースのクラスタリング手法であるDBSCANを用いることを提案する.これにより,距離ベースのクラスタリング手法を使った既存手法の問題点であった外れ値の影響を減らし,情報検索の高精度化を目指す.また,単純な密度ベースクラスタリング結果を用いただけでは不適合文書を考慮していない.そこで,適合文書と不適合文書の比率を考慮してクラスタリングを行うことで,さらなる高精度化を目指す.


離散値特徴量や 特異な嗜好ケースを考慮した コピュラを用いた推薦システム (朝日 諒)

本研究では,コピュラを用いた既存の推薦手法が扱える嗜好ケースの拡張を試みた.
既存手法はコピュラという確率モデルでユーザの嗜好アイテムから嗜好モデルを学習し推薦を行うもので,学習結果が解釈し易いという利点がある.しかし,既存手法は特徴量の分布が正規分布であるため離散値分布に対応できない.さらに,特徴量値に嗜好の強さが単調増加するという前提に反する嗜好に対応できない.よって前者の問題点に対しカーネル密度推定で対応し,後者の問題点に対し許容範囲フィルターで対応する手法を提案した.評価実験の結果,指摘した問題点まで想定したデータセットで既存手法より有意に(p < 0.01) 性能がよいことを確認した.


2016 年度卒

コピュラを用いた情報推薦に関する研究 (鈴木 崇弘)


情報推薦において, 学習結果の理解が容易な確率モデルであるコピュラを用いたユーザプロファイリング手法を提案する.コピュラを用いたパラメータ学習手法は既に情報検索の分野で提案されているが, その手法では特定のパラメータへの重み付けは行われていないため, ユーザの嗜好を柔軟に表現することができない. 本研究ではKLダイバージェンスを用いて, アイテムの各特徴パラメータに対するユーザの関心度を算出し, それらの値を元にパラメータの選定を行った後にコピュラを用いて学習を行う.評価実験を行った結果, 提案手法は従来の機械学習手法や既存のコピュラによる手法よりも高精度で推薦を行えることを示した.


ヒストグラムとカーネル密度推定を組み合わせた集約演算結果の推定 (張 涵)


ビッグデータ分析には高速な集約演算が必要である背景を踏まえ,分散 KVS 上の集約演算処理について,データ要約を導入し許容範囲内の誤差で結果を推定する手法を提案する.過去に,部分集約法を利用した多次元データに対する集約演算を効率化する手法が提案されているが,この手法では依然としてクエリスループットの低下の原因となるデータの全スキャンが発生する.提案手法では,従来手法にヒストグラム及びカーネル密度推定を用いたデータ要約を導入して,集約演算処理時には結果を推定し,データの全スキャンを完全に回避することで処理を効率化する.5 次元データを用いた評価実験の結果,従来手法と比べ高いクエリスループットを実現し,かつ平均誤差5%以下の推定精度を達成した.


GPU を用いた大規模な文書に対する高精度検索のための高速な重み付け計算 (柳本 晟熙)


GPUを用いて大規模な文書集合に含まれる索引語に対して重み付け計算を行う手法を提案する.VRAM(GPUのメモリ)のサイズに限りがある中で大規模な文書集合を扱うために,提案手法では文書集合を複数のチャンク(小さな文書集合)に分割して処理を行う.また,パイプライン処理を行うことで高速化を実現する.提案手法により,先行研究では扱うことができなかったサイズの文書集合を扱うことが可能となった.評価実験より, チャンクサイズをVRAMに格納して計算を行うことができる最大のサイズよりも小さく設定することで全体の実行時間が短くなることが判明した. この実測値による最適なチャンクサイズは,作成したコストモデルによって推定された最適値と一致する.

2015 年度卒

スカイライン演算を用いたユーザ嗜好を考慮した情報推薦のランキング手法の精度改善について (岸田 脩平)

kishida
情報推薦において,スカイライン演算で推薦する候補を絞った後にランキングする手法として,ユーザの潜在的な嗜好を反映させる手法やアイテムの密度を考慮した手法を新たに提案する.過去に,スカイライン演算を利用したスコアリング手法が提案され,限られた実験環境においては有用性が確認された.より大規模なユーザスタディを行った結果,ユーザの嗜好の優先度と意思決定における重要度は必ずしも一致しないという問題が明らかになったため,これらを解決すべくユーザフィードバックを用いた手法や密集したアイテムのスコアを均一化する手法を考案した.評価実験の結果,提案手法は従来手法より高精度な推薦が可能であることを示した.


GPU上の効率的な辞書の構成に関する研究 (若月 駿尭)

wakatsuki
大規模な語彙をGPU上で扱う辞書として,簡潔データ構造を用いるトライ木のデータ構造及び参照アルゴリズムを,GPUの特性を考慮し省メモリかつメモリへのランダムアクセスの少ない方法で実装する手法を提案する .GPU を用いて効率的にテキスト処理を行うためには,単語を ID に変換する辞書データ構造が必要である.英単語の語彙集合を用いて提案手法を評価した結果,提案手法は一般的なトライ木の実装方法である状態遷移表 (STT) を用いたトライ木と比較して40分の1以下のメモリ使用量であり,単語から ID への変換に要する実行時間について,辞書に含まれる語彙数が多いとき,提案手法は STT よりも実行時間が短くなることが判明した.


RDBとKVSを相互に利用した多次元データに対する集約演算の効率化 (渡 佑也)

watari
本研究では,RDBとKVSを相互に活用して多次元データに対する集約演算を効率化する手法を提案する.提案手法では,多次元データを複数のグリッドに分割した上で,グリッドごとの集約値,すなわち部分集約結果を事前に計算する.その際,膨大な量に上る実データや頻繁に更新される部分集約結果をKVSで保持し,実データほどデータサイズは多くないが複雑な構造を持つグリッド分割の情報をRDBで保持することで,両者の利点を活用して集約演算を効率化した.評価実験として4次元の範囲クエリを処理した結果,提案手法はパラメータを適切に設定することで,RDBやKVSを単体で用いた場合に比べ高いクエリスループットを実現した.