Algunos antecedentes: Estoy interesado en encontrar límites inferiores "menos conocidos" (o resultados de dureza) para el problema de Aprendizaje con errores (LWE) y generalizaciones de los mismos como Aprender con errores sobre anillos. Para definiciones específicas, etc., aquí hay una buena...
Aquí hay un problema con un sabor similar al de las juntas de aprendizaje: Entrada: Una función f:{0,1}n→{−1,1}f:{0,1}n→{−1,1}f: \{0,1\}^n \rightarrow \{-1,1\} , representada por un oráculo de membresía, es decir, un oráculo que dado xxx , devuelve f(x)f(x)f(x) . Objetivo: encontrar un subcubo...
Es bien sabido que para una clase de concepto con VC dimensión , es suficiente obtener ejemplos etiquetados para PAC learn . ¿No me queda claro si el algoritmo de aprendizaje PAC (que utiliza estas muestras) es correcto o incorrecto? En los libros de texto de Kearns y Vazirani, así como de Anthony...
Dana Angluin ( 1987 ; pdf ) define un modelo de aprendizaje con consultas de membresía y consultas teóricas (contraejemplos de una función propuesta). Ella muestra que un lenguaje regular que está representado por un DFA mínimo de estados se puede aprender en tiempo polinómico (donde las funciones...
DDD{0,1}d×{0,1}{0,1}d×{0,1}\{0,1\}^d\times \{0,1\}CCCf:{0,1}d→{0,1}f:{0,1}d→{0,1}f:\{0,1\}^d\rightarrow\{0,1\}f∈Cf∈Cf \in Cerr(f,D)=Pr(x,y)∼D[f(x)≠y]err(f,D)=Pr(x,y)∼D[f(x)≠y]err(f,D) = \Pr_{(x,y) \sim D}[f(x) \neq y]OPT(C,D)=minf∈C err(f,D)OPT(C,D)=minf∈C err(f,D)OPT(C,D) = \min_{f \in C}\...
Mi pregunta es un poco genérica, así que estoy inventando una buena historia para justificarla. Ten paciencia conmigo si no es realista ;-) Historia El Sr. X, jefe del departamento de seguridad informática de una gran empresa, es un poco paranoico: exige que todos los empleados cambien sus...
Angluin y Laird ('88) formalizaron el aprendizaje con datos corruptos al azar en el modelo "PAC con ruido de clasificación aleatoria" (o PAC ruidoso). Este modelo es similar al PAC aprendizaje , a excepción de las etiquetas de los ejemplos dados para el alumno están dañados (volteado), de forma...
Los datos del mundo real a veces tienen una cantidad natural de clústeres (intentar agruparlos en una cantidad de clústeres menor que un poco de magia k causará un aumento dramático del costo de la agrupación). Hoy asistí a una conferencia del Dr. Adam Meyerson y se refirió a ese tipo de datos como...
Específicamente, solicito recursos para aprender sobre los sistemas de aprendizaje automático que pueden actualizar sus respectivas redes de creencias (o equivalentes) durante la operación. Incluso me he encontrado con algunos, aunque no pude marcarlos. Como puede imaginar, es un tema bastante...
¿Cuál es el resultado del estado del arte sobre la complejidad de las consultas de las fórmulas de aprendizaje 2-DNF PAC adecuadas con consultas de muestra y bajo distribución uniforme ? ¿O alguna atadura no trivial? Debido a que no estoy familiarizado con la teoría del aprendizaje y esta pregunta...
En primer lugar, todavía no estoy seguro de si la teoría está bien adaptada para esta pregunta, por lo que no me ofenderé si la multitud cree que no es así ... En el marketing de motores de búsqueda, varios problemas son interesantes. El diseño de mecanismos de subasta justos (y rentables) y el...
Definamos una clase de funciones sobre un conjunto de bits. Arregle dos distribuciones p , q que sean "razonablemente" diferentes entre sí (si lo desea, su distancia de variación es al menos ϵ , o algo similar).nnnp,qp,qp, qϵϵ\epsilon Ahora cada función en esta clase se define mediante una...
¿Qué clasificadores de aprendizaje automático son los más paralelizables? Si tuviera un problema de clasificación difícil, tiempo limitado, pero una LAN decente de computadoras para trabajar, ¿qué clasificadores probaría? Por supuesto, me parece que algunos clasificadores estándar que conozco se...
Recientemente he estado leyendo una buena cantidad de documentos CoLT. Aunque no lucho con los documentos individuales (al menos no más de lo que normalmente lucho con otros documentos de teoría), no creo que tenga una buena comprensión del campo en general. ¿Existe un texto estándar, encuestas o...
Es bien sabido que para el aprendizaje PAC clásico, los ejemplos de son necesarios para lograr un límite de error de ε whp, donde d es la dimensión VC de la clase de concepto.Ω(d/ε)Ω(d/ε)\Omega(d/\varepsilon)εε\varepsilonddd ¿Se sabe que se necesitan ejemplos de en el caso...
Estoy bastante familiarizado con la teoría detrás de VC-Dimension, pero ahora estoy mirando los avances recientes (últimos 10 años) en la teoría del aprendizaje estadístico: promedios (locales) Rademacher, Lema de clase finita de Massart, Números de cobertura, Encadenamiento, Dudley Teorema,...
Supongamos que tengo puntos en R d . Estos inducen un diagrama de Voronoi. Si asigno a cada uno de los k puntos una etiqueta ± , estos inducen una función binaria en R d . Pregunta: ¿cuál es la dimensión VC de todas esas funciones binarias posibles inducidas por algunos k puntos y algún etiquetado...
Los bosques aleatorios tienen una reputación entre los profesionales de estar entre las técnicas de clasificación más efectivas. Sin embargo, no los encontramos mucho en la literatura teórica del aprendizaje, de la cual deduzco una ausencia de resultados teóricos profundos. Si uno quisiera...
Me refiero específicamente a las familias de idiomas que admiten cadenas arbitrariamente largas, no conjunciones sobre n bits o listas de decisiones o cualquier otro lenguaje "simple" contenido en {0,1} ^ n. Estoy preguntando acerca de los lenguajes regulares "autómatas-teóricos" en lugar de los...
Mi deseo es describir la complejidad temporal de varios enfoques de agrupación. Por ejemplo, supongamos que tenemos puntos de datos en m espacio dimensional.nnnmmm Supongamos además que la matriz de diferencia de pares ΔΔ\Delta de n×nn×nn\times n dimensiones ya está calculada y que ya hemos...