jueves, 20 de marzo de 2008

On Intelligence

On Intelligence

On Intelligence. Jeff Hawkins con Sandra Blakeslee. Times Books. Octubre 2004. Inglés. 272 páginas. Web oficial: OnIntelligence.org.

Hace un mes que comenté por aquí la existencia de este libro (ver Jeff Hawkins sobre el cerebro humano y el interesante hilo de comentarios original) y prometí una reseña completa en cuanto pudiera leerlo porque era de lo más prometedor.

Efectivamente, On Intelligence no defraudada en lo más mínimo. Es provocador, profundo y sin duda se podría decir que revolucionario (en cierto modo, tanto como A New Kind of Science). Habla sobre el cerebro, la mente, el funcionamiento de los sentidos, la memoria y el aprendizaje y, sobre todo, de la inteligencia artificial: por qué fracasó, pero también cómo funcionará realmente en el futuro — que no es como la mayoría de los expertos piensan.

Jeff Hawkins, ayudado por la periodista Sandra Blakeslee, comienza explicando con total humildad que tal vez él puede proponer esta teoría sobre el funcionamiento de la inteligencia precisamente por estar fuera de los circuitos científicos habituales. él es más conocido por haber fundado Palm Computing y haber inventado la Palm y el sistema de escritura Graffiti para las PDA. Resulta que él es un ingeniero (no un biólogo ni un neurocirujano), acostumbrado a traajar en productos que fallan, así que puede permitirse aprender de los errores — mientras que un científico probablemente vería frustrada su carrera para toda la vida si tras cinco o diez años investigando publicara se atreviera a publicar algo como este libro y resultara ser un fiasco.

El córtex cerebral

La teoría de Hawkins comienza explicando que en el córtex cerebral es donde residen realmente la memoria y por tanto la inteligencia — otras partes del cerebro se encargan de los instintos básicos, mas primitivos y automáticos. El córtex es básicamente igual en todas partes, y aunque se sabe que diversas zonas tienen relación con ciertos sentidos y atributos (ej. la visión, el tacto, el lenguaje, etc.) en realidad todas sus partes, capas celulares, densidad, etc. son básicamente iguales. Según Hawkins, todas las capas del córtex pueden realizar las mismas funciones. Lo cual explicaría por qué funciones en zonas que son dañadas por accidentes o enfermedad (ej. el lenguaje), se puedan volver a desarrollar en otra zona distinta. El hecho de que ciertas zonas del córtex esten relacionadas con ciertos sentidos o funciones se debe únicamente a dónde están conectadas (ej. al nervio óptico o auditivo). Pero esa situación es circunstancial, no «obligatoria». De hecho, ya se ha demostrado que se puede «ver» a traves de un sensor en la lengua, por ejemplo.

El número y disposición de las conexiones al córtex, así como la diferencia de tamaño relativo (cuerpo/cerebro), y el tipo y número de neuronas en el córtex humano y el de los animales es lo que nos hace básicamente diferentes: los humanos somos inteligentes porque somos en cierto modo más «conscientes» del mundo que nos rodea y porque tenemos mayor capacidad de predicción y «simulación mental».

El mundo de los sentidos

Conocemos el mundo a través de los sentidos. Incluso hay muchos más sentidos que los cinco habituales que suelen enseñar en el colegio. El equilibro, por ejemplo, podría considerarse un sentido. En cierto modo, todos estos sentidos «digitalizan» información del exterior y la transmiten al córtex a través del sistema nervioso. Hawkins propone que esa información entrante se procesa siempre mediante los mismos algoritmos, se guarda de la misma forma y se accede a ella de idéntica manera. Da igual si es la foto de un dálmata o el olor de una magdalena. Este proceso (algoritmo) es tan simple pero tan versátil que puede explicarlo todo sobre el funcionamiento de la mente. Incluso aunque el cerebro lo utilice para acciones tan distintas como ver, oler u ordenar mover una mano (que no es una sensación sino una acción).

La memoria

El algoritmo que utiliza la mente es un proceso que almacena patrones y hace predicciones sobre los patrones que encuentra o espera encontrar. La exposición a los diversos estímulos (inputs) se guarda en el córtex. Pero el córtex es muy diferente a lo que habitualmente conocemos como «la memoria» de un ordenador. Las diferencias fundamentales de cómo funciona la memoria en el cerebro respecto a otros tipos de memorias (como un archivo o un ordenador) son estas:
  • La memoria almacena secuencias de patrones en vez de los datos en sí. Esto es como almacenar las diferencias de una nota a otra en una canción en vez de almacenar las notas en sí. Esto permite reconocer canciones aunque estén en otra «escala» o palabras escritas aunque estén «en otro tipo de letra». Las secuencia, ademas, están almacenadas siempre en un orden determinado. Todo el mundo recuerda el alfabeto, pero es difícil recitarlo al revés. Lo mismo sucede con tu número de teléfono: tienes almacenada la secuencia pero no sabrías decirlo al revés sin pensarlo cuatro o cinco veces. Es como si en realidad no tuvieras memorizado el número en sí. Además, para recordar cosas, debemos hacerlo siempre en cierto orden («pensando en ello»: «ayer fui al parque y en el parque había un lago y en el lago peces...», no somos capaces de recordar todo de una sola vez «instantáneamente»).
  • La memoria es accesible de forma auto-asociativa. Todos los recuerdos están asociados unos con otros de algún modo: ver una parte de una cara está asociado con que esa cara corresponde a una cabeza completa. Las cabezas están encima de cuerpos, los cuerpos corresponden a personas, etc. Oímos una frase y la entendemos, aunque en realidad no hayamos escuchado todas las palabras exactamente (pero las completamos). Aunque fltn algns ltrs pdmos ntndr frss cm sta sn myr prblm. Eso eso porque lo que almacenamos son los patrones y sencuencias, y asociamos patrones incompletos con patrones que conocemos (y predecimos), a pesar de que a veces haya pequeños errores. Las imágenes imposibles nos llaman la atención y resultan divertidas precisamente por esto.
  • La memoria almacena los patrones enformato invariante. Una vez que has aprendido a leer, puedes reconocer las palabras y leerlas en cualquier ángulo, perspectiva, condición luminosa o aunque cambie el tipo de letra. Puedes reconocer una cara como perteneciente a la misma persona de día, noche, vista de perfil, etc. Imagine de John Lennon existe en miles de versiones, y podrías reconocerlas todas como tal oyendo unas pocas notas, aunque no las hayas escuchado completas nunca antes. Esta forma de almacenamiento es radicalmente distinta de forma en que se almacenan datos en los ordenadores. Además, funciona también «al revés»: puedes haber aprendido una poesía de memoria simplemente leyéndola, pero puedes reproducirla escribiéndola a mano, a máquina o recitándola de viva voz (incluso en otro idioma).
  • Los patrones se almacenan en una jerarquía. El concepto de jerarquía tiene que ver con las diversas capas del córtex, y básicamente consiste en una estructura que podría denominarse fractal, bellamente simétrica porque además cuenta con retroalimentación, en el que las regiones de menor nivel transmiten los patrones y los «nombres» que asignan a los patrones a las zonas de nivel superior. Pero todas son iguales y equivalentes en realidad. Esta jerarquía se corresponde, curiosamente, con el hecho de que también el Mundo en sí sea jerárquico. Las notas musicales forman melodías, las melodías secuencias, las secuencias canciones, las canciones álbumes, etc. Las hojas estan en las ramas, las ramas en los árboles, los árboles en el bosque. Las letras forman palabras que forman frases que forman párrafos, capítulos, libros y los libros están en estanterías, dentro de bibliotecas. Entendemos y almacenamos la información así la realidad del mundo es así, por tanto es la forma más práctica de hacerlo. Las diversas capas del córtex transmiten esa información según esos conceptos de «nombres» asignados a los patrones. La información más básica va primero, luego más elaborada, etc. asignándole «nombres» como «mmm... veo algo», «tiene forma de cara», «es una persona», «es Juan, mi hermano».

Acciones y comportamiento

Adicionalmente, todo esto funciona también al revés. La estructura del córtex está llena de señales que viajan en dirección opuesta a la de la percepción, hacia los centros motores. Está todo lleno de retroalimentación (feedback). Cuando queremos hacer algo como «voy a coger el vaso», realizamos la acción mediante una predicción, es decir «visualizamos» qué va a suceder («mi mano derecha agarrará el vaso así») y el hecho de recuperar ese patrón de la memoria automáticamente envía esas señales («patrones») a los lugares adecuados para que se cumpla esa predicción («mano, muévete y coge el vaso»). Al hacerlo, vemos el resultado, que queda reforzado en la memoria por el hecho de que ese patrón ha funcionado realmente. Todo esto puede sonar extraño, pero explica todas las habilidades aparentemente tan complicadas que demostramos los seres inteligentes. Explica cómo una persona (o un perro) pueden predecir la trayectoria de una pelota para cogerla, sin calcular ecuaciones físicas. También explica por qué muchos deportistas y personas mejoran su rendimiento «visualizando» que hacen algo, antes de hacerlo realmente, como por ejemplo descender una pista nevada o dar una conferencia.

El nuevo modelo de la inteligencia

En el capítulo dedicado al nuevo modelo de la Inteligencia [supongo que esa es la traducción habitual de framework] es donde Hawkins combina todas las ideas sobre cómo funciona el cerebro y la memoria para explicar qué es en realidad la inteligencia y cómo y por qué funciona como funciona. Previamente, también explica por qué cree que el Test de Turing no sirve para demostrar genuinamente que algo es inteligente. Tú puedes ser inteligente simplemente estando sentado en una habitación oscura sin hacer nada. Comportarse inteligentemente no quiere decir que realmente lo seas, como demuestra el experimento de la sala china. Deep Blue no es inteligente, simplemente calcula rápido jugadas de ajedrez.

Hawkins propone que la capacidad de predicción de patrones es la clave de la inteligencia. Durante nuestra existencia, aprendemos y memorizamos patrones. El córtex tiene algoritmos para almacenarlos y reconocerlos. Somos inteligentes porque somos capaces de predecir qué sigue a un patrón determinado en base a la experiencia. Y cuando fallamos, eso nos sorprende. Entonces podemos añadirlo a la lista y seguir aprendiendo. Tal vez más revolucionario es que ese modelo y la existencia de la retroalimentación de patrones en el córtex explique también por qué cuando pensamos «hacer algo» en realidad podemos hacerlo.

Aunque Hawkins admite que parte de estas ideas de es probable que ya existieran anteriormente, pero que su teoría las une todas en un conjunto comprensible, consistente, y mucho más simplificado, que cubre desde cómo funcionan los sentidos (y el hecho relevante de que todos funcionan igual) a cómo esto está relacionado con la memoria y la inteligencia, nuestra capacidad de aprender y llevar a cabo acciones — todo ello mediante un único algoritmo extremadamente simple.

Datos sobre el cerebro

Una buena parte del libro está dedicada a explicar cómo funciona físicamente el córtex. Es tal vez la más técnica y complicada, aunque no hace falta ser neurocirujano para entenderlo, dado que los autores han tenido la habilidad de simplificar y poner ejemplos suficientemente claros. A los autores, de todos modos, les puede achacar la falta de ejemplos visuales y de datos concretos que seguramente son importantes para entender mejor lo que cuentan. El libro sólo tiene unas diez o quince figuras y diagramas ilustrativos, y datos como el número de neuronas en el córtex, la velocidad de transmisión de las señales se mencionan sólo de pasada — aunque algunas veces es porque ni siquiera los neurocientíficos tienen claro todo eso.

Se calcula, por ejemplo, que en el córtex puede haber unos 32 billones de sinapsis en las neuronas, que podrían equivaler a unos 8 billones de bits informáticos. Eso son 8 terabytes, que a día de hoy puedes comprar en forma de discos duros por unos 10.000 euros y guardar en un cajón. Pero no tendrías la misma memoria que en tu cerebro. La diferencia es que en el cerebro la «memoria» está en realidad altamente interconectada, de modo que para replicarla el principal problema no es tanto de capacidad como de conectividad — aunque esto puede resolverse tanto en la teoría como en la práctica, del mismo modo que una misma línea telefónica puede contener señales para cientos de conversaciones.

Otro dato curioso del libro: se sabe que en un segundo una señal puede transmitirse digamos linealmente a través de unas 200 neuronas si estuvieran puestas en línea (en otras palabras: una neurona unos tarda 5 milisegundos en recibir, procesar y transmitir una señal). Esa es la «velocidad del pensamiento». No es nada espectacular, la verdad. Pero sí es sorprendente que si en un experimento nos enseñan una serie de fotos podamos reconocer en 0,5 segundos si hay en ellas un gato o no y pulsar rápidamente un botón — algo que ningún ordenador puede hacer hoy en día. Eso significa que la «solución» a ese problema visual (o a casi cualquier otro problema) existe realmente a menos de 100 neuronas de distancia en nuestro cerebro. Eso, según Hawkins es indicativo de que el cerebro no calcula la solución siguiendo una serie de «pasos», sino que simplemente recupera la solución, que ya existe, desde la memoria.

Cuando oí hablar de este libro una de mis dudas era si sería demasiado teórico y poco práctico o realista. Sin ser ningún experto, creo que no está demasiado alejado de la realidad. Las explicaciones sobre el funcionamiento real de las neuronas en el córtex están dentro de lo aceptado por la comunidad científica, y su modelo (teórico) sobre los patrones tiene la elegancia de la simplicidad, que tantas veces esta detrás de muchos aciertos. También tiene ese punto curioso de desvelar que «el emperador está desnudo» que tanto fastidia a muchos científicos (lo poco que en realidad se conoce sobre el tema XYZ, el hecho de que en realidad se estaban haciendo las preguntas equivocadas, etc.) así que es de esperar un buen número de críticas y refutaciones, que por supuesto habrá que leer con avidez.

Preguntas, respuestas y vacíos

En uno de los últimos capítulos Hawkins responde a las preguntas a las que habitualmente contesta cada vez que da conferencias: ¿Qué es la imaginación? ¿Son inteligentes los animales? ¿Qué es la creatividad? ¿Se puede ser más creativo? ¿Qué es la consciencia? Todas ellas tienen una respuesta clara, incluso diría que de sentido común, dentro de su modelo de la inteligencia.

La que más me llamó la atención es la descripción de por qué la inteligencia humana es fundamentalmente diferente de la de los animales. Según Hawkins se trata básicamente de diferencias físicas a las que hemos llegado tras siglos de evolución natural en cuanto al modelo de memoria y capacidad de predicción de patrones. Nuestro córtex es más grande y por tanto mejor que el de otros animales.

Los organismos más simples tenían una capacidad de predicción básica, del tipo «debo nadar hacia donde haya comida» pero eran incapaces de transmitirla. Sólo existía cierta capacidad de transmitir una especie de «memoria» generacional a través del ADN, durante la reproducción (y vinculada a la selección natural). De repente, se desarrolló una memoria predictiva que llegó a tener utilidad durante la vida del organismo (ya más larga), que es la que actualmente tienen los animales («no debo acercarme al fuego», «si veo un león, debo correr, porque ya ví cómo se comían a mis congéneres»). Los delfines probablemente tienen un modelo o conocimiento muy amplio del mundo que les rodea, memoria de todos los sitios que han visitado alguna vez e incluso pueden comunicar conceptos básicos a otros delfines y entender a las personas con el entrenamiento adecuado.

Pero solo el ser humano alcanzó la capacidad más diferenciadora de todas: desarrollar profundamente el lenguaje. El lenguaje nos permite intercambiar de forma práctica y rápida nuestras memorias (recuerdos y patrones) con otros seres de nuestra especie. Y no sólo durante nuestra vida, sino a través de generaciones. Y actualmente, no sólo con nuestros vecinos, sino con cualquier otro ser humano del planeta. Aunque otros mamíferos, animales e incluso plantas tienen sus particulares versiones del lenguaje, no son tan sofisticados y eso nos diferencia profundamente de ellos.

Algunas otras preguntas o temas se quedan por desgracia sin respuesta. Temas por ejemplo como qué son los sueños, por qué soñamos o por qué es necesario soñar, no se tratan a lo largo del libro. ¿Qué es realmente un déjà-vu? No hay comentarios. El libro sí explica en cambio cómo encajan en su teoría algunas enfermedades relacionadas con el cerebro (como la sinestesia o incluso la curiosa anterograde amnesia que sufre el protagonista de Memento), pero no cómo encajan otras como la amnesia normal, el Parkinson, los distintos tipos de retraso mental u otras deficiencias y enfermedades. Habla en cambio de por qué las alucionaciones son tan reales o por qué es tan fácil engañar al cerebro: sencillamente porque los humanos estamos diseñados para encontrar patrones, y tendemos a verlos incluso donde no los hay. Hawkins tampco entra a hablar, en cambio (todo un acierto) de las cuestiones filosóficas sobre la inteligencia, la personalidad, la consciencia y demás. Tal vez porque ese tipo de debates es para otro tipo de libros, y el suyo tiene un carácter más práctico.

Inteligencia y ordenadores

Jeff Hawkins es ingeniero. El supergeek. Inventó la Palm, incluyendo el sistema de reconocimiento de escritura Graffiti*, y posteriormente la Handspring (finalmente, todo eso se fusionó de nuevo cuando Palm compró Handspring). En el libro, afirma que creó Palm para poder ganar dinero en una industria que también le interesaba, pero para poder dedicarse realmente a investigar el cerebro. Con el dinero que ganó fundó el Redwood Neuroscience Institute que es donde realiza su trabajo científico.
(*) Curiosamente, Graffiti no es en sí un sistema inteligente que «aprenda» la escritura humana, al contrario de lo que mucha gente piensa. Hawkins explica exactamente cómo lo inventó: «En 1994 mis colegas y yo estábamos intentando adivinar cuál sería un buen sistema para introducir datos en los ordenadores de mano. Todo el mundo estaba concentrado en los sistemas de reconocimiento de texto inteligentes. Sin embargo, esos sistemas resultaron ser muy difíciles de realizar y nunca funcionaban bien (...) Un día, decidí dar un paso atrás y ver el problema desde otra perspectiva. Me dijo a mí mismo: «¿Cómo introducimos ahora texto en los ordenadores? Tecleamos en un teclado. ¿Cómo aprendemos a teclear? Bueno, no es fácil. Es un invento reciente y requiere su tiempo aprender (...) Sin embargo, millones de personas lo hacen. ¿Por qué? Sencillamente, porque funciona. De modo que continué mi analogía: Tal vez yo pueda inventar un sistema para introducir texto que no sea intuitivo, que requiera que la gente lo tenga que aprender, pero que lo utilicen sencillamente porque funcione. Literalmente, así es el proceso que seguí para inventarlo.»
Lógicamente, Hawkins no podía dejar pasar la oportunidad de explicar en su libro todas las diferencias entre el cerebro humano y los ordenadores, así como su visión sobre la inteligencia artificial, cómo cambia esa visión bajo la luz de su teoría y cuál es el posible futuro que nos espera.

Nada más empezar el libro dedica un capítulo a explicar el porqué del fracaso de la IA durante las últimas décadas del siglo XX. Ninguno de los sistemas era genuinamente inteligente. Algunos se comportaban «como si pensaran» pero en entornos terriblemente limitados (Eliza, Deep Blue). Todo el mundo creía que las capacidades de memoria y cálculo eran la verdadera limitación y que los ingenieros del hardware vendrían a salvar a la AI. Redes neurnales, redes bayesianas, sistemas expertos... nada. Todo esto demostró ser claramente un error.

Hawkins se atreve a predecir que no habrá en el futuro sistema de inteligencia artificial como Robbie el Robot, C-3PO o el malévolo HAL, que se comporten como humanos, sencillamente porque para eso deberían ser humanos: tener las mismas capacidades sensoriales que un humano, el mismo tipo de memoria y con la misma capacidad, exactamente el mismo algoritmos pero además... vivir exactamente la vida de un humano desde su nacimiento. Y además, aunque parezca que se haya desentrañado cómo funciona el cerebro, todavía desconocemos todavía muchos de los detalles (por ejemplo, los 30 millones de sinapsis de un cerebro típico podrían ser en realidad 300 ó 3.000) y algunos efectos como la conectividad exacta entre dichas sinapsis permanecen inexplorados.

En cambio, Hawkins sí predice que si su teoría es correcta se podrán crear sistemas inteligentes que tal vez no hablen como C-3PO, pero si que resulten prácticos y últiles, realmente revolucionarios. Basándose en su teoría de reconocimiento de patrones desarrolla ideas sobre de sistemas de reconocimiento de voz, coches verdaderamente inteligentes, sistemas de predicción del clima y de otras aplicaciones industriales.

Su ejempo de coche inteligente es realmente interesante. Si dentro de 10 ó 20 años (el plazo que él estima) se desarrolla un sistema predictivo con las capacidades que propone, los fabricantes crearían un coche con todo tipo de sensores visuales y de radar (e incluso otros: un sensor acústico podría predecir cierto tipo de situaciones). Dicho coche partiría de un conocimiento «cero». No habría que pre-programarle nada, pero sí que debería pasar meses o años aprendiendo del mundo real — como un bebé: circulando conducido por una persona. Con el tiempo, crearía un modelo de patrones predictivos en su interior y se formaría un modelo del mundo real — el primero paso para demostrar inteligencia. En un momento dado, el coche ya sería capaz de poder predecir situaciones y, con los mecanismos adecuados, de tomar el control del vehículo y circular como lo hace una persona. Haría cosas realizando acciones que cumplieran sus predicciones. Con el suficiente aprendizaje, ese coche sería incluso capaz de frenar si ve una pelota rebotando que cruza la carretera, porque sabría que probablemente saldrá un niño corriendo detrás de ella y no debe atropellarle. La diferencia entre la inteligencia de ese coche y la de una persona sería que se podrían tomar los patrones de la memoria del coche y «clonarlos» en toda una línea de coches idénticos, al instante. El fabricante podría decidir además que el coche siga aprendiendo (o no) tras vendérselo al propietario. El coche sería inteligente, sería útil y no tendría nada que ver con los coches actuales.

Esa tecnología tal vez no debería llamarse entonces «Inteligencia Artificial» porque en la práctica sería «Inteligencia Real».

Toda una revolución que, si Hawkins está en lo correcto en el fondo y en los plazos, tendremos la increíble suerte de ver y disfrutar a lo largo de nuestras vidas.

Construyendo la realidad

Construyendo la realidad

Jeff Hawkins,

Jeff Hawkins, creador de la agenda electrónica Palm, es uno de los triunfadores de la electrónica de Silicon Valley. Los fondos obtenidos con sus inventos le permitieron fundar el Redwood Neuroscience Institute, donde investiga su gran pasión: cómo funciona el cerebro humano desde la perspectiva de un sistema informático, no desde el paradigma neurológico tradicional. Su libro “On Intelligence” expone las teorías que hasta ahora ha ido estableciendo.

Eduard Punset
El día que se tenga éxito produciendo lo que tu sugieres en este libro sobre máquinas inteligentes posiblemente será el día más feliz de mi vida, porque ya estoy cansado de que se diga que somos los únicos reyes del universo y los que estamos mejores construidos, etc.
Es decir que por primera vez acabarás con la historia de que los ordenadores son completamente diferentes de los cerebros, y vas a construir una máquina que realmente funciona como un cerebro.

Jeff Hawkins
En realidad hago dos cosas, la primera es comprender cómo funciona el cerebro, y no todo el cerebro sino sólo el neocórtex y algunas cosas relacionadas con él. Queremos saber qué hace y como lo hace. Una vez que sepamos qué es el cerebro y cómo funciona podemos construir una máquina que funciona de manera similar, con unos principios parecidos. Mi libro trata del córtex, y hablo de cómo construir máquinas con los mismos principios... cuando estaba escribiendo el libro no sabía cómo hacerlo, pero ahora sí lo que sabemos.

Eduard Punset
Caramba, y serás capaz de reproducir –bueno, dices que desde que has escrito el libro has progresado mucho- de mostrar en una capa cortical (cortical sheet) estas máquinas inteligentes.

Jeff Hawkins
Sí. Déjame hacer una distinción que hago muy cuidadosamente en el libro. Lo que estamos haciendo es un neocórtex, no estamos intentando crear humanos, porque los humanos tienen muchas más cosas: tienen el cuerpo físico, tienen emociones, aspiraciones y muchas cosas que van más allá del neocórtex. El neocórtex es la parte del cerebro que piensa, es la parte inteligente, y desde que escribí el libro hemos progresado mucho. Junto con otro científico, Deleep George, hemos redactado una fórmula matemática para expresar lo que el neocórtex está haciendo, cómo ponerlo en un marco matemático, y con él hemos empezado a hacerlo y a construir los sistemas. Y en realidad lo estamos haciendo, hemos empezado con el sistema de visión, y tenemos sistemas que funcionan mucho mejor que cualquier cosa que se haya hecho antes, y lo hace de esta manera, lo hace de la forma en que lo hace un humano. Estamos construyendo una herramienta de software, o una serie de herramientas, que permiten construir neocórtex pero en software. No es un ordenador, sino que es un algoritmo que funciona en un ordenador, y lo captura todo igual que lo hace el neocórtex. Y podremos construir máquinas que serán inteligentes, aunque tu dirás que no son como los humanos. No podremos sentarnos y tomarnos un café con ellas, pero podrán pensar cosas, comprender y percibir el mundo como lo hacemos tu y yo.

Eduard Punset
Porque se comportarán de la misma manera que lo hace el córtex

Jeff Hawkins
Es como el córtex, puede sentir cosas y podrá decir: sé lo que es esto; y también tendrá expectativas de futuro, y podrá predecir: después de decir “sé lo que es esto” hará una predicción de lo que sucederá.

Eduard Punset
Tu dices dos cosas increíbles, primero dices que no importa tanto el sentido, ya sea la vista, el oído o el tacto, ya que al final en el neocórtex todo se convierte en la misma cosa, las mismas señales, y esto me lo vas a explicar; y la segunda cosa es que dices que para ser inteligente tienes que ser capaz de predecir, y eso es lo que hace el neocórtex, ya que puede predecir cosas, porque almacena lo que tu denominas “patrones de observación” (observational patterns). Es verdad que el cerebro primero observa patrones, los almacena y gracias a el almacenamiento puede hacer predicciones. Y tu dices que si puedes hacer predicciones eres inteligente.

Jeff Hawkins
Si se hacen de la forma correcta, sí. Pero vayamos a la primera parte de la pregunta. Que el córtex hace todo lo que hace utilizando el mismo método, el mismo algoritmo, es un descubrimiento increíble. Lo propuso por primera vez, hace 25 años, en Inglaterra, un señor llamado Mauntcastle, y dijo que aunque el neocórtex se parece a una servilleta grande, y las distintas partes hacen cosas diferentes (hay partes que son la vista, o el oído, o la música, o las matemáticas), si se analizan las células y su estructura son casi idénticas en todas partes. Lo que Mountcastle propuso es que era idéntico en todas las partes y aunque es difícil de creer es así. He preguntado a muchos neurocientíficos si creían en esto o no, y la mitad no lo creen y la mitad sí, y si se les pregunta por qué no se lo creen, dicen que porque es difícil de creer. Pero es el descubrimiento más importante hecho sobre el cerebro y explica cómo funciona y que es todo igual. Si fueras un cerebro y analizaras las señales que entran --entran por las fibras nerviosas del cerebro llamadas axones--, las que entran por los ojos son idénticas a las que entran por los oídos, o por la piel. No hay ningún sonido, o visión u tacto que entre en el cerebro, ya que en cuanto entran en el cerebro son todas unos patrones y son idénticos. La percepción del mundo es muy diferente, pero tiene que ver con la naturaleza del patrón, no tiene nada que ver con el mecanismo en si, porque es el mismo.

Eduard Punset
Y entonces una pregunta me viene a la mente. Sí esto es así, las máquinas inteligentes del futuro no hace falta que informen de lo que informan los sentidos tradicionales humanos, puede que estén afinadas para informar de otras cosas, que no tienen nada que ver con estos sentidos a los que estamos acostumbrados.

Jeff Hawkins
Exactamente, es algo muy importante en los descubrimientos de la naturaleza y es un método muy poderoso, que viene a decir: “si me das cualquier dato sensorial, construiré el modelo que lo causó”. Si estudiamos a los mamíferos, y pensamos en los humanos, tenemos vista, oído, olfato, tacto y gusto, pero también otros sentidos como el del propio cuerpo, que en realidad es de la posición del cuerpo; y otros animales, como los roedores, tienen los bigotes, que en realidad es un sentido completamente diferente que va al córtex, que lo procesa.

Eduard Punset
Y las abejas...

Jeff Hawkins
Las abejas no tienen córtex, sólo los mamíferos lo tienen, pero tienes razón ya que cuando construyamos las máquinas, en el futuro, funcionarán con el mismo principio: no hará falta que tengan oídos y ojos, sino que podrán funcionar con cualquier tipo de sensor, cosas simples como el sonar o el radar, e incluso sentidos más exóticos. He escrito en el libro que si se tiene un país y se piensa en las estaciones metereológicas que hay distribuidas por toda la geografía, es lo mismo que la retina del ojo, que va recogiendo todos los puntos de luz... pues lo mismo sucedería con las estaciones metereológicas, cuyas mediciones se podrían entrar en un sistema que “vería” el tiempo metereológico de la misma manera en que tu y yo vemos la luz. O sea que se podrían tener sentidos exóticos y funcionaría así.

Eduard Punset
Pero Jeff, ¿cómo nos comunicaríamos? Porque si hay diferentes sentidos, ¿cómo nos comunicaremos con estas máquinas que funcionan con diferentes sentidos de los que conocemos?

Jeff Hawkins
No es muy difícil. Imagínate lo siguiente: hay personas que no tienen todos los sentidos. Helen Keller es una mujer muy conocida y no podía ni ver ni oír, sólo tenía tacto, y sin embargo construyó un modelo del mundo que no es muy distinto del tuyo o el mío. No tenía unos sentidos distintos a los nuestros, sólo tenía uno y consiguió construir un modelo que se podía comunicar con nosotros. Nosotros estamos pensando en máquinas que se construirán de esta forma, y será muy fácil comunicarse con ellas. Evidentemente no tendremos una conversación como ésta, no se trata de esto, pero a los modelos, como por ejemplo el del tiempo metereológico, etc. será posible interrogarlos. Por ejemplo, les podremos preguntar ¿qué has descubierto? O ¿en qué estás pensando?

Eduard Punset
Cuando haces predicciones probablemente usas la capacidad metafórica de relacionar una cosa con la otra y decir que esto me permite hacer una predicción porque lo he visto, etc. ¿Es esto creatividad? O déjame que lo diga de otra manera: ¿qué es la creatividad?

Jeff Hawkins
Es creatividad, pero déjame que lo ponga en perspectiva. Cuando se hace una predicción, durante cada momento de la vida en que se está despierto no se es consciente de estar haciéndola. Cuando pongo una mano en algún sitio, tengo expectativas de cómo se sentirá y dónde y como lo sentiré. Nunca he estado en exactamente esta situación con anterioridad, y nunca me he sentado hablando contigo antes, de forma que todo esto es nuevo, y nunca he visto este papel antes, pero si lo toco tengo una expectativa de lo que hará: se puede quemar, puede volver, tiene un cierto tacto... y se que estoy haciendo predicciones porque lo conozco, porque si fuera diferente, como cristal o como gelatina o como algo frío diría: caramba, qué sorprendente. Es decir que el cerebro hace esto todo el tiempo y no nos damos cuenta. La segunda cosa que es sorprendente es que las entradas al cerebro siempre son nuevas, son únicas, suceden una vez y no se repiten nunca más, me puedes ver 100 veces y cada vez es un modelo distinto, porque o me he movido un poco, o porque la luz ha cambiado, es decir que se hacen predicciones sobre cosas nuevas todo el tiempo; este es un trozo de papel nuevo que nunca he visto antes y tengo una predicción sobre él. Nunca he tocado esta silla con anterioridad y tengo predicciones, los espectadores están oyendo y viéndome y tienen predicciones sobre lo que voy a decir. O sea que se hacen nuevas predicciones sobre situaciones novedosas, y esta es la esencia de la creatividad, pero se hacen a distintos niveles, no vemos esto como ser creativo. Yo no creo que estoy siendo increíblemente creativo cuando toco esta hoja de papel, o cuando anticipo lo que dirás, pero es lo mismo: en el córtex hacemos esto a niveles inferiores y superiores. Los niveles superiores son aquellos a los que llamamos creatividad: tenemos un nuevo problema que no he visto antes, quizá es un problema científico, se hace una predicción que es la hipótesis sobre la causa y por lo tanto se hace una predicción de lo que sucederá después. Es decir que se tiene un experimento que se va a probar y hacemos predicciones, y a un nivel superior creemos que es creatividad, pero es lo mismo, utilizamos información que tenemos del pasado y decimos que esto es algo similar. Un matemático puede decir: esta ecuación es similar a otra en la que trabajé hace 5 años, y si parece similar voy a utilizar una metodología similar a ver si puedo solucionarla.

Eduard Punset
Pero si todos los cerebros son creativos, ¿por qué algunas personas son más creativas que otras?

Jeff Hawkins
Vale, todo el mundo es creativo, y hay personas que son más creativas que otras en ciertas áreas. Se puede decir que yo soy más creativo que tu en ciertas tareas, y es posible que tu lo seas en otras. Yo creo que es parte del clásico debate naturaleza / entorno. Claramente una parte es aquello a lo que se ha estado expuesto, si no he estado expuesto a una serie de cosas no sabré hacer predicciones para eso; si me pones delante un nuevo idioma al que nunca con anterioridad he estado expuesto, para mi no tendrá ningún sentido, y no seré capaz de hacer predicciones de lo que se está hablando, o lo que se dirá después, o lo que hará alguien, etc. Es decir que se tiene que estar expuesto a los modelos para poder ser creativo, y cuanto más altos son los niveles más creativo se es: si he estado muchos años estudiando física, se puede ser muy creativo en física. La segunda cosa es que hay diferencias entre los cerebros humanos, sabemos que hay mucha variabilidad en los cerebros humanos, y las áreas dedicadas a tareas diferentes cambian mucho. Un hecho increíble es que si se toma el área visual del cerebro humano, que es el área más grande del neocórtex, varía en una factor de 3 entre distintas personas, es decir que es posible que una persona tenga una área tres veces más grande que otra. Todos pueden ver, pero una tendrá una visión más exacta, pero esto no se sabe: yo no puedo decir que tengo una visión más exacta que la tuya, no lo sé. Y de la misma manera hay personas que tienen un cerebro que es mejor para unas tareas determinadas. Pero no quiero predecir ni quién ni como, es algo natural.

Eduard Punset
Es cierto que si dañas el córtex de una rata hay cosas que pasarán de forma diferente, pero no muchas; sin embargo, si se destruye el córtex de un humano se paraliza por completo ¿no?

Jeff Hawkins
Esto es por la evolución del córtex porque el córtex empezó realmente con los mamíferos, y los no mamíferos no tienen córtex, pero todos los mamíferos lo tienen. Y en una rata el córtex es muy pequeño, quizá tiene el tamaño de un sello de correos, o algo así, y no juega un papel dominante en la vida de la rata. La rata tiene un cerebro primitivo como el de un reptil y un pequeño córtex, es decir que es de una cierta ayuda pero no es dominante, y como tu has dicho puedes extirpar el córtex de una rata y ella sigue moviéndose y tiene una apariencia casi normal. En los humanos, y en la progresión evolutiva, el córtex juega un papel muy dominante en la vida y tiene un tamaño enorme: de 1000 centímetros cuadrados. Y es muy importante, o sea que si se extrae el córtex de un humano es posible que respire y digiera alimentos pero nada más.

Eduard Punset
Porque realmente el córtex suplantó de alguna manera...

Jeff Hawkins
Sí, el córtex creció físicamente de una manera increíble alrededor del cerebro y tiene una fuerza dominante, aunque por supuesto no lo controla todo. Por ejemplo, si te digo que dejes de respirar es posible que lo hagas, pero la parte primitiva del cerebro en un cierto punto dirá que hay que respirar, ya que no se puede estar sin respirar, o sea que no lo controla todo, pero sí casi todo.

Eduard Punset
O sea que este comportamiento en la mayoría de los animales, y desde luego en los no mamíferos, obedece al cerebro primitivo, y en los humanos tenemos esta especie de monstruo que crece en el cerebro y ha suplantado muchas de sus funciones.

Jeff Hawkins
Teníamos el cerebro primitivo, el de un cocodrilo o de un reptil o lo que fuera, pero al caminar, por ejemplo, la mayoría del control motor, que es el que hace que se muevan las piernas, no viene del córtex sino de partes del cerebro primitivo; sin embargo en los humanos, con la excepción de unos movimientos básicos, el habla, el movimiento de las manos, la interacción social, casi todo lo que hacemos, todo está controlado por el córtex. Seguimos teniendo esta parte primitiva, todavía está ahí y el mejor ejemplo es que al aprender a montar en bicicleta...

Eduard Punset
No tiene nada que ver con el córtex...

Jeff Hawkins
No mucho, la mayoría de la gente no sabe cómo montan en bicicleta y es por eso que se caen, porque el córtex no tiene mucho que ver y el cerebro primitivo sí. Resulta que cuando se quiere ir a la izquierda hay que ir primero a la derecha para que la bicicleta se incline y se pueda hacer una curva a la izquierda. Si cuando se quiere ir a la izquierda se gira el manillar inmediatamente te caes, y esto es algo que el córtex no controla, y hay alguna historia similar, pero todo lo demás lo sabe hacer el córtex.

Eduard Punset
Has mencionado la evolución y pensemos en la célula, primero... estoy pensando en la predicción que significa inteligencia. La célula, o todos los organismos vivos, me imagino que hacen una cierta predicción: la célula, las plantas y las neuronas. Y si es así, la pregunta obvia que la audiencia haría es: ¿los animales son inteligentes?

Jeff Hawkins
Esta es una respuesta compleja, aunque intentaré hacerla sencilla. Cualquier comportamiento del animal depende de tener un cierto modelo del mundo que hace las predicciones, para eso están los modelos. Una planta hace predicciones porque sube hacia el tejado en busca de la luz, y envía las raíces hacia abajo en busca del agua. Esto no es pensar, las plantas no tienen una conversación y no dicen dónde voy a poner las raíces para buscar agua, pero sí que es predicción. La definición de la inteligencia es construir un modelo del mundo y hacer predicciones. Hay una gama: desde lo más simple, como los animales unicelulares o las plantas, etc. hasta los más sofisticados que son los humanos. Y a un nivel muy elevado se hace lo mismo, lo que se tiene que pensar con los mamíferos es que hemos desarrollado un sistema para hacer esto durante la vida, es decir que aprendemos mucho durante nuestra vida. Casi todo lo que sabemos del mundo, sobre los programas de TV, o ciencia, o sillas, o lo que sea, no nacimos sabiendo eso, lo hemos aprendido; y la planta no es así, no aprende nada durante su vida, pero nosotros lo aprendemos todo durante la vida. Y el córtex tiene una forma muy genérica de hacer esto: puede aprender casi todo; anteriormente en la genética se tenía que aprender de forma evolutiva, pero nosotros podemos aprender casi todo durante la vida. A un cierto nivel las plantas son inteligentes, pero es un nivel muy mínimo, no se puede decir que tengan un nivel ideal de inteligencia. Pero cuando hablamos de mamíferos, de la rata, ¿es inteligente? Claro que lo es. No es tan inteligente como nosotros, ni puede comprender el mundo como nosotros, no puede aprender lo mismo, pero por definición puede hacer predicciones y tiene un mundo de percepciones, por lo tanto la rata es mínimamente inteligente. No sirve de mucho poner unas marcas de inteligencia: éste animal es inteligente y éste no lo es, todo es una gama que va desde los humanos hasta el organismo más simple.

Eduard Punset
Cuando te oigo hablar sobre la creatividad me da tanto miedo... porque pienso: caramba, es posible que mi creatividad me pierda, que me lleve a algún sitio que...

Jeff Hawkins
Déjame que te explique otro término que utilizamos: las creencias. Cuando el cerebro está expuesto al mundo, construye un modelo del mundo, y ese modelo es básicamente cómo funciona el mundo, y esto genera unas creencias. Todos los seres humanos compartimos algunas creencias. Compartimos unas creencias sobre el sol, sobre la gravedad, sobre alimentos, sobre el agua y sobre rutinas de cada día. Pero cuando vamos subiendo en ideas abstractas en la jerarquía del córtex las creencias difieren, formamos creencias distintas, cada religión tiene un conjunto diferente de creencias, y no todas pueden ser correctas. También podemos formar creencias falsas que a veces denominamos estereotipos, pero es muy fácil para los humanos crear las falsas creencias. El algoritmo que nos ha llevado a conocer el mundo y nos permite hacer predicciones, y ser creativos, puede formar creencias falsas del mundo, y por lo tanto puede crear predicciones falsas y llevarnos a hacer cosas malas. Y aquí es donde se produce la mayor parte de los conflictos del mundo, y es porque todos tenemos un conjunto diferente de creencias en la parte superior, mientras que todos compartimos las básicas: los hombres y las mujeres hacemos lo mismo, pero es en la parte superior donde tenemos creencias fundamentalmente diferentes sobre cómo funciona el mundo.

Eduard Punset
Vamos a volver a las máquinas, a las máquinas inteligentes. La gente todavía tiene miedo a las máquinas inteligentes: ¿por qué?

Jeff Hawkins
Tiene historia: cuando se construyo la máquina de vapor se le tenía miedo, era como un milagro, una máquina que se mueve como un cuerpo, y eso da miedo. Cuando se inventó el ordenador, se pensó que iba a sobrepasar el comportamiento humano, y esto no sucedió; la gente tiene el mismo miedo de las máquinas inteligentes, creen que serán igual que los humanos. Es como de ciencia ficción y como si fueran un robot, como R2-D2 en Star Wars o algo así. Creen que será como un robot humano, pero no será así, las máquinas inteligentes tienen una apariencia muy aburrida y es posible que sean como ordenadores pero puede que estén pensando o que sientan el mundo: tampoco tendrán hambre, o querer tener sexo, o protegerse a si mismas, o querer reproducirse a si mismas, de la misma manera que los ordenadores no son así, ni las máquinas de vapor tampoco lo son. La gente se pone nerviosa porque se está recreando la humanidad, pero yo creo que es un error, y en realidad no tengo ningún deseo de hacerlo; sin embargo, entender cómo funciona el contexto y recrearlo creo que traerá grandes beneficios, que será muy bueno.

Eduard Punset
¿Cómo cuál? ¿Qué hacen las máquinas inteligentes? Trabajan más rápidamente que el cerebro, esto es seguro.

Jeff Hawkins
Trabajan más rápidamente que el cerebro y pueden ser más grandes y más inteligentes que el cerebro. Pero déjame que ponga en dos categorías lo que pueden hacer las máquinas inteligentes. La primera categoría es la obvia pero un poco más aburrida. Las máquinas pueden hacer lo que hacen los humanos, se pueden construir máquinas que conduzcan coches, o que miren las cámaras de seguridad para vigilar lo que sucede; se pueden construir máquinas que hagan traducción automática de idiomas, etc.: cosas que pueden hacer los humanos, pero que no son realmente interesantes. Hay una serie de cosas que tradicionalmente el mundo de la inteligencia artificial ha intentado hacer. Para mí lo que es más interesante de construir córtex como los del cerebro es que hagan cosas que los
humanos tienen problemas para hacer, como lo que hemos hablado antes de innovar en nuevos sensores. O, por ejemplo, los humanos no son muy buenos en física o en matemáticas, nos cuesta mucho y necesitamos mucho tiempo para ser buenos en eso, y creo que podemos construir máquinas que puedan ser realmente excelentes. Lo que es interesante, y de hecho es lo que motiva todo el trabajo que hago, es construir una máquina que nos ayude a entender cómo funciona todo el mundo, que responda a grandes preguntas como son la naturaleza del tiempo y el espacio, o de dónde viene el universo y a dónde va. Estas son para mi preguntas muy interesantes, y creo que construyendo unas máquinas muy inteligentes que se concentren en estos problemas –faltan algunos años para que suceda pero estoy seguro que sucederá– seremos capaces de tener un entendimiento mayor del mundo y de lo que realmente sucede aquí, y eliminar algunas de las creencias falsas.

sábado, 8 de marzo de 2008

Genetic programming

Genetic programming

Genetic programming (GP) is an evolutionary algorithm based methodology inspired by biological evolution to find computer programs that perform a user-defined task. It is a specialization of genetic algorithms where each individual is a computer program. Therefore it is a machine learning technique used to optimize a population of computer programs according to a fitness landscape determined by a program's ability to perform a given computational task. The roots of GP begin with the evolutionary algorithms first utilized by Nils Aall Barricelli in 1954 as applied to evolutionary simulations but evolutionary algorithms became widely recognized as optimization methods as a result of the work of Ingo Rechenberg in the 1960s and early 1970s - his group was able to solve complex engineering problems through evolution strategies (1971 PhD thesis and resulting 1973 book). Also highly influential was the work of John Holland in the early 1970s, and particularly his 1975 book. The first results on the GP methodology were reported by Stephen F. Smith (1980)[1] and Nichael L. Cramer (1985),[2]. In 1981 Forsyth reported the evolution of small programs in forensic science for the UK police. John R. Koza is a main proponent of GP and has pioneered the application of genetic programming in various complex optimization and search problems [3].

GP is very computationally intensive and so in the 1990s it was mainly used to solve relatively simple problems. But more recently, thanks to improvements in GP technology and to the exponential growth in CPU power, GP produced many novel and outstanding results in areas such as quantum computing, electronic design, game playing, sorting, searching and many more.[4] These results include the replication or development of several post-year-2000 inventions. GP has also been applied to evolvable hardware as well as computer programs. There are several GP patents listed in the web site [5].

Developing a theory for GP has been very difficult and so in the 1990s GP was considered a sort of outcast among search techniques. But after a series of breakthroughs in the early 2000s, the theory of GP has had a formidable and rapid development. So much so that it has been possible to build exact probabilistic models of GP (schema theories and Markov chain models).[citation needed]

Contents

[hide]

Chromosome representation

A function represented as a tree structure
A function represented as a tree structure


GP evolves computer programs, traditionally represented in memory as tree structures. Trees can be easily evaluated in a recursive manner. Every tree node has an operator function and every terminal node has an operand, making mathematical expressions easy to evolve and evaluate. Thus traditionally GP favors the use of programming languages that naturally embody tree structures (for example, Lisp; other functional programming languages are also suitable).

Non-tree representations have been suggested and successfully implemented, such as the simpler linear genetic programming which suits the more traditional imperative languages [see, for example, Banzhaf et al. (1998)]. The commercial GP software Discipulus,[6] uses AIM, automatic induction of binary machine code[7] to achieve better performance.[8] MicroGP[9] uses a representation similar to linear GP to generate programs that fully exploit the syntax of a given assembly language.

Genetic operators

Crossover

The main operators used in evolutionary algorithms such as GP are crossover and mutation. Crossover is applied on an individual by simply switching one of its nodes with another node from another individual in the population. With a tree-based representation, replacing a node means replacing the whole branch. This adds greater effectiveness to the crossover operator. The expressions resulting from crossover are very much different from their initial parents.

The following code suggests a simple implementation of individual deformation using crossover:

individual. Children[randomChildIndex] = otherIndividual.Children[randomChildIndex];

Mutation

Mutation affects an individual in the population. It can replace a whole node in the selected individual, or it can replace just the node's information. To maintain integrity, operations must be fail-safe or the type of information the node holds must be taken into account. For example, mutation must be aware of binary operation nodes, or the operator must be able to handle missing values.

A simple piece of code:

individual. Information = randomInformation;

or

individual = generateNewIndividual;

Meta-Genetic Programming

Meta-Genetic Programming is the proposed meta learning technique of evolving a genetic programming system using genetic programming itself. [10]. It suggests that chromosomes, crossover, and mutation were themselves evolved, therefore like their real life counterparts should be allowed to change on their own rather than being determined by a human programmer. Meta-GP was proposed by Jürgen Schmidhuber in 1987 [11]; it is a recursive but terminating algorithm, allowing it to avoid infinite recursion.

Critics of this idea often say this approach is overly broad in scope. However, it might be possible to constrain the fitness criterion onto a general class of results, and so obtain an evolved GP that would more efficiently produce results for sub-classes. This might take the form of a Meta evolved GP for producing human walking algorithms which is then used to evolve human running, jumping, etc. The fitness criterion applied to the Meta GP would simply be one of efficiency.

For general problem classes there may be no way to show that Meta GP will reliably produce results more efficiently than a created algorithm other than exhaustion. The same holds for standard GP and other search algorithms, of course.


Otra referencia Util ( tut GP)


Genetic programming is a branch of genetic algorithms. The main difference between genetic programming and genetic algorithms is the representation of the solution. Genetic programming creates computer programs in the lisp or scheme computer languages as the solution. Genetic algorithms create a string of numbers that represent the solution. Genetic programming, uses four steps to solve problems:
1) Generate an initial population of random compositions of the functions and terminals of the problem (computer programs).

2) Execute each program in the population and assign it a fitness value according to how well it solves the problem.

3) Create a new population of computer programs.
i) Copy the best existing programs
ii) Create new computer programs by mutation.
iii) Create new computer programs by crossover(sexual reproduction).

4) The best computer program that appeared in any generation, the best-so-far solution, is designated as the result of genetic programming [Koza 1992].


Figure 1: genetic programming Flowchart.



Fitness Function
The most difficult and most important concept of genetic programming is the fitness function. The fitness function determines how well a program is able to solve the problem. It varies greatly from one type of program to the next. For example, if one were to create a genetic program to set the time of a clock, the fitness function would simply be the amount of time that the clock is wrong. Unfortunately, few problems have such an easy fitness function; most cases require a slight modification of the problem in order to find the fitness.


Gun Firing Program
A more complicated example consists of training a genetic program to fire a gun to hit a moving target. The fitness function is the distance that the bullet is off from the target. The program has to learn to take into account a number of variables, such as wind velocity, type of gun used, distance to the target, height of the target, velocity and acceleration of the target. This problem represents the type of problem for which genetic programs are best. It is a simple fitness function with a large number of variables.

Water Sprinkler System
Consider a program to control the flow of water through a system of water sprinklers. The fitness function is the correct amount of water evenly distributed over the surface. Unfortunately, there is no one variable encompassing this measurement. Thus, the problem must be modified to find a numerical fitness. One possible solution is placing water-collecting measuring devices at certain intervals on the surface. The fitness could then be the standard deviation in water level from all the measuring devices. Another possible fitness measure could be the difference between the lowest measured water level and the ideal amount of water; however, this number would not account in any way the water marks at other measuring devices, which may not be at the ideal mark.

Maze Solving Program
If one were to create a program to find the solution to a maze, first, the program would have to be trained with several known mazes. The ideal solution from the start to finish of the maze would be described by a path of dots. The fitness in this case would be the number of dots the program is able to find. In order to prevent the program from wandering around the maze too long, a time limit is implemented along with the fitness function.


Functions and Terminals
The terminal and function sets are also important components of genetic programming. The terminal and function sets are the alphabet of the programs to be made. The terminal set consists of the variables and constants of the programs. In the maze example, the terminal set would contain three commands: forward, right and left. The function set consists of the functions of the program. In the maze example the function set would contain: If "dot" then do x else do y. In the gun firing program is the terminal set would be composed of the different variables of the problem. Some of these variables could be the velocities and accelerations of the gun, the bullet and target. The functions are several mathematical functions, such as addition, subtraction, division, multiplication and other more complex functions.

Crossover Operation
Two primary operations exist for modifying structures in genetic programming. The most important one is the crossover operation. In the crossover operation, two solutions are sexually combined to form two new solutions or offspring. The parents are chosen from the population by a function of the fitness of the solutions. Three methods exist for selecting the solutions for the crossover operation.

The first method uses probability based on the fitness of the solution. If is the fitness of the solution Si and

is the total sum of all the members of the population, then the probability that the solution Si will be copied to the next generation is [Koza 1992]:


Another method for selecting the solution to be copied is tournament selection. Typically the genetic program chooses two solutions random. The solution with the higher fitness will win. This method simulates biological mating patterns in which, two members of the same sex compete to mate with a third one of a different sex. Finally, the third method is done by rank. In rank selection, selection is based on the rank, (not the numerical value) of the fitness values of the solutions of the population [Koza 1992].

The creation of the offsprings from the crossover operation is accomplish by deleting the crossover fragment of the first parent and then inserting the crossover fragment of the second parent. The second offspring is produced in a symmetric manner. For example consider the two S-expressions in Figure 2, written in a modified scheme programming language and represented in a tree.


Figure 2: Crossover operation for genetic programming. The bold selections on both parents are swapped to create the offspring or children. (The child on the right is the parse tree representation for the quadratic equation.)



Figure 3: This figure illustrates one of the main advantages of genetic programming over genetic algorithms. In genetic programming identical parents can yield different offspring, while in genetic algorithms identical parents would yield identical offspring. The bold selections indicate the subtrees to be swapped.


An important improvement that genetic programming displays over genetic algorithms is its ability to create two new solutions from the same solution. In the Figure 3 the same parent is used twice to create two new children.

Mutation
Mutation is another important feature of genetic programming. Two types of mutations are possible. In the first kind a function can only replace a function or a terminal can only replace a terminal. In the second kind an entire subtree can replace another subtree. Figure 4 explains the concept of mutation:


Figure 4: Two different types of mutations. The top parse tree is the original agent. The bottom left parse tree illustrates a mutation of a single terminal (2) for another single terminal (a). It also illustrates a mutation of a single function (-) for another single function (+). The parse tree on the bottom right illustrates a the replacement of a subtree by another subtree.



Summary
Genetic programming is much more powerful than genetic algorithms. The output of the genetic algorithm is a quantity, while the output of the genetic programming is a another computer program. In essence, this is the beginning of computer programs that program themselves.

Genetic programming works best for several types of problems. The first type is where there is no ideal solution, (for example, a program that drives a car). There is no one solution to driving a car. Some solutions drive safely at the expense of time, while others drive fast at a high safety risk. Therefore, driving a car consists of making compromises of speed versus safety, as well as many other variables. In this case genetic programming will find a solution that attempts to compromise and be the most efficient solution from a large list of variables.

Furthermore, genetic programming is useful in finding solutions where the variables are constantly changing. In the previous car example, the program will find one solution for a smooth concrete highway, while it will find a totally different solution for a rough unpaved road.


REFERENCES

Koza, John R. 1992. Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA: The MIT Press.

Cramer, Nichael Lynn: "A Representation for the Adaptive Generation of Simple Sequential Programs", Proceedings, International Conference on Genetic Algorithms and their Applications, July 1985 [CMU], pp183-187.