Post on 16-Jan-2017
Buenos Aires, marzo de 2016Eduardo Poggi
www.wsj.com/articles/when-machines-think-and-feel-1458311760/
Aprendizaje Automático
¿Máquinas que aprenden? Sistemas de aprendizaje Métodos para aprender
AA: ¿AI?
Sim
ular
Emular
4AA: ¿AI / ML?
Computer Science Artificial Intelligence
Planning Natural Language Robotics K Representation … Machine Learning
“Knowledge” Discovery Clusters Rules Concepts Patterns …
AA: ¿AI / ML?
AA: ¿AI / ML?
AA: ¿AI / ML?
8AA: ¿AI / ML?
Marvin Minsky (1927-2016): Las personas poseen procesos
que les permiten resolver problemas complejos, al conjunto de estos procesos que desconocemos denominamos inteligencia.
Definición en cambio permanente = “Regiones inexploradas de África”.
9AA: ¿AI / ML?
Galileo Galilei (1564-1642):
Todas las verdades son fáciles de comprender una vez descubiertas. El asunto es descubrirlas.
10AA: ¿AI / ML?
Entonces: ¿cómo hacen las máquinas para … descubrir conceptos? resolver problemas matemáticos difíciles? reconocer de que tema trata un paper? conducir un auto? jugar al ajedrez o al go como un maestro? predecir un contrabando o un delito? entender gestos? recomendar un libro adecuado a un lector? detectar comportamiento anormales? …
11AA: ¿AI / ML?
Hay problemas en Informática que se pueden “definir” concretamente y son simples de convertir en un algoritmo:
Ordenar alfabéticamente una lista, calcular el balance de una cuenta.
Hay otros que son simples de “entender” pero muy difíciles de “definir” y convertir en algoritmo:
Detectar una sonrisa en una cara, disntiguir entre un gato y un perro, interpretar un gesto hecho con un lápiz como una letra.
El Aprendizaje Automatizado introduce métodos que pueden resolver esas tareas “aprendiendo” la solución a partir de ejemplos de como se realiza la misma:
12AA: Resolver problemas como búsqueda en un grafo
AA: Resolver problemas como búsqueda en un grafo
Generar hipótesis inicial Generar el espacio de hipótesis posibles Recorrer el grafo
Evaluar hipótesis Seleccionar mejor hipótesis
Proponer hipótesis
¿Si se sabe resolver un problema, siempre se puede encontrar una solución?
AA: Resolver problemas como búsqueda en un grafo
Desafortunadamente, recorrer un grafo y encontrar la solución óptima es un problema intratable.
Es preciso buscar soluciones no óptimas pero tratables:
Subdividir el problema. Usar algoritmos aproximativos. Usar heurísticas. …
AA: Resolver problemas como búsqueda en un grafo
¿Problema intratable? Cualquier algoritmo cuya función de complejidad
temporal no pueda ser acotada a un polinomio O(p(n)), se denomina algoritmo de tiempo exponencial.
La mayoría de los algoritmos de tiempo exponencial son simples variaciones de una búsqueda exhaustiva, mientras que los algoritmos de tiempo polinomial, usualmente se obtienen mediante un análisis más profundo de la estructura del problema.
En la teoría de la complejidad computacional, existe el consenso de que un problema no está "bien resuelto" hasta que se conozca un algoritmo de tiempo polinomial que lo resuelva.
Por tanto, nos referiremos a un problema como intratable, si es tan difícil que no existe algoritmo de tiempo polinomial capaz de resolverlo.
AA: Resolver problemas como búsqueda en un grafo
AA: Resolver problemas como búsqueda en un grafo
¿Heurística? Como metodología científica, la heurística es aplicable a
cualquier ciencia e incluye la utilización de: medios auxiliares, principios, reglas, estrategias o algoritmos que faciliten la búsqueda de vías de solución a problemas.
“Sobre un punto de vista heurístico concerniente a la producción y transformación de la luz”, Albert Einstein, 1905
AA: Resolver problemas como búsqueda en un grafo
Generar hipótesis iniciales Hasta condición de terminación
Extraer hipótesis Extraer reglas de transformación válidas Evaluar reglas prometedoras y filtrar Aplicar reglas para generar nuevas hipótesis Evaluar hipótesis prometedoras y filtrar Ordenar lista de hipótesis
Proponer hipótesis
AA: Soluciones aproximadas
AA: Inferencia
Inferir: establecer una relación entre razones y conclusión.
Tres formas básicas: Deducción Inducción Abducción
AA: ML vs Statistics
Machine Learning is … an algorithm that can learn from data without relying on
rules-based programming.
Statistical Modelling is … formalization of relationships between variables in the
form of mathematical equations.
AA: ML vs Statistics
23AA: ¿DM?
www.mmds.org
23
MachineLearning
Statistics
Data Mining
Database systems
24
Given lots of data Discover patterns and models that are:
Valid: hold on new data with some certainty Useful: should be possible to act on the item Unexpected: non-obvious to the system Understandable: humans should be able to
interpret the pattern
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org 24
AA: What is DM?
25AA: DM tasks
Descriptive methods Find human-interpretable patterns that
describe the data Example: Clustering
Predictive methods Use some variables to predict unknown
or future values of other variables Example: Recommender systems
25
26AA: Analytics answers
26
27AA: ¿DS?
www.forbes.com/sites/gilpress/2013/05/28/a-very-short-history-of-data-science/
28AA: Experiencia y Memoria
29AA: Experiencia
30Sistema de aprendizaje: estructura
Experience
(E)
Computer +Learning
Algorithm
Class of Task
(T)
Performance
(P)
“Se dice que un programa aprende si mejora su performance en una cierta tarea al incorporar
experiencia”
31Sistema de aprendizaje: componentes
Para definir un sistema de aprendizaje debemos establecer:
La experiencia. El conocimiento a aprender. El modelo de aprendizaje. La medida de performance.
El modelo de monitoreo.
Lenguaje de
representación de la
experiencia
Lenguaje de
representación de la
experiencia
32Sistema de aprendizaje: componentesLe
ngua
je d
e
repr
esen
tació
n de
la e
xper
ienc
ia
EjemplosEvidencia
Experiencia
Atributos
Variables
Clase y
valores de la clase
Valores de los
atributos
33Sistema de aprendizaje: componentes
IF Grupo=juguetes AND Procedencia=py THEN Fiscalizacion=fraude marcario
(juguetes;*;*;*;*;*;py;*;*;*;fraude marcario)
Ejemplo
s de e
ngua
jes
de re
prese
ntació
n de l
a
expe
rienc
ia
34Sistema de aprendizaje: ejemplo
Aprendizaje supervisado: A partir de un conjunto de ejemplos clasificados obtener
una función que permita predecir casos no vistos. Si X es el espacio de ejemplos posibles e Y es el espacio de clases posibles: aprender F: X Y
Por ejemplo: Aprendiendo a jugar al ajedrez:
X: espacio de configuraciones de tableros. Y: espacio de movida válidas.
Conduciendo: X: espacio de contextos posibles. Y: espacio de acciones de manejo.
35Sistema de aprendizaje: ejemplo
Ejemplo: decidir si un paciente que entra a la guardia de un hospital debe ser atendido por urgencia cardíaca.
X1 : temperatura corporal X2 : presión sanguínea X3 : tipo de sangre X4 : edad X5 : peso
Encontrar una función lineal: Obtener wi i=1..n / f(X) = w1 x1 + w2 x2 + … + wn xn dado un nuevo caso X = < x1, x2, …, xn > If f(X) > T
Con problema cardíaco Sin problema cardíaco.
36Sistema de aprendizaje: tipos
Clasificación: Dado un objeto (conjunto de características medidas de alguna forma)
asignarle una (o varias) etiqueta de un conjunto finito. Predecir la relación euro-dolar de mañana. Predecir niveles de stock/ventas a futuro.
Regresión: Dado un objeto asignarle un número real.
Predecir la relación euro-dolar de mañana. Predecir niveles de stock/ventas a futuro.
Búsqueda y ranking Dado un objeto, asignarle y ordenar las respuestas más probables
dentro de una base de datos. Buscadores en Internet Sistemas de recomendación
Detección de novedades: Detectar "outliers", objetos que son diferentes a los demás.
Alarmas de comportamiento en compras con tarjeta. Detección de fallas en equipos críticos.
Clustering Detectar grupos de objetos que tienen características similares.
Segmentación de consumidores/clientes a partir de sus patrones de compra/búsqueda. Marketing "dirigido".
37Sistema de aprendizaje: tipos
Clasificación Descripción:
Explicitar las características (descriptivas y/o discriminantes) que caracterizan un conjunto de casos.
Predicción: Explicitar la “clase” más probable para un caso.
Prescripción: Explicar y/o justificar una predicción.
Métodos para aprender
Método básico: Identificar el problema y conseguir conocimiento experto. Conseguir muchos datos. Limpiarlos. Elegir un modelo adecuado. Entrenar el modelo con el conjunto de entrenamiento. Evaluar el modelo con el conjunto de validación. Estimar error. Proponer hipótesis.
Deductivos Memorización
Inductivos Clasificación Clustering Teorización
Híbridos EBL – Explanation base learning SML – Similarity base learning CBL – Case base learning
Métodos para aprender: diferentes modelos
Stream data
Métodos para aprender
Preparar datos
Resampling Modelizar Ensamblar Validar
ObtenerLimpiar
CompletarSelecciona
r
Partir por instancias
y/o atributos
Generar modelos y cambiar
parámetros
Generar ensambles y cambiar parámetro
s
Validar,
validar, …,
validar.
Modelo validado
Métodos para aprender
Método real: Identificar el problema y conseguir conocimiento experto. Conseguir muchos datos. Limpiarlos. Seleccionar o no datos. Elegir varios métodos adecuados. Entrenar muchos modelos con diferentes parámetros con
varios subconjuntos de entrenamiento, evaluarlos con el conjunto de validación.
Ensamblar varios métodos con varios modelos de ensambles y validarlos con el conjunto de validación.
Estimar error. Proponer hipótesis.
Métodos para aprender: selección de variables
Muchos problemas actuales tienen cientos o miles de variables medidas (sobre pocos ejemplos)
Modelar esos problemas “directamente” suele ser subóptimo.
Para mejorar la performance de los métodos de aprendizaje:
Algunos métodos trabajan mucho mejor con menos variables.
Aunque los métodos modernos de ML suelen ser muy resistentes al problema de la dimensionalidad.
En ciertos casos muchas variables no son informativas del problema (ruido o redundancias).
Al eliminarlas reducimos el riesgo de sobreajuste.
Métodos para aprender: selección de variables
Para descubrir: Cuáles son las variables más importantes en un
problema. Cuáles variables están correlacionadas, co-reguladas, o
son dependientes y cuáles no.
La selección de variables no es más una técnica de pre-procesado, actualmente es una herramienta para descubrir información de un problema.
Métodos para aprender: selección de variables
Univariados: consideran una variable a la vez. Multivariados: consideran subconjuntos de
variables al mismo tiempo. Filtros: Ordenan las variables con criterios de
importancia independientes del predictor. Wrappers: Usan el predictor final para evaluar la
utilidad de las variables.
Métodos para aprender: selección de variables
Metodología: Usar el train para elegir las variables. Usar validación independiente para determinar la
cantidad de variables a retener. Hacer una selección final con train+test. Estimar el error con el test set.
46Métodos para aprender: Medidas de Performance
Efectividad = Qr / Qp Eficacia = Efectividad * Tp / Tr Eficiencia = Eficacia * Rp / Rr
Q = Cantidad de unidades (incluye calidad). T = Tiempo R = Recursos p = previsto r = real
Métodos para aprender: Cross Validation
Métodos para aprender: Cross Validation
Métodos para aprender: Matriz de confusión
Sistema de aprendizaje: validación
51Sistema de aprendizaje: esfuerzo
52¿Y ahora?
Classic data processing
Machine Learning (+
Statistics)DM
Simulates a deductive reasoning (= applies an
existing model)
Simulates an inductive reasoning (= invents a
model)
Simulates an inductive reasoning ("even more
inductive")
validation according to precision
validation according to precision
validation according to utility and
comprehensibility
Results as universal as possible
Results as universal as possible
Results relative to particular cases
elegance = conciseness elegance = conciseness elegance = adequacy to the user's model
Tends to reject AIEither tends to reject AI
(Statistics) or claims belonging to AI (ML)
Naturally integrates AI, DB, Stat., and MMI.
¿Y ahora?
¿Y ahora?
¿Hago muchas cuentas o genero y pruebo?
¿Y ahora?
Intelligence amplification (IA) Aka: cognitive augmentation, machine augmented intelligence Se refiere al uso efectivo de la tecnología de la información para
aumentar las inteligencia humana. La idea no es nueva, fue propuesta inicialmente en los 50-60
por los pioneros de la computación y la “cibernética”.
William Ross Ashby - Intelligence Amplification Ashby, W.R. (1956): “An Introduction to Cybernetics”. Chapman and Hall, London, UK, 1956.
Reprinted, Methuen and Company, London, UK, 1964. (PDF) J.C.R. Licklider - Man-Computer Symbiosis
Licklider, J.C.R. (1960): "Man-Computer Symbiosis", IRE Transactions on Human Factors in Electronics, vol. HFE-1, 4-11, Mar 1960. (Eprint)
Douglas Engelbart - Augmenting Human Intellect Engelbart, D.C. (1962): “Augmenting Human Intellect: A Conceptual Framework”, Summary
Report AFOSR-3233, Stanford Research Institute, Menlo Park, CA, October 1962.
“Instead of trying to make a better robot, try to make a better man.”
Shimon Peres
57¿Y ahora?
Should I care about Machine Learning at all? Machine learning is becoming increasingly popular and
has become a cornerstone in many industrial applications.
Machine learning provides algorithms for data mining, where the goal is to extract useful pieces of information (i.e., patterns) from large databases.
The computer industry is heading towards systems that will be able to adapt and heal themselves automatically.
The electronic game industry is now focusing on games where characters adapt and learn through time.
58¿Y ahora?
Los científicos construyen explicaciones contando historias que son comprobadas minuciosamente para verificar si describen la vida real.
Peter Medawar, 1915-87
59¿Y ahora?
La mayor parte del trabajo científico cotidiano no es la búsqueda de hechos … sino la de hipótesis. Un experimento bien diseñado dará lugar a dos tipos de resultados experimentales: los que encajan con la hipótesis o los que son inconsistentes.
Si los resultados encajan, entonces, se piensa que se va por el buen camino y deberá plantear hipótesis y pruebas más rigurosas todavía.
Peter Medawar, 1915-87
60¿Y ahora?
… No importa cuantas manzanas caen hacia abajo en lugar de hacia arriba … no se puede decir que se ha probado que sea cierta la hipótesis que encarna la teoría de gravitacional de newton. Cualquier hipótesis es susceptible de ser sustituida por otra distinta.
Peter Medawar, 1915-87
¿Y ahora?
Lo disuadieron dos consideraciones: la conciencia de que la tarea era interminable, la conciencia de que era inútil. Pensó que en la hora de la muerte no habría acabado aún de clasificar todos
los recuerdos de la niñez.
Funes el memorioso, Artilugios, JLB, 1944.
eduardopoggi@yahoo.com.ar
eduardo-poggi
http://ar.linkedin.com/in/eduardoapoggi
https://www.facebook.com/eduardo.poggi
@eduardoapoggi
Biblio
North, Matthew (2012): Data Mining for the Masses