## ＜テクニカルレポート＞Complexity of Computing Generalized VC-Dimensions

作成者 作成者姓名 Shinohara, Ayumi 篠原, 歩 所属機関 所属機関名 Research Institute of Fundamental Information Science, Kyushu University 九州大学理学部附属基礎情報学研究施設 英語 Research Institute of Fundamental Information Science, Kyushu University 九州大学理学部附属基礎情報学研究施設 1993-10-12 RIFIS Technical Report 78 accepted open access In the PAC-learning model, the Vapnik-Chervonenkis (VC) dimension plays the key role to estimate the polynomial-sample learnability of a class of binary functions. For a class of multi-valued function...s, the notion has been generalized in various ways. This paper investigates the complexity of computing some of generalized VC-dimensions: $VC^*$- dimension, $Psi _*$-dimension, and $Pai _G$-dimension. For each dimension, we consider a decision problem that is, for a given matrix representing a class F of functions and an integer K, to determine whether the dimension of .F is greater than K or not. We prove that the $VC^*$-dimension problem is polynomial-time reducible to the satisfiability problem of length J with $Oleft (log^2 J\right)$ variables, which includes the original VC-dimension problem as a special case. We also show that the $Psi _G$ -dimension problem is still reducible to the satisfiability problem of length J with $Oleft (log^2 J\right)$ , while the $Psi_*$,-dimension problem becomes NP-complete.続きを見る

### 本文情報を非表示

rifis-tr-78 pdf 756 KB 76

### 詳細

レコードID 3177 査読無 RIFIS Technical Report || 78 || p1-12 http://www.i.kyushu-u.ac.jp/research/report.html Proc. European Conference on Machine Learning, Lecture Notes in Artificial Intelligence 784, 415-418, 1994 テクニカルレポート 2009.04.22 2017.01.20