Aproximacion Integrales: Método Montecarlo

Los métodos de montecarlo son un conjunto de métodos de aproximación y optimización basado en la computación de escenarios aleatorios para la obtención de los resultados más óptimos. Este tipo de métodos, que llevan el nombre en honor al casino de Montecarlo, son muy usados en múltiples campos de la ciencia como la física, ingeniería, finanzas, inteligencia artificial, etc.

En este post nos vamos a centrar en el método Montecarlo para la aproximación de funciones integrales definidas en un intervalo dado. El algoritmo se centra, básicamente en la generación de un número N de datos aleatorios* dentro de una superficie (coincidente con el intervalo a calcular la integral).

Una vez generados dichos N datos aleatorios, se dibuja la función a integrar en dicho intervalo. Una vez dibujada dicha gráfica, nos disponemos a calcular cada uno de los puntos aleatorios de por debajo de la función a calcular. Como último paso calculamos el área aproximada que queda por debajo de la curva (definición de integral en un intervalo dado) en relación con el área total de la superficie en donde se han dibujado los N puntos.

Es fácil de imaginarse que a mayor número de elementos generados aleatoriamente sobre la superficie mayor es la aproximación de la integral debido a que el porcentaje de puntos por debajo de la curva se acerca con mayor precisión a la superficie a aproximar.

En las imágenes mostradas a continuación se ha representado la función integral definida entre los puntos 0 y 1 de la función x^2. EL valor real de dicha integran es de 1/3. El valor calculado por el algoritmo para 500.000 puntos aleatorios es de 0.333320.

* La generación de los números aleatorios debe ser realizada uniformemente por toda la superficie S.

NOTA: Si el lector necesita o quiere el código en OCTAVE/MATLAB que escriba un comentario con su mail.

Video Captchas

Los captchas son sistemas de seguridad para detectar dentro de la red si el verdadero usuario de un servicio es un ser humano o una computadora. El funcionamiento de este tipos de sistemas radica en una imagen formada por caracteres u objetos los cuales el usuario debe ser capaz de identificar para autenticar su humanidad.

Estos sistemas son fácilmente rompibles debido a que están estrechamente ligados con una rama de la inteligencia artificial dedicada al procesamiento de imágenes y vídeo, la cual ha sufrido grandes evoluciones a lo largo de estos últimos años. Esta evolución en la inteligencia artificial ha provocado que los captchas estén en continua evolución e incluso han provocado la reformulación del sistema.

En sus comienzos, los captchas eran sistemas formados por imágenes en las que había que detectar la palabra o caracteres ocultos. Este sistema fue automatizado con la detección de caracteres mediante técnicas de OCR, es decir, entrenando a un modelo de forma automática con el fin de detectar los diferentes caracteres de una imagen. Ante esta ruptura de los captchas, los desarrolladores de los mismos se dedicaron a crear caracteres sobre posicionados con líneas o cuadros con el fin de dificultar la tarea a esta detección de caracteres de forma automática. Estas medidas adoptadas no fueron suficientes para parar la detención automática de de caracteres y, ante este nuevo fallo, los investigadores de estos sistemas dieron lugar a una nueva generación de captchas.

Estos nuevos sistemas están formados por imágenes rotadas, vídeos, sonidos o incluso formados por anuncios de productos. En el caso de las imágenes rotadas ya existen investigaciones y estudios dedicados a la identificación de imágenes independientemente del ángulo de inclinación. En el resto de casos será un buen momento para ver hasta donde son capaces de llegar los sistemas de detección automática.

Problema con la Xbox

Este post lo he escrito como mi solución a un problema que me dio hace poco con la Televisión, la conexión HDMI y la videoconsola Xbox. El problema que me ocurría radica en la conexión HDMI con el televisor, al conectar la videoconsola, la televisión me mostraba un mensaje de error denominado "Modo no compatible". Lo que hizo saltar mis alarmas fue que en la televisión donde probé la videoconsola si que funcionaba la conexión HDMI. La solución al problema es muy sencilla como posteriormente podréis leer.

Primeramente y para completar el post, decir que la conexión HDMI es un estándar creado por las grandes compañías de televisión y derivados como LG, Sony, Samsung... Al utilizar la conexión HDMI, tanto el audio como el vídeo se transfieren sin comprimir y por un mismo cable. La vulnerabilidad de este sistema radica en la conexión y el puerto de los dispositivos. Los dispositivos con este sistema quedan conectados pero no quedan identificados entre sí.

Referente a las televisiones, mencionar que en las ultimas generaciones de estos dispositivos se ha puesto muy de moda el FullHD y muchas características de sonido. Pero en este caso, vamos a hablar de las diferentes calidades en las diferentes resoluciones de la televisión, es decir, los pixels por punto o pulgada (ppp). Los pixels por punto no identifican una resolución de la televisión sino la calidad de la misma, es decir, indican los puntos dedicados a la representación de un punto dentro de la pantalla. Las televisiones de hoy en día pueden soportar desde los 420p o 420i, a los 1080p o a los 1080i. Pero, ¿cual es el significado de la "p" y de la "i"? La "p" hace referencia a la abreviación de progresivo y la "i" de interlazado. Es decir las letras hacen referencia al modo de crear la imagen en pantalla. En principio el tratamiento de la imagen es mejor en modo progresivo ya que lo hace doblemente más rápido que el interlazado.

Volviendo al problema que se planteaba al principio, en mi caso, tenia la videoconsola XBox configurada a 1080p, esta configuración es incompatible con el modelo de mi televisión. El cable HDMI no detectaba el dispositivo, por lo que tenía que dar uso de la conexión mediante el eurocontector durante un tiempo. Como solución, propongo primeramente al usuario ver las diferentes configuraciones de la televisión y seguido, al conectar la XBox configurarla según dichas configuraciones leídas. En el caso de que la Xbox no detecte la conexión HDMI se deberá conectar la videoconsola a otra televisión que soporte la conexión configurada y reconfigurarla a una menor y que sea soportada por la televisión que vaya a albergar de forma continua la Xbox.

Artificial Intuition

La semana pasada se habló del aprendizaje como vía para la creación de programas inteligentes. Como dotar al sistema de la inteligencia y la experiencia necesaria. Para ello nos centramos en el aprendizaje de los niños en su primera etapa de vida.

Esta semana, veremos una temática parecida, la intuición artificial, es decir, la creación de programas inteligentes con el único objetivo de predecir valores futuros o estados futuros.

La experiencia o aprendizaje de estos sistemas esta centrado en las Bases de Datos. Las Bases de datos proporcionan los datos necesarios para que el sistema adquiera la experiencia necesaria y uniéndolo con la información referente al problema, estos simples datos son transformados en conocimiento:

DATOS+INFORMACIÓN= CONOCIMIENTO

La intuición artificial, tal y como se ha mencionado en los párrafos anteriores, esta muy ligada al aprendizaje supervisado y más concretamente con las técnicas predictivas. Dentro de las técnicas predictivas se tienen técnicas usadas en la Inteligencia Artificial como Redes Neuronales, Árboles de Clasificación, Redes Bayesianas, Algoritmos genéticos, algunos algoritmos bioinspirados... que en futuros artículos espero comentar.

Como se puede observar, dentro de la inteligencia artificial hay conceptos muy ligados entre sí. Pero lo importante no es definirlos perfectamente sino saber que existen y que pueden ayudar a mejorar los sistemas actuales.

Esos locos bajitos

El otro día, mientras trabajaba, salió la discusión sobre los aspiradores automáticos, aspiradores que limpian la casa aprendiendo primeramente el mapa de la casa. Realmente, esta discusión acaparó mi atención, sobre todo la forma de escaneo de la casa, no pasar sobre una misma superficie varias veces. La verdad, me pareció fascinante que la inteligencia artificial (IA) este avanzando a esos niveles de usabilidad en el mercado corriente.

Pero no fue hasta hace dos días, cuando, de repente, un articulo recientemente publicado por Frank Guerin llamó mi atención. El título de dicho artículo es “Learning like a Baby: A survey of AI aproaches”. Dicho artículo se centra en la creación de un sistema que emule la forma de obtener conocimiento de un bebé.

Como ya se sabe, los bebes, para llevar a cabo la obtención de conocimiento, utilizan gran parte de sus sentidos (tacto, oído, vista, gusto) y mediante prueba error van sabiendo que es cada elemento del mundo físico. Basándonos en esta filosofía, en el artículo muestran las diferentes técnicas de inteligencia artificial para emular o aproximarse a la creación de esta forma de obtención de conocimiento innato aplicado a las máquinas. En el documento, se hace una diferenciación entre las diferentes formas de obtener conocimiento (creación-extrapolación de mapas, acciones reflejas, adquisición de hábitos...) del conocimiento obtenido a la hora de aplicar ese aprendizaje interno dentro del mundo físico real (identificación de objetos, movimiento de los objetos...).

Dentro de las conclusiones de dicho documento, afirman que en un futuro será posible canalizar este conocimiento, aunque también se afirma que queda un largo camino por recorre e investigar dentro de estos campos. La verdad es que no es la primera vez que científicos y psicólogos se centran en la forma de obtener conocimiento o la forma sencilla pero eficiente de dar ideas por parte de los niños y/o bebés. Una de las posibles razones de este fenómeno pueden estar centradas en las barreras de conocimiento que impiden a la gente adulta tomar, en una primera instancia, soluciones más sencillas a los problemas surgidos.

KASUMI ATTACK

El 2010 comienza por todo lo alto en lo que a seguridad informática se refiere. Y es que en estas tres semanas que llevamos de nuevo año ya se ha reducido el tiempo de cómputo de dos grandes algoritmos. La primera noticia se pudo leer el pasado 13 de Enero de 2010 bajo el título de RSA 768-bit cuyo método radica en introducir más procesadores en paralelo con el fin de reducir el tiempo de cómputo. La segunda noticia ha salido a lo largo de esta semana, donde O.Dunkelman, N. Keller y A. Shamir han conseguido reducir el tiempo de cómputo del algoritmo A5/3, muy usado en los teléfonos de tercera generación (tecnología GSM).

Esta noticia esta muy unida con la publicada el pasado 28 de Diciembre de 2009 en la CCC donde K. Nohl consiguió romper uno de los algoritmos de GSM, más concretamente A5/1. Este algoritmo es el encargado de cifrar todas las conexiones de voz inalámbricas. Con este descubrimiento, Nohl dejó claro que la seguridad dentro de la telefonía inalámbrica debe mejorar considerablemente.

Como mencionaba al principio, en escasas 3 semanas de la publicación en la CCC, O.Dunkelman, N. Keller y A. Shamir han publicado un articulo donde muestran un algoritmo de ataque sobre el algoritmo A5/3, evolución directa de sus antecesores A5/1 (1980) y A5/2 (1999). Este algoritmo de telefonía de tercera generación, A5/3 o Kasumi, nació a partir de un algoritmo mucho más robusto denominado MISTY (1997). En cierto modo, el algoritmo A5/3 es una reducción de complejidad de MISTY dotando a Kasumi de una mayor rapidez y manejabilidad a nivel de hardware.

Centrándonos en el ataque, el algoritmo propuesto es una variación del ataque boomerang al que los autores han denominado ataque sandwich. El ataque boomerang esta basado en estudiar como las modificaciones dentro del texto plano afectan al texto encriptado. La modificación realizada en el ataque sandwich ha sido el de introducir una nueva capa al algoritmo (basada en la construcción de Feister) con el fin de reducir los casos de estudio y con ello se aumenta la probabilidad de éxito. En la imagen que se muestra a continuación, se pueden ver las diferencias entre ambos algoritmos:

Esta nueva capa introducida se aprovecha de las construcciones de Feister, es decir, funciones simétricas (misma función) para encriptar y desencriptar datos. Tal y como se menciona en el documento, gracias a este truco se consigue un fallo del algoritmo a favor del atacante. El punto negativo de este ataque, desde el punto de vista de algoritmia, reside en la gran cantidad de paquetes que deben ser capturados para descubrir la clave.

Como conclusión a este documento mencionar que no se debe descuidar la seguridad informática y que hay que mantenerla actualizada, debido a que en cualquier momento, se pueden dar algun que otro susto como en el caso de la telefonía.

FUENTE: la imagen ha sido obtenida del documento original publicado.

FIBONACCI

La historia se remonta cinco años atrás, cuando entre en la universidad a estudiar ingeniería informática. En las prácticas de una de las asignaturas, el profesor, mandó realizar un programa que imprimiera por pantalla la serie de Fibonacci de orden 10, es decir:

0,1,1,2,3,5,8,13,21,34,55,89

Ese fue mi primer contacto con dicha serie no volviéndola a ver hasta pasados unos años.En aquel momento, no hice ninguna indagación acerca de dicha sucesión y ese hecho friki-anecdótico quedo en mi recuerdo como una práctica más realizada con éxito.

Hace unos pocos meses me vino a la mente ese recuerdo, junto con apariciones de dicha serie en libros de fantasía y películas de semi-acción. Esta vez si creí oportuno indagar más, de dónde proviene la serie, porque esa serie es tan famosa, etc.

El origen de esta sucesión se debe al problema de la cría de conejos que dice lo siguiente:

"Cierto hombre tenía una pareja de conejos juntos en un lugar cerrado y uno desea saber cuántos son creados a partir de este par en un año cuando es su naturaleza parir otro par en un simple mes, y en el segundo mes los nacidos parir también”

Pero la serie se hizo realmente famosa de la mano de Édouard Lucas, ya que demostró que la serie converge en el infinito en el número aúreo. Por esta razón, la serie define muchos procesos de la naturaleza como la colocación de las celdas de la colmena, la disposición de las semillas de los girasoles, la estructura de los caparazones de los caracoles…

Llegados a este punto decidí realizar una prueba que consiste en intercambiar la base o comienzo de la serie, tomando distintos valores como marco a continuación:

1,1,2,3,5,8,13,21,34…
1,2,3,5,8,13,21,34…
1,3…
1,4…

Posteriormente, me propuse realizar la resta entre una fila y la siguiente de la matriz, dando como resultado la serie de Fibonacci en distintos ordenes. Éste resultado se asemeja a uno de los capítulos de un libro de Douglas Hofstader, "Gödel, Escher, Bach: un Eterno y Grácil Bucle", dónde compara los distintos momentos de tensión de la música de Bach (cadencia perfecta) con los momentos de falsa tensión (cadencia imperfecta). Es decir, se compara la función fundamental de la serie con los diferentes armónicos de dicha serie. En el libro se compara la el morfismo utilizado para crear la serie frente al conjunto de números válido para generarlo.

Esta serie, al explicar numerosos procesos de la naturaleza abre el debate en numerosos campos como el de la ciencia, leyes de la física frente al azar en los procesos naturales, el de la música, Bach frente a Jonh Cage, o incluso el de la filosofía, filosofía occidental frente a la filosofía Zen u oriental.

Una red social para gobernarlas a todas

Hoy en día, casi todo el mundo está conectado con sus amigos por medio de una o varias redes sociales y pocas son las personas que no las utilizan o que no tienen conocimiento sobre ellas. Existen redes sociales para todos los gustos, pero, por regla general, la gente suele tener dos tipos diferenciados de redes sociales, la red social laboral y la red social de amigos. La primera de ellas, como su nombre indica, es la dedicada a contactos laborales: búsqueda de trabajo, foros de discusión de temas relacionados con el trabajo realizado, etc. En cambio, la segunda de ellas es la dedicada a las relaciones más íntimas, es decir, dedicada a estrechar relaciones con los amigos y/o búsqueda de otros tipos de relaciones mucho más íntimas.

Pero el afán del ser humano por generalizar las aplicaciones, es decir, el afán por englobar en una misma aplicación diferentes funcionalidades para otorgar mayor comodidad a los usuarios de redes sociales, ha dado lugar a una red social denominada Plaxo.

Esta red social une las mejores prácticas de las redes sociales laborales como, por ejemplo, la organización de contactos en base a una agenda/libreta de direcciones fácilmente consultable, sencillos formularios para editar/actualizar tu currículum vitae, calendario para programar eventos y tareas, sencillez en la sincronización con dispositivos móviles/correo electrónico, compartición de noticias y marcadores … Estas funcionalidades se unen con las mejores prácticas de las redes sociales de amigos como comentar el estado personal, incluir/etiquetar fotos dentro del perfil, aplicaciones de explotación de datos personales, importación de contactos de diferentes cuantas de correos y de diferentes redes sociales como Facebook, envío de mensajes privados a otros contáctos, conexión redes sociales de música y streaming, etc.

Pero, no todo es gloria para esta red social debido a que tiene algún problema de visualización dentro de las nuevas versiones de los navegadores, así como una gran competitividad dentro del mercado ya que, por ejemplo, en el mercado español, debe luchar con Tuenti y Facebook, líderes en redes sociales de amistades, y con LinkedIn, red social líder en el mercado de redes sociales dedicadas a contactos profesionales.

En conclusión, pese ser Plaxo una buena aplicación gestora de los contactos personales, va a ser difícil que se haga con un hueco en el mercado español ya afianzado con redes como las mencionadas con anterioridad. Aun y todo, a lo largo de este año veremos su evolución.