E1-1

Multiple Zero-suppressed Binary Decision Diagrams
による自動テスト構成
Automated Test Assemblyusing Multiple Zero-suppressed Binary Decision Diagrams
渕本 壱真*1, 植野 真臣*1
Kazuma FUCHIMOTO*1, Kazuma FUCHIMOTO*1*1
電気通信大学大学院 情報理工学研究科*1
Graduate School of Informatics and Engineering, University of Electro-Communications
Email: fuchimoto@ai.lab.uec.ac.jp
あらまし：近年，異なる問題で構成されているにも関わらず，同一精度の測定を実現できる e-Testing が注目されている．現在，最も多くのテストを構成する手法として，Zero-suppressed Binary Decision Diagrams(ZDD)を用いた手法が提案されている．しかし，この手法ではテスト数が各節点の変数順序に影響される．
そこで，本研究では変数順序を考慮した ZDD 手法を提案する．
キーワード：e-Testing，項目反応理論，教育評価，Zero-suppressed Binary Decision Diagrams

1.

情報量を項目情報量と呼び，以下の式で表す．

はじめに

e-Testing とは，異なる問題で構成されているのも関わらず，同一精度の測定を実現できるコンピューターテストのことである．e-Testing では，同一能力の受検者が異なるテストを受検しても同一得点となる保証がある．実際に，e-Testing は医療系大学間共用試験や情報処理技術者試験などハイステークスな試験に用いられている．e-Testing の最も重要な課題の一つは問題データベースから可能な限り多くのテスト（問題の組合せ）を自動構成することである．
これにより，各受検者は異なるテストを受験でき，カンニング対策や複数回受験を可能にする．したがって，受検者数と同数以上のテストが自動構成できることが望ましい．
近年，最も多くのテストを自動構成する手法として ， 渕 本 ら は 二 分 決 定 木 の 圧 縮 表 現 の Zerosuppressed Binary Decision Diagrams (ZDD) (1)を用いた手法(2)を提案した．しかし，この手法は各問題項目を表す変数の処理順がテスト数に大きく影響を与える．
そこで，本研究では，この変数順序を入れ替えた複数の ZDD を生成することでこの影響を緩和でき，従来手法よりも多くのテストを構成できた．

2.

𝐼" +𝜃! , = 1.7# 𝑎"# 𝑝" +𝜃! , <1 − 𝑝" +𝜃! ,=(2)

項目情報量の総和をテスト情報量と呼び，以下の式で表す．
𝐼+𝜃! , = ? 1.7# 𝑎"# 𝑝" +𝜃! , <1 − 𝑝" +𝜃! ,= #(2)
テスト情報量の逆数は受検者の能力推定値の漸近分散に収束する．そのため，多くの先行研究(2,3)は受検者の能力値𝜃$ = (𝜃% , 𝜃# , … , 𝜃& )におけるテスト情報量の上限UB' $・下限LB'! 制約の範囲に収まるテストを受検者の測定精度が等質であるとしている．
(3)
LB'! ≤ 𝐼+𝜃! , ≤ UB' $3.

ZDD を用いた自動テスト構成

ZDD (1)（図 1–右）とは，二分決定木（図 1–左）の圧縮表現で，冗長な節点の削除と等価な節点の共有により得られる．これにより，組合せ集合を効率良く列挙・演算できる．現在，ZDD を用いた自動テスト構成手法(2)が最も多くのテストを生成できる．この手法では，図 1 のように，各節点が各問題と対応し，各節点はその問題を出題するか否かで二項目反応理論

e-Testing の自動構成手法の多くは項目反応理論を用いて同一精度の測定を実現する．項目反応理論で最もよく使われる 2 母数ロジスティックモデルでは，能力値𝜃! ∈ (−∞, ∞)を持つ受験者𝑗が項目𝑖に正答する確率𝑝" (𝜃! )を以下のように定義する．
1(1)𝑝" +𝜃! , =1 + exp (−1.7𝑎" (𝜃! − 𝑏" )ただし，𝑎" ∈ [0, ∞], 𝑏" ∈ [0, ∞]は識別力パラメータ，困難度パラメータと呼ばれる項目パラメータである．
また，項目𝑖において，確率𝑝" +𝜃! ,のフィッシャー

図 1. 二分決定木（左）と ZDD（右）分する．また，テスト情報量がある閾値𝐼() 以下となる二節点を共有する．この際，二節点のテスト情― 31 ―

教育システム情報学会 JSiSE2023
第48回全国大会 2023/8/29-8/31

報量が平均値近似される．ZDD の構築は幅優先技法(4,5)を用いる．これにより，根から葉までの各経路がそれぞれ近似の範囲内で測定精度の等質なテストとなる．この ZDD からランダムサンプリング(1)を繰り返し，式（3）の制約を満たすテスト群を eTesting で用いる．これにより，従来手法よりも多くのテストを構成できた．しかし，この手法は測定精度を近似するため，節点を共有する度に測定誤差が大きくなる．したがって，変数順序が大きい問題項目ほど，この近似の影響を強く受けたテストに属する可能性が高くなる．

4.

表 1. テスト構成数の比較
OC ZDD(2)Proposal
4320862612215916473
512
20878310290
24147086
16578928 1545602
1602380
32 1548327
1602872
36 1548498
1602959
40 1548902
1603087

提案手法

変数順序の影響を緩和するために，本研究では，
図 2 のように，節点の変数順序を入れ替えた複数のZDD を先行研究(2)と同様に𝛼個生成する．この際，変数順序は ZDD ごとにランダムに並び替る．
その後，提案手法は以下のアルゴリズムでテスト群𝒯を求める．
1. 𝛼個の ZDD の中からランダムに一つ選択する．
2. 選択した ZDD の中からランダムサンプリングにより，テストを一つ取り出す．
3. ランダムサンプリングしたテストが式（3）やその他のテスト制約を満たす場合，テスト群𝒯に追加する．
4. 𝛼個の ZDD 全てについて，3 でサンプリングしたテストに相当する経路を削除する（差集合をとる）．
5. 予め決めた制限時間か𝛼個の ZDD 全てについて全探索するまで，提案手法は 1〜3 を繰り返す．

図 2. 提案手法の概要

5.

先行研究(2)と同様である．
結果を表 1 に示す．ただし，OC とは任意の 2 つのテスト間に許される問題の最大重複数である．例
えば，OC=0 の場合，任意の 2 つのテスト間に重複する問題が存在しない．表 1 より，提案手法は従来手法よりも多くのテストを構成できた．これにより，より大規模な試験において，e-Testing を実施できる．

評価実験

提案手法の有効性を示すために，比較実験を行った．実験には実際の試験で用いられている実データを用いた．この実データは 978 問の問題項目が格納されたデータベースである．このデータベースから制限時間 1 日として，100 問のテストを自動構成する．また，生成する ZDD の個数𝛼は予め比較実験を行い，最も多くテストを生成できた値を用いた．テ
スト情報量の制約等，そのほかの実験条件・手順はまた，紙面の都合上詳細は割愛するが，ZDD の構造に関する以下の 2 点を実験により確認できた．
1. 節点の共有条件である閾値𝐼() の値に反比例して，枝刈りの回数が増加すること
2. ZDD の個数𝛼の値がテスト構成数に与える影響

6.

まとめ

本研究では，さらに多くのテストを自動構成できる ZDD 手法を提案した．今後は適応型テストへのZDD 手法の拡張を目指す．なお，本稿で説明を省略した ZDD 手法の特徴やアルゴリズムは発表当日に説明する．
参考文献(1) Minato, Shin-ichi. Zero-suppressed BDDs for set
manipulation in combinatorial problems. Proceedings ofthe 30th International Design Automation Conference.
1993.
(2) 渕本 壱真，湊 真一, 植野 真臣．Zero-suppressed
Binary Decision Diagrams を用いた自動テスト構成．人
工知能学会論文誌 2022.
(3) Kazuma Fuchimoto, Takatoshi Ishii, and Maomi Ueno.
Hybrid maximum clique algorithm using parallel integer
programming for uniform test assembly.
IEEETransactions on Learning Technologies, (2022).
(4) Iwashita, H. and Minato, S.-i.: Efficient top-down ZDD
construction techniques using recursive specifications,Technical report, Hokkaido University, Division ofComputer Science, TCS Technical Reports, TCS-TR-A-1369 (2013)(5) Knuth, D. E.: The art of computer programming: Bitwise
tricks & techniques, Binary Decision Diagrams, Vol. 4,AddisonWesley (2009)― 32 ―