著者

乾 伸雄 品野 勇治 鴻池 祐輔 小谷 善行

出版者

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

雑誌

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

巻号頁・発行日

vol.46, no.2, pp.105-117, 2005-01-15

参考文献数

10

被引用文献数

1

---

本論文では,最長しりとり問題をネットワークの問題としてモデル化し,整数計画問題として定式化を行う.この定式化では,変数の数が頂点数に対して,指数オーダで増加するため,事実上,整数計画問題として直接的に解くことは難しい.そのため,緩和問題を設定し,LP ベースの分枝限定法によって解決した.これによって,19 万語程度の辞書から最長しりとりをXeon2.8GHz プロセッサのPC を使って1 秒程度で作成することができた.また,本論文では,局所探索による解法と比較し,問題の困難さを実験的に調べた.さらに,様々なインスタンスにおける解を分析することで,最長しりとり問題の性質を調べた.This paper describes the definition of the longest Shiritori problem as a problem of network flow and the solution using the the integer problem. This formulation requires a large number of variables being of exponential order. To overcome the difficulty, we propose a solution based on the LP-based branch-and-bound method, which solves the relaxation problems repeatedly and enumerates all the solutions implicitly. This method is able to calculate the longest Shiritori sequences for 190 thousand words dictionary in a second in Xeon 2.8GHz PC. In this paper, we compare the performances for the heuristic local search and investigate the results for a variety of instances to explore characteristics of the longest Shiritori problem.

著者

乾 伸雄 品野 勇治 鴻池 祐輔 小谷 善行

雑誌

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

巻号頁・発行日

vol.46, no.SIG2(TOM11), pp.105-117, 2005-01-15

---

本論文では,最長しりとり問題をネットワークの問題としてモデル化し,整数計画問題として定式化を行う.この定式化では,変数の数が頂点数に対して,指数オーダで増加するため,事実上,整数計画問題として直接的に解くことは難しい.そのため,緩和問題を設定し,LP ベースの分枝限定法によって解決した.これによって,19 万語程度の辞書から最長しりとりをXeon2.8GHz プロセッサのPC を使って1 秒程度で作成することができた.また,本論文では,局所探索による解法と比較し,問題の困難さを実験的に調べた.さらに,様々なインスタンスにおける解を分析することで,最長しりとり問題の性質を調べた.

著者

小谷 善行

出版者

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

雑誌

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

巻号頁・発行日

vol.34, no.5, pp.973-984, 1993-05-15

被引用文献数

1

---

一般人の扱いやすい、日本語表現の論理型プログラミング言語の仕様を設計した。Prologなどの論理型書語は、表現が非日本語的であるだけでなく、述語の引数に存在する変数の間の対応をよく理解するには数学的素養が必要であり、なじみやすくはない。そこで単なるワープロ使用者にも利用可能とすることを想定し、自然な日本語の文構造や語藁体系を素直に反映したプログラミング言語の仕様を設計した。本言語仕様は、述語の引数は陽には記述しないという特徴をもつ。データは、入力と出力の2ポートに区分して述語に与えられる。プログラミングは、メタ述語と呼ばれる演算子で述語間の結びつきを指定することで行う。述語は主としてユーザが定義し、通常、日本語の名詞を用いると読みやすい設計となっている。メタ述語は主としてシステム組込みであり、助詞や接頭語で表される。メタ述語は日本文としての理解と一致するように、語義に基づき選定されている。プログラムは分かち書せず、「祖母とは親の母」のように、ほとんど日本語そのままのプログラム表現となる。本言語によるプログラムは、Plologプログラムを日本語で自然に読み下した文に非常に近い。さらに意味ネットワークなどの知識を記述する観点からも、本仕様はその意味を自然に表現した形になっている。また、本仕様に対しその意味定義を与え、プログラム例による可読性および、システムを試作し効率を調査した。

著者

竹中 姫子 古宮 嘉那子 小谷 善行

出版者

情報処理学会

雑誌

研究報告情報基礎とアクセス技術(IFAT) (ISSN:21862583)

巻号頁・発行日

vol.2011, no.1, pp.1-6, 2011-03-21

---

Twitter ではハッシュタグという,自分の投稿 (ツイート) に則した内容のインデックスをつける機能が提供されている.本研究ではハッシュタグのついていないツイートにたいしてハッシュタグを推定することを目的とする.そこでハッシュタグのついたツイートを学習し,そしてあるツイートがどのハッシュタグに属するかの推定を行った.分類器としてベイジアンフィルターを使用し,それぞれのタグについて 2 値分類を行い,複数のハッシュタグの推定を行った.実験では 50 種類のハッシュタグのつきの約 4 万件のツイートを学習データとして使用した.ツイート文にベイジアンフィルターを適用する場合は既知語に限定して処理を行うことで良い結果が得られるとわかった.In this paper, we propose a method of discovering hashtags, which are indexes in Twitter. We estimate hashtags of tweets without hashtags using tweets with hashtags. Binary classifier was developed for every tweet so as to they have more than one tags, and Bayesian filtering was used to classify. In the experiment, about 40,000 tweets with 50 kinds of hashtags are classified. The result shows Baysian filtering with limiting known words is effective in estimating hashtags of tweets.

著者

小谷 善行

雑誌

全国大会講演論文集

巻号頁・発行日

vol.33, pp.505-506, 1986-10-01

---

Prologを学生に教えるとき、教えにくいところのひとつがカットオペレータである。これを日本語でわかりやすく読み下すことを試みている。Prologのプログラムの説明には論理的説明と手順的説明の2通りがある。論理的説明によれば理解は著しく速い。しかしカットオペレータがあると、その部分は手順的説明をするのか普通であり、それが教えにくい点であった。本稿ではカットオペレータを含むPrologプログラムを、なるべく適切に日本語で読み下すにはどうすればよいかついて論じる。この結果は次の点に寄与すると考える。(1)Prologプログラムの説明の多くの部分を論理的説明ですますことができる。(2)日本語Prologの言語仕様の設計の知見を得る。

著者

小谷 善行

雑誌

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

巻号頁・発行日

vol.34, no.5, pp.973-984, 1993-05-15

---

一般人の扱いやすい、日本語表現の論理型プログラミング言語の仕様を設計した。Prologなどの論理型書語は、表現が非日本語的であるだけでなく、述語の引数に存在する変数の間の対応をよく理解するには数学的素養が必要であり、なじみやすくはない。そこで単なるワープロ使用者にも利用可能とすることを想定し、自然な日本語の文構造や語藁体系を素直に反映したプログラミング言語の仕様を設計した。本言語仕様は、述語の引数は陽には記述しないという特徴をもつ。データは、入力と出力の2ポートに区分して述語に与えられる。プログラミングは、メタ述語と呼ばれる演算子で述語間の結びつきを指定することで行う。述語は主としてユーザが定義し、通常、日本語の名詞を用いると読みやすい設計となっている。メタ述語は主としてシステム組込みであり、助詞や接頭語で表される。メタ述語は日本文としての理解と一致するように、語義に基づき選定されている。プログラムは分かち書せず、「祖母とは親の母」のように、ほとんど日本語そのままのプログラム表現となる。本言語によるプログラムは、Plologプログラムを日本語で自然に読み下した文に非常に近い。さらに意味ネットワークなどの知識を記述する観点からも、本仕様はその意味を自然に表現した形になっている。また、本仕様に対しその意味定義を与え、プログラム例による可読性および、システムを試作し効率を調査した。

著者

小谷 善行

出版者

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

雑誌

情報処理 (ISSN:04478053)

巻号頁・発行日

vol.46, no.7, pp.811-813, 2005-07-15

被引用文献数

3

著者

木村 健 小谷 善行

雑誌

第53回プログラミング・シンポジウム予稿集

巻号頁・発行日

vol.2012, pp.91-96, 2012-01-06

---

本稿ではGPGPU(グラフィックスプロセッサの汎的計算への応用)を用いた将棋ゲーム木探索手法を提案する。チェスや将棋などのゼロ和完全情報ゲームにおける並列ゲーム木探索の研究は決して新しい研究ではない。しかしながらさまざまな技術が年を経るごとに開発されているにつけ、並列探索の技術も変化を必要としている。GPU上における並列計算環境であるCUDAと、CUDAライブラリの一部であるCUDA版C++STLとも言えるThrustを用いた、並列ゲーム木探索手法を提案する。提案手法は1993年にTransputer上に実装されたYBWCをベースにしており、高いスピードアップが期待できる。ただし、CUDA固有の高スループット実現の難しさもあり、提案手法の実際の実装についての知見が必要である。

著者

三塩 武徳 小谷 善行

雑誌

研究報告ゲーム情報学(GI)

巻号頁・発行日

vol.2014-GI-31, no.4, pp.1-6, 2014-03-10

---

ゲームの不完全情報の推定を行うアルゴリズム Using Past Playout(UPP) を提案する.UPP はモンテカルロ法において過去のシミュレーション結果のうち現在局面に至るものを取り出し,仮定した情報の間の勝率を比較する.相手側の勝率が高い部分は実際の局面と等しい可能性が高い.これを使って不完全情報の推定を行う.アレックス・ランドルフ (Alex Randolph) [1] によって発表された二人零和確定不完全情報ゲームである 「ガイスター」 において UPP を用いたプログラムと既存手法の猪突戦法,および通常のモンテカルロ法とで対局を行った.結果,猪突戦法に対しては思考時間 0.25 秒で 94%の勝率,モンテカルロ法との対局ではお互いの思考時間 1 秒で 55%の勝率を挙げた.これらの結果より,ガイスターにおける UPP の有効性を示した.

著者

小谷 善行

雑誌

研究報告ゲーム情報学(GI)

巻号頁・発行日

vol.2009-GI-22, no.8, pp.1-8, 2009-06-19

---

古来からある計算パズルの一つである虫食い算について,解記述の候補における制約を用いて虫食い算パズルを非探索的に解く方法を示した.それに最小分岐を行う探索アルゴリズムを付加することにより,普通の問題がみな解ける効率的な虫食い算解法アルゴリズムを作った.さらにそれを用いて虫食い算を作成するシステムを設計し,巨大な虫食い算を作った

著者

竹中 姫子 古宮 嘉那子 小谷 善行

出版者

情報処理学会

雑誌

研究報告デジタルドキュメント(DD) (ISSN:21862583)

巻号頁・発行日

vol.2011, no.1, pp.1-6, 2011-03-21

---

Twitter ではハッシュタグという,自分の投稿 (ツイート) に則した内容のインデックスをつける機能が提供されている.本研究ではハッシュタグのついていないツイートにたいしてハッシュタグを推定することを目的とする.そこでハッシュタグのついたツイートを学習し,そしてあるツイートがどのハッシュタグに属するかの推定を行った.分類器としてベイジアンフィルターを使用し,それぞれのタグについて 2 値分類を行い,複数のハッシュタグの推定を行った.実験では 50 種類のハッシュタグのつきの約 4 万件のツイートを学習データとして使用した.ツイート文にベイジアンフィルターを適用する場合は既知語に限定して処理を行うことで良い結果が得られるとわかった.In this paper, we propose a method of discovering hashtags, which are indexes in Twitter. We estimate hashtags of tweets without hashtags using tweets with hashtags. Binary classifier was developed for every tweet so as to they have more than one tags, and Bayesian filtering was used to classify. In the experiment, about 40,000 tweets with 50 kinds of hashtags are classified. The result shows Baysian filtering with limiting known words is effective in estimating hashtags of tweets.

著者

古宮 嘉那子 伊藤 裕佑 佐藤 直人 小谷 善行

出版者

一般社団法人 言語処理学会

雑誌

自然言語処理 (ISSN:13407619)

巻号頁・発行日

vol.20, no.2, pp.161-182, 2013-06-14 (Released:2013-09-14)

参考文献数

17

---

本論文は,文書分類のための新手法として,Negation Naive Bayes (NNB) を提案する.NNB は,クラスの補集合を用いるという点では Complement Naive Bayes (CNB) と等しいが,Naive Bayes (NB) と同じ事後確率最大化の式から導出されるため, 事前確率を数学的に正しく考慮している点で異なっている.NNB の有効性を示すため,オークションの商品分類の実験とニュースグループの文書分類の実験を行った.ニュースグループの文書分類では,一文書あたりの単語数(トークン数)を減らした実験と,クラスごとの文書数を不均一にした実験を行い,NNB の性質を考察した.NB,CNB,サポートベクターマシン (SVM) と比較したところ,特に一文書当たりの単語数が減り,クラスごとの文書数が偏る場合において,NNB が他の Bayesian アプローチより勝る手法であること,また,時には SVM を有意に上回り,比較手法中で最も良い分類正解率を示す手法であることが分かった.

著者

石井 余史子 Bipin Indurkhya 野瀬 隆 乾 伸雄 小谷 善行 西村 恕彦

出版者

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

雑誌

情報処理学会研究報告コンピュータと教育(CE) (ISSN:09196072)

巻号頁・発行日

vol.1997, no.125, pp.31-38, 1997-12-19

参考文献数

5

被引用文献数

1

---

こどもが複数の絵からお話を作成できるように、絵を利用してこどもの作文作成を支援するシステム、STEP("Story TElling from Pictures") の改良を次の二点について行った。まず一つめは、こどもの日常生活場面の知識を調べるアンケートを行い、その結果から、こどもの日常生活を表現した絵を作成し、こどもの生活を反映するように、STEPの絵のデータベースの改良を行った。次に二つめとして、こどもがSTEPで遊べるように、お話作成支援の方法にジャンニ・ロダーリの提案する方法を利用した。改良後、作文の不得意な小学一年生の男女各一名にSTEPで遊んでもらった結果、こどもは複数の絵からひとつのお話を作ることができた。In this paper, we describe the modifications to our system, Story TElling from Pictures ("STEP") in which children practice their writing as a game. First, we changed pictures in STEP, from unfamiliar ones to the ones with which children are familiar. In order to do so, we asked 12 children to fill out a questionnaire, prepared pictures using the information from the questionnaire, and used these pictures in STEP. Then, we incorporated some techniques from Gianni Rodari's " The Grammar of Fantasy" into STEP to promote creative writinar in children. In our test, one girl and one bow (first graders) had fun making stories using STEP-we present that data here.

著者

小谷 善行

雑誌

情報処理

巻号頁・発行日

vol.46, no.7, pp.811-813, 2005-07-15

著者

大川 貴之 桜井 貴文 小谷 善行 辻 尚史

出版者

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

雑誌

情報処理学会研究報告ゲーム情報学(GI) (ISSN:09196072)

巻号頁・発行日

vol.2002, no.27, pp.73-80, 2002-03-15

被引用文献数

2

---

2人ゲームではαβ法などにより枝刈りを行って、ゲーム木の中で読む場合の数を大幅に減らすことができるが、一般の多人数ゲームでは相手が複数で、複数のプレイヤーの有利不利が入り交じったりするので、2人ゲームと同じ方法で枝刈りを行うことはできない。 本論文では、各プレイヤーの評価値の和が一定であるという仮定を設けて、多人数ゲームにおける枝刈りを行う方法を考えた。多人数・零和・有限・確定・完全情報の条件を満たすゲームとして「四人将棋」がある。 本論文では、我々が考案した多人数ゲーム木の枝刈り法を実証するため、四人将棋をプレイするプログラムを作成し、実験を行った。In this paper, we study a pruning method which searches an multi-player game tree. We concentrate here on multi-player, zero-sum, deterministic, and perfect information games. In the case of two-player game, the alpha-beta technique is used to speed up the search of a tree by maintaining cutoff values. But it is not applicable to a multi-player game, since each player has more than one opponent. Here, we introduce a pruning method in searching a multi-player game tree. Moreover, we implemented a program that plays Yonin-shogi, and we show that the method introduced here is effective in the search of a game tree of Yonin-shogi.

著者

但馬 康宏 北出 大蔵 中野 未知子 藤本 浩司 中林 智 小谷 善行

出版者

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

雑誌

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

巻号頁・発行日

vol.2007, no.76, pp.7-12, 2007-07-24

---

本研究において、比較的長い対話に対する話題分割を行う手法を提案する。隠れマルコフモデル(HMM)による話題分割は、これまでも盛んに研究されており、音声認識の分野で特に成果をあげている。しかし、一般的に対話を単語の列として取り扱うため、長さが数百語程度以上の対話の場合にその対話の発生確率が著しく低くなり、有効精度不足となる。本手法では、対話における発話を HMM の出力単位として話題分割を行う。対話における1発話ごとにベイズ推定によりあらかじめ話題のラベルを付けた後、そのラベル列を出力する HMM を構成することにより話題の切り替わりを特定する。ここで、HMM はすべての状態間の遷移を許したモデルとした。68 名の被験者で対話実験を行い、62 対話を作成し、本手法の有効性を検証した。この結果、1500 単語程度の長さの対話にたいして良好な分割精度を出せたことを報告する。We propose a dialogue segmentation and topic structure finding method via Hidden Markov Model (HMM). HMM has been applied for this problem in previous studies and its advantages have been shown. Nevertheless, the length of the dialogue must be restricted about a hundred words because of computational errors, i.e. the occurrence probability of a dialogue which has a thousand words tends to be less than 10-1000 and we fail to construct HMM because of lack of computational precision. In this paper, we propose a new approach for this problem by HMM whose state outputs a symbol of an utterance. Every utterance is classified into some symbols of a segment by a Bayesian classifying method, then we construct an HMM for the target dialogue. The HMM in our method can handle a long dialogue whose length is about 1500 words for 1000 kinds of words. We used 62 dialogues by 68 testee and evaluate our method.

著者

小谷 善行

出版者

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

雑誌

情報処理 (ISSN:04478053)

巻号頁・発行日

vol.46, no.7, pp.811-813, 2005-07-15

参考文献数

5

被引用文献数

3

著者

蛭田 雄一 桑原 悟 柴原 一友 但馬 康宏 小谷 善行

出版者

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

雑誌

情報処理学会研究報告コンピュータと教育(CE) (ISSN:09196072)

巻号頁・発行日

vol.2008, no.13, pp.41-48, 2008-02-16

---

日本の情報教育・情報処理教育に関する提言2005では,国民全体に対して何らかのプログラミング教育が必要であるとしている.プログラミングはとても知的な活動であるが故に,その面白さを感じるまでに多くの時間を要する.多くの人がつまづく原因としては,キータイピングが億劫であることや,構文規則等を習得が難しいことがあげられる.そこで,本稿ではより考える過程に重点をおき,ソースプログラムを作成する段階から楽しめる学習環境「すご@ぷろ」を提案し実装した.本稿ではすご@ぷろの提案と,それらを約80名程度の学生に対し講義で実験を行った.その結果,半数以上の学生が一般的なプログラミング言語ではみられない双六のマスを並べて形を作ることを楽しんでいた.結論として,短い講義時間の中で約 80% 以上の学生に対し,プログラミングに対し興味を持たせることに成功した.In the proposal 2005 about the Japanese information education / computer science education, it is assumed that some kind of programming educationis necessary for the all Japanese. It need much tie because programming is very intellectual activity until the human feels the fun. Reasons why many people fail in are probably troublesome key typing and the difficulty of learning sentence structure rules. Therefore we put an important point by this report in a process to think about more and we suggested learning environment "sugo@pro" to be able to enjoy when coding the source program and implemented it. In this paper, we tested them by a lecture for about 80 students. As a result, it enjoyed that many students arranged and sat square of the sugoroku and made something shape. In concolusion, we succeeded in having them be interested for programming more than about 80% students in short lecture time.

著者

是川 空 小谷 善行

雑誌

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

巻号頁・発行日

vol.53, no.6, pp.1617-1624, 2012-06-15

---

本研究ではパズルの思考過程のモデル化の研究として,四川省と呼ばれる麻雀牌を利用したパズルの難易度推定を行う.これは四川省パズルの問題に対して,計算機によって算出された状態空間が持つ特徴量と,人間が実際に問題を解いているときの正答率や解答時間などの難易度に関わる項目との間にどのような相関があるかを測るものである.四川省パズルの持つ状態空間は解状態への経路を持つ状態と持たない状態の2つに分割することができる.解状態への経路を持つ局面をsolvable局面,持たない局面をunsolvable局面と定義し,問題から局面構造の特徴として平均可能手数,solvable局面とunsolvable局面の割合,平均unsolvable遷移パス割合,unsolvable局面空間の最長経路の4種類の特徴量を抽出した.それに対し人間のパズルを解く思考過程を得る方法として,Web上に四川省プログラムを設置しデータを収集した.収集されたデータから各問題に対する解答時間と正答率に対する難易度指標値を算出した.問題から得られた特徴と収集したデータから算出した難易度指標値の間の相関を測るため,回帰分析によって特徴から難易度指標値を推定する予測式を得た.この結果より平均解答時間を推定するには平均可能手数が大きく寄与していることが分かった.一方で正答率は平均可能手数に加え状態空間構造の特徴を回帰式に導入することで相関が向上した.

著者

三塩 武徳 小谷 善行

出版者

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

雑誌

研究報告ゲーム情報学(GI) (ISSN:09196072)

巻号頁・発行日

vol.2014, no.4, pp.1-6, 2014-03-10

---

ゲームの不完全情報の推定を行うアルゴリズム Using Past Playout(UPP) を提案する.UPP はモンテカルロ法において過去のシミュレーション結果のうち現在局面に至るものを取り出し,仮定した情報の間の勝率を比較する.相手側の勝率が高い部分は実際の局面と等しい可能性が高い.これを使って不完全情報の推定を行う.アレックス・ランドルフ (Alex Randolph) [1] によって発表された二人零和確定不完全情報ゲームである 「ガイスター」 において UPP を用いたプログラムと既存手法の猪突戦法,および通常のモンテカルロ法とで対局を行った.結果,猪突戦法に対しては思考時間 0.25 秒で 94%の勝率,モンテカルロ法との対局ではお互いの思考時間 1 秒で 55%の勝率を挙げた.これらの結果より,ガイスターにおける UPP の有効性を示した.We propose an algorithm Using Past Playout (UPP) which estimates incomplete information of the game. The algorithm UPP extracts the playouts of current position from the simulation results of the past, and compares the winning percentages between the assumed information. The higher the part the other side's winning percentage is, the higher the possibility equal to actual aspects is. It estimates the incomplete information with it. We performed experiment of playing using UPP, Foolhardiness (Chototsu) Tactics and normal Monte Carlo method in the game "geister", two person zero sum determined incomplete information game, which was invented by ALEX RANDOLPH[1]. As a result, UPP listed a winning percentage of 94% in 0.25 seconds thinking time against Foolhardiness (Chototsu) Tactics and 55% in one seconds thinking time for both against normal Monte Carlo method. The results show the effectiveness of the UPP in it.