Muestra la distribución de disciplinas para esta publicación.
Publicaciones WoS (Ediciones: ISSHP, ISTP, AHCI, SSCI, SCI), Scopus, SciELO Chile.
| Indexado |
|
||
| DOI | |||
| Año | 2025 | ||
| Tipo |
Citas Totales
Autores Afiliación Chile
Instituciones Chile
% Participación
Internacional
Autores
Afiliación Extranjera
Instituciones
Extranjeras
Delle Rose et al. (COLT'23) introduced an effective version of the Vapnik-Chervonenkis dimension, and showed that it characterizes improper PAC learning with total computable learners. In this paper, we introduce and study a similar effectivization of the notion of Littlestone dimension. Finite effective Littlestone dimension is a necessary condition for computable online learning but is not a sufficient one-which we already establish for classes of the effective Littlestone dimension 2. However, the effective Littlestone dimension equals the optimal mistake bound for computable learners in two special cases: a) for classes of Littlestone dimension 1 and b) when the learner receives as additional information an upper bound on the numbers to be guessed. Interestingly, a finite effective Littlestone dimension also guarantees that the class consists only of computable functions.
| Ord. | Autor | Género | Institución - País |
|---|---|---|---|
| 1 | Delle Rose, Valentino | - |
Agenzia per la Valutazione del Sistema Universitario e Della Ricerca - Italia
|
| 2 | Kozachinskiy, Alexander | - |
Centro Nacional de Inteligencia Artificial - Chile
|
| 3 | Steifer, Tomasz | - |
Pontificia Universidad Católica de Chile - Chile
Polish Academy of Sciences - Polonia |
| Fuente |
|---|
| Agencia Nacional de Investigación y Desarrollo |
| National Center for Artificial Intelligence CENIA |
| Agradecimiento |
|---|
| Kozachinskiy is funded by the National Center for Artificial Intelligence CENIA FB210017, Basal ANID, while Steifer received financial support from the Millennium Science Initiative Program - Code ICN17002 and the Agencia Nacional de Investigaci\u00F3n y Desarrollo grant no. 3230203. |