Temas del atlas
Atlas de los temas que hay que dominar para aprobar los cursos de IA y de Machine Learning del OMSCS, agrupados en siete bloques y con el ejemplo resuelto, los errores frecuentes y el ejercicio de cada uno.
Matemáticas para IA
Reúne el álgebra lineal, el cálculo en varias variables y la probabilidad que sostienen cualquier modelo de aprendizaje, desde el producto punto hasta la divergencia de Kullback y Leibler. Prepara el terreno de CS 7641, CS 7643, ISYE 6420 y CS 6601, cursos que dan por sabidas esas herramientas desde la primera semana.
- Vectores y producto puntoEl producto punto de dos vectores suma los productos de sus componentes y mide cuánto apunta uno en la dirección del otro.
- Normas y distanciasUna norma asigna un tamaño no negativo a un vector, y la distancia entre dos puntos es la norma de su diferencia.
- Matrices y transformaciones linealesUna matriz representa una transformación lineal que estira, rota, refleja o proyecta el espacio, y multiplicar matrices equivale a encadenar dos de esas…
- Rango e independencia linealEl rango de una matriz es el número de columnas linealmente independientes, es decir, la dimensión del espacio que esas columnas alcanzan a cubrir.
- Autovalores y autovectoresUn autovector de una matriz es un vector al que la transformación no gira, solo escala, y el factor de escala es su autovalor.
- Descomposición en valores singularesToda matriz real se escribe como el producto de una rotación, un estiramiento a lo largo de ejes perpendiculares y otra rotación, y los factores de ese…
- Gradiente y regla de la cadenaEl gradiente de una función de varias variables es el vector de sus derivadas parciales y apunta en la dirección de máximo crecimiento.
- Matriz jacobiana y matriz hessianaLa jacobiana reúne las derivadas primeras de una función que devuelve varios valores, y la hessiana reúne las derivadas segundas de una función que…
- ConvexidadUna función es convexa cuando el segmento que une dos puntos de su gráfica nunca queda por debajo de ella, y en ese caso todo mínimo local es también…
- Descenso de gradienteEl descenso de gradiente busca el mínimo de una función avanzando en cada paso una fracción del gradiente, pero en sentido contrario.
- Probabilidad condicional y teorema de BayesEl teorema de Bayes invierte una probabilidad condicional: Convierte la probabilidad del dato dada la hipótesis en la probabilidad de la hipótesis dado el…
- Esperanza y varianzaLa esperanza es el promedio ponderado de los valores de una variable aleatoria y la varianza mide cuánto se separan de ese promedio.
- Distribución normal y teorema central del límiteLa distribución normal queda descrita por su media y su desviación típica, y el teorema central del límite explica por qué la media de muchas variables…
- Máxima verosimilitudLa estimación por máxima verosimilitud elige los parámetros que hacen más probables los datos observados.
- Entropía y divergencia de Kullback y LeiblerLa entropía mide la incertidumbre media de una distribución en bits, y la divergencia de Kullback y Leibler mide cuántos bits se desperdician al codificar…
- Intervalos de confianza y contrastes de hipótesisUn intervalo de confianza del 95 % es un procedimiento que, repetido muchas veces, atrapa el valor verdadero en el 95 % de las muestras, y un contraste…
Algoritmos
Cubre el análisis asintótico, las recurrencias, la programación dinámica, los algoritmos de grafos, el flujo máximo y las reducciones entre problemas NP completos. Es la preparación directa de CS 6515 y del componente de búsqueda de CS 6601.
- Notación asintóticaLa notación O grande acota por arriba el crecimiento del coste de un algoritmo cuando el tamaño de la entrada tiende a infinito, sin mirar constantes ni…
- Recurrencias y teorema maestroEl teorema maestro resuelve recurrencias de la forma T(n) = a T(n/b) más f(n) comparando el trabajo que se acumula en las hojas con el trabajo que cuesta…
- Divide y vencerásLa estrategia de divide y vencerás parte el problema en subproblemas independientes del mismo tipo, los resuelve por recursión y combina sus soluciones.
- Programación dinámicaLa programación dinámica resuelve un problema definiendo subproblemas que se solapan, ordenándolos y resolviendo cada uno una sola vez con una recurrencia…
- Problema de la mochilaEl problema de la mochila busca el subconjunto de objetos de mayor valor cuyo peso total no supera una capacidad dada.
- Subsecuencia creciente más largaDada una sucesión de números, se busca la subsecuencia más larga cuyos elementos aparecen en el mismo orden y crecen de forma estricta.
- Recorridos en anchura y en profundidadEl recorrido en anchura visita los vértices por capas con ayuda de una cola, y el recorrido en profundidad se adentra por una rama con ayuda de una pila…
- Componentes fuertemente conexasEn un grafo dirigido, una componente fuertemente conexa es un conjunto máximo de vértices en el que cada uno alcanza a todos los demás.
- Algoritmo de DijkstraEl algoritmo de Dijkstra halla el camino de menor peso desde un origen hasta todos los vértices de un grafo con pesos no negativos.
- Algoritmo de Bellman FordEl algoritmo de Bellman Ford calcula caminos mínimos desde un origen admitiendo pesos negativos, y además detecta si existe un ciclo de peso negativo…
- Árbol de expansión mínimaUn árbol de expansión mínima conecta todos los vértices de un grafo no dirigido con peso total mínimo y sin formar ciclos.
- Flujo máximo y corte mínimoEl flujo máximo que una red puede llevar de la fuente al sumidero coincide con la capacidad del corte mínimo que los separa.
- Programación lineal y dualidadUn programa lineal optimiza una función lineal sujeta a restricciones lineales, y su dual proporciona una cota que en el óptimo coincide con el valor del…
- Reducciones y NP completitudUn problema es NP completo cuando pertenece a NP y todo problema de NP se reduce a él en tiempo polinómico, de modo que resolverlo deprisa resolvería…
- Transformada rápida de FourierLa transformada rápida de Fourier evalúa un polinomio en n raíces de la unidad en tiempo n log n, lo que permite multiplicar polinomios en ese mismo orden.
- Algoritmos aleatorizados y hashingUn algoritmo aleatorizado toma decisiones al azar para garantizar un buen rendimiento esperado sea cual sea la entrada, y el hashing universal aplica esa…
IA clásica
Recorre la IA anterior al aprendizaje profundo, es decir la búsqueda, los juegos, la satisfacción de restricciones, la lógica, la planificación y el razonamiento probabilístico con redes bayesianas y modelos ocultos de Markov. Prepara para CS 6601, CS 7637 y CS 7638.
- Agentes y entornosUn agente racional elige en cada instante la acción que maximiza el valor esperado de su medida de rendimiento, dadas las percepciones recibidas hasta ese…
- Búsqueda no informadaLa búsqueda no informada recorre el grafo de estados usando solo la estructura del problema, y sus tres variantes de examen son anchura, profundidad y…
- Búsqueda A estrellaLa búsqueda A estrella expande siempre el nodo de menor f(n) = g(n) + h(n), donde g(n) es el coste real acumulado desde el inicio y h(n) es una estimación…
- Heurísticas admisibles y consistentesUna heurística es admisible cuando nunca sobreestima el coste real restante, y es consistente cuando cumple la desigualdad triangular h(n) <= c(n, a, n')…
- Búsqueda bidireccionalLa búsqueda bidireccional lanza dos frentes a la vez, uno desde el estado inicial hacia adelante y otro desde la meta hacia atrás, y se detiene cuando las…
- Recocido simuladoEl recocido simulado es una búsqueda local que acepta siempre un vecino mejor y acepta uno peor con probabilidad exp(-delta / T), donde delta es el…
- MinimaxEn un juego de dos jugadores, suma cero e información perfecta, el valor minimax de un nodo es el máximo de los valores de sus hijos si le toca mover al…
- Poda alfa betaLa poda alfa beta descarta ramas que no pueden cambiar el valor minimax de la raíz, manteniendo alfa como el mejor valor asegurado para MAX y beta como el…
- Satisfacción de restriccionesUn problema de satisfacción de restricciones se define por un conjunto de variables, un dominio de valores para cada una y un conjunto de restricciones, y…
- Lógica proposicional e inferenciaUna base de conocimiento implica una sentencia, escrito KB |= alfa, cuando alfa es verdadera en todos los modelos en los que KB es verdadera, y esa…
- Redes bayesianasUna red bayesiana es un grafo dirigido acíclico en el que cada nodo guarda la distribución de una variable condicionada a sus padres, de modo que la…
- Inferencia aproximada por muestreoCuando la inferencia exacta en una red bayesiana resulta inviable, se estiman las probabilidades generando muestras de la red, ya sea por rechazo, por…
- Modelos ocultos de MarkovUn modelo oculto de Markov describe una secuencia de estados no observables que evolucionan con una matriz de transición, y de los que solo se ven…
- Algoritmo de ViterbiEl algoritmo de Viterbi calcula por programación dinámica la secuencia completa de estados ocultos más probable dada una secuencia de observaciones,…
- Filtro de Kalman y filtro de partículasLos filtros bayesianos mantienen una creencia sobre el estado continuo alternando predicción y corrección, y el filtro de Kalman resuelve el caso lineal…
- Razonamiento basado en casos y analogíaEl razonamiento basado en casos resuelve un problema nuevo recuperando el caso pasado más parecido, adaptando su solución al contexto actual, revisando el…
Machine Learning
Trata el compromiso entre sesgo y varianza, los modelos supervisados clásicos, la optimización aleatoria, el agrupamiento, la reducción de dimensionalidad y las métricas con las que se juzga un resultado. Da la base de CS 7641, CS 7646 y la parte de modelado de CSE 6242.
- Descomposición de sesgo y varianzaEl error cuadrático esperado de un modelo en un punto se descompone en tres sumandos, el cuadrado del sesgo, la varianza del propio modelo y el ruido…
- Validación cruzadaLa validación cruzada de k pliegues parte los datos en k trozos, entrena k veces dejando fuera un trozo distinto cada vez y promedia los k errores de…
- Métricas de clasificaciónLa matriz de confusión resume los aciertos y los fallos de un clasificador, y de ella se derivan la precisión, que mide la pureza de lo predicho como…
- Regularización de cresta y de lazoLa regularización añade a la función de coste un término que penaliza el tamaño de los pesos, con la norma al cuadrado en el caso de cresta y con la suma…
- Árboles de decisiónUn árbol de decisión parte el conjunto de datos eligiendo en cada nodo el atributo que más reduce la impureza de las etiquetas, medida con entropía o con…
- K vecinos más cercanosEl método de k vecinos más cercanos clasifica un punto nuevo por votación entre las k muestras de entrenamiento más próximas según una distancia elegida,…
- Máquinas de vectores de soporteUna máquina de vectores de soporte busca el hiperplano que separa las clases dejando el margen más ancho posible, y ese margen queda definido por unos…
- Boosting y baggingEl bagging entrena muchos modelos sobre remuestreos de los datos y promedia sus predicciones para reducir la varianza, mientras que el boosting entrena…
- Redes neuronales básicasUna red neuronal encadena capas de unidades que calculan una combinación lineal de sus entradas seguida de una función de activación no lineal, y sus…
- Optimización aleatoriaCuando la función objetivo no tiene gradiente útil, se optimiza con métodos que solo la evalúan, y los cuatro del temario son el ascenso de colinas con…
- Selección de característicasLa selección de características elige un subconjunto de las variables de entrada, ya sea con métodos de filtrado que puntúan cada variable por su relación…
- Agrupamiento por k mediasEl algoritmo de k medias alterna dos pasos hasta converger, asignar cada punto al centroide más cercano y recalcular cada centroide como la media de los…
- Mezclas gaussianas y algoritmo EMUna mezcla gaussiana modela los datos como una suma ponderada de campanas, y el algoritmo de esperanza y maximización ajusta sus parámetros alternando el…
- Análisis de componentes principalesEl análisis de componentes principales busca las direcciones ortogonales que concentran la mayor varianza de los datos centrados, que resultan ser los…
- Componentes independientes y proyecciones aleatoriasEl análisis de componentes independientes busca una transformación lineal cuyas salidas sean estadísticamente independientes y lo más alejadas posible de…
- Procesos de decisión de MarkovUn proceso de decisión de Markov describe un problema secuencial con estados, acciones, una función de transición estocástica, una recompensa y un factor…
Aprendizaje profundo
Explica cómo se entrena una red neuronal de principio a fin, con retropropagación, activaciones, normalización, optimizadores, convoluciones, atención y modelos generativos. Prepara para CS 7643 y para la parte moderna de CS 6476.
- PerceptrónEl perceptrón clasifica un vector de entrada según el signo de una combinación lineal de sus componentes más un sesgo, y corrige sus pesos cada vez que se…
- RetropropagaciónLa retropropagación calcula el gradiente de la pérdida respecto de todos los pesos de una red aplicando la regla de la cadena desde la salida hacia la…
- Funciones de activaciónUna función de activación introduce una no linealidad entre capas, sin la cual una pila de capas lineales se reduce a una sola transformación lineal.
- Inicialización de pesosLa inicialización fija la escala de los pesos antes del entrenamiento de modo que la varianza de las activaciones y la de los gradientes se mantengan…
- Normalización por lotesLa normalización por lotes resta la media y divide entre la desviación típica de cada característica dentro del lote, y después reescala el resultado con…
- OptimizadoresUn optimizador convierte el gradiente en un paso de actualización, y las variantes con momento o con tasa adaptativa reescalan ese paso según el historial…
- Regularización y abandonoLa regularización limita la capacidad efectiva de la red para que el error sobre datos nuevos baje, aunque el error sobre los datos de entrenamiento suba.
- Convolución y agrupamientoUna capa convolucional desliza un mismo núcleo pequeño por toda la imagen y produce un mapa de respuestas, con lo que reparte los mismos pesos entre todas…
- Arquitecturas convolucionalesLas arquitecturas convolucionales célebres comparten un patrón en el que la resolución baja mientras el número de canales sube, y se diferencian por la…
- Detección y segmentaciónLa detección devuelve una caja y una clase por cada objeto de la imagen, mientras que la segmentación asigna una clase a cada píxel.
- Redes recurrentes y memoria larga y cortaUna red recurrente mantiene un estado que se actualiza en cada paso de la secuencia con los mismos pesos, y la memoria larga y corta añade compuertas que…
- AtenciónLa atención calcula una media ponderada de unos valores, donde el peso de cada valor sale de comparar una consulta con la clave asociada a ese valor.
- TransformadorEl transformador apila bloques formados por atención de varias cabezas, una red densa por posición, conexiones de salto y normalización por capas, sin…
- Autocodificadores y autocodificador variacionalUn autocodificador comprime la entrada en un código de baja dimensión y la reconstruye desde él, y la variante variacional sustituye ese código puntual…
- Redes generativas antagónicasUna red generativa antagónica entrena a la vez un generador que fabrica muestras y un discriminador que intenta distinguirlas de las reales, en un juego…
- Aprendizaje por transferenciaEl aprendizaje por transferencia reutiliza los pesos de una red entrenada en una tarea grande y los adapta a otra tarea con pocos datos, ya sea congelando…
Aprendizaje por refuerzo
Estudia la decisión secuencial sobre procesos de decisión de Markov, desde la iteración de valor y el aprendizaje por diferencias temporales hasta el gradiente de política y los métodos actor crítico. Prepara para CS 7642 y para los proyectos de agentes de CS 7646.
- Procesos de decisión de MarkovUn proceso de decisión de Markov describe un problema de decisión secuencial mediante estados, acciones, probabilidades de transición, recompensas y un…
- Ecuaciones de BellmanLas ecuaciones de Bellman expresan el valor de un estado como la recompensa inmediata esperada más el valor descontado del estado siguiente, con esperanza…
- Iteración de valorLa iteración de valor aplica repetidamente el operador de optimalidad de Bellman a una tabla de valores hasta que deja de cambiar, y extrae la política al…
- Iteración de políticaLa iteración de política alterna un paso de evaluación, que calcula el valor de la política actual, con un paso de mejora, que fija en cada estado la…
- Métodos de Monte CarloLos métodos de Monte Carlo estiman el valor de un estado promediando los retornos observados en episodios completos, sin modelo de transiciones y sin…
- Aprendizaje por diferencias temporalesEl aprendizaje por diferencias temporales actualiza el valor de un estado hacia la recompensa inmediata más el valor estimado del estado siguiente, sin…
- SARSA y aprendizaje dentro de políticaSARSA actualiza el valor de un par de estado y acción usando la acción que la política eligió de verdad en el estado siguiente, de modo que aprende el…
- Q-learningQ-learning estima directamente la función de valor óptima de los pares de estado y acción usando el máximo sobre las acciones del estado siguiente, con…
- Trazas de elegibilidadLas trazas de elegibilidad guardan una huella que decae de los estados visitados hace poco y reparten cada error temporal entre todos ellos, lo que…
- Bandidos de varios brazosUn problema de bandidos de varios brazos plantea la elección repetida entre acciones de recompensa desconocida sin estados, y obliga a equilibrar la…
- Aproximación de funcionesLa aproximación de funciones sustituye la tabla de valores por un modelo con parámetros, lo que permite generalizar a estados nunca vistos a costa de…
- Red Q profundaUna red Q profunda aproxima los valores de acción con una red neuronal y estabiliza el entrenamiento con una memoria de repetición y con una red objetivo…
- Gradiente de política y REINFORCELos métodos de gradiente de política optimizan directamente los parámetros de una política estocástica subiendo por el gradiente del rendimiento esperado,…
- Métodos actor críticoUn método actor crítico combina una política con parámetros, el actor, con una estimación de valor, el crítico, y usa el error temporal del crítico como…
- Teoría de juegos y equilibrio de NashUn equilibrio de Nash es un perfil de estrategias en el que ningún jugador mejora su pago cambiando de estrategia por su cuenta, y es el concepto de…
- Formación de recompensasLa formación de recompensas añade una señal auxiliar para guiar al agente cuando la recompensa original es escasa, y la forma basada en potencial…
Lenguaje natural y modelos de lenguaje
Va de los n gramas y los embeddings estáticos al transformador, el preentrenamiento, la decodificación y el ajuste por instrucciones con retroalimentación humana. Prepara para CS 7650 y CS 7652.
- Tokenización y normalizaciónTokenizar es partir una cadena de texto en las unidades discretas que el modelo cuenta y predice, y normalizar es decidir qué diferencias de escritura se…
- Modelos de n gramasUn modelo de n gramas estima la probabilidad de la palabra siguiente contando cuántas veces siguió a las n menos 1 palabras anteriores en un corpus de…
- Suavizado y palabras desconocidasEl suavizado traslada una parte de la masa de probabilidad de los n gramas observados hacia los que no aparecieron, con el fin de que ninguna secuencia…
- PerplejidadLa perplejidad de un modelo sobre un texto es la exponencial de la entropía cruzada por token, y se lee como el número medio de continuaciones igualmente…
- Bolsa de palabras y clasificación de textoLa representación de bolsa de palabras describe un documento por la frecuencia de cada término del vocabulario y descarta el orden, lo que basta para…
- Embeddings de palabrasUn embedding asigna a cada palabra un vector denso de unos cientos de dimensiones, entrenado para que las palabras de contextos parecidos queden cerca en…
- Tokenización por subpalabrasLa codificación por pares de bytes construye el vocabulario fusionando de forma repetida el par de símbolos adyacentes más frecuente, de manera que las…
- Etiquetado de secuenciasEl etiquetado de secuencias asigna una etiqueta a cada token de la oración, como la categoría gramatical o el esquema de principio, interior y exterior…
- Análisis sintáctico de dependenciasEl análisis de dependencias construye un árbol donde cada palabra cuelga de su núcleo sintáctico con una etiqueta de relación, de forma que la oración…
- Atención sobre secuenciasLa atención calcula para cada posición una media ponderada de los valores de todas las posiciones, con pesos que salen de comparar la consulta de esa…
- El transformador para lenguajeEl transformador apila bloques formados por atención de varias cabezas y una red densa por posición, cada uno con conexión residual y normalización, y…
- Preentrenamiento y ajuste finoEl preentrenamiento aprende representaciones generales resolviendo una tarea automática sobre texto sin etiquetar, y el ajuste fino adapta esos pesos a…
- Decodificación y temperaturaLa decodificación convierte la distribución que el modelo produce en cada paso en un texto concreto, ya sea eligiendo el máximo, explorando varias…
- Evaluación de texto generadoLa métrica BLEU compara la salida con una o varias referencias contando cuántos n gramas del candidato aparecen en ellas, con un recorte por repetición y…
- Ajuste por instrucciones y RLHFEl ajuste por instrucciones entrena con pares de instrucción y respuesta escrita, mientras que el aprendizaje por refuerzo con retroalimentación humana…
- Generación aumentada por recuperaciónLa generación aumentada por recuperación busca fragmentos relevantes en una colección externa y los coloca en el contexto antes de generar, de modo que la…