| 講演名 | 2013-03-08 疎グラフに基づくグループテスト方式に関する情報理論解析について 和田山 正, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本稿では、疎グラフに基づく非適応的グループテスト方式に関する情報理論的な解析を示す。n個の検査対象は、確率pのi.i.d.ベルヌーイ確率変数によりモデル化される。検査は、(l,r,n)のパラメータを持つ疎2部グラフにより定められる。ここで、lは左ノード次数、rは右ノード次数,nは左ノードの個数を表す。本研究の主要な結果は、任意に小さい推定誤り率の推定器が存在するための条件の導出である。この条件は、典型系列推定器の誤り率の上界のアンサンブル平均より導かれる。本稿において導かれた結果は、検査対象数が無限の漸近領域において、グループテスト問題の再現可能性に関するしきい値の存在を強く示唆している。 |
| 抄録(英) | In this paper, an information theoretic analysis on non-adaptive group testing schemes based on sparse pooling graphs is presented. The binary status of objects to be tested are modeled by i.i.d. Bernoulli random variables with probability p. An (l, n)-regular pooling graph is a bipartite graph with left node degree l and right node degree r, where n is the number of left nodes. Two scenarios are considered; one is the noiseless setting and another is the noisy setting. The main contributions of this paper are direct part theorems which give conditions for existence of an estimator achieving arbitrary small estimation error probability. The direct part theorems are proved by averaging an upper bound on estimation error probability of the typical set estimator over an (l,r,n)-regular pooling graph ensemble. The numerical results obtained here indicate sharp threshold behaviors in the asymptotic regime. |
| キーワード(和) | グループテスト / スパースグラフ / しきい値 / 典型系列推定器 |
| キーワード(英) | group testing / sparse graph / threshold / typical set estimator |
| 資料番号 | IT2012-103,ISEC2012-121,WBS2012-89 |
| 発行日 |
| 研究会情報 | |
| 研究会 | IT |
|---|---|
| 開催期間 | 2013/2/28(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Theory (IT) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 疎グラフに基づくグループテスト方式に関する情報理論解析について |
| サブタイトル（和） | |
| タイトル（英） | An Analysis on Non-Adaptive Group Testing based on Sparse Pooling Graphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グループテスト / group testing |
| キーワード(2)（和/英） | スパースグラフ / sparse graph |
| キーワード(3)（和/英） | しきい値 / threshold |
| キーワード(4)（和/英） | 典型系列推定器 / typical set estimator |
| 第 1 著者 氏名（和/英） | 和田山 正 / Tadashi WADAYAMA |
| 第 1 著者 所属（和/英） | 名古屋工業大学 Nagoya Institute of Technology |
| 発表年月日 | 2013-03-08 |
| 資料番号 | IT2012-103,ISEC2012-121,WBS2012-89 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | 460 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |