著者

林 淑隆 獅々堀正幹 伊与田 敦 津田 和彦 青江 順一

雑誌

情報処理学会研究報告自然言語処理(NL)

巻号頁・発行日

vol.1994, no.104, pp.63-70, 1994-11-17

---

文献検索システムなどにおいて、キーワードをいかに効率良く、かつ正確に抽出するかは重要な課題である。本論文では、日本語文書においてキーワードとなることが多い複合語が、キーワード抽出の際に多大なマッチング処理を要することに着目し、複数キーワードのストリングパターンマッチングマシンの手法を応用した複合語キーワードの効率的な抽出法を提案する。本手法は、形態素解析部と複合語キーワード抽出マシンAC部、複合語キーワード候補マシンAC部からなる。14個の複合語文法構造と10個のキーワード評価ルールを定義し、26文書について実験評価を行った結果、形態素解析部を除く平均抽出速度は16.58ミリ秒、文書1KBあたり6.18ミリ秒の結果が得られ、本手法の有効性を確認した。また、抽出キーワードの選別で必要となる重なり語の抽出は、候補マシンACにより効率的に行えるので、利用者はこのマシンACに対する抽出ルールを決定することで、多種多様なキーワードを決定することが可能となる。Extracting keywords efficiently is an important task in text retrieval systems. In Japanese text, there are many compound words consisting some kinds of characters (Katakana, Kanji, etc.) and the text has no delimiter among words. Therefore, extracting keywords from such a text takes a lot of time. This paper presents a technique of detecting keywords from compound keywords by introducing a set of rules, which are conditions for keywords construction. A string pattern matching machine for a finit number of patterns is applied to matching of the rules and storing keyword candidates. From the simulation results for 26 Japanese text files that the algorithm presented has performed 6.2ms/KB.

著者

柘植 覚 獅々堀正幹 北 研二

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告自然言語処理(NL) (ISSN:09196072)

巻号頁・発行日

vol.2001, no.20, pp.1-6, 2001-03-05

被引用文献数

4

---

ベクトル空間モデル(Vector Space Model; VSM)は情報検索における代表的な検索モデルであり,検索対象文書および検索質問を多次元ベクトルで表現するという特徴を持っている.しかし,これらのベクトルは一般にスパースかつ高次元であるため,計算機のメモリによる制限や検索時間の増大などの問題が生じる.また,次元が増加するに連れ,文書中に含まれる不必要な単語がノイズ的な影響を及ぼし検索精度を低下させてしまうという現象も起こってくる.本稿では,Non-negative Matrix Factorization(NMF)を用いたベクトル空間モデルの次元圧縮手法を提案する.NMFは非負行列を2つの非負行列の積に分解する手法であり,分解された非負の2行列は基底行列とその基底のもとでの座標値から成る行列とみなすことができる.基底行列のランクを元の行列のランクより小さくすることにより,次元圧縮が可能となる.NMFは,主成分分析や特異値分解などと異なり,非負制約条件で行列分解を行うため,元の行列を減算を伴わない加算のみの線形結合で表現することができる.これは部分から全体を構成するという我々の直観を反映している.また,NMFは単純な繰り返し演算のみで実行可能であるため,大規模な行列に対して,計算コストや記憶容量の点で他の次元削減手法よりも優れている.MEDLINEコレクションを用いた検索実験を行い,NMFは通常のベクトル空間モデルよりも高い検索性能を示すことができた.The Vector Space Model(VSM) is a conventional information retrieval model, which represents a document collection by a term-by-document matrix. Since term-by-document matrices are usually high-dimensional and sparse, they are susceptible to noise and are also difficult to capture the underlying semantic structure. Additionally, the storage and processing of such matrices places great demands on computing resources. Dimensionality reduction is a way to overcome these problems. Principal Component Analysis(PCA) and Singular Value Decomposition(SVD) are popular techniques for dimensionality reduction based on matrix decomposition, but they contain both positive and negative values in the decomposed matrices. In the work described here, we use non-negative matrix factorization(NMF) for dimensionality reduction of the vector space model. Since decomposed matrices by NMF only contain non-negative values, the original data is represented by only additive, not subtractive, combinations of the basis vectors. This characteristic of parts-based representation is appealing because it reflects the intuitive notion of combining parts to form a whole. Also NMF computation is based on the simple iterative algorithm, it is therefore advantageous for applications involving large matrices. Using MEDLINE collection, we experimentally showed that NMF offers great improvement over the vector space model.

著者

獅々堀正幹 大西 泰代 柘植 覚 北 研二

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.48, no.1, pp.300-311, 2007-01-15

被引用文献数

1

---

近年,楽曲配信サービスの普及により,容易に音楽データをダウンロードして試聴できるようになった.しかし,サーバ側で蓄積している音楽データが膨大になるにつれ,音楽データに対する効率的な検索手法が必要になっている.特にハミングを入力とする検索手法が近年活発に研究されており,音楽特徴量間の類似度計算にDP マッチングやユークリッド距離を用いる手法が主流であった.本論文では,距離尺度としてEarth Mover's Distance(EMD)を用いたハミング検索手法を提案する.EMD は輸送問題における輸送コストの最適解であり,本手法では輸送問題における各供給地が有する資源量を各音符の音長,輸送コストを各音符の出現時間と音高情報から算出することで,リズムと音程との類似度を同じ距離尺度で計り,全体の曲調が類似した曲を検索する.さらに,EMD の計算量が音符数に対して指数関数的に増加することに着目し,検索精度を維持しつつ計算コストを低減可能な音楽特徴量を提案する.約500 曲の音楽データベースに対してハミングデータ40 曲を入力とした評価実験を行った結果,ユークリッド距離を用いる手法より検索結果上位10 位以内に正解データが出現する割合が約30%向上した.また,DP マッチングを用いる手法と比べて,極端に音高の外れた音符を含むハミングデータに対する柔軟性を確認した. 付録:<a href="http://www.ipsj.or.jp/08editt/contents/JNL4801/index.html#28"target="_brank">http://www.ipsj.or.jp/08editt/contents/JNL4801/index.html#28</a>Music retrieval systems are extremely useful for collecting digital music data from on-line music distribution sites. Especially, there is a great need to develop effective techniques for content-based music retrieval systems, which can retrieve by humming query. The main issues in this research is how to decide the similarity of each music features extracted from music data. In order to calculate the similarity, some conventional methods use Euclid distance or DP matching, but it is very hard to solve the problem of the vagueness of humming query. In this paper, we propose a new similar music retrieval method based on humming query using the Earth Mover's Distance as the distance measure. Computing the EMD is based on a solution to the transportation problem, and the EMD is applied as the distance measure on similar image retrieval systems. In addition, we focus that the time complexity of the EMD is exponential worst case toward the number of notes, the improved method to decrease the number of notes in the music feature is also proposed. Experimental results show that the proposed method can improve the retrieval precision of conventional systems.appendices:<a href="http://www.ipsj.or.jp/08editt/contents/JNL4801/index.html#28"target="_brank">http://www.ipsj.or.jp/08editt/contents/JNL4801/index.html#28</a>

著者

好田 勲 柘植 覚 獅々堀正幹 北 研二

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告自然言語処理(NL) (ISSN:09196072)

巻号頁・発行日

vol.2003, no.23, pp.17-22, 2003-03-06

被引用文献数

4

---

ベクトル空間モデル(Vector Space Model;VSM)は情報検索における代表的な検索モデルであり,検索対象文書および検索質問を多次元ベクトルで表現するう特徴を持っている.しかし,これらのベクトルは一般にスパースかつ高次元であるため,計算機のメモリによる制限や検索時間の増大などの問題が生じる.また,次元が増加するに連れ,文書中に含まれる不必要な索引語がノイズ的な影響を及ぼし検索精度を低下させてしまうという現象も起こってくる.以前,我々はこの問題を解決するため,Non-negative Matrix Factorization(NMF)を用いたVSMの次元圧縮手法を提案した.しかし,メモリの問題がまだ存在する.そこで,本稿では,k-means NMF を用いたVSMの次元圧縮手法を提案する.また,スパースな行列に対し有効な検索手法である検索質問拡張にNMFを用いる手法を提案する.MEDLINEコレクションを用いた検索実験を行った結果,NMFを用いた場合とk-means NMFを用いた場合では,検索精度を劣化することなく計算に必要なメモリを約$1/10$に軽減することができた.また,NMFを用いた検索質問拡張もVSMよりも高い検索精度を示すことができた.The Vector Space Model (VSM) is a conventional information retrieval model, which represents a document collection by a term-by-document matrix. Since term-by-document matrices are usually high-dimensional and sparse, they are susceptible to noise and are also difficult to capture the underlying semantic structure.Additionally, the storage and processing of such matrices places greatdemands on computing resources. Dimensionality reduction is a way toovercome these problems. We proposed non-negative matrix factorization(NMF) for dimensionality reduction of the vector space model.However,this method did not overcome memory problems. Hence, we proposek-means NMF for dimensionality reduction of the vector space model. And,we propose query expansion using NMF in this paper.Using MEDLINE collection, we experimentally showed that k-means NMF offers great improvement over the vector space model.

著者

北 研二 獅々堀正幹 大恵俊一郎

雑誌

情報処理学会研究報告自然言語処理(NL)

巻号頁・発行日

vol.2003, no.98(2003-NL-157), pp.9-16, 2003-09-29

---

高次元空間における最近傍検索(nearest neighbor search)は、マルチメディア・コンテンツ検索、データ・マイニング、パターン認識等の分野における重要な研究課題の1つである。高次元空間では、ある点の最近点と最遠点との間に距離的な差が生じなくなるという現象が起こるため、効率的な多次元検索手法を設計することが極度に困難となる。本稿では、線形探索アルゴリズムにおける距離計算中の不要な演算を削減することにより、きわめて高速な最近傍検索アルゴリズムを提案する。さらに、不必要な演算を早期検出するために、要素の分散値を用いた次元ソート法、並びに主成分分析に基づくデータ変換法を提案する。実験によると、従来の SR-tree や VP-tree 等よりも 20倍?50倍高速であり、高次元の場合にも性能の劣化はほとんどない。

著者

西川 伸紀 獅々堀正幹 柘植 覚 北 研二

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌データベース(TOD) (ISSN:18827799)

巻号頁・発行日

vol.48, no.20, pp.28-38, 2007-12-15

参考文献数

15

---

本研究では映像内の文字情報である字幕に着目した字幕検索システムを開発する.従来,字幕検索は映像内に出現する字幕に対して文字認識を行う手法が主流であった.しかし,この手法では,事前に文字認識を行うための時間コストが必要であり,また,完全な文字認識結果が得られない場合には検索精度が低下するという問題があった.本論文では,上記の問題点を解決した高精度かつ高速な字幕検索手法を提案する.字幕検索を実現するためには,映像中に出現するすべての字幕を正確に認識する必要はなく,検索キーに対する字幕だけを認識できれば適切な検索結果を得ることができる.そこで本手法では,各字幕の文字画像特徴量と検索キーに対応する文字画像特徴量との距離に基づいて該当の字幕が出現するフレームを検索する.また,各字幕の文字画像特徴量を多次元索引化することで,検索キーの文字画像特徴量との距離計算を高速化する.さらに,本手法では検索過程で特徴量照合を行うため,前処理で文字認識処理が必要でなく,時間コストを軽減することができる.実際に3時間分の映像データに対して映像中の出現頻度が比較的多い91単語を用いて検索実験を行った結果,1-gram特徴量を用いた場合には最大98.61%,2-gram特徴量を用いた場合には最大99.59%の平均適合率を得ることができた.検索時間に関しても,2-gram特徴量を用いた場合でも約0.5秒で検索結果を得ることができた.Video telop retrieval methods based on telop characters can retrieve the corresponding telops to the query from the huge video data. The conventional methods make the text data from the image data of telop characters by recognizing all telop characters in the video data, and then the full text search is operated toward the recognized text data. The conventional methods can not retrieve with high precision, because all telop characters can not recognize as their right characters perfectly. In this paper, a new video telop retrieval method based on telop characters is proposed. In order to specify the suitable telop, this method recognizes the only corresponding telop characters to the query keyword not all characters. This method calculates the distance between each image features of telop characters and template image features of query keyword. The number of distance calculations can decrease by indexing the multidimensional data for image features of telop characters. Experimental results, using 91 query keywords, show that the average precision of proposed method using 1-gram feature becomes 98.61%, and using 2-gram feature becomes 99.59%. Moreover, the retrieval time can be obtained in about 0.5 seconds when using 2-gram feature.

著者

大野将樹 岡村亮一 獅々堀正幹 沼尾雅之

出版者

一般社団法人情報処理学会

雑誌

研究報告音楽情報科学(MUS)

巻号頁・発行日

vol.2013, no.35, pp.1-6, 2013-08-24

---

本稿では,音楽的・音響的に違和感の少ないメドレー曲を自動的に生成する手法を提案する.メドレー曲を構成する楽曲断片間の連結の妥当性に関する指標として,局所的接続と大局的接続がある.本研究では,局所的接続と大局的接続に対する個人の嗜好をシステムに反映することによって,違和感のないメドレーを生成する.7 段階評価による被験者実験により,パーソナライズを実施しなかった場合のメドレー曲は 3.74,提案手法は 5.02 のスコアが得られ,個人の嗜好を反映した提案手法の有効性が示された.

著者

柘植 覚 獅々堀正幹 黒岩 眞吾 北 研二

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.44, no.1, pp.59-67, 2003-01-15

被引用文献数

5

---

近年のインターネット技術の発展により,World Wide Web(WWW)を代表とする個人で扱えるオンラインテキストデータの量が増加している.それにともない,莫大なテキストデータ中から必要な情報を検索する機会も増え,情報検索に関する研究への関心が高まっている.情報検索システムとして,検索対象文書と検索質問を多次元ベクトルで表現するベクトル空間モデル(VSM: Vector Space Model)が広く使用されている.VSMを用いた検索システムの精度を改善する手法の1つとして,適合性フィードバック手法(Relevance Feedback)が提案されている.この手法は,VSMを用いた1次検索結果に対し,利用者が適合・不適合の判断を行いその情報をシステムにフィードバックし,再検索を行うことで検索精度を向上させている.本論文では,この利用者からのフィードバック情報を検索対象文書全体の適合・不適合の判別に用いた.判別を行う識別器として,従来手法より,判別の能力が高く,汎化性に優れたサポートベクターマシン(SVM: Support Vector Machine)を用いた.このフィードバック手法をサポートベクターマシンによる適合性フィードバックとして本論文で提案する.日本語テストコレクション(BMIR-J2)を用いた類似文書検索実験において,提案手法は従来手法と比較し,利用者が判断し,システムにフィードバックされる文書数が50の場合,24.0%の検索精度改善を得ることが可能であった.With the rapid growth of online information, e.g., the World Wide Web(WWW), a large collection of full-text documents is available andopportunity for getting a useful piece of information is increased.Information Retrieval (IR) is now becoming one of the most importantissues for handling large text data.Relevance feedback is a technique that improves retrieval performancebased on relevance judgments from the user. Here, we propose therelevance feedback method using Support Vector Machine (SVM).Experiment results on Japanese test collection BMIR-J2 show that theproposed method is useful feedback method comparing to theconventional feedback method. Especially, the proposed method improvedthe performance of IR system.