| Presentation | 1994/7/23 On the Complexity of Hypothesis Space and the Sample Complexity for Machine Learning Makoto Nakazawa, Toshiyasu Matsushima, Shigeichi Hirasawa, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The problem of learning a concept from examples in the model introduced by Valiant is discussed.According to the traditional ways of thinking,it is assumed that the learnability is independent of theoccurence probability qf instance.By utilizing this probability,we propose the metric as a new measure to determine the complexity,of hypothesis space.The metric measures the hardness of discrimination between hypotheses. Furthermore,we obtain the average metric dependent on prior information.This metric is the measure of complexity for hypothesis space in the average.Similarly in the worst case,we obtain the minimum metric. We make clear the relationship between these measures and the Vapnik-Chervonenkis(VC)dimension.Finally,we show the upper bound on sample complexity utilizing the metric.This results can be applied in the discussion on the learnability of the class with an infinite VC dimension. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Concept learning / learning from example / PAC learning / sample complexity / VC-dimension |
| Paper # | IT94-42 |
| Date of Issue |
| Conference Information | |
| Committee | IT |
|---|---|
| Conference Date | 1994/7/23(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Information Theory (IT) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | On the Complexity of Hypothesis Space and the Sample Complexity for Machine Learning |
| Sub Title (in English) | |
| Keyword(1) | Concept learning |
| Keyword(2) | learning from example |
| Keyword(3) | PAC learning |
| Keyword(4) | sample complexity |
| Keyword(5) | VC-dimension |
| 1st Author's Name | Makoto Nakazawa |
| 1st Author's Affiliation | Department of Industrial Engineering and Management,School of Science and Engineering,Waseda University() |
| 2nd Author's Name | Toshiyasu Matsushima |
| 2nd Author's Affiliation | Department of Industrial Engineering and Management,School of Science and Engineering,Waseda University |
| 3rd Author's Name | Shigeichi Hirasawa |
| 3rd Author's Affiliation | Department of Industrial Engineering and Management,School of Science and Engineering,Waseda University |
| Date | 1994/7/23 |
| Paper # | IT94-42 |
| Volume (vol) | vol.94 |
| Number (no) | 171 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |