Otros Complejidad computacional de las operaciones matemáticas.

[guibix]

Hola gente!

Estoy inmerso en un proyecto para una simulación de vida artificial evolutiva con la implementación de redes neuronales para la IA de los autómatas. Se trata de un proyecto bastante complejo del que no hablaré porque no viene al caso.

El proyecto lo hacemos en colaboración con un amigo que sabe bastante de programación, pero no domina mucho el tema matemático. Mi caso es opuesto, no sé casi nada de programación pero se me da bien el tema matemático, por lo que hacemos un buen equipo.

Como dato que no sé si es relevante, la simulación la estamos planteando en C++ pero estamos tanteando lenguajes de Linux que suponemos podrían ser mejores.

El tema es que estoy definiendo una serie de operaciones y funciones que los autómatas deben ejecutar. La complejidad computacional de la simulación respecto del número de autómatas tiene una componente exponencial debida a las interacciones entre autómatas. Y esto me obliga a ser muy prudente a la hora de elegir una función u otra. Esto me lleva al problema:

¿Existe alguna manera de cuantificar la complejidad para ejecutar una función determinada? Con ejecutar me refiero a encontrar uno o varios valores de la función para un punto de la variable en los reales y con una precisión dada (15 dígitos, por ejemplo)

Lo que me interesa de manera más concreta es poder comparar distintas funciones candidatas para quedarme con la más rápida. Pero también me interesa saber cuanto gano o pierdo con cada elección.

Para poner un ejemplo tonto, sé que $f(x)=x$ debe de ser más simple que $g(x)=x+x^2$, ¿pero cuánto más simple? Este no es el caso, pero si $g(x)$ fuera el candidato más aproximado para solucionar el problema y la lineal fuera una aproximación buena pero peor, ¿cuánto pierdo en rendimiento por elegir $g(x)$?

Es un problema de optimización en donde yo ya sé el grado de aproximación que me dan las funciones pero no sé lo que gano en rendimiento por elegir una peor aproximación.

Perdón por si estoy pasando algo fundamental por alto pero soy un auténtico analfabeto en computación y mi amigo sabe lo suficiente de programación pero tampoco domina los temas de rendimiento y optimización. Así que aquí estoy buscando el consejo de los sabios.

Gracias y un saludo.

[pod]

Re: Complejidad computacional de las operaciones matemáticas.

Hay toda una teoría bastante elaborada para obtener aproximaciones al tiempo de ejecución de un programa en términos del tamaño de su entrada. No obstante, lo que domina la complejidad es el número de veces que se ejecuta la función, no tanto lo que tarda dicha función en ejecutarse. En resumen, si tu tienes que ejecutar un número cuadrático de veces esa función (ese será el caso si las interacciones entre autómatas son uno a uno; hay un número cuadrático de parejas de autómatas, no un número exponencial), entonces el tiempo total de ejecución será el tiempo que tarda la función en ejecutarse una vez (lo cual es un valor constante) multiplicado por algo cuadrático. Asintoticamente, eso se expresa diciendo $o(n^2)$.

Lo que estás intentando hacer tú es reducir la constante. Que está bien, pero con eso conseguirás una ganancia marginal. Lo que realmente te conllevaría una mejora considerable en la complejidad del algoritmo sería reducir la dependencia en el número de autómatas, por ejemplo si bajas a $o( n \log n )$ (esta es la complejidad de los algoritmos de ordenación genéricos) o incluso a $o(n)$.

Si de verdad quieres detenerte a optimizar nimiedades, simplemente cuenta el número de operaciones que la CPU debe hacer. Por ejemplo, la función $f(x) = x$ se traducirá básicamente en copiar un valor y retornarlo (lo cual es extremadamente rápido si usas un ordenador de 64 bits, ya que se puede implementar usando únicamente registros sin tocar la RAM). La función $f(x) = x + x^2$ necesitará copiar el valor a dos registros diferentes (uno para cada término), ejecutar el producto en coma flotante en uno de ellos y finalmente sumar. Eso son cuatro operaciones en vez de una, así que probablemente tardará cuatro veces más, aproximadamente.

Sin embargo, en vez de ponerte a contar operaciones como un idiota, que además tampoco es sencillo porque no sabemos cómo el compilador decidirá implementar cada cosa (hay muchísimos años de investigación en optimización en los compiladores actuales), lo que puedes hacer son experimentos. Ejecuta mil millones de veces cada función con argumentos aleatorios y mira cuanto tarda.

Algo que puedes hacer para ganar velocidad es declarar la función como "inline", por ejemplo

inline double f(double x) { return x + x*x; }

Esto hace que el compilador copie el código de la función cada vez que la llamas, en vez de implementar la llamada a la función como un salto en el código máquina. Con esto, obtendrás un ejecutable más "gordo", pero bastante más rápido porque el compilador puede ahorrarse de meter el código necesario para hacer las llamadas a funciones (que suele involucrar mover valores entre la RAM y los registros, lo cual es bastante más lento). Lo malo es que las funciones "inline" sólo pueden ser usadas en el archivo donde están definidas (porque a ojos del "linker" no existen), o bien tienen que definirse en un archivo .h.

Además, al compilar utiliza la opción -O3, y si tienes una CPU de 64bits, asegúrate que el compilador se aprovecha de ello.

Por último, ¿que quieres decir con lenguajes de linux? Que yo sepa, no hay ningún lenguaje propio de linux. Linux en si está escrito en su mayor parte en C. C++ es una extensión de C. Si no utilizas algunas funciones más abstractas (como métodos virtuales), es esencialmente igual de rápido que C (es la gracia de C++, como se suele decir, sólo pagas por lo que usas).

[guibix]

Re: Complejidad computacional de las operaciones matemáticas.

(ese será el caso si las interacciones entre autómatas son uno a uno; hay un número cuadrático de parejas de autómatas, no un número exponencial), entonces el tiempo total de ejecución será el tiempo que tarda la función en ejecutarse una vez (lo cual es un valor constante) multiplicado por algo cuadrático. Asintoticamente, eso se expresa diciendo $o(n^2)$.

Ya que lo comentas, me justificaré:

Sí, la base de la complejidad es cuadrática. Lo que le da una cierta componente exponencial es la implementación de una especie de atractores generados por las interacciones y que influyen en comportamientos grupales. Es una especie de "truco" en el que los autómatas reconocen identidades grupales. Estos atractores refuerzan (y en parte pueden debilitar) los fenómenos emergentes grupales, facilitando la creación de una o varias "meta-identidades" propias en distintos niveles jerárquicos.

Llevado al extremo, el sistema relacionaría cada posible conjunto de autómatas con todos los demás conjuntos posibles, esto es lo que le daría una complejidad de $o(2^n)$. Evidentemente he impuesto limitaciones que evalúen solo los conjuntos que se crean mediante las interacciones y cada entidad tendrá limitada la interacción con las demás. Solo que cada entidad es un conjunto (incluido los conjuntos de un solo autómata) y cada autómata es una unidad de memoria comunicación y acción de los conjuntos a los que pertenece, empezando por él mismo.

Claro que esto hace que la complejidad crezca con el tiempo sin que aumente el número de autómatas pero a la larga se estabiliza. La idea principal es intentar que el sistema genere contenido informativo simbólico grupal e individual, algo parecido a un lenguaje simbólico que las entidades codificarían con un lenguaje "hablado" como herramienta de comunicación. Para lograrlo trato de conseguir que las entidades reconozcan acciones además de objetos y para ello además de definir estados del sistema también hay que definir las variaciones de los estados como entidades simbólicas propias para poder construir "frases" con sujeto y verbo. Así las entidades relacionan objetos y acciones para "generar conocimiento". Pero esto ya es otra historia .

Sé que parece una tontería usar un sistema así y seguramente lo es (espero que me lo desmontéis para poder ahorrármelo ). El tema es que entre otras cosas precisamente quiero poner a prueba un sistema de complejidad $o(2^n)$ para ver si se pueden conseguir fenómenos emergentes más ricos con el mismo número de autómatas, aunque ello suponga un despilfarro de recursos. Pero intuyo que precisamente aquí sí me puede ser útil optimizar los cálculos. ¿O tampoco ganaría mucho?.

Lo que estás intentando hacer tú es reducir la constante. Que está bien, pero con eso conseguirás una ganancia marginal. Lo que realmente te conllevaría una mejora considerable en la complejidad del algoritmo sería reducir la dependencia en el número de autómatas, por ejemplo si bajas a $o( n \log n )$ (esta es la complejidad de los algoritmos de ordenación genéricos) o incluso a $o(n)$

Entiendo que simplificando la complejidad respecto al número de entidades, se reduce enormemente el cálculo y permite tener una simulación con muchos más elementos en juego. Pero a partir de cierto número grande de elementos, los sistemas de baja complejidad parecen estancarse en reproducir una variedad limitada de fenómenos. Y añadir más elementos y tiempo aumenta la complejidad de los fenómenos emergentes, pero siempre parece que no aumenta en la misma medida su variedad. Hasta que para lograr un poco más de variedad fenomenal, hay que añadir una infinidad de entidades más.

Soy consciente que desde un punto de vista físico, la interacción en un sistema de complejidad $o(n^2)$ debería poder generar la mayoría de los fenómenos emergentes conocidos, eso si tuviéramos suficientes elementos, potencia de cálculo y tiempo (aunque no sé yo si en cuántica esto es así). Pero no puedo evitar ver en muchos fenómenos complejos de nuestra vida humana y animal, esta componente $o(2^n)$ en dónde un fenómeno emergente debe tratarse como una identidad simbólica propia, para poder dar un paso evolutivo de un "nivel superior" del estado del sistema.

A lo mejor estoy patinando y ya que lo he expuesto me gustaría saber si este planteamiento es conceptualmente coherente, ya que soy muy novato en los temas más fundamentales del estudio de la complejidad. No me importa tanto su viabilidad computacional como su validez conceptual. Digamos que mi razonamiento básico es que si la realidad puede tener un solo fenómeno de cierta complejidad (por ejemplo $o(n^2)$), entonces es muy probable que la realidad tenga como mínimo este tipo de complejidad de base. En tal caso, los fenómenos de menor complejidad podrían ser "atajos" de un espacio más complejo.

Sé que quizás suene atrevido e incluso ingenuo (¿lo es?). Aunque solo sea una asunción puede valer la pena ponerla a prueba. Es solo que eso es lo que me cuadra con lo que me parece observar en algunos fenómenos complejos. A lo mejor esto entra en choque directo con algunas bases filosóficas de lo que se supone que un fenómeno emergente es, ya que podría sugerir que la complejidad no surge de la simplicidad, sino que está implícita de una forma potencial, pero también se puede ver como un simple artificio para simplificar funciones biológicas demasiado complejas para ser simuladas (y me quedo tan ancho ).

Si está super demostrado que esto no es o no puede ser así, entonces decidme como entenderlo, que aún no le he dedicado mucho y estoy a tiempo de corregir el rumbo del proyecto. Tampoco me iría mal alguna referencia que pueda consultar respecto a estos temas. Pues tengo algún material, pero se me está quedando obsoleto .

Por último, ¿que quieres decir con lenguajes de linux? Que yo sepa, no hay ningún lenguaje propio de linux. Linux en si está escrito en su mayor parte en C. C++ es una extensión de C. Si no utilizas algunas funciones más abstractas (como métodos virtuales), es esencialmente igual de rápido que C (es la gracia de C++, como se suele decir, sólo pagas por lo que usas).

Supongo que la confusión es mía. El compañero trabaja básicamente en Windows, solo que comentó que en Linux podría haber no sé qué ventajas y que estaba mirandolo, pero nada más. Quizás lo que yo entendí como "lenguaje" se refería a librerías, aplicaciones o maneras de hacerlo, no sé. La verdad es que ni siquiera lo hemos debatido, además soy un gran pagano en la materia. De momento estamos en fase de brainstorming y por el momento el que se rebana el seso soy yo (que por otra parte soy yo el interesado en desarrollarlo ).

Por lo que respecta al resto de tus especificaciones técnicas, creo que lo mejor será transmitirlas a mejor entendedor. Sinceramente, no tengo base para apreciar el valor real de tu aportación en esta parte, aunque estoy convencido de que nos será de gran ayuda.

Llevado por la inercia comentaré algo más que estoy planteando para ver que os parece. He pensado tratar las acciones individuales de los autómatas como un sistema físico en el cual el estado interno de cada autómata y entidad combinado con la información que recibe del entorno, define un especie de campo que determina su acción. De manera análoga al principio de acción, los conceptos creados por el método que he comentado antes, generan potenciales sobre las entidades del entorno identificadas por un autómata y dependen del beneficio/pérdida que puede producir la entidad identificada. Por ejemplo, una entidad identificada como depredador del autómata generará un potencial repulsivo para ese autómata. Y de la misma manera una presa creará un potencial atractivo. Solo que la energía máxima de ese potencial, es la energía de la que dispone el autómata y se extrae de él.

Los detalles no los tengo muy claros, pero lo planteo por la duda que me genera y que me carcome a un nivel más filosófico. Quizás debería abrir un hilo nuevo para ello, pero lo suelto de todos modos porque está directamente relacionado. La duda está en la interpretación de la medida de la variación de la energía cinética para medir la variación de energía potencial. Permitidme exponerlo de esta manera:

Imaginaos conduciendo por una carretera en un caso ideal. Ahora observamos la trayectoria del coche y las fuerzas brutas que aplica a lo largo del recorrido: Las fuerzas normales (las del volante) por un lado y las tangenciales (gas y freno) por el otro lado. Si integramos las fuerzas a lo largo del recorrido obtenemos una especie de potencial en forma de "tubo gan". La pendiente puede interpretarse como la bajada de la energía potencial del combustible/freno por un lado, pero también hay unas "paredes" de potencial. Por efecto de una retro-alimentación negativa en el cerebro del conductor, cuanto más cerca está el coche del borde de la vía, más probable es que una fuerza mayor del volante reoriente el coche hacia el centro de la vía. Esto es lo que representaría las paredes del "tubo gan".

Esto me lleva a pensar que los sistemas vivos actúan de manera análoga a las partículas y sus acciones están relacionadas con atracciones/repulsiones al estilo de campos físicos. Quizás la diferencia principal es que el papel de las partículas transportadoras no transfieren una fuerza sino información. Luego una entidad observadora decodifica la información en base a su estado interno, identificándola como entidad simbólica y asigna una cantidad de energía para generar una fuerza en respuesta a la información. De alguna manera, y a pesar de la complejidad, cuando un ser vivo reacciona a una información aplicando una fuerza, es como si "modelara" un potencial para que las moléculas en sus células musculares caigan en él produciendo una fuerza. Y de algún modo, como ocurre con los campos físicos ese potencial depende directa o indirectamente de la posición de los objetos.

De todos modos, al menos parece algo curioso e interesante. Aunque lo más probable es que sea otra de mis patinadas épicas. Por favor, sed piadosos conmigo, solo soy demasiado entusiasta, curioso e ingenuo para mi nivel .

Como veis, de momento solo es una idea poco desarrollada y no tenía intención de exponer nada hasta tener algo más solido. Pero debido a que Pod me tira de la lengua ya he revelado más de lo que debía (no por secreto, sino por verde), aprovecho para pedir un cable con lo expuesto. Supongo que tarde o temprano apareceré por algún rincón de la web pidiendo cosas extrañas y excéntricas que probablemente estén relacionadas con esto (es que...).

Gracias Pod por tu interés ayuda y paciencia.

Salud!

[pod]

Re: Complejidad computacional de las operaciones matemáticas.

Ya que lo comentas, me justificaré:

Sí, la base de la complejidad es cuadrática. Lo que le da una cierta componente exponencial es la implementación de una especie de atractores generados por las interacciones y que influyen en comportamientos grupales. Es una especie de "truco" en el que los autómatas reconocen identidades grupales. Estos atractores refuerzan (y en parte pueden debilitar) los fenómenos emergentes grupales, facilitando la creación de una o varias "meta-identidades" propias en distintos niveles jerárquicos.

Llevado al extremo, el sistema relacionaría cada posible conjunto de autómatas con todos los demás conjuntos posibles, esto es lo que le daría una complejidad de $o(2^n)$. Evidentemente he impuesto limitaciones que evalúen solo los conjuntos que se crean mediante las interacciones y cada entidad tendrá limitada la interacción con las demás. Solo que cada entidad es un conjunto (incluido los conjuntos de un solo autómata) y cada autómata es una unidad de memoria comunicación y acción de los conjuntos a los que pertenece, empezando por él mismo.

Claro que esto hace que la complejidad crezca con el tiempo sin que aumente el número de autómatas pero a la larga se estabiliza. La idea principal es intentar que el sistema genere contenido informativo simbólico grupal e individual, algo parecido a un lenguaje simbólico que las entidades codificarían con un lenguaje "hablado" como herramienta de comunicación. Para lograrlo trato de conseguir que las entidades reconozcan acciones además de objetos y para ello además de definir estados del sistema también hay que definir las variaciones de los estados como entidades simbólicas propias para poder construir "frases" con sujeto y verbo. Así las entidades relacionan objetos y acciones para "generar conocimiento". Pero esto ya es otra historia .

Sé que parece una tontería usar un sistema así y seguramente lo es (espero que me lo desmontéis para poder ahorrármelo ). El tema es que entre otras cosas precisamente quiero poner a prueba un sistema de complejidad $o(2^n)$ para ver si se pueden conseguir fenómenos emergentes más ricos con el mismo número de autómatas, aunque ello suponga un despilfarro de recursos. Pero intuyo que precisamente aquí sí me puede ser útil optimizar los cálculos. ¿O tampoco ganaría mucho?.

No soy capaz de imaginar ninguna circunstancia física en que haya una interacción que involucre a más de 2, 3 o 4 partículas. De hecho, si no recuerdo mal, por análisis dimensional una QFT con una interacción a 5 o más partículas (es decir, con términos quínticos en el lagrangiano) es no renormalizable.

La gracia de los fenomenos colectivos es, precisamente, que emergen a partir de interacciones realmente simples. Aunque en esto seguramente te podrá ayudar más la gente de materia condensada (física estadística y esas cosas) que uno de altas energías como yo.

Entiendo que simplificando la complejidad respecto al número de entidades, se reduce enormemente el cálculo y permite tener una simulación con muchos más elementos en juego. Pero a partir de cierto número grande de elementos, los sistemas de baja complejidad parecen estancarse en reproducir una variedad limitada de fenómenos. Y añadir más elementos y tiempo aumenta la complejidad de los fenómenos emergentes, pero siempre parece que no aumenta en la misma medida su variedad. Hasta que para lograr un poco más de variedad fenomenal, hay que añadir una infinidad de entidades más.

Soy consciente que desde un punto de vista físico, la interacción en un sistema de complejidad $o(n^2)$ debería poder generar la mayoría de los fenómenos emergentes conocidos, eso si tuviéramos suficientes elementos, potencia de cálculo y tiempo (aunque no sé yo si en cuántica esto es así). Pero no puedo evitar ver en muchos fenómenos complejos de nuestra vida humana y animal, esta componente $o(2^n)$ en dónde un fenómeno emergente debe tratarse como una identidad simbólica propia, para poder dar un paso evolutivo de un "nivel superior" del estado del sistema.

La sociedad, por ejemplo, se suele modelar bastante bien con relaciones binarias unidireccionales (como el "me sigue" en twitter) o binarias (como la relación de "amistad" en facebook). No creo que haya realmente necesidad de establecer una interacción que inherentemente dependa del conjunto de potencias de la población.

A lo mejor estoy patinando y ya que lo he expuesto me gustaría saber si este planteamiento es conceptualmente coherente, ya que soy muy novato en los temas más fundamentales del estudio de la complejidad. No me importa tanto su viabilidad computacional como su validez conceptual. Digamos que mi razonamiento básico es que si la realidad puede tener un solo fenómeno de cierta complejidad (por ejemplo $o(n^2)$), entonces es muy probable que la realidad tenga como mínimo este tipo de complejidad de base. En tal caso, los fenómenos de menor complejidad podrían ser "atajos" de un espacio más complejo.

La complejidad computacional te dice cuando tardas en calcular algo. Tu define un problema, y la teoría te dirá a qué clase de complejidad te enfrentas. Ahora, si ese problema es una aproximación a otro problema más complejo, eso no te lo puede decir hasta que definas ese otro problema.

Sé que quizás suene atrevido e incluso ingenuo (¿lo es?). Aunque solo sea una asunción puede valer la pena ponerla a prueba. Es solo que eso es lo que me cuadra con lo que me parece observar en algunos fenómenos complejos. A lo mejor esto entra en choque directo con algunas bases filosóficas de lo que se supone que un fenómeno emergente es, ya que podría sugerir que la complejidad no surge de la simplicidad, sino que está implícita de una forma potencial, pero también se puede ver como un simple artificio para simplificar funciones biológicas demasiado complejas para ser simuladas (y me quedo tan ancho ).

Hombre, la filosofía no es lo mío. Pero yo diría que si para simular un fenómeno necesitas tener en cuenta la interacción al conjunto de potencias, entonces ya no es un fenómeno emergente. Ya que no está emergiendo de una interacción más simple, sino que lo simulas directamente.

Si está super demostrado que esto no es o no puede ser así, entonces decidme como entenderlo, que aún no le he dedicado mucho y estoy a tiempo de corregir el rumbo del proyecto. Tampoco me iría mal alguna referencia que pueda consultar respecto a estos temas. Pues tengo algún material, pero se me está quedando obsoleto .

Yo, con mi escasez de conocimiento al respecto, y el poco contexto que tengo sobre lo que estás haciendo, tampoco me podría atrever a decir que está "super demostrado".

Supongo que la confusión es mía. El compañero trabaja básicamente en Windows, solo que comentó que en Linux podría haber no sé qué ventajas y que estaba mirandolo, pero nada más. Quizás lo que yo entendí como "lenguaje" se refería a librerías, aplicaciones o maneras de hacerlo, no sé. La verdad es que ni siquiera lo hemos debatido, además soy un gran pagano en la materia. De momento estamos en fase de brainstorming y por el momento el que se rebana el seso soy yo (que por otra parte soy yo el interesado en desarrollarlo ).

El sistema operativo siempre paga su factura, y probablemente el uso de recursos de linux sea infinitamente mejor que el de windows (por lo que probablemente algo ganarás), pero yo diría que utilizando un lenguaje que compila directamente a ensamblador, el rendimiento debería ser esencialmente del mismo orden de magnitud. Me parece mejor opción utilizar técnicas de programación de alto rendimiento (hiperthreading, GPGPU, etc) antes que cambiar de sistema de referencia.

En cualquier caso, si nunca ha programado en entorno POSIX, seguramente tu amigo sacará bastante provecho de ponerse a ello.

Imaginaos conduciendo por una carretera en un caso ideal. Ahora observamos la trayectoria del coche y las fuerzas brutas que aplica a lo largo del recorrido: Las fuerzas normales (las del volante) por un lado y las tangenciales (gas y freno) por el otro lado. Si integramos las fuerzas a lo largo del recorrido obtenemos una especie de potencial en forma de "tubo gan". La pendiente puede interpretarse como la bajada de la energía potencial del combustible/freno por un lado, pero también hay unas "paredes" de potencial. Por efecto de una retro-alimentación negativa en el cerebro del conductor, cuanto más cerca está el coche del borde de la vía, más probable es que una fuerza mayor del volante reoriente el coche hacia el centro de la vía. Esto es lo que representaría las paredes del "tubo gan".

Esto me lleva a pensar que los sistemas vivos actúan de manera análoga a las partículas y sus acciones están relacionadas con atracciones/repulsiones al estilo de campos físicos. Quizás la diferencia principal es que el papel de las partículas transportadoras no transfieren una fuerza sino información. Luego una entidad observadora decodifica la información en base a su estado interno, identificándola como entidad simbólica y asigna una cantidad de energía para generar una fuerza en respuesta a la información. De alguna manera, y a pesar de la complejidad, cuando un ser vivo reacciona a una información aplicando una fuerza, es como si "modelara" un potencial para que las moléculas en sus células musculares caigan en él produciendo una fuerza. Y de algún modo, como ocurre con los campos físicos ese potencial depende directa o indirectamente de la posición de los objetos.

Quizá te resulta interesante buscar información sobre el regulador PID. Es uno de los algoritmos más sencillos y exitosos de la inteligencia artificial, y que muchas veces se utiliza en robots móviles para calcular trayectorias y velocidades.

[guibix]

Re: Complejidad computacional de las operaciones matemáticas.

No soy capaz de imaginar ninguna circunstancia física en que haya una interacción que involucre a más de 2, 3 o 4 partículas. De hecho, si no recuerdo mal, por análisis dimensional una QFT con una interacción a 5 o más partículas (es decir, con términos quínticos en el lagrangiano) es no renormalizable.
La gracia de los fenomenos colectivos es, precisamente, que emergen a partir de interacciones realmente simples. Aunque en esto seguramente te podrá ayudar más la gente de materia condensada (física estadística y esas cosas) que uno de altas energías como yo.

Quizás primero debo aclarar que no pretendo hacer ninguna teoría física ni mucho menos. Lo que pretendo es crear un modelo que permita simular comportamientos sociales de grupo. También he de decir que no solo tengo un solo enfoque, sino varios. Pero en todos los casos necesito algo que permita definir la estructura de los conjuntos sociales. Tengo unos modelos bastante simples nada operativos, pero que sirven para marcar las directrices a seguir para complicar más los problemas. Para ilustrarlo, voy a poner un par de ejemplos distintos que son el máximo ideal a lograr y que aún están muy verdes en muchos aspectos. Pero los comento de todos modos para mostrar parte del planteamiento:

-El primer caso podría ser la inteligencia artificial para un juego de estrategia militar. Tengo que decir que soy 99% pacifista, pero en mi 1% beligerante, tengo gran debilidad por el estudio de la historia militar y de las claves, complejidades y teoría de la estrategia, la táctica y la logística. Es un enfoque totalmente antropológico y lúdico para la posible creación de un vídeo-juego de estrategia en tiempo real y para el estudio de comportamietos cooperativos y competitivos. Tratándose de un tema tan delicado como la guerra, quiero dejar claro que no daría nunca ningún uso que pudiera ser dañino para nadie. Mi interés es meramente lúdico y académico.

Dicho esto y siguiendo con el tema: En la realidad los ejércitos se organizan en una estructura piramidal casi fractal. Cada soldado pertenece a una escuadra, un conjunto de escuadras forman un pelotón, varios pelotones forman una compañía y varias compañías un batallón. Así subiendo toda la jerarquía (es un poco más complejo pero esta es la idea). En este caso los grupos y sub-grupos están predeterminados, así como algunas doctrinas militares y un sinfín de consideraciones tácticas, estratégicas y logísticas que no vienen al caso (aunque es la parte que más trabajo me da ).

Al final es la acción de los individuos lo que determina el resultado, pero se tiene que evaluar la situación en todos los niveles jerárquicos para tomar una buena decisión. Cada jefe de escuadra tiene una orden y necesita información de la situación de su escuadra, de las colindantes y de las fuerzas enemigas, así como temas del terreno y demás, para evaluar la situación y poder dar las sub-órdenes más adecuadas y también para poder informar a su superior. Cada jefe en cada nivel pasa por el mismo proceso pero a una escala creciente, pero todos y cada uno tiene un número reducido de unidades a manejar y coordinar.

En este caso no pretendo que se formen grupos, pues ya están pre-asignados y la complejidad adicional que generan es mínima. La idea es primero crear un "ejército" básico con poca variedad y efectividad (de baja tecnología). Luego se enfrentarían copias entre ellas o contra un jugador humano, en distintos terrenos y situaciones, para que evolucionen por distintos caminos. Aquí el algoritmo de aprendizaje se basa una combinación inter-conectada de redes neuronales de propagación inversa, redes de otros tipos y diagramas de flujo. La supervisión del aprendizaje es automática y se basa en los costes/beneficios resultantes de aplicar una determinada acción. Los diagramas de flujo también estás conectados por pesos sujetos al aprendizaje. Cada individuo tiene esto en su cerebro y además todos están conectados por la cadena de comunicación formando una sola red. Con algunos ajustes adicionales para esta red, podría conseguir que todo el ejército aprenda y mejore luchando como una sola unidad combinando sus partes y cada parte haría lo mismo en su escala.

Cuando el aprendizaje llegue a un mínimo local o global se pueden mejorar ligeramente las armas, armaduras, transporte, etc. para ver si alguno de los ejércitos es capaz de sacar un provecho táctico reajustando las doctrinas. Las doctrinas son un mismo diagrama de flujo para cualquier tamaño, estructura, situación y acción. Lo que las hace distintas son los pesos que conectan el diagrama y que algunas partes del diagrama son operadores de lógica difusa con una entrada y múltiples salidas ponderadas, los parámetros de los cuales también están sujetos al aprendizaje. También estoy mirando de que la estructura jerárquica pueda modificarse para adaptarse a nuevas necesidades tácticas.

Como ves, en este caso los fenómenos emergentes que busco son las formas "creativas" que algunas unidades podrían desarrollar para maximizar el ratio beneficio/coste en ciertas situaciones antes desventajosas. Podría hacer lo mismo sin todo esto, pero el único comportamiento al que podría aspirar en conseguir de manera emergente, sería una doctrina marcial al más puro estilo colmena (como las hormigas, termitas y abejas). Este logro por si mismo ya sería más que deseable, pero se puede tratar como un caso particular en el que todos los individuos, aunque puedan tener atributos distintos, forman un solo grupo.

-El segundo caso sería el de varios grupos de individuos (tribus), en dónde existen distintas jerarquías. Por ejemplo están las jerarquías familiares con distintos niveles de parentesco. También están las demás relaciones como grupos de caza y recolección. En este caso se puede empezar la simulación solo con individuos sin nada más. La idea es que si dos individuos interaccionan muy a menudo (por ejemplo una pareja sexual), se puede formar el concepto de "pareja". Si la pareja tiene hijos se puede formar el concepto "familia" además de la pareja. Esto sirve para que los individuos identifiquen y separen los conceptos para multitud de temas prácticos. Sería una versión más compleja que la anterior con más roles que los estrictamente militares y dejando que las jerarquías y grupos se generen a base del aprendizaje colectivo adquirido con la interacción mutua.

El objetivo aquí es el mismo que el del caso anterior y conseguir que uno o más grupos grupo ("tribus") generen especializaciones y mejoren las técnicas de supervivencia colectiva. Además de comunicarse con un limitado lenguaje hecho por ellos mismos que ya comentaré más adelante. Aquí es donde la complejidad puede crecer exponencialmente durante cierto período y luego se estabiliza por una serie de límites pre-establecidos. Pero este crecimiento no solo se debe a un gran número de grupos diferentes, sino que cada grupo crea su conocimiento y su propia conducta en relación a los otros grupos conocidos. Y los otros grupos son vistos para el grupo "observador" con una visión subjetiva basada en sus observaciones y no en como se hayan definido a si mismos. O sea que todos los grupos que se auto-definen como tal, definen el resto de objetos/grupos con los que topan y solo con los elementos que pueden observar y que puedan usar para definir grupos y conjuntos en su propio "bestiario". Muchos de estos grupos no se han auto-definido como tal, sino que "alguien" los ha definido. Esto intenta emular como distintos individuos, grupos, culturas, etc. pueden definir las mismas cosas de manera diferente.

En todos los casos estoy intentando crear un código genético para describir tanto los atributos como las estructuras cerebrales de los individuos. Con él podría aplicar algoritmos genéticos de mutación y de cruce para hacer experimentos de selección genética de todo tipo (¡Al fin podré tener mi legión de una raza virtual de orcos criados por mi! Después de todo mi 1% beligerante puede ser más peligroso de lo que parecía )

Soy consciente de que todo esto se podría tratar con un grafo en el que los distintos niveles de relación que pueda haber entre dos individuos se podrían representar con distintos tipos de conexión binaria, limitando el problema al tipo $o(n^2)$. Pero esto me obliga a aumentar considerablemente las capacidades cognitivas de los cerebros individuales hasta un punto intratable. Al fin y al cabo solo se trata de un truco para almacenar y procesar la mayor parte de información colectiva. Así la información no tiene que estar copiada en la memoria de todos y cada uno de los individuos, sino que tienen un "manual/diccionario" que consultan cuando lo necesitan. Y ese manual puede evolucionar según la experiencia colectiva sin que todos los individuos tengan que tener la experiencia ni tengan que memorizarlo. Además estos "conceptos" se aplican en forma de esos "pseudo-campos" de los que hablé, aplicando "atractores" y "deflectores" sobre objetos, grupos y sobre el terreno para hallar las trayectorias óptimas para cada situación y objetivo. Otra cosa necesaria para ello es que los individuos y los grupos tengan la capacidad de crear y cambiar objetivos en función de las necesidades. Pero esto es otra larga historia, así como lo es la evaluación de rutas que minimicen la distancia de los caminos en función de distintos criterios (el más directo, el menos pendiente, el más a cubierto) e incluso con ponderaciones de combinaciones de los criterios .

Hombre, la filosofía no es lo mío. Pero yo diría que si para simular un fenómeno necesitas tener en cuenta la interacción al conjunto de potencias, entonces ya no es un fenómeno emergente. Ya que no está emergiendo de una interacción más simple, sino que lo simulas directamente.

La justificación "filosófica" es en realidad muy simple: Si creo un simulador de física atómica y molecular con gran número de partículas, gran potencia computacional y mucho tiempo, a lo sumo conseguiré que emerja alguna molécula orgánica y poco más. Pero difícilmente surgirá nada parecido al ARN o a un atisbo de ser vivo (aunque tampoco creo que sea imposible). Para simular vida artificial, no hay más remedio que considerar ciertos fenómenos emergentes muy complejos como unidad básica e indivisible. Con unas reglas simples que "fuerzan" su comportamiento para aparentar algo que realmente es demasiado complejo para ser tratado computacionalmente, pero que cumplen algunas de sus funciones básicas. Con cuatro sensores, cuatro motores, cuatro neuronas artificiales, cuatro algoritmos y una generosa interconexión, ya puedes simular algo parecido a una hormiga. Pero el precio filosófico a pagar es que te cargas a la torera su auténtica complejidad de miles de millones de años de evolución emergente y la mayoría de procesos físicos que llevan a ello, para tener un modelo elegante que tenga plumas y pico de pato, camine como un pato y grazne como un pato, pero que está algo lejos de ser un auténtico pato .

Digamos que me sirvo por un lado de la ambigüedad que existe en la definición de lo que es una "unidad básica" en términos de vida artificial. Ya que en la vida real a veces es difícil y arbitrario decidir qué es un individuo y qué un grupo de individuos muy interdependientes. Una colonia de hormigas puede llegarse a considerar una especie de "ameba" individual con una estructura e interconexión interna, que tiene exactamente las mismas funciones que un ser vivo completo. Se reproduce y puede morir entero si algunas de sus partes vitales se disgregan. Pero como sus partes tienen una gran capacidad regenerativa y adaptativa cuando sufre bajas o disgregaciones, podría también considerarse un grupo de individuos con gran interdependencia, pero no total.

Quizás una buena manera de definir el individuo biológico sea precisamente aquél sistema que lo dividas como lo dividas, al menos todas las partes menos una colapsan todos sus subsistemas hasta el nivel molecular (mueren con una única parte que puede sobrevivir mutilada). Pero multitud de sistemas vivos considerados individuos no cumplen esta definición, como muchos vegetales y hongos. ¿Debo considerar estos casos como colonias de células parientes que al dividirse pueden sobrevivir si las colonias restantes tienen una masa crítica, recursos y funciones suficientes para regenerarse, de la misma manera que ocurre con muchas colonias animales? ¿O simplemente digo "árbol", "seta" ? (pregunta sarcástico-retórica )

Por otro lado también quiero simular el concepto humano de almacenar información de manera externa a los individuos para ahorrarles memoria individual. La definición, identificación y clasificación de los grupos y conjuntos con cierta identidad propia es vital para generar "conocimiento escrito" (o un atisbo ligeramente parecido a un lenguaje). Además cada conjunto se relaciona con el espectro de comportamientos y acciones colectivas. Así como comportamientos que "reivindican" la identidad del grupo (Por ej: todos los de la tribu se pintan del mismo color).

"Uno sabe que la tribu de los "roe-huesos" se pintan de rojo, siempre van juntos y se comen a los de nuestra tribu: son "malos" y peligrosos y nunca se ha podido hacer nada efectivo contra ellos. Veo un "roe-huesos": Habrá más: malo para mi y para los "nuestros": 1-Huye, 2-Busca y avisa a los "nuestros", 3-huid todos. Los "lanza-piedras" son peligrosos, siempre van solos, se pintan de azul y se les puede ganar si somos más de 3 para conseguir comida. Veo un Lanza-piedras: ¿Somos más de 3?- No: 1-Huye, 2-Busca y avisa a los "nuestros". Encuentro algunos de los nuestros: ¿Somos más de 3?- Sí : A por él!!"

Esto no es más que una burda descripción teatral de estos procesos que aún están en verde desarrollo y con un modelo mucho más simple que puede extenderse a más y más complejidad semántica. La idea es que las formas/colores sean los adjetivos. Los conjuntos son nombres. Las acciones son los verbos y forman adjetivos atribuibles a aquello que realiza la acción, así como adverbios circunstanciales. Con algunas formas gramaticales más y una base sintáctica simple, se pueden construir frases para la comunicación de hechos e intenciones, así como en forma de manual supervivencia para identificar las situaciones y seguir las instrucciones más apropiadas.

La sociedad, por ejemplo, se suele modelar bastante bien con relaciones binarias unidireccionales (como el "me sigue" en twitter) o binarias (como la relación de "amistad" en facebook). No creo que haya realmente necesidad de establecer una interacción que inherentemente dependa del conjunto de potencias de la población.

Bueno, una parte quizás ya te la haya contestado, pero ya que pones el ejemplo de facebook, hay cantidad de grupos, entidades, clubes y demás que se "generan" de las interacciones entre individuos. Incluso muchos de ellos crean un perfil personal en lugar de una página de grupo, con el cual tienes una relación de "amistad".

Luego, como ya dije, sí que podríamos tener un grafo con todas las interconexiones entre individuos e incluso con todo tipo de relaciones binarias añadidas entre ellos. Incluso creo que modelado así, representa la mayor parte de la información de un sistema real y sus relaciones. Pero solo es una representación que no puede "generar" enlaces de cualquier manera. Los motivos por los que de crean enlaces no quedan representados cuando son precisamente la causa, ni tampoco dercribe el proceso de formación de un grupo. Voy a poner un ejemplo:

Yo mismo me hice un grafo con una aplicación de facebook con las relaciones de todas mis amistades. Es realmente interesante y divertido ver los grupos que se forman. En mi caso hay un gran grupo muy interconectado entre si. Es toda la gente de mi "colla castellera" "Sagas d'Osona". Lo bueno es que la mayoría no nos conocemos demasiado entre nosotros y muchos no somos del mismo grupo por ser amigos, sino que somos amigos por ser del mismo grupo. Formamos una misma "tribu" con nuestro color calabaza y todo tipo de simbologías, lemas identitarios y nuestros ensayos, actuaciones y demás actos sociales. Para mi y muchos "castellers" crear un "castell" es un acto de gran trascendencia simbólica que además de reafirmar una identidad propia como grupo, intenta representar un conjunto de valores sobre la conducta grupal. Y al mismo tiempo tiene una manifestación física en forma de "castell" ¿No es acaso un "castell" un fenómeno emergente, al mismo tiempo pre-diseñado e intencionado, una especie de molécula humana con una energía superior que decae al cabo de un rato deshaciendo sus enlaces? ¿O es la vida de un gigante que crece, llega a su clímax y decae en pocos segundos? ¿Acaso no es un fenómeno emergente nuestras propias computadoras y sus software pre-diseñado e intencionado del que surgen nuevos fenómenos emergentes?

Considerad la mayor parte de esto último como el fruto de mi ánimo poético hacia la vida, pero también me gustaría generar alguna reflexión sobre la diferencia que existe entre entidades individuales y grupales. Quizás la única diferenciación objetiva posible sea el grado de interconección, interdependencia y parentesco de sus sub-sistemas, por lo demás, puede existir un gran franja borrosa entre individuo y grupo. Además no tiene porqué existir el parentesco genético, pues incontables simbiontes han co-evolucionado con nosotros (y dentro nuestro) sin tener parentesco nada cercano. Nosotros como individuos no seríamos tal sin nuestra flora intestinal y demás bacterias y hongos simbiontes. De echo, el número de individuos simbiontes de nuestro cuerpo supera al número de personas en la Tierra.

La complejidad computacional te dice cuando tardas en calcular algo. Tu define un problema, y la teoría te dirá a qué clase de complejidad te enfrentas. Ahora, si ese problema es una aproximación a otro problema más complejo, eso no te lo puede decir hasta que definas ese otro problema.

Bueno, como ves la cosa se me ha desbordado mucho más allá del tema del hilo. Recórtalo y cámbialo si lo crees necesario. Pero al menos he intentado justificar que por lo menos la complejidad es de base $o(n^2)$ y puede tener una componente exponencial limitada. Llevado al caso extremo, cada conjunto de cosas tendría una relación real (la que define el conjunto) y las relaciones subjetivas del mismo conjunto creadas por las observaciones de cada uno conjuntos posibles restantes. No digo que este caso tenga ningún interés especial ni sentido alguno (no todos los conjuntos posibles pueden "pensar" e interactuar sobre todos los conjuntos posibles), pero es el límite posible para el modelo en donde la complejidad es de tipo $o(2^n).$ Estrictamente creo que sería $o(2^{2n}),$ pero supongo que es el mismo tipo de complejidad.

También me queda una duda teórica: ¿En este supuesto caso extremo de complejidad $o(2^n),$ la optimización de las funciones se vuelve realmente una ganancia importante o solo es menos marginal?

Yo, con mi escasez de conocimiento al respecto, y el poco contexto que tengo sobre lo que estás haciendo, tampoco me podría atrever a decir que está "super demostrado".

Esta solo era una manera cómico-dramática de decir que si existe algún error de fundamentos básicos, que pase por alto y que "derrumbe" mis planteamientos, prefiero saberlo ahora que solo tengo la estructura para llenar de detalles y lo puedo cambiar sin mucho trabajo.

El sistema operativo siempre paga su factura, y probablemente el uso de recursos de linux sea infinitamente mejor que el de windows (por lo que probablemente algo ganarás), pero yo diría que utilizando un lenguaje que compila directamente a ensamblador, el rendimiento debería ser esencialmente del mismo orden de magnitud. Me parece mejor opción utilizar técnicas de programación de alto rendimiento (hiperthreading, GPGPU, etc) antes que cambiar de sistema de referencia.

En cualquier caso, si nunca ha programado en entorno POSIX, seguramente tu amigo sacará bastante provecho de ponerse a ello.

Tomo nota de esto y lo comentaré y lo investigaré.

Quizá te resulta interesante buscar información sobre el regulador PID. Es uno de los algoritmos más sencillos y exitosos de la inteligencia artificial, y que muchas veces se utiliza en robots móviles para calcular trayectorias y velocidades.

Por lo que he podido ver, parece que es lo mismo que se usa en muchas redes neuronales de señal continua con retro-alimentación negativa. Las redes hopfield usan esto o algo muy parecido para auto-organizar la red hacia un mínimo de energía. Dónde más he tratado con algo así es en la aplicación de vida artificial evolutiva Framesticks. Y sí, esto voy a usarlo en muchas de las partes de la red como regulador de muchos procesos por su gran capacidad estabilizadora.

Como ves tengo muchos frentes abiertos e ideas dispersas que debo ir acotando poco a poco. Evidentemente iré eliminando y añadiendo cosas a medida que concrete más detalles. Mi intención era mostrar todo este trabajos pero no aún, tengo demasiados cabos sueltos. Claro que en este hilo ya he revelado gran parte de mis ideas y he abierto la veda para tratar muchas de ellas. Pero no hace falta discutirlo todo en este hilo. Digamos que todo lo que he dicho es para justificar los temas de la complejidad. Se puede dividir el hilo para tratar los temas que no estén directamente relacionados con él o haced lo que creéis conveniente.

Gracias pod por tu infinita paciencia con mis excentricidades .

Saludos!

[guibix]

Re: Complejidad computacional de las operaciones matemáticas.

Bueno, creo que el tema se me ha ido de las manos, jeje. Dejemos el debate para otro hilo y me centraré en el tema.

¿Independientemente de para qué quiero una complejidad $o(2^n),$ es útil optimizar las funciones o sigue siendo una ganancia marginal?


Por otra parte, tengo entendido que la resolución computacional de sistemas cuánticos es precisamente de una complejidad tipo $o(2^n)$.

¿Esto es así, o solo ocurre en sistemas entrelazados y/u otros casos especiales?

[pod]

Re: Complejidad computacional de las operaciones matemáticas.

Bueno, creo que el tema se me ha ido de las manos, jeje. Dejemos el debate para otro hilo y me centraré en el tema.

¿Independientemente de para qué quiero una complejidad $o(2^n),$ es útil optimizar las funciones o sigue siendo una ganancia marginal?

Hombre, el tiempo total de ejecución, simplificando, será el tiempo que tarda la ejecución de la función multiplicado por el número de veces que se llama a esa función. Si consigues que la función se ejecute en la mitad de tiempo, todo el algoritmo se ejecutará en la mitad de tiempo.

El problema con la complejidad exponencial viene al cambiar el tamaño del sistema que estás estudiando. Si la complejidad es $2^n$ y aumentas el tamaño en sólo una unidad, entonces estás duplicando el tiempo de ejecución. Aproximadamente un orden de mangitud más por cada tres elementos que añadas al sistema. No hay optimización de la función ni ley de Moore que te permita seguir un crecimiento exponencial de esa forma.

Pero si te fijas en un tamaño del sistema concreto, y no lo cambias, por supuesto cualquier optimización que hagas se traduce directa y linealmente en una mejora del tiempo total.

Por otra parte, tengo entendido que la resolución computacional de sistemas cuánticos es precisamente de una complejidad tipo $o(2^n)$.

¿Esto es así, o solo ocurre en sistemas entrelazados y/u otros casos especiales?

En esto no puedo ayudarte. Mis conocimientos de computación cuántica son limitados.

[guibix]

Re: Complejidad computacional de las operaciones matemáticas.

Vale, gracias pod. Para otros detalles menos relacionados con el tema, ya abriré otro hilo.

En esto no puedo ayudarte. Mis conocimientos de computación cuántica son limitados.

Bueno, más bien no me refiero a la computación cuántica, sino a la simulación por computación convencional de sistemas cuánticos. Creo recordar que uno de los problemas para simular sistemas grandes (cuánticamente hablando) es precisamente la complejidad exponencial al añadir elementos a la simulación. Y también por esto (entre otras cosas) se busca la computación cuántica, porqué puede simular sistemas cuánticos complejos "directamente". Lo que no sé es si esto es generalizable para todo tipo de sistemas o solo ocurre en algunos casos especiales.

Gracias de nuevo y un saludo.

[pod]

Re: Complejidad computacional de las operaciones matemáticas.

Bueno, más bien no me refiero a la computación cuántica, sino a la simulación por computación convencional de sistemas cuánticos. Creo recordar que uno de los problemas para simular sistemas grandes (cuánticamente hablando) es precisamente la complejidad exponencial al añadir elementos a la simulación. Y también por esto (entre otras cosas) se busca la computación cuántica, porqué puede simular sistemas cuánticos complejos "directamente". Lo que no sé es si esto es generalizable para todo tipo de sistemas o solo ocurre en algunos casos especiales.

Gracias de nuevo y un saludo.

Hoy en día se dice que hay tres tipos de físicos: teóricos, experimentales y computacionales. Yo siempre he estado sobre todo en el primer grupo, y de los otros dos sólo he rascado la superfície. He pgoramado (y programo) mucho en la vida pero, por desgracia, nunca relacionado con la física computacional. Es un campo extraordinariamente amplio.

Lo que sí te puedo indicar es que hay simulaciones de sistemas cuánticos de diversos tipos. Lo más sencillo puede ser la resolución de ecuaciones diferenciales, y en eso la cuántica no es diferente a cualquier disciplina física o matemática. Hay métodos exactos y aproximados para la resolución de las ecuaciones de Schödinger, Dirac y compañía para muchos cuerpos. Por ejemplo, el inolvidable método de Hartree-Fock.

Lo de mayor complejidad computacional a lo mejor (lo propongo con todas las reservas de no ser un experto en el tema) se refiere a la teoría cuántica de campos en el retículo. Es decir, hacer una aproximación de espacio-tiempo discreto para hacer cálculos en QFT (por ejemplo, QED o QCD).