Saturday, February 14, 2009

Algunas comentarios en el Algoritmo del Vecino K más cercano

El algoritmo del vecino K más cercano es un algoritmo muy eficaz que es usado en muchos problemas prácticos.
Aun cuando existan ejemplos de entrenamiento que tengan ruido,este algoritmo resulta ser bastante robusto . Además puede ser bastante effectivo si se le da un conjutno de entrenamiento lo suficientemente grande. Esto tiene sentido, si recordamos que este algoritmo clasifica a un elemento X dependiendo de como es la clasificación que poseen la mayoría de los vecinos cercanos, por ende se puede suavizar el impacto de un ejemplo de entrenamiento que tenga ruido.

Una cierto "prejuicio" que se tiene en este algoritmo, es que se asume que la clasificación de un elemento x, será muy similar a la clasificación elegida para otros elementos que están cercanos a x.

Ahora bien, otra cosa interesante que hay que considerar de este algoritmo, es que la distancia entre elementos se calcula con base en todos los atributos que poseen. Aunque puede surgir aquí un pequeño inconveniente, ya que, ¿Qué sucedería, si de los 20 atributos solamente 2 son relevantes para la clasificación?
En este caso, es claro que se podrían tener dos elementos cuyos 2 relevantes atributos sean iguales, mas por los demás atributos que poseen,podrían estos elementos estar muy separados entre si. Lo cual haría que este algoritmo fuera bastante "engañoso". Lo que determinaría la distancia entre vecinos, serían los numerosos atributos irrelevantes que los elementos poseen. A esto, se le suele llamar, La maldición de la dimensionalidad!


Un modo para solucionar esto es:
Cuando se está calculando la distancia en la que están dos objetos, se deberá dar un peso differente a cada atributo, esto es, darle prioridad a los atributos de interés, la multiplicación de una constante grande por los atributos de interés, y la multiplicación de una constante pequeña por los atributos menos relevantes, hace esto posible.

Friday, February 06, 2009

Das Höhlengleichnis in Zeiten des Fernsehen

Wegen der Entwircklung können die Leute sich über die Berichte informieren.
Egal ob es Abend oder Mittag ist, die Leute können wissen, was passiert in der Welt, in der sie leben. Sie wissen, wenn der Mann von Britney Spears gemein zu ihr war, sie wissen, was der Hund von Obama essen will. Sie wissen alles, das sie gerne wüssten.
Aber das Problem ist nicht, dass sie zu wenig Information bekommen können. Das Problem ist, dass sie mehr über was passiert im Irak wissen, als darüber was in ihrem Haus passiert. Sie haben keine zeit, um zu wissen, und manchmal interessieren sie sich nicht für die Beziehung, die in ihrem Leben sind.
Es ist leichter ein anderes Leben zu sehen, und zu sagen, was die Leute, die dort leben machen sollten. Es gibt zum beispiel viele " Wer, WeiBe, Was" Web Seite auf den die Leute sagen, was Britney Spears machen soll.

Diese Leute sind die Gefangenen, sie leben in Finsternis. Sie leben nicht ihrer Realität, sondern auch in einem schönen Bild, in dem sie das Leben der Andern sehen.
Aber ich bedauerne diese Leute nicht,ich denke, dass sie sich nicht entfesseln möchten. sie sind fröhlich in dieser Realität. Vielleicht ist diese Realität besser als die Realität, die sie hätten, wenn sie nicht das Leben der Andern anschauen können.

Ich weiB nicht, ob es nicht richtig ist, in einer "Virtuellen" Welt zu leben. Ich arbeite jetzt in der Schule,um bessere Virtuelle Welten zu machen.
Für die Leute, die Krank sind, ist die Virtuele Welt, die Welt, wo sie wircklich gut leben können.




Thursday, February 05, 2009

Los vecinos K más cercanos


Resumen Del Algoritmo de los k vecinos: (Por si no quieres leer toooda la explicación)
El algoritmo es simple, supongamos que se tiene un objeto X que se quiere clasificar,y se tiene además un conjunto de entrenamiento, el cual consiste de una serie de objetos cada uno con su etiqueta correspondiente. El algoritmo lo que hará para clasificar al objeto X, es tomar del conjunto de entrenamiento K elementos, estos K elementos son los K elementos del conjunto de entrenamiento que más se parecen a X. Se analizará cual etiqueta de los K elementos es la que se presenta con más frequencia, y esta etiqueta será la que se le pondrá a X. Tengo un objeto nuevo que quiero clasificar, pues le pondré el nombre del objeto que más se paresca a él que ya conosco con anterioridad. Así de simple =)


El algoritmo de los K vecinos más cercanos es uno de los algoritmos más simples que existen que muestran la escencia del aprendizaje basado en instancias.
Este algorimo asume que todas las instancias corresponden a puntos que se encuentran en un espacio de dimensión n. El vecino más cercano de una instancia es definido en términos de la distancia Euclidiana estándar.
Para aclarar esto, imagínese una instancia arbitraria x descrita por el vector:
( a1(x), a2(x) , . . .,an(x)



Donde a r(x) corresponde al valor del r"eavo" atributo de la instancia x. Entonces la distancia entre las instancias xi y xj se define por d(xi,xj), donde
:

d(xi,xj)=radical symbol Σ (ar(xi)- ar(xj))^2

En este algoritmo, la función objetivo puede contener valores discretos o valores continuos.
Por ahora consideraremos que queremos aprender una función objetivo que es discreta.
El algoritmo para aproximar una funcion objetivo que es discreta es:


Algoritmo de entrenamiento:
  • Para cada uno de los ejemplos de entrenamiento (x,f(x)) agrega el ejemplo a la lista de ejemplos de entrenamiento.

Algoritmo de clasificacion:
  • Dada una instancia Xq que quiere ser clasificada,

  • Sean x1 . . .xk las k instancias de los ejemplos de entrenamiento que están más cercanas a Xq
  • Regresa
un vector f(xq)=argmax Σ D(v,f(xi))

donde D (a,b)=1 si a=b y D(a,b)=0 en cualquier otro caso.
v pertenece al conjunto finito V:(v1,...v2). Este es el conjunto finito al cual es mapeada la función objetivo.


En resumen:
Este algoritmo funciona siguiendo un modelo basado en la memoria. La memoria guarda un conjunto de objetos ó instancias que forman parte del entrenamiento. Para cada uno de estos objetos, se sabe cual es su salida, esto es, los objetos están etiquetados. Cada ejemplo contiene un conjunto de valores independientes que producen un conjunto de salida dependiente de ellos.

Cuando las variables dependientes son continuas,se dice que la tarea a tratar es regresión. De lo contrario se trata de clasificación. Por ende este algoritmo puede manejar tanto tareas de regresión y de clasificación.

Dado un conjunto nuevo de valores independientes se busca estimar medinate los k vecinos más cercanos, la salida de este. Esto se logra encontrando k ejemplos de entrenamiento, que en distancia estén más cercanos al objeto a clasificar, de allí el nombre k vecinos más cercanos.


Para la regresión, las prediciones de los K vecinos más cercanos se basan en los promedios de las salidas de los k vecinos más cercanos; Para la clasificación, se utiliza una votación mayoritaria.

En el método de los vécinos K más cercanos, aprender significa Memorizar!

Ahora dare un pequeño ejemplo, para aclarar las cosas
Observese el siguiente dibujo, se tienen dos tipos de instancias, las estrellas y los pentagonos. La tarea del clasificador, será decir si una instancia X es un trapecio ó una estrella. Los ejemplos de entrenamiento son lo que que se muestran, en conjunto con un elemento "?" que se quiere clasificar. Si se tomará el primer vecino más cercano, esto es K=1, entonces se clasificaría al elemento ?, como estrella. Pero, si se tomarán los 5 vecinos más cercanos, se clasificaría al elemento ? como trapecio.

Monday, February 02, 2009

¿Cómo aprendería una máquina un concepto?

Cuando hablamos de aprendizaje, nos referimos al hecho de mejorar alguna tarea usando la experiencia .
Esto es:
  • Mejorar en la tarea T
  • Con respecto a la medida de rendimiento P
  • basándose en la experiencia E.

    Por ejemplo, aprender a jugar ajedrez:

  • *T:Jugar ajedrez
  • *P: % de juegos ganados en torneos.
  • *E:Opportunidad de jugar contra uno mismo.

Es fácil de entender esto, ya que en la vida cotidiana cuando un individuo aprenda un concepto nuevo, es muy común que utilice una serie de ejemplos específicos que le sirven de entrenamiento. Si el individuo está aprendiendo lo que es una vaca, los ejemplos de entrenamiento que podría tener son fotos diversas de vacas, donde se le indique que esas fotos son efectivamente de vacas, también se podría tener como entrenamiento fotos de otros animales, y se le podría indicar que esas fotos NO representan una vaca.
Con esto podemos observar, que se puede definir que un concepto es una función booleana valuada sobre un conjunto mayor. Es decir, es una función definida sobre TODOS los animales, cuyo valor será verdadero para las vacas y falso para cualquier otro tipo de animal.
Un problema interesante que existe, es obtener un método mediante el cual se pueda inferir de manera automática la definición general de un concepto, dados unos ejemplos que muestran miembros o no-miembros del concepto. Este tipo de tarea se suele llamar Aprendizaje de conceptos o Concept Learning.
Aprendizaje de Conceptos
El Aprendizaje de Conceptos se refiere al hecho de inferir una función booleana apartir de ejemplos que muestran sus entradas y salidas .
Para entender mejor, todo esto, empezaré por definir unas cosas:
El conjunto de elementos o instancias sobre el cual un concepto es definido se llama el conjunto de instancias, el cual será denotado por la letra X.
El concepto ó función a ser aprendido se llama el concepto meta,el cual será denotado por una c.
En general, la c puede ser cualquier función booleana definida sobre las instancias X.
Esto es c: X ->{0,1}
Ahora bien, como se mencionó antes usualmente cuando una persona aprende un concepto se le presentan una serie de ejemplos que facilitan el aprendizaje. Cada ejemplo consiste en una instancia de x que pertenece a X, así como su concepto objetivo valuado,c(x) Ya que se presentaron estos ejemplos, el individuo debe tratar de estimar cual es el concepto meta. Se usará el símbolo H para denotar todas las posibles hipótesis ó estimaciones de c que el aprendiz genere en su búsqueda por definirla.
Con esto, es claro que la tarea del aprendiz, es encontrar una hipótesis h, que sea idéntica al concepto c.
Para aterrizar más esto, considerese el ejemplo de aprender el concepto objetivo de “Días en los que mi amado disfruta besarme bajo la luna”.
La siguiente tabla muestra un conjunto de ejemplos de días, cada uno representado por un conjunto de atributos.

Ejemplo

Cielo

Temperatura

Viento

GustaBesarme

1

Estrellado

Caliente

Fuerte

2

Estrellado

Caliente

Fuerte

3

Nublado

Frío

Fuerte

No

4

Estrellado

Caliente

Fuerte


El atributo de GustaBesarme indica si a mi amante le gusta besarme bajo la luna en ese día. La tarea es aprender a predecir el valor de GustaBesarme para un día arbitrario, basándose en los valores de los otros atributos.

Lo primero que se deberá hacer, es definir como se quiere representar a las hipótesis.
En este caso, podemos definir a h, como una conjuncion de restricciones sobre los atributos.
Cada una de las restricciones puede ser:
  • Un valor especifico. Esto es: Cielo=Estellado
  • Sin importancia . Cualquier valor es aceptado para este atributo. Esto es Cielo=?
  • Un valor no aceptado. Esto es Cielo=0
Por ejemplo, se podría tener:
Cielo Temp Viento
Estrelallado ? Alto

Si una instancia x satisface todas las restricciones de la hipótesis h, entonces la hipótesis h clasifica a x como un ejemplo positivo (h(x)=1)
Por ejemplo, la hipótesis que dice que a mi amante le gusta besarme bajo la luna en días con temperatura alta y cielo estrellado, independientemente de como esté el viento, se representa por la expresión:
(estrellado,alta,?)
En resumen, en la tarea de aprender el concepto de GustaBesarme, se requiere aprender el conjunto de días para los cuales GustaBesarme=sí, este conjunto de días se puede describir mediante una conjunción de restricciones sobre las instancias de atributos. Como por ejemplo, el cielo deberá estar estrellado, y la temperatura deberá ser alta, para que a mi amante le guste besarme bajo la luna.

La hipótesis de aprendizaje inductiva
Es importante notar que aunque la tarea en el aprendizaje es encontrar la hipótesis h que es igual al concepto objetivo c sobre un conjunto de instancias X, la única información disponible sobre c, es el valor que posee dentro de los ejemplos de entrenamiento. Dicho más fácilmente, la única información que se tiene con respecto a los días en que a mi amante no le gusta besarme bajo la luna, está en los ejemplos de entrenamiento.
Ahora bien, debido a que no poseemos más información, se asume que la mejor hipótesis para instancias no vistas, es la hipótesis que mejor le queda a nuestros ejemplos.
Si encontramos con los ejemplos de entrenamiento, que la mejor hipotesis que explica en que días a mi amante le gusta besarme bajo la luna, es cuando la temperatura es alta, ,entonces usaremos esta hipótesis para clasificar instancias de días no vistas en los entrenamientos. Si tuvieramos un día, que fuera estrellado con temperatura baja y viento fuerte , diríamos que en este día a mi amante no le gusta besarme bajo la luna, ya que temperatura=baja.

La hipótesis del aprendizaje inductivo : Cualquier hipótesis que se encuentre que aproxima bien la función ó el concepto objetivo sobre un conjunto suficientemente grande de ejemplos de entrenamiento, también se aproximará bien a la función ó concepto objetivo en ejemplos no vistos durante el entrenamiento.

El Aprendizaje de un concepto como una búsqueda
El aprendizaje de conceptos se puede ver como la tarea de buscar, a través de un espacio grande de hipótesis, a la que mejor representa a los ejemplos de aprendizaje.
Es importante notar que las hipótesis que se encunetran en el espacio, están definidas bajo una cierta representación, que está a manos del diseñador, debido a esto, el diseñador está implicitamente declarando el espacio de todas las hipótesis que el program puede represnetar, y por ende aprender.