El objetivo principal de la PCA es saber con certeza qué tan buena generaliza nuestra hipótesis. Podemos encontrar nuestra hipótesis h desde el espacio de hipótesis H. Pero, ¿qué tan seguros estamos de que esto h generaliza correctamente nuestro concepto objetivo C.
Ahora puede ver claramente en la imagen que (C XOR h) {región señalada con marcas de flecha} es nuestra región de error y queremos que la probabilidad de (C XOR h) sea <= E (epsilon), donde epsilon es el parámetro de error.
- Sea m una máquina de turing y sea w una corriente de entrada de m. ¿Cómo puedo definir el tiempo de ejecución tm (w) de m en la entrada w?
- ¿Por qué identificamos algoritmos que actúan en diferentes tamaños de entrada?
- ¿Cuáles son las cuatro aplicaciones prácticas de la teoría de conjuntos en informática?
- ¿Qué estructura de datos se usa para calcular enteros muy largos, por ejemplo, el número primo más grande?
- Tengo los datos de todos mis productos (altura-ancho-longitud) pero quiero encontrar el número óptimo de cajas N y el tamaño de cada N cajas (medidas como HWL). ¿Cómo puedo hacerlo?
Ahora mi objetivo es encontrar la hipótesis h de manera que concuerde con C. Esta hipótesis se llama hipótesis coherente.
Pero para alcanzar esta hipótesis coherente, tenemos que pasar por todas las instancias disponibles, pero esto no se puede lograr en tiempo polinómico. Por lo tanto, hacemos la hipótesis que se basa en menos ejemplos. Queremos saber VERDADERO ERROR pero solo conocemos el error de entrenamiento.
El verdadero error se puede dar como:
Anotaciones:
–X: conjunto de todos los ejemplos posibles
–D: distribución de la que se extraen ejemplos
–H: conjunto de todas las hipótesis posibles
–N: el número de ejemplos en el conjunto de entrenamiento
–F: la verdadera función a aprender
Por lo tanto, queremos encontrar h para estar cerca de c.
Por lo tanto, una hipótesis h es aproximadamente correcta si, error (h) ≤ ε.
donde ε es un umbral dado, una pequeña constante
Ahora el tema principal de PAC que nos interesa:
Complejidad de la muestra: ¿En cuántas instancias de capacitación debo entrenar a mi clasificador para el aprendizaje PAC? Se puede administrar siguiendo la fórmula.
Su implementación se puede encontrar en:
Aquí n es el número de características. Y para los primeros ejemplos podemos ver que necesitaremos 280 ejemplos (instancias) para llegar a una hipótesis consistente.
Referencias
- Aprendizaje automático -Tom Mitchell
- algunas fotos para las diapositivas de la conferencia NPTEL.
Gracias.
