1.6MB - 高知工科大学

平成 25 年度
学士学位論文
文書分類手法を用いた自然言語仕様からの
プログラム部品自動選択
Automatic selection of program components
from natural language specification
with document classification
1140385
山内雅斗
指導教員
高田喜朗
2014 年 2 月 28 日
高知工科大学情報学群
要旨
文書分類手法を用いた自然言語仕様からの
プログラム部品自動選択
山内雅斗
ソフトウェアの開発には多大な労力が必要である. それは大きなソフトウェア開発になれ
ばよりいっそう際立つことになる. 仮に開発を一部自動化できるならば負担の軽減につなが
る. 本論文では, 自然言語の仕様書からそのプログラムが使用するであろうプログラム部品
を予測する方法を研究する. ソフトウェアをプログラム部品の集合として考えた場合, 仕様
書には使用されるプログラム部品が潜在的に記述されている. 仕様書に潜在的に書かれたプ
ログラム部品を選択するために文書分類手法を利用する. ここではベイズ分類器を使用して
仕様書からプログラム部品を選択可能であるかどうかを調べる.
結果, 自然言語の仕様書に対して分類器を使用することである程度プログラム部品を推測
することができた. 今後, 選択されたプログラム部品から実際に実行可能なプログラムを構
築することが可能かを吟味する必要がある.
キーワード
プログラム自動生成, 自然言語仕様, ベイズ分類器, プログラム部品
–i–
Abstract
Automatic selection of program components
from natural language specification
with document classification
Masato YAMAUCHI
It is diﬃculty of us to develop a software. The bigger software, the more diﬃcult
we develop it. If we can automate programing, we would reduce the burden. In this
paper, we investigate the automatic selection of program components from natural
language specification with document classification. We assume that a software is a
set of components. Specification latently indicates what components should be used.
We predicate the program components using a document classification method. In
this paper we investigate whether we can predicate the program components with the
Bayesian classifier. The results suggest that the classification is possible. As a future
work, we will examine how to build an executable program from the selected program
components.
key words
Automatic program generation,
Bayesian classifier, Program components
– ii –
Natural language specification,
目次
第1章
1.1
第2章
2.1
第3章
はじめに
1
研究目的と背景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
関連技術
3
単純ベイズ分類器
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
実験と評価
4
3.1
実験方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
3.2
評価方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
3.2.1
正解率という尺度での性能評価方法
. . . . . . . . . . . . . . . . .
5
3.2.2
F 値という尺度での性能評価方法 . . . . . . . . . . . . . . . . . . .
5
3.3
評価 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
3.4
考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
結論
8
第4章
謝辞
9
参考文献
付録 A
10
実験データ
11
– iii –
図目次
1.1
プログラムと仕様書の関係 . . . . . . . . . . . . . . . . . . . . . . . . . .
1
A.1 オンラインマニュアルを学習に使用した結果 1 . . . . . . . . . . . . . . . .
11
A.2 オンラインマニュアルを学習に使用した結果 2 . . . . . . . . . . . . . . . .
12
A.3 コメント文を学習に使用した結果 1 . . . . . . . . . . . . . . . . . . . . . .
13
A.4 コメント文を学習に使用した結果 2 . . . . . . . . . . . . . . . . . . . . . .
14
– iv –
表目次
3.1
正解率の平均
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
3.2
F 値の平均 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
A.1 それぞれの分類器における F 値の部品ごとの比較 1 . . . . . . . . . . . . .
15
A.2 それぞれの分類器における F 値の部品ごとの比較 2 . . . . . . . . . . . . .
16
A.3 それぞれの分類器における F 値の部品ごとの比較 3 . . . . . . . . . . . . .
17
A.4 それぞれの分類器における F 値の部品ごとの比較 4 . . . . . . . . . . . . .
18
–v–
第1章
はじめに
1.1
研究目的と背景
ソフトウェアの開発には労力が必要である. もし, 仕様書からプログラムを作り出すこと
が可能ならば開発者の労力は大きく軽減される. 自然言語で記述されたプログラムの仕様書
から, プログラムを自動生成することは困難である. 困難な理由として２つが挙げられる.
１つ目の理由は, 自然言語は曖昧性という特徴を持つ点である. ２つ目の理由は, 仕様書とプ
ログラムが一般に直訳関係では無いという点である.
そこで, 現実的な目標として自然言語の仕様書からプログラム部品を選択することとする.
ここでプログラムはプログラム部品の集合であると考える. そして仕様書にはプログラムが
使用する部品の要素に関する情報が潜在的に記述されているものと考える (図 1.1).
ここでは, プログラム部品を選択する手法として文書分類器を使用する. すなわち, プログ
図 1.1 プログラムと仕様書の関係
–1–
1.1 研究目的と背景
ラム部品をカテゴリとして, 文書を分類する. 本研究では文書分類器を使用して自然言語仕
様からプログラム部品の自動選択が可能かどうかを検証する.
–2–
第2章
関連技術
2.1
単純ベイズ分類器
単純ベイズ分類器の元となる確率モデルは強い独立性仮定と共にベイズの定理を適用する
ことに基づいている [3]. P (B) を事象 B が発生する確率とする. P (B|A) を事象 A が起き
た後での事象 B の確率とする. ベイズの定理によれば, P (A) > 0 の条件のもと, 以下の等式
が成り立つ,
P (B|A) =
P (A|B)P (B)
P (A)
特徴変数 F1 , F2 , ..., Fn が与えられた時のカテゴリ C の確率はベイズの定理より以下のよう
に書くことができる.
P (C|F1 , F2 , ..., Fn ) =
P (C)P (F1 , F2 , ..., Fn |C)
P (F1 , F2 , ..., Fn )
分子は乗法定理から次のように変形することが可能である. 分母は C に依存しないためここ
では分母を考慮しない. 条件付き独立性を仮定すると分子は以下のようになる.
P (C, F1 , F2 , ..., Fn ) = P (C)P (F1 |C)P (F2 |C)...P (Fn |C)
カテゴリの決定は, 事後確率が最大となる c を選択することで行う.
n
∏
classify(f1 , ..., fn ) = argmax P (C = c)
P (Fi = fi |C = c)
c
i=1
–3–
第3章
実験と評価
3.1
実験方法
本実験では, C 言語で記述されたソースコードと自然言語で記述されたプログラムの説明
文, オンラインマニュアル, およびソースコード中のコメント文を使用する. 説明文, オンラ
インマニュアル, ソースコードのコメント文を仕様書とする. ソースコードの数は 500 個で
あり, そのソースコードの半数である 250 個に添付されている仕様書を学習用の情報として
使用する. また, 残りの 250 個に付属されている仕様書を推定精度の評価に使用する.
ソースコードは Google code [5] で配布されているアプリケーションと Unix コマンドの
ものを使用する. テキストデータは全て英文であり, 語数は最小 271 語, 最大 22707 語, 平均
2577 語である. なお, 2.1 節においての特徴変数は仕様書中の各単語の出現回数に相当する.
分類器にはベイズ分類器 [1][2] を使用する.
分類器は 2 種類用意する. 一方はソースコード中のコメント文を使い学習した分類器, も
う一方はプログラムの説明文とオンラインマニュアルを使用して学習した分類器である.
分類器は自然言語で記述された文書から使用されると推測できるプログラム部品を選択す
るというものである. 今回の実験でのプログラム部品は C 言語の標準ライブラリ関数であ
る. 標準ライブラリ関数の数だけ分類器を用意し, 各分類器は「その関数を使う」, または
「使わない」の 2 カテゴリのうちどちらか一方を出力する. 本実験では, ライブラリ関数は
80 種類使用する.
–4–
3.2 評価方法
3.2
3.2.1
評価方法
正解率という尺度での性能評価方法
正解率という観点での性能評価方法は, 選択結果の正解率を使用する. 例えば, A という
部品を使うプログラムの仕様書 (AU) が 50 個, A という部品を使わないプログラムの仕様
書 (ANU) が 50 個存在したとする. AU のうち分類器が部品 A を使うと判定したものが 30
個, ANU のうち分類器が部品 A を使わないと判定したものが 40 個であった時, 正解率は
(30 + 40)/(50 + 50) = 70% となる.
3.2.2
F 値という尺度での性能評価方法
分類器単体の性能評価方法は適合率 (P ) と再現率 (R) の相加平均 (F 値) を求めて評価す
る [4]. 部品を一つ固定し, その部品を実際使用しているプログラムの仕様書のうち, その部
品を使用すると判断されたもの (正解) の数を tp, 使用しないと判断されたもの (不正解) の
数を f n とする. 同様に, その部品を使用していないプログラムの仕様書のうち, その部品を
使用しないと判断されたもの (正解) の数を tn, 使用すると判断されたもの (不正解) の数を
f p と定義した時, 適合率 (P ) は以下の式で定義される.
P =
tp
tp + f p
次に再現率 (R) は以下の式で定義される.
R=
tp
tp + f n
よって F 値 (F ) は適合率と再現率の相加平均なので次のように求まる.
F =
2P R
P +R
これで 1 つの分類器に対する性能が求まる. F 値は 1 に近いほど分類システムとして性能が
良い.
n 個の分類器がそれぞれの F 値を F1 , F2 , ..., Fn とする. 分類器の集合の評価をするとき
は, F1 から Fn の平均値を取る.
–5–
3.3 評価
表 3.1
コメント文での学習
添付文書での学習
89.1%
82.0%
表 3.2
3.3
正解率の平均
F 値の平均
コメント文での学習
添付文書での学習
0.86
0.82
評価
オンラインマニュアルと添付文書を使用して学習した分類器全体の正解率の平均は 82.1%,
ソースコード中のコメント文を使用して学習した分類器全体の正解率の平均は 89.1% となっ
た (表 3.1).
また, オンラインマニュアルと添付文書を使用して学習した分類器全体の F 値の平均は
0.82, ソースコード中のコメント文を使用して学習した分類器全体の正解率の平均は 0.86 と
なった (表 3.2).
以上の結果よりオンラインマニュアル, 添付文書を使用して学習を行った分類器よりも
ソースコード中のコメント文を使用して学習した分類器のほうが精度が高いという結果と
なった.
3.4
考察
上記のように, おおよそ 8 割前後の確率で, 該当部品を選択できることがわかった. よっ
て, 100%の精度は無いがある程度のプログラム部品の選択は可能であると言える. 実際に
部品単体ごとの分析結果においても 8 割程度の分類性能が出ていると言える (付録のグラフ
A.1∼A.4 を参照).
また, コメント文を使用して学習させた分類器のほうが添付ドキュメントとオンラインマ
–6–
3.4 考察
ニュアルを使用して学習させた分類器より分類性能が高い (付録の表 A.1∼A.4 を参照). こ
のような結果となった理由としてオンラインマニュアルやプログラムの添付文書には主に使
用方法が書かれていることに対して, コメント文にはプログラムの内容に関連した文書が多
く書かれているためと推測する.
一方, qsort など予測精度が低いものも確認される (付録のグラフ A.1∼A.4 を参照). qsort
については, qsort は使っていないがそれ以外の方法でソーティングを行うプログラムの仕
様書に対し, 分類器が「qsort を使用する」と判定している場合があることが確認された.
–7–
第4章
結論
本研究では既存の文書分類手法によってプログラムの仕様書からプログラム部品を選択す
ることが可能かどうかを調べるため, ベイズ分類器を使用した実験を行った. 検証の結果お
およそ 8 割前後の確率で選択することができるということが判明した. よって, 100% の精
度では無いにしろある程度プログラム部品の選択は可能であると言える.
現在の状態では, 部品が使用されているか, 使用されていないかが推測可能であるが, 部品
の組み合わせの情報は得ることができない. そのため, 実際のソースコードのようにコンパ
イル後にすぐ実行するということはできない. 問題点は, ソースコードのどの場所に部品が
使用されているかということや, どのような構造のプログラムであるかを推測できない点で
ある. 今後の目標として, 選択されたプログラム部品をソースコードに近い形に組み立てる
方法を考察する予定である.
–8–
謝辞
本研究を進めるにあたり, 助言, 御指導をいただきました高知工科大学情報学群高田喜朗
准教授に心より感謝申し上げます. また, 本研究の副査を快く引き受けてくださった横山和
俊教授, 吉田真一准教授にも心より感謝申し上げます. そして, 様々な助言をいただきまし
た高田研究室の皆様にも心より感謝申し上げます.
また, 技術的援助や, 学生生活, 精神面を支えてくださった同期の皆様, 先輩の皆様, 後輩
の皆様, Daniel Rojas 氏, Alexander Vargas 氏, Ирина Уланова氏に心より感
謝申し上げます.
最後に本学で勉強をする機会を与えてくれ, 経済面, 精神面で支えてくれた親, 兄弟にも心
より感謝申し上げます.
–9–
参考文献
[1] Haoyang Liu, “Applications of Bayesian Classifiers”, VDM Verlag, 2008.
[2] “Naive Bayes classifier in 50 lines”, http://ebiquity.umbc.edu/blogger/2010/12/07/naivebayes-classifier-in-50-lines/
[3] C. M. ビショップ, “パターン認識と機械学習 : ベイズ理論による統計的予測”, 丸善出
版, 2012.
[4] David M W, “Evaluation: From Precision, Recall and F-Factor to ROC, Informedness, Markedness and Correlation”, 2012
[5] “Google code”, https://code.google.com/
– 10 –
付録 A
実験データ
図 A.1
オンラインマニュアルを学習に使用した結果 1
– 11 –
図 A.2
オンラインマニュアルを学習に使用した結果 2
– 12 –
図 A.3
コメント文を学習に使用した結果 1
– 13 –
図 A.4
コメント文を学習に使用した結果 2
– 14 –
表 A.1
それぞれの分類器における F 値の部品ごとの比較 1
name
コメント文で学習した
オンラインマニュアル, 添付文書
abort
0.85
0.8
abs
0.86
0.82
acos
0.87
0.88
asin
0.89
0.87
atan
0.9
0.87
atan2
0.87
0.87
atof
0.86
0.82
atoi
0.9
0.86
atol
0.86
0.81
calloc
0.87
0.82
ceil
0.91
0.84
clock
0.82
0.78
cos
0.89
0.88
cosh
0.91
0.86
exit
0.91
0.87
exp
0.91
0.83
fabs
0.91
0.88
fclose
0.89
0.86
ferror
0.89
0.83
ﬄush
0.38
0.72
– 15 –
表 A.2
それぞれの分類器における F 値の部品ごとの比較 2
name
コメント文で学習した
オンラインマニュアル, 添付文書
fgetc
0.89
0.85
floor
0.74
0.59
fmod
0.9
0.88
fopen
0.89
0.86
fputc
0.89
0.86
fread
0.89
0.84
free
0.88
0.87
freopen
0.87
0.86
fseek
0.88
0.86
fwrite
0.88
0.84
getc
0.61
0.36
getchar
0.9
0.86
gets
0.88
0.86
gets
0.9
0.86
isalnum
0.9
0.87
isalpha
0.91
0.87
isdigit
0.91
0.87
islower
0.85
0.79
isspace
0.91
0.87
isupper
0.85
0.8
– 16 –
表 A.3
それぞれの分類器における F 値の部品ごとの比較 3
name
コメント文で学習した
オンラインマニュアル, 添付文書
fgetc
0.89
0.85
floor
0.74
0.59
fmod
0.9
0.88
fopen
0.89
0.86
fputc
0.89
0.86
fread
0.89
0.84
free
0.88
0.87
freopen
0.87
0.86
fseek
0.88
0.86
fwrite
0.88
0.84
getc
0.61
0.36
getchar
0.9
0.86
gets
0.88
0.86
gets
0.9
0.86
isalnum
0.9
0.87
isalpha
0.91
0.87
isdigit
0.91
0.87
islower
0.85
0.79
isspace
0.91
0.87
isupper
0.85
0.8
– 17 –
表 A.4
それぞれの分類器における F 値の部品ごとの比較 4
name
コメント文で学習した
オンラインマニュアル, 添付文書
srand
0.9
0.87
stderror
0.86
0.86
strcat
0.91
0.88
strchr
0.92
0.88
strcmp
0.84
0.78
strcpy
0.91
0.87
strcspn
0.91
0.88
strerror
0.89
0.88
strlen
0.91
0.88
strncat
0.84
0.78
strncmp
0.91
0.88
strncpy
0.84
0.79
strrchr
0.89
0.88
strtod
0.86
0.81
strtok
0.78
0.77
strtoul
0.86
0.81
system
0.9
0.87
tan
0.9
0.88
tanh
0.76
0.62
time
0.89
0.79
– 18 –

Download Report