著者

高橋 徹 小林 亜樹

出版者

情報処理学会

雑誌

研究報告データベースシステム(DBS) (ISSN:09196072)

巻号頁・発行日

vol.2009, no.26, pp.1-8, 2009-11-13

---

Web 情報システムにおける情報推薦では,協調フィルタリング技術がしばしば用いられている.本稿では,その推薦精度が必ずしも高くない理由について分析する.分析には,MovieLens Data Set を用いる.協調フィルタリング技術の,類似した嗜好を持つユーザは,未知の商品などのアイテムにおいても同様の嗜好を示す,という仮定がどの程度正しいか分析する.その結果,この仮定が成り立たない場合が相当程度ある事を明らかにし,また,cold-start 問題として知られる,嗜好が蓄積されていない状況と似ている事を指摘する.その後,これらの問題に対処するための考察を進める.Collaborative filtering techniques are often used to Information recommendation in the Web information system. In this paper, the reason why the recommendation precision is not always high is analyzed by using the Movie Lens data set. We think that collaborative filtering technique is based on a fundamental assumption. It is, if users had similar preference in an item set, it will be same as in other item sets. We show that the assumption is not approved in a respectable degree with similarity distribution histogram. Moreover, it is pointed out that the situation is similar to the cold-start situation, because of the same situation about user preference data is not available to collaborative filtering. Afterwards, it is considered to deal with these problems.

著者

吉田 光男 乾 孝司 山本 幹雄

出版者

情報処理学会

雑誌

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

巻号頁・発行日

vol.54, no.12, pp.2502-2512, 2013-12

---

ブログページには,Web検索エンジンなど機械的にページを処理するシステムにおいてノイズになる部分が含まれる.そのため,ブログのコンテンツを利用するためには,コンテンツの抽出処理が必要になる.さらに,ブログのコンテンツは,ポストと呼ばれるブログの書き手によるコンテンツと,コメントと呼ばれるブログの読み手によるコンテンツに二分できる.ポストとコメントの存在はブログの特性の1つであり,ブログの特性を活用するシステムや研究では,ポストおよびコメントを別々に抽出できていることが望ましい.本論文では,ブログページ集合を用いることにより,ポストとコメントを自動的に分離抽出する手法を提案する.複数のブログ記事ページを含むあるブログサイトにおいて,ポストはすべての記事ページに出現するが,コメントはいずれかの記事ページにしか出現しないという点に着目し考案した.また,本手法のアルゴリズムを実装したソフトウェアを用いて実験を行い,日本語ブログサイトに対しての有効性を検証し,コンテンツをポストおよびコメントに分離できることを確認した.Content extraction is necessary to use blogs as data for Web search engines, because blog pages are excessively added noisy parts such as menus, advertisements and copyright notices. Most of the blog contents are texts, and those can be divided in two parts, posts and comments. A post is a content written by the blog owner and a comment is piece of text written by readers in response to the owner's post. In this paper, we propose a simple method to extract the posts and comments separately from series of blog pages, whose posts are all written by the same owner. The proposed method is based on the assumption that although posts appear in all blog pages, comments do not. We describe experimental results to show good performance of the proposed method using real Web pages of the blog sites in Japanese.

著者

相川 拓也 杉木 章義 加藤 和彦

出版者

情報処理学会

雑誌

情報処理学会論文誌コンピューティングシステム(ACS) (ISSN:18827829)

巻号頁・発行日

vol.5, no.5, pp.138-151, 2012-10-15

---

サーバのチューニングは,性能を左右する重要なタスクである一方で,管理者にとって困難をともなう.パラメータの最適値は多くの場合, 1 回のチューニングでは求まらず,さまざまな試行錯誤を行う必要がある.また, 1 回の試行においても,サーバの設定を変更するだけではなく,複数台からなるクライアントの設定を変更し,起動するなど,煩雑な手続きが必要である.本研究では,このチューニングにおける試行錯誤の過程を効率化するスクリプティング環境を提案する.本提案では,サーバやクライアントなどチューニングに関連する要素をすべて分散オブジェクト化し,統一的な環境で高水準に試行の過程を記述可能とする.また,自動チューニングアルゴリズムのライブラリ化を行うことで,利便性の向上を図る.実験では, SPECweb2005 ベンチマーク下の Apache ウェブサーバと Hadoop を対象として実験を行い,本環境を利用してチューニングができることを確認した.Although parameter tuning is critical for server performance, that tuning process is error-prone and time consuming. An administrator must repeat many iterations to find an optimal configuration and even at each step non-trivial tasks, including proper configuration of a server and launching benchmark clients, are required. In this paper, we present a scripting environment for efficiently describing such tuning process. We offer distributed objects as ways to manipulate a server and benchmark clients. By this way, tuning process can be described by scripting them in an integrated environment. We also provide automatic tuning as a library for further efficiency. In the experiments, we confirmed that tuning of an Apache web server under SPECweb2005 benchmark and a Hadoop cluster were successfully possible in our tuning environment.

著者

二見 晋平 藤本 貴之

出版者

情報処理学会

雑誌

研究報告情報システムと社会環境(IS) (ISSN:09196072)

巻号頁・発行日

vol.2010, no.18, pp.1-7, 2010-03-10

参考文献数

3

---

近年,競技性を持ったコンピュータゲームが 「e-sports」 と呼ばれ,注目を集めている.特に欧米を中心に e-sports を新しいスポーツの一つとしてみるような動きも始まっており,商業的な成功を収めつつある.しかしながら,日本ではコンピュータゲームである 「e-sports」 は,未だまだ 「遊戯」 の域を出るものとは考えられておらず,その認知度も低い.また,コンピュータゲームそのものが 「内向的な遊び」 と捉えられているため,その競技性も認められていない.本論文では,e-Sports が持つ競技性について議論し,それが身体性を拡張に及びす影響について言及をする.そしてそのトレーニングを支援するための e-Sports Learning System を提案する.Recently, the computer game with the playability is called "e-sports". And, "e-sports" is paid to attention as one of new sports. However, "e-sports" is still thought as "Toy Game", and are low levels of acknowledgment in Japan. Moreover, the playability is not admitted. In this paper, we discuss the playability of "e-Sports", we propose "E-Sports Learning System" to improve physical strength in Real World.

著者

小川 拓貴 松本 和幸 任 福継

出版者

情報処理学会

雑誌

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

巻号頁・発行日

vol.2010, no.2, pp.1-6, 2010-01-21

参考文献数

12

被引用文献数

1

---

本研究では,Webサービス"えもにゅ"の投稿文をコーパスとして用い, 単語1-gramを素性としたSVMによるつぶやきや一言を対象とした感情推定手法を提案する."えもにゅ"とは一言メモに感情マークを付加して投稿できるWebサービスで, この投稿文をコーパスとして用いることで書き手の感情をコーパスに直接反映でき, また感情タグ付け作業を削減できる. 単語1-gramを素性とした理由としては, つぶやきや一言のような短文において書き手が感情表現する際に単語や記号の言語的意味を用いて感情を表現することが多いと考えられる事,1文あたりに含まれる素性の数が少ないつぶやきや一言から十分な素性の出現頻度を得るためには素性数を抑えることで1素性あたりの出現頻度を上げる必要がある事が挙げられる. 評価実験として, 単語1-gramを素性とした場合と単語2-gramを素性とした場合で比較をしたところ, F値を評価基準とすると単語1-gramを素性とした場合の方が全ての感情において高い値を示した.This paper proposes a SVM-based emotion estimation method from a short message or a word by using word 1-gram as feature and use contribution of "Emonyu" as a corpus. "Emonyu" is a web service to which users contribute a short message or a word with a emotion mark.Therefore, the corpus using"Emonyu"contribution enables reflect writer's emotion directly,and reduce work of adding emotion tags to sentences of corpus. We use word 1-gram as feature is,in short sentences like a short message or a word including a few features,a writer generally express emotion using a linguistic meaning of a word or a mark and it is necessary to reduce a number of kinds of feature to get exact appear frequency of features. The result of experiments show that the F-measure of proposed method is higher than the F-measure of method using word 2-gram as a feature in all emotions.

出版者

情報処理学会

雑誌

情報処理学会研究報告. 自然言語処理研究会報告

巻号頁・発行日

vol.78, no.9, pp.65-72, 1990-07-19

---

最も簡単な表現形式をもつ名詞述語文の意味解釈手続きを具体的に提案する.名詞述語文を理解する際には,モジュール的ではあるが,適用順序に柔軟性のある数個の手続きが適用されると考える.また,各手続きごとに,適用時に参照するいくつかの知識源も想定している.このうち,語彙知識には,ネットワーク的表現を採用している.このような手続きを考えることで,既知の名詞から作られる名詞述語文すべての意味解釈の分岐を考えることができる.とくに,"文字通り"の解釈や隠喩的解釈,"うなぎ"文的解釈などの違いを明確に区別できる.なお,これらの手続きの内容や適用方法は,文脈を存在を考慮し,一般化されている。We propose semantic procedures in understanding Japanese noun-predicate sentences.These procedures have module-like characteristics but their adpoted order is flexible. Each procedure uses specific knowledge basis such as lexical knowledge. The lexical knowledge is represented in a network fashion. Using such procedures and knowledge basis, we can allocate all of the interpretations of Japanese noun-predicate sentences into "literal" interpretations, "metaphorical" interpretations, "UNAGI-BUN" interpretations, and so on.

著者

全 泰賢 川村 隆浩 中川 博之 田原 康之 大須賀 昭彦

出版者

情報処理学会

雑誌

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

巻号頁・発行日

vol.53, no.11, pp.2485-2493, 2012-11-15

---

近年,商品やサービスを販売するECサイトの市場規模がますます拡大している.しかし,多くのECサイトの商品検索機能はカテゴリ絞り込みやキーワード検索に限られており,単語での特徴指定が困難な商品の検索においては難がある.たとえば,ECサイトの中でも特に売上げが伸びている服飾系の商品においては,ユーザは事前にブランド名やデザイン種別などの商品知識を頭に入れる必要があり,それによって商品群を絞り込んだ後にも何十というサムネイル画像を順番に見ていかなければならない.そこで本研究では,ユーザが閲覧した衣服(デザイン)の履歴を,商品画像の局所特徴量と商品説明文中のキーワードから,我々が事前に用意した服飾オントロジ上にマッピングする.そして,オントロジ内の距離計算によってユーザのデザインに関する嗜好を推定し,ユーザ嗜好に沿った衣服を抽出・推薦するエージェントシステムを提案する.また,推薦精度に関する評価実験を行い,70%超の再現率を達成していることを確認した.E-commerce market has been expanding, recently. However, search functionality for products in most of e-commerce sites are limited to keyword search and category selection, thus there is a problem to search for the product, to which it is difficult to specify its characteristics by words. In terms of a fashion product whose sales have been increasing year after year, users are required to learn the keywords like brand names and design terms in advance, and after just narrowing a list of the products they need to check small thumbnail images of enormous items one by one. Therefore, we propose an 'agent' service, which maps the user's browsing history of the product designs to the prepared fashion ontology based on local features of product images and keywords in product descriptions. Then, it estimates his/her favorite designs by calculating distances in the ontology and recommends the unseen items to the user. Also, we conducted an experiment for the recommendation accuracy, and confirmed more than 70% of recall.

著者

横山 哲郎 今井 敬吾 曾 剛 冨山 宏之 高田 広章 結縁 祥治

出版者

情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.2, no.2, pp.54-69, 2009-03-23

---

動的電圧制御 (DVS: dynamic voltage scaling) は,プロセッサへの供給電圧とその動作周波数をプログラム実行時に変化させる技術であり,現在,多くの商用プロセッサに実装されている.本稿では,デッドラインなどの制約のあるリアルタイムシステムを対象に,DVS システムにおいて動的エネルギー消費のより少ないプログラムを開発する方法論の 1 つを提示する.DVS システムで実行されるプログラムに動的エネルギー消費の最適化が有効であるためには,残り予測実行時間の実行早期の正確な見積りを容易にすることが重要である.そのため,プログラムは何を計算するかに加えどう計算するかをうまく指定する必要がある.しかし,プログラム改変によるエネルギー消費の最適化はプログラムのモジュール性を著しく損なう.本稿では,プログラムから独立し,エネルギー消費の最適化戦略を開発する手法を提案する.提案手法により,エネルギー消費の最適化を行うときに元のプログラムの部分正当性が容易に保存され,元のプログラムおよびエネルギー消費の最適化を行うための評価戦略が独立してそれぞれモジュール性を有するようになった.遅延評価などのプログラミング言語の特徴や構成的アルゴリズム論における組化などを活用することにより半自動化が実現できたことが,本開発法の特徴の 1 つである.本稿では,整列,選択,文字列検索などの基本的なアルゴリズムに提案手法を適用する.また,電力モデルを備えた命令セットシミュレータ(ISS: instruction set simulator)において実験を行い,エネルギー消費がどれだけ最適化されたかを評価する.基本的なアルゴリズムにおいて,本稿のアプローチが有効であることから,複雑なアルゴリズムに対しても本手法が効果的であることが期待される.DVS (dynamic voltage scaling) is a technique for scaling the processor's supply voltages and working frequencies. Several commercially available processors provide voltage/frequency controls. We propose a development method for deriving dynamically energy efficient programs on DVS-enabled real-time systems, which have several constraints such as deadline. In order to improve energy efficiency of programs on DVS systems, it is necessary to accurately estimate remaining predicted execution time in the early phase of the execution of programs. Thus, how to execute codes is as important as what codes to execute. However, the revision of programs for energy efficiency seriously harms their modularity. We separate concerns of the development of energy optimization strategy from the development of programs. As the result, partial correctness of original programs is preserved, and each of original programs and energy optimization strategy has modularity, independently. Lazy evaluation of functional programming languages and tupling in constructive algorithmics are employed for realizing the semi-automation of our development method. Our techniques are applied to basic algorithms such as sorting, selection, and string matching. Their energy efficiency is evaluated by using an instruction set simulator (ISS) with a power model.

著者

細谷 悟 桝田 秀夫

出版者

情報処理学会

雑誌

研究報告インターネットと運用技術(IOT) (ISSN:09196072)

巻号頁・発行日

vol.2010, no.19, pp.1-5, 2010-02-22

参考文献数

14

---

ホストをネットワークに接続する為の様々な設定を自動的に行う仕組みとして,DHCP が広く用いられている.一般的な DHCP サーバは,割り当てる IP アドレス等の情報を,MAC アドレスに紐付けたり指定した範囲から適切に割り当てる機能を持っている.一方,割り当てる IP アドレスをクライアントの接続されたスイッチのポートに紐付けたり,DDNS UPDATE の際に要求のあった DNS 名の衝突回避機構,DHCP サーバのコンフィグレーション情報を LDAP サーバに格納できるようになど,ネットワーク情報割り当ての際に追加の処理を行いたいという需要がある.本稿では,ISC DHCP に比較的規模の小さい変更を加えることで,クライアント設定情報の割り当てポリシの設定が可能な外部呼び出し機能 (ポリシ委譲機能) を 2 種類の方式で実装した.また,それぞれの実装方式のオーバーヘッドを計測し,評価,考察を行った.その結果,ポリシ委譲機能は約 600 行で実装できた.また,ポリシ委譲機能にかかるオーバーヘッドは 0.3% 程度となった.DHCP is used widely as organization performing various setteing to connect a computer to the network automatically. The general DHCP server has a function to assign the configuration parameter such as IP address adequately from the range that appointed or fixed in a client MAC address. By the way, it is expected that IP address in communication log become more useful for network use management, if there is a lease policy of IP address such as fixed in client-connecting port of switching hub. In this paper, We impremented and evaluated of flexible lease policy hook for ISC DHCP server.

著者

井上 拓 小松 秀昭 中谷 登志男

出版者

情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.1, no.2, pp.1-8, 2008-09-26

---

近年,XMLなど多くの用途において,テキストデータの標準的な表現形式として,1文字を1~3バイトの可変長で表現するUTF-8エンコーディングが用いられている.一方,Java仮想マシンなど多くの処理系においては,文字列の内部表現として1文字が2バイトの固定長であるUTF-16エンコーディングが用いられている.そのため,Javaで記述されたWebアプリケーションサーバなどの多量のテキストデータを取り扱うワークロードにおいては,テキストデータをUTF-8とUTF-16との間で相互に変換する処理が大きな処理時間を占める場合があり,このテキストデータ変換処理の高速化はシステム全体の性能向上において重要な意味を持つ.本研究では,SIMD命令を用いてUTF-8からUTF-16への変換をはじめとする可変長符号化データのデコード処理を高速に行う手法を提案する.この手法では複数のデータを並列に処理することに加えて,条件分岐での分岐予測ミスによるオーバヘッドを減少させることで,大きな性能向上が得られる.本手法をPowerPCアーキテクチャのSIMD命令セットであるVMX命令を用いて実装し,様々なテキストデータを入力としてUTF-8文字列デコード処理の性能を計測した結果,SIMD命令を用いない既存の方法と比較して単純な例で10倍以上,実際のテキストデータを用いたケースでも2倍から10倍の性能向上が得られた.Recently UTF-8 encoding is widely used as a standard format for text data exchange. The Java programming language, however, uses UTF-16 encoding as its internal representation format for text data. As a result, data conversions between UTF-8 and UTF-16 consume considerable amount of CPU time in workloads that process large amount of text data, such as web application servers. Hence accelerating these conversions are important to improve the performance of many applications. In this paper, we present our new technique to accelerate decoding of variable-length formats, such as conversion from UTF-8 to UTF-16, by using SIMD instructions. The new technique can achieve higher performance by reducing overhead of branch mispredictions in addition to exploiting data parallelism of SIMD instructions. We implemented the technique using VMX instructions of the PowerPC architecture and evaluated its performance to decode various UTF-8 sequences on a PowerPC 970MP processor. As a result, we showed that our technique significantly accelerated the UTF-8 decoding compared to the existing method.

著者

須佐 雄輝 小泉 直也 上間 裕二 常盤 拓司 杉本 麻樹 稲見 昌彦

出版者

情報処理学会

雑誌

研究報告 エンタテインメントコンピューティング(EC) (ISSN:21862583)

巻号頁・発行日

vol.2011, no.24, pp.1-6, 2011-03-19

---

パーソナルファブリケーションに代表されるような,個人の手によって行う創造活動が増えている.その結果,食分野においても,「キャラ弁」 などの文化が生まれてきた.そこで,食品による創造活動に着目し,菓子による造形のワークショップを開き,観察を行った.その観察から 「菓子組み」 の価値を見つけ出し,その実現に必要となる機能を抽出した.それらをシステムの設計指針として菓子組みを支援する造形アプリケーションの開発を行った.It has become popular to do creative work by one's own hands, for example a culture known as "Personal Fabrication". As a result, in the field of food, it has also burn a culture that creates "Characterized" lunch boxes. Therefore, we focused on the creative works of food, and held a creative workshop using sweets, then we observed it. From the observation, we discovered a value of "Sweets Assemblance", and we extracted features to realize the sweets as-semblance. we regarded them as a design guide, and we developed a sweets assemblance support application.

著者

長瀧 寛之

出版者

情報処理学会

雑誌

研究報告コンピュータと教育(CE) (ISSN:09196072)

巻号頁・発行日

vol.2010, no.3, pp.1-8, 2010-07-03

---

本稿は,著者が現在岡山大学にて開講中の授業科目 「テレビゲームからみる情報科学概論」 の実践についてその概要と現在までの実践結果を報告するものである.本科目は学部 1,2 年生を対象とした教養教育科目であり,工学系の知識に馴染みが薄い学生も履修生となり得る.そのため,情報科学の学問的側面を直感的に伝える方法として,テレビゲームを具体例として多用する講義スタイルを考えた.現在進行中の科目であるが,アンケート結果からは,情報科学への興味や学習意欲の向上について学部を問わず好意的な反応が得られている.This paper presents an abstract of "Introduction to Computer Science through video games", an introductory course of computer science for liberal arts. This course provides students with basic knowledge of computer science through many examples of video games. This course is designed for students who are interested in video games or computer science. This is an on-going class of 2010 liberal arts at Okayama University. Many students attending the class evaluate that connecting computer science with video games helps them to understand computer science easily.

著者

西本 一志 渡邊 洋 馬田 一郎 間瀬 健二 中津 良平

出版者

情報処理学会

雑誌

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

巻号頁・発行日

vol.39, no.5, pp.1556-1567, 1998-05-15

---

音楽との能動的な接し方の特徴は, 自分なりの音楽表現という創造性の発揮にある.しかし現実には音楽理論や楽器操作技術の困難により, 多くの人は能動的な音楽との接触を諦めている.筆者らは, これらの困難を計算機で支援することにより, だれでも容易に創造的音楽表現に取り組める楽器の実現を目指している.本論文では, そのための手段として, 音機能固定マッピング手法を提案する.従来の楽器は音高を演奏インタフェース上の固定ポジションにマッピングする音高固定マッピング型の楽器であった.しかし, 音には音高以外の属性があり, その1つとして, 音楽的環境に応じて個々の音が人に様々な情動的作用を与える, 機能という属性がある.音機能固定マッピングとは, 常時一定の演奏ポジションに一定の機能を持つ音をマッピングする手法である.ある音の機能の判定には音楽理論に基づく解析が必要であるが, この手法によれば, 演奏者は必要な機能を持つ音を理論的解析を行うことなく直接取り出せ, さらにそれらを自由に組み合わせるとこにより, 容易に自分なりの創造的音楽表現を実現できるようになる.本論文では, 特に音の機能の考え方が重要となるジャズの即興演奏を対象として作成した試作器と, それを用いた被験者実験について説明し, 本手法の可能性について検討する. : Many people cannot help but give up to play music because of difficulty of a musical theory or a manipulation of a musical instrument. The authors aim to develop a musical instrument with which anyone can enjoy creating of music with the support of a computer. In this paper, we propose a concept called the"fixed mapping of note-functions". With an ordinary musical instrument, a specific pitch is always mapped on a specific position of the instrument; this is a"fixed mapping of pitch"instrument. However, a note has other attributes. A note-function, i.e., the emotional effect of a note depending on the temporal musical situation, is one of them. The mapping of a specific note-function on a specific position is the basis of the"fixed mapping of note-functions"concept. In order to determine the note-function, a theoretical analysis is usually necessary. Using the proposed method, however, it becomes possible to directly extract notes with the required functions without any theoretical considerations and to exhibit creativity by combining the notes. In this paper, we show a prototype of an instrument for improvisational jazz, provide several subjective experimental results and dsicuss the possibilities of the method.

著者

上間 裕二 永谷 直久 杉本 麻樹

出版者

情報処理学会

雑誌

研究報告 エンタテインメントコンピューティング(EC) (ISSN:21862583)

巻号頁・発行日

vol.2011, no.26, pp.1-4, 2011-03-19

---

本研究では情報環境における操作対象であるアバターなどの操作に伴う身体の動揺に着目する.コントローラ型のインタフェースによってアバターを操作する際,操作者が操作対象を動かしたい方向へ自らの身体を傾けるという現象が観察できる.この現象は自己投射性の高い情報環境で,アプリケーションに没頭しているために起こると考えられる.また,アバター操作に伴う動揺はベクションにより引き起こされる身体動揺とは異なるものであると考えられる.本研究では,この現象に注目して身体動揺の記録を行い定量的な現象の観察と議論を行うことを目標とする.In this study, we focus on effects of operation-induced synchronous postural sway with avatars in virtual environments. Operation-induced postural sway is observed especially with primary input interfaces such as controller pads. User sometimes not only input commands for a controller pad, but also show postural sway. These effects can be observed in high-immersion virtual environments when users are deeply attached to a game play. Also, postural sway caused by operating controller can be deferent from postural sway by vection. We conducted experiment aiming to analyze and discuss operation-induced synchronous postural sway with the help of a motion capturing system.

著者

斎藤 寿樹 川原 純 吉仲 亮 鈴木 拡 湊 真一

出版者

情報処理学会

雑誌

研究報告アルゴリズム(AL) (ISSN:21862583)

巻号頁・発行日

vol.2011, no.17, pp.1-6, 2011-02-28

被引用文献数

1

---

与えられたグラフ中のパスを列挙する問題は古典的な問題である.これまで,解を列挙するアルゴリズムや解の数を数えるアルゴリズムがいくつか提案されているが,一般に解の数は極めて多く,解の数を求める問題は #P-完全であるため,満足のいく高速な列挙アルゴリズムの実現は難しい.近年 Knuth は,ZDD (Zero-suppressed Binary Decision Diagram) を用いた任意のグラフの任意の 2 点間を端点とするパスを列挙するアルゴリズムを提案した.ZDD とは集合族を圧縮して表現できるデータ構造である.グラフの経路を辺の集合と同一視することによって,経路の集合は ZDD で表現することができる.提案されたアルゴリズムは,出力結果がパス集合の ZDD による圧縮表現であり,従来手法に比べ高速に動作する.本発表では,まず Knuth のアルゴリズムを紹介し,次に Knuth のアルゴリズムを基にした筆者らによる多項式回の ZDD の基本演算でパスの列挙を行うアルゴリズムを提案する.これらの手法と既存手法との比較実験を行い,ZDD によるパスの列挙手法の利を論ずる.The listing of all paths in a given graph is a classical problem. Although there are known algorithms for the problem, the number of the solutions tends to be huge and the counting problem is #P-hard. Recently, Knuth has proposed an algorithm for enumerating paths by using the ZDD (zero-suppressed binary decision diagram). The ZDD is a condensed representation of a family of sets. By identifying a path in a graph as a set of edges, the sets of paths can be represented by ZDD. His algorithm outputs a ZDD representing a set of paths. In this paper, we first introduce Knuth's algorithm, and propose an algorithm where ZDD operations implemented polynomial many times by extending Knuth's algorithm. We experiment with these algorithms and a known enumeration algorithm, and discuss the advantage of the algorithms using ZDD from the experimental result.

著者

池畑 望 伊藤 毅志

出版者

情報処理学会

雑誌

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

巻号頁・発行日

vol.52, no.12, pp.3817-3827, 2011-12-15

---

2007年よりIEEEのCIGシンポジウムの中でMs. Pac-Manの自動操作を競う大会が開かれている.この大会以来,Ms. Pac-Manは,デジタルゲームAIの研究対象として注目を集めつつある.これまでの大会では,知識ベースを用いた古典的な手法によるAIが最も良い成績を収めているが,その性能には限界が見え始めており,知識ベースに代わる新しいアプローチが求められている.そこで,本稿では囲碁で成功したモンテカルロ木探索によるMs. Pac-Manの自動操作システムを実現し,その有効性を検証した.モンテカルロ木探索は乱数によって生成された未来局面についてのシミュレーションを繰り返すことで,専門的知識に頼らずに期待値の高い次の手を求めることができる.性能評価実験ではモンテカルロ木探索による自動操作システムは過去にMs. Pac-Man Competitionに参加したすべてのプログラムよりも優秀な成績を示し,Ms. Pac-Manにおけるコンピュータの世界記録を上回る結果を得た.The competition of controller program for Ms. Pac-Man has been held in the CIG symposium of IEEE every year from 2007. Since this competition was held, Ms. Pac-Man has become to an attractive subject of research on digital game AI. In the competition by this year, the classical AI method by using the knowledge base has gotten the best result. But, since the improvement by this method is becoming a limit, a new approach is required. In this paper, we realized the Ms. Pac-Man controller by the using Monte-Carlo tree search which is effective on Go, and examined the effectiveness. By repeating the simulation about the future phase generated with the random number, the Monte Carlo tree search can select the next move with a high expected value, without depending on professional expertise. In an evaluation experiment, the controller by the Monte Carlo tree search showed results more excellent than all the programs which participated in Ms. Pac-Man Competition in the past.

著者

久保田 彰人 北島 規雄 小林 祐貴 市村 哲

出版者

情報処理学会

雑誌

研究報告グループウェアとネットワークサービス(GN) (ISSN:09196072)

巻号頁・発行日

vol.2009, no.18, pp.1-6, 2009-05-14

---

現在,気軽に使える移動手段として自転車が利用されることが多い.しかし,自動車のような免許制度がなく,自転車事故に対する危機意識の低さがある.そこで本稿では,危険箇所や注意箇所などに対し運転者に注意喚起を行う,自転車用安全運転支援システムを提案する.本システムは,自転車運転時に 3 軸加速度センサーを用いて道路状況を推定し,GPS から得た位置情報と合わせて地図上に書き込み,Web 上で他のユーザーと共有する.その地図データを用いて自転車運転時に危険箇所や注意箇所で運転者に警告や注意といった注意喚起を行う.注意喚起の方法として,運転中の画面注視は危険であるため,振動機器を腕に取り付け,その振動パターンで情報を通知するようにした.A bicycle is used as a transportation vehicle which can be used casually in many cases. However, there is no license system like a car and there is lowness of a sense of crisis to a cycling accident. Then, we propose the safe driving supporting system for bicycles which can gives warning and cautions to a driver near a dangerous places. Three axis acceleration sensor is used for this system, and it senses a road condition. The positional information acquired from GPS, are shared among users on the Internet. Warning and cautions are notified to a driver near dangerous places. As gazing at a screen is dangerous while riding bicycle, a vibrating device is attached to an arm.

著者

イェ チョウトゥ 浦野 義頼

出版者

情報処理学会

雑誌

研究報告ヒューマンコンピュータインタラクション(HCI) (ISSN:09196072)

巻号頁・発行日

vol.2009, no.7, pp.1-7, 2009-05-08

---

今日,ミャンマーの携帯電話マーケットには,MyTapとM9の2つのキーパッド・レイアウトあるいは文字入力手法のみが存在している.本論は,この2手法に関し,ミャンマー文字の入力に必要なキーストローク,1分間に入力可能な文字数(CPM),ユーザーによる評価の観点から比較するものである.研究の結果,両手法とも次に入力する文字によって子音・母音モードを切り替えることが分かった.M9のキーパッド・マッピングは興味深いが,初心者ユーザーが習得するのは容易ではない.ユーザースタディの結果,(i-modeの場合)MyTapのCPMとM9のCPMに大差はなく、分散分析の結果は(<i>F</i>_1,4 = 0.144, ns)であった.また,MyTapのキーパッド・レイアウトは表示がややこしく,入力編集作業の妨げとなる.ユーザーの多くは上述の2手法のもつタイムアウト問題にわずらわしさを感じている.Today, there are only two keypad layouts or text input methods in the Myanmar mobile phone market namely MyTap and M9. This paper reports a comparison of those two methods in terms of Keystrokes required to type a Myanmar character, Characters per Minute (CPM) and users' evaluation. What we have noticed from this study is that both methods are preparing the next text input step or changing consonant to and from vowel mode. Although M9 keypad mapping is interesting, it is not easy for first-time users to learn it. According to the current user study, CPM of MyTap is not statistically significant as the one of M9 (i-mode=on). The result of an analysis of variance (ANOVA) is (<i>F</i>_1,4 = 0.144, ns). MyTap also has a complicated keypad layout displaying feature for typing and editing process. Most users feel uncomfortable with time out problem of those two methods.

著者

金子 仁美 川上 大輔 嵯峨山 茂樹

出版者

情報処理学会

雑誌

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

巻号頁・発行日

vol.2010, no.7, pp.1-8, 2010-05-20

---

我々は,楽曲の和声解析の記述仕様 ("KS notation") を策定し,機能和声解析を行ってデータを作成し,その統計解析を行った.和声推定は自動採譜や楽曲検索など多数の目的に有用で,その和声進行の確率モデルの作成と統計学習のために有用である.また,音楽学的な見地からは,和声学の規則や傾向などが計量的に検証でき,時代や作曲者や楽曲スタイルを和声学的に解明する基礎となろう.機能和声記述のために,和音,転回,借用和音,省略,変位,転調,付加音などの記述を可能とし,さらに楽譜なしで演奏が可能なように音価も表現した.また,人間とコンピュータ双方の可読性の両立させコンパクトに表現できるようにした.データ作成には,RWC 音楽データベース所収のクラシック曲 50 曲について,人手により機能和声解析してデータを作成した.そのデータを統計解析し,音楽的な知見から説明を試み,機能和声モデルが従来のモデルより工学的和声モデルとして優位であることを示す.We designed a new notation (called "KS notation") for harmony analysis, built a functional harmony analysis dataset and made statistical analyses on the data. Harmony (chord sequence) estimation is useful in many purposes including automatic music transcription and music information retrieval, while, from musicological viewpoint, harmony theory and rules are verified quantitatively using the data across periods, composers and styles may be investigated. For description of functional harmony analysis, the notation include chord, inversion, borrowed chord, omission, alteration, key modulation, additional notes, etc. and enables playing chords from the notation without the score by representing the note value. Readability was emphasized both for human and computer. The KS-notation dataset was built from 50 titles included in the RWC classical music database. New findings are discussed based on statistical analysis of the data and functional harmony model is shown to be advantageous over the conventional chord sequence model from the engineering point of view.

著者

関 治之

出版者

情報処理学会

雑誌

情報処理学会デジタルプラクティス (ISSN:18845541)

巻号頁・発行日

vol.2, no.4, pp.237-241, 2011-08