著者

持橋 大地 山田 武士 上田 修功

雑誌

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

巻号頁・発行日

vol.2009, no.36(2009-NL-190), pp.49-49, 2009-03-18

---

本論文では,教師データや辞書を全く必要とせず,あらゆる言語に適用できる教師なし形態素解析器および言語モデルを提案する。観測された文字列を,文字 n グラム ‐ 単語 n グラムをノンパラメトリックベイズ法の枠組で統合した確率モデルからの出力とみなし,MCMC 法と動的計画法を用いて,繰り返し 「単語」 を推定する。提案法は,あらゆる言語の生文字列から直接,高精度で未知語のない n グラム言語モデルを構築する方法ともみなすことができる。

著者

山田 武士 斉藤 和己 上田 修功

出版者

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

雑誌

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

巻号頁・発行日

vol.44, no.9, pp.2401-2408, 2003-09-15

被引用文献数

3

---

ネットワークで表現されたデータを低次元ユークリッド空間へ埋め込む新たな方法を提案する.本手法では,ネットワークの隣接行列が定義するノード間の離散類似度と,現在の埋め込み配置から導かれる連続類似度との間のクロスエントロピーを最小にすることによって最適な配置を求める.さらに,与えられた埋め込みにおいてにおいて,ノードの接続関係がいかに忠実に再現されているかを定量的に評価する新たな評価尺度を提案する.最後に実際のネットワークデータを用いた実験によって,本手法の有効性を検証した.We present a novel approach to embed network data into a low dimensional Euclidean space. Theproposed method attempts to minimize cross-entropy between the discrete node similarity measure induced by theadjacency matrix and the continuous node similarity function derivedfrom current embedded node positions.We also propose a natural criterion to effectively evaluate an embeddednetwork layout in terms of how well node connectivities are preserved.Experiments using real network data show the effectiveness of theproposed method.

著者

岩田 具治 斉藤 和巳 山田 武士

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. DE, データ工学 (ISSN:09135685)

巻号頁・発行日

vol.107, no.114, pp.57-62, 2007-06-21

---

オンラインストアの収益を向上させるためには,顧客生涯価値(LTV)を高めることが重要である.従来のリコメンデーション法はユーザの興味と最も適合する商品を推薦する.しかしながら,従来法により必ずしもLTVが高まるとは限らない.本研究では,LTVが上昇する確率を最大化する新たなリコメンデーション法を提案する.提案法では,まずLTVの高いユーザに特徴的な購買パターンを抽出する.そして,抽出されたパターンと同じような購買行動になるように商品を推薦する.生存時間解析を応用し,ログデータから効率的に購買パターンの抽出を行う.また,効果的なリコメンデーションにするため,最大エントロピーモデルを用いてユーザの嗜好を推定する.LTVが高まることはユーザがサービスに満足した結果であるため,提案法はオンラインストアだけでなく,ユーザにとっても好ましいリコメンデーションである.音楽配信サイトの実ログデータを用い,提案法の有効性を示す.

著者

山田 武士 中野 良平

出版者

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

雑誌

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

巻号頁・発行日

vol.38, no.6, pp.1126-1138, 1997-06-15

参考文献数

32

被引用文献数

11

---

ジョブショップスケジューリング問題(JSSP)はNP?困難な組合せ最適化問題の中でも特に難しい問題の1つとされている.本論文では,JSSPの近似解法として,局所近傍探索と遺伝的アルゴリズム(GA)との組合せによる多段階探索交叉GA (MSXF?GA)を提案する.MSXF?GAは,アクティブスケジュールのクリティカルブロック(CB)上の作業の移動に基づく近傍であるアクティブCB近傍に基づく近傍探索と,問題空間の距離と近傍構造に基づく交叉である多段階探索交叉(MSXF)を用いたGAから構成される.さらに,アクティブスケジュールに対し「スケジュールの反転」という概念を導入し,与えられた問題に適した方向を適応的に選択する機構を取り入れて,解法の高速化を図る.MSXF?GAを含むいくつかの解法をジョブショップスケジューリング問題(JSSP)のベンチマーク問題に適用したところ,高品質の解が高速かつ安定して求まるという,MSXF?GAの優れた性能が明らかになった.The job-shop scheduling problem(JSSP) is one of the most difficult NP-hard combinatorial optimization problems.In this paper,an approximation method for JSSP called MSXF-GA is proposed using local neighborhood search and evolutionary computation,especially Genetic Algorithms(GA).MSXF-GA is composed by a neighborhood search that uses active CB neighborhood based on an active scheduler and operation permutations on the critical path,and Multi-Step Grossover Fusion(MSXF) that utilizes a neighborhood structure and a distance measure in the search space.The "reversal of the direction" of an active schedule is also introduced and MSXF-GA can adaptively select an appropriate direction for a given problem.Experimental results showed such a promising performance of MSXF-GA that it quickly found near optimal schedules in most cases.

著者

川前 徳章 高橋 克巳 山田 武士

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

電子情報通信学会論文誌 D (ISSN:18804535)

巻号頁・発行日

vol.J90-D, no.10, pp.2746-2754, 2007-10-01

---

本論文はユーザの情報検索を効率化するために,ユーザの興味とオブジェクトのトピックに着目した新しい情報検索モデルを提案する.我々は情報検索におけるユーザとその検索対象であるオブジェクトの関係はユーザの興味とオブジェクトのトピックの関係に射影することで説明できると仮定し,この射影を行うための手法としてLatent Interest Semantic Map(LISM)を提案する.LISMの特徴はLatent Semantic Analysisとユーザモデルの構築を同時に行い,射影した空間を用いることでユーザとオブジェクトの関係をユーザの興味やトピックの内容といった意味的な観点から説明できる点にある.この手法を協調フィルタリングに適用することで,ユーザのオブジェクトに対する評価予測やリコメンデーションを興味やトピックといった意味的な観点から実現できる.これらの手法を著名なベンチマークデータに適用した実験の結果,協調フィルタリングにおいて提案手法が情報検索においてユーザの情報検索を効率化することを確認した.

著者

風間 一洋 佐藤 進也 斉藤 和巳 山田 武士

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.24, no.1, pp.1_81-1_90, 2007 (Released:2007-06-11)

被引用文献数

1

---

本論文では,人間関係のネットワークから活発な人間で構成されるコミュニティ構造を互いの重なりを許容しながら抽出するSR-2法を提案する.本手法は,スペクトラルグラフ分析の一手法であり,ネットワーク構造中で他と重なりを持つような結合が密なコア部を抽出できる特徴を持つSR法を,特に共起ネットワークに対して,より詳細な分類ができるように変更したものである.この特性を調べるために,SR-2法に加えてSR法とk-クリークコミュニティ法を,実際のWebデータから抽出した小規模な人間関係に適用して抽出されたノード集合を可視化すると共に,抽出性能を評価する.さらに,より大規模なネットワークとして論文の共著関係を取り上げ,各手法で抽出されるノード集合のサイズの分布を分析する.この結果,SR-2法は,現実の人間の集まりに対応した妥当なコミュニティ構造を抽出できることを示す.

著者

岩田 具治 斉藤 和巳 山田 武士

出版者

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

雑誌

情報処理学会論文誌数理モデル化と応用(TOM) (ISSN:18827780)

巻号頁・発行日

vol.48, no.6, pp.65-74, 2007-03-15

参考文献数

19

---

定額制サービスを提供しているオンラインストアが収益をあげるためには,ユーザの契約期間をできるだけ延ばすことが必要である.従来レコメンド法では,購入される確率を最大化するためにユーザの嗜好に合致する商品を提示する.しかしながら,従来法により必ずしも契約期間が延びるとは限らない.本研究では,定額制サービスを想定し,契約期間が延びる確率を最大にするレコメンド法を提案する.提案法では,まず契約期間の長いユーザに特徴的な購買パターンを抽出する.そして,抽出されたパターンと同じような購買行動になるように商品をレコメンドする.生存時間解析を応用し,ログデータから効率的に購買パターンの抽出を行う.また,効果的なレコメンドにするため,最大エントロピーモデルを用いてユーザの嗜好を推定する.契約期間が延びることはユーザがサービスに満足した結果であるため,提案法はオンラインストアだけでなく,ユーザにとっても好ましいレコメンドである.携帯電話用漫画配信サイトのログを用い,提案法の有効性を示す.Online stores providing subscription services need to extend user subscription periods as long as possible to increase their profits. Conventional recommendation methods recommend items that best coincide with user's interests to maximize the purchase probability, which does not necessarily contribute to extend subscription periods. We present a novel recommendation method for subscription services that maximizes the probability of the subscription period being extended. Our method finds frequent purchase patterns in the long subscription period users, and recommends items for a new user to simulate the found patterns. Using survival analysis techniques, we efficiently extract information from the log data for finding the patterns. Furthermore, we infer user's interests from purchase histories based on maximum entropy models, and use the interests to improve the recommendations. Since a longer subscription period is the result of greater user satisfaction, our method benefits users as well as online stores. We evaluate our method using the real log data of an online cartoon distribution service for cell-phone.

著者

持橋 大地 山田 武士 上田 修功

出版者

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

雑誌

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

巻号頁・発行日

vol.190, 2009-03-18

被引用文献数

2

著者

中野 允裕 石黒 勝彦 木村 昭悟 山田 武士 上田 修功

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 (ISSN:09135685)

巻号頁・発行日

vol.113, no.286, pp.197-204, 2013-11-12

---

本稿では,関係データ解析への応用を目的として,無限サイズを持つ行列の長方形分割を行う確率過程について議論する.関係データ解析法の一つとして、与えられたデータを行列として表現し、その行列を少数の長方形クラスタに分割する手法が広く利用されている。長方形分割を表す確率的生成モデルとして従来Chinese restaurant processの積やMondrian processなどが用いられてきたが,これらは限られたクラスの長方形分割しか表現することが出来なかった.より一般に任意の長方形分割を生成しうる確率モデルとしてGilbert tessellationが知られているが,これは統計的な振る舞いの解析が困難であることが知られている.そこで本稿では,有限確率モデルの無限拡張によって長方形分割のための確率過程を構成する方法を提案する.はじめに,確率過程構成の常套手段であるKomogorovの拡張定理を用いた方法を示し,その問題点を明らかにした後,より洗練された構成法として有限のベイズ階層モデルに関する射影系をOrbanzの拡張定理によって無限拡張する方法を提案する.

著者

松林 達史 山田 武士

雑誌

情報処理学会論文誌数理モデル化と応用(TOM) (ISSN:18827780)

巻号頁・発行日

vol.48, no.SIG15(TOM18), pp.126-136, 2007-10-15

---

本研究では,大規模なネットワークデータのための高速かつ効率的な可視化座標計算の手法を提案する.従来のネットワーク可視化手法の1つとして Fruchterman らによる力学モデルを用いる手法がよく知られている.彼らの手法はノード間やエッジに対し力学関数を与えることにより,系全体のエネルギーを定義し,加速度方向に各ノードの座標を更新することによって,系のエネルギーの極小状態を求める.この手法では座標の更新頻度は一様で,すべてのノードを毎回更新していたが,提案手法では階層的独立固有時間刻み法を用いて個々のノードに独立な更新時間を設定し,局所的に更新頻度を変えることにより計算の高速化を可能にした.この手法は,天体力学において用いられている局所的に密集した領域を精度良く計算する手法を,グラフ可視化手法に拡張したものである.また,提案手法は並列処理に適しており,粒子間相互作用専用並列計算機 MDGRAPE-3 PCI-X に実装することによって,計算速度の数百倍高速化が可能であることを示した.さらに,LGL(Large Graph Layout)法を用いた Opte Project の可視化結果との比較を行い,提案手法により高精度な可視化が可能であることを示した.

著者

桑田 修平 上田 修功 山田 武士

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. PRMU, パターン認識・メディア理解 (ISSN:09135685)

巻号頁・発行日

vol.107, no.115, pp.81-86, 2007-06-21

被引用文献数

3

---

本稿では,ノンパラメトリックベイズモデルに基づくグラフクラスタリング手法を提案する.近年Newmanらは,混合多項分布モデルに基づき,リンク先が類似するノードを同一クラスに分類する,という一般的な仮定のみを用いた,クラスタ構造に関する事前情報を必要としない,汎用的かつ効率的なクラスタリング手法を提案した.しかし,予めクラス数を与える必要があるという問題があった.提案手法は,Newmanらのモデルを発展させ,ノンパラメトリックベイズの枠組でクラスの生成過程をデータの生成過程に含めることにより,クラス数を動的に推定しながらより柔軟なクラスタリングを行うことができる.人工データと実データを用いた実験により提案法の有効性を示す.

著者

岩田 具治 渡部 晋治 山田 武士 上田 修功

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D, 情報・システム (ISSN:18804535)

巻号頁・発行日

vol.93, no.6, pp.978-987, 2010-06-01

被引用文献数

4

---

購買ログデータを用いて,時間変化するユーザの興味及び商品の流行を追跡するためのトピックモデルを提案する.提案モデルは,興味や流行の変わりやすさをデータから逐次推定するため,変化に柔軟に対応可能である.また,新たなデータが得られた際,過去のデータで既に推定された興味・流行に基づいて,現在の興味・流行を推定するため,過去のデータを保持する必要がなく記憶容量を削減でき,かつ計算効率も高い.実購買ログデータを用いた実験により,購買行動の予測精度及び推定の計算効率の観点で提案モデルの有効性を示す.

著者

松林 達史 山田 武士 藤村 滋 藤村 考

出版者

情報処理学会

雑誌

情報処理学会論文誌数理モデル化と応用(TOM) (ISSN:18827780)

巻号頁・発行日

vol.1, no.1, pp.88-101, 2008-09-26

被引用文献数

1

---

本研究では,ラベル付きグラフ可視化のための,ラベルどうしが重ならない効率的な可視化座標計算の手法を提案する.従来のラベル付きグラフ可視化の座標計算アルゴリズムはForce-directed法やバネモデルといった,ノードを"点"として扱う座標計算を行うために,文字列や,異なるサイズのラベルを扱う場合,ラベルどうしが重なってしまうという問題が生じる.ラベルの重なりを回避する手法はいくつか提案されているが,いずれの手法も可視化計算を行った後に,再び座標計算処理を必要とする.これ等の手法では大規模なグラフ可視化では計算量が莫大となり,さらに元の可視化結果を破壊してしまうという問題が生じる.そこで,各ノードの斥力項として,ラベルサイズに依存した固有楕円ポテンシャルを与え,さらに,点対称ポテンシャルと固有楕円ポテンシャルの関数の重ね合わせる手法を提案する.提案法により,メンタルマップを保ちつつ,かつ,局所的なラベルの重なりを回避できることを示した.We present a new graph layout algorithm for a graph with node labels. The proposed algorithm can generate a graph layout efficiently avoiding overlapping of node labels. Most of the conventional algorithms such as force-directed and spring methods compute node positions by treating nodes as "points", and thus may cause node overlapping when strings or labels with various sizes are added to the nodes. Most of the conventional approaches to solve this problem require an initial graph layout creation phase without considering label sizes and a separate layout adjustment phase for overlap removal as its post processing. These methods are not suitable for a large-scale graph layout, because their computational costs are high and they may even destroy the initial graph layout. The proposed algorithm gives an individually different ellipsoidal potential to each node depending on its label size as well as a common point-symmetric potential, and the combination of these two potentials defines the repulsion force. This enables an efficient graph layout that can avoid local node overlaps while maintaining the mental map.

著者

石黒 勝彦 山田 武士 上田 修功

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D, 情報・システム = The IEICE transactions on information and systems (Japanese edition) (ISSN:18804535)

巻号頁・発行日

vol.92, no.3, pp.371-381, 2009-03-01

参考文献数

14

被引用文献数

1

---

従来の複数対象トラッキング手法は,すべての追跡対象について一つのダイナミックスモデルを適用することが多い.しかし,シーン内に存在するすべての対象が常に同一のダイナミックスに従うとは考えにくい.この問題に対処するためには複数のダイナミックスパターンが必要となるが,シーンの解析前に適切な数のダイナミックスパターンをすべて人手で決定することは困難であり,自動的に学習できることが望ましい.複数のダイナミックスパターンを学習する問題は,時系列データを複数のパターンにクラスタリングし,各クラスタごとに適切なパラメータを推定する問題ととらえることができる.本論文では,複数の移動対象をトラッキングするとともに,同時にそれらをクラスタリングしてダイナミックスモデルを学習する確率的な生成モデルを提案する.人工データ,及び実動画データを用いた実験を通じて,提案モデルがトラッキングとダイナミックスのクラスタリングを同時に実現可能であること,またトラッキング自体の性能も向上することを示した.

著者

川前 徳章 坂野 鋭 山田 武士

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D, 情報・システム (ISSN:18804535)

巻号頁・発行日

vol.93, no.6, pp.949-959, 2010-06-01

---

本論文では文書間,それらの著者間及び両者の意味的な関係を明らかにするために,著者の興味と文書の内容の潜在変数及びそれら変数間の依存関係を導入したモデルを提案する.提案モデルの特徴は,文書及び著者各々に潜在変数を導入し,通常のトピックモデルを拡張している点にある.文書ごとに導入する変数(文書クラス)は,文書のトピックを選択するための確率分布をもち,類似した内容の文書群は共通の文書クラスをもつ.同様に著者ごとに導入する変数(著者クラス)は,文書クラス選択の確率分布をもち,類似した興味をもつ著者群は共通の著者クラスをもつ.このモデルにより,文書生成を著者クラス,文書クラス及びトピックとそれら変数の依存関係を用いて表現し,その依存関係を用いて著者間及び文書間の意味的な関係を説明できる.各種データを用いた実験で,提案手法により著者クラス及び文書クラスを推定し,その結果,文書と著者の関係データを内容と興味に相当する低次元の空間に射影できること,及びテキスト生成モデルとして有効であることを確認できた.また,提案モデルは潜在変数の興味を抽出し,協調フィルタリングにも適用できることを実験で確認できた.

著者

岩田 具治 山田 武士 上田 修功

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. AI, 人工知能と知識処理 (ISSN:09135685)

巻号頁・発行日

vol.109, no.51, pp.13-18, 2009-05-15

---

トピックモデルに基づく内容に関連するタグの抽出法を提案する.ソーシャルアノテーションサービスでは,ユーザが任意のタグを付与できるため,しばしば内容に関連しないタグが含まれる.内容に関連するタグの抽出により,情報検索の性能向上や,文書分類や画像認識などの機械学習タスクの精度向上が期待できる.提案法では,内容とタグが生成される過程をモデル化し,確率的EMアルゴリズムを用いてモデルを推定することにより,関連するタグを自動的に抽出する.人工データ,および,Webページと画像を対象とするソーシャルアノテーションサービスの実データを用いて提案法の有効性を示す.

著者

川前 徳章 山田 武士

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. AI, 人工知能と知識処理 (ISSN:09135685)

巻号頁・発行日

vol.109, no.51, pp.19-24, 2009-05-15

---

本稿では文書間及びそれらの著者間各々の類似性を評価する為に,著者の興味と文書の内容の依存関係を反映した潜在変数モデルを提案する.提案モデルの特徴は,通常のトピックモデルを拡張し,文書間及び著者間各々に潜在変数を導入している点である.文書毎に導入される変数(文書クラス)は,文書のトピックを選択するための確率分布を持ち,類似した内容の文書間で共有されるものとする.同様に著者毎に導入される変数(著者クラス)は,文書クラス選択の確率分布を持ち,類似した興味を持つ著者間で共有されるものとする.それ故,文書生成を著者クラス,文書クラス及びトピックとその依存関係を用いてモデル化し,そのクラスを用いて著者間及び文書間の類似性を評価できる.論文著者データを用いた実験により,提案手法が著者クラス及び文書クラスを推定し,その結果,文書と著者の関係データを内容と興味の低次元の空間に射影できること,及びテキスト生成モデルとしての有効性を確認できた.

著者

石黒 勝彦 山田 武士 上田 修功

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

電子情報通信学会論文誌 D (ISSN:18804535)

巻号頁・発行日

vol.J92-D, no.3, pp.371-381, 2009-03-01

---

従来の複数対象トラッキング手法は,すべての追跡対象について一つのダイナミックスモデルを適用することが多い.しかし,シーン内に存在するすべての対象が常に同一のダイナミックスに従うとは考えにくい.この問題に対処するためには複数のダイナミックスパターンが必要となるが,シーンの解析前に適切な数のダイナミックスパターンをすべて人手で決定することは困難であり,自動的に学習できることが望ましい.複数のダイナミックスパターンを学習する問題は,時系列データを複数のパターンにクラスタリングし,各クラスタごとに適切なパラメータを推定する問題ととらえることができる.本論文では,複数の移動対象をトラッキングするとともに,同時にそれらをクラスタリングしてダイナミックスモデルを学習する確率的な生成モデルを提案する.人工データ,及び実動画データを用いた実験を通じて,提案モデルがトラッキングとダイナミックスのクラスタリングを同時に実現可能であること,またトラッキング自体の性能も向上することを示した.

著者

岩田 具治 田中 利幸 山田 武士 上田 修功

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

電子情報通信学会論文誌 D (ISSN:18804535)

巻号頁・発行日

vol.J92-D, no.3, pp.361-370, 2009-03-01

---

分布が時間的に変化するデータが与えられたとき,最新データを高い精度で予測するためのモデルの学習法を提案する.提案法では,最新データに関する期待誤差を近似するように,時刻に応じてサンプルに重みを付ける.過去のサンプルも重みを付けて学習データとして用いることにより,頑健なモデル学習が期待できる.提案法では,時間発展をモデルに組み込む必要はないため,時間を考慮しない既存のモデルを,分布が変化するデータに容易に適用することができる.人工データ,及び,購買データを用いた実験により,提案法の有効性を示す.

著者

山田 武士 中野 良平

出版者

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

雑誌

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

巻号頁・発行日

vol.37, no.4, pp.597-604, 1996-04-15

被引用文献数

7

---

ジョブショップスケジューリング問題(JSSP)はNP-困難な組合せ最適化問題の中でも特に難しい問題のひとつとされている. 本論文では 確率的な局所探索法であるシミュレーテッドアニーリング(SA)法を用い これに確定的(deterministic)な局所探索法であるshifting bottkeneck(SB)法を組み合わせることによってJSSPの効率的な近似解法を提案する.現在のスケジュールに対して新たなスケジュールがクリティカルパス上の作業順序の入れ換えと Giffer and Thompsonのアクテイブスケジュール生成法を用いて生成され SAによって確率的に受理される. さらに 受理されなかったスケジュールに対して 本方法のために変更を加えたSB法が適用され スケジュールは修正される. 修正されたスケジュールは改善が見られた場合に限って受理される. 本方法をよく知られたいくつかのべンチマーク問題に適用した結果 解の品質において従来の近似解法を上回る結果を得ることができた.The Job-Shop Scheduling Problem (JSSP) is one of the most difficult NP-hard combinatorial optimization problems. This paper proposes a new method for solving JSSPs based on simulated annealing (SA), a stochastic local search, enhanced by shifting bottleneck (SB), a problem specific deterministic local search. In our method new schedules are generated by a variant of Giffler and Thompson's active scheduler with operation permutations on the critical path. SA selects a new schedule and probabilistically accepts or rejects it. The modified SB is applied to repair the rejected schedule; the new schedule is accepted if an improvement is made. Experimental results showed the proposed method found near optimal schedules for the difficult benchmark problems and outperformed other existing local search algorithms.