半空間の和集合の例からの推定

• Item type: SIG Technical Reports(1)
• 公開日: 2002-05-23
• タイトル: 半空間の和集合の例からの推定
• タイトル / 言語: en
• タイトル: Inferring a Union of Halfspaces from Examples
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 京都大学化学研究所バイオインフォマティクスセンター／京都大学大学院情報学研究科知能情報学専攻
• 著者所属: 東京大学医科学研究所 ヒトゲノム解析センター
• 著者所属(英): en
• 著者所属(英): Bioinformatics Center, Institute for Chemical Research, Kyoto University/Dept. Intelligence Science and Technology, Graduate School of Informatics, Kyoto University
• 著者所属(英): en
• 著者所属(英): Human Genome Center, Institute of Medical Science, University of Tokyo
• 著者名: 阿久津, 達也; オットザーシャ
• 著者名(英): Tatsuya, Akutsu; Sascha, Ott
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 半空間を利用して分類を行う研究はサポートベクタマシンなどを始めとして盛んに行われている。本稿では、ユークリッド空間上の正例と負例が与えられた時、半空間の和集合を用いて分離する問題を考える。なお、和集合は正例のみをカバーするものとする。本稿では、分離するために必要な半空間の個数を最小化する問題について主に考察し、一般にはグラフ彩色問題と少なくとも同等以上に近似困難であることを示す。一方、２次元においては多項式時間で最適解が計算できることも示す。さらに、近似的に分類する場合などの関連する結果についても示す。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We consider the following problem which is motivated by applications in Bioinformatics: given positive and negative points in d-dimensions, find a minimum cardinality set of halfspaces whose union covers all positive points and no negative points. We prove that approximation of this problem is at least as hard as approximation of graph coloring. On the other hand, we show that the two-dimensional case of the problem can be solved in polynomial time. Other related results are shown, too.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2002, 号 42(2002-AL-084), p. 73-80, 発行日 2002-05-23
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会