不完全データの論理的解析

• Item type: SIG Technical Reports(1)
• 公開日: 1998-07-08
• タイトル: 不完全データの論理的解析
• タイトル / 言語: en
• タイトル: Logical Analysis of Incomplete Data
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 京都大学情報学研究科
• 著者所属: 大阪大学基礎工学研究科
• 著者所属: Rutgers University
• 著者所属(英): en
• 著者所属(英): Kyoto University
• 著者所属(英): en
• 著者所属(英): Osaka University
• 著者所属(英): en
• 著者所属(英): Rutgers University
• 著者名: 茨木, 俊秀; 牧野, 和久; Endre, Boros
• 著者名(英): Toshihide, Ibaraki; Kazuhisa, Makino; Endre, Boros
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 正例のデータ集合T⊆｛0 1｝^nと負例のデータ集合F⊆｛0 1｝^nからなる部分定義論理関数(T F)が与えられたとき、それと整合する論理関数〓：｛0 1｝^n→｛0 1｝（すなわち拡大）を求める問題はデータの論理的解析の一形態である。本研究では、データに誤りや不完全ビットが存在する場合の対応として、誤りベクトル数を最小にするという基準、不完全ビットの扱いに関してロバスト性の度合に基づく3種の基準を提案し、それらの下で拡大を求める問題を計算の複雑さの観点から調べた。その結果、〓の属する関数のクラスCに応じて多項式時間で解ける場合とNP困難になる場合がどのように区別されるかが明らかになった。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Given a partially defined Boolean function (T,F) defined by a set of positive examples T ⊆ {0,1}^n and a set of negative examples F ⊆ {0,1}^n , the problem of finding a Boolean function 〓 : {0,1}^n → {0,1} consistent with it (i.e., an extension of (T,F)) has been studied as logical analysis of data. This paper considers the situation in which data may contain errors and/or incomplete bits. We introduce the criterion of minimizing the number of error vectors and three criteria of how to allow robustness of incomplete data. Under these criteria, we clarify the complexity of the problems to find the existence of extensions in several classes of functions C. It turns out that some problems can be solved in polynomial time, while others are NP-complete.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10112482
• 書誌情報: 情報処理学会研究報告データベースシステム（DBS）; 巻 1998, 号 57(1998-DBS-116), p. 413-420, 発行日 1998-07-08
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会