Algorítmica y complejidad computacional. Enlaces varios, diciembre 2014.

1. Computational Protein Design Using AND/OR Branch-and-Bound Search.

2. The Nonequilibrium Many-Body Problem as a paradigm for extreme data science.

3. TOWARDS A BROADER VIEW OF THEORY OF COMPUTING –
PART 1. El autor es Narendra Kamarkar inventor del primer algoritmo de tiempo polinómico para problemas de programación lineal.

4. Uniformity is weaker than semi-uniformity for some
membrane systems.

Un resultado sobre membrane systems, modelos de computación basados en células. Ver también.  

5. La solución a un problema añejo de complejidad computacional. Se pasa de una cota superior doblemente exponencial (¿ en uso de espacio ?) a otra que lo situa en la clase pspace-complete.

REACHABILITY IN TWO-DIMENSIONAL VECTOR ADDITION SYSTEMS WITH STATES IS PSPACE-COMPLETE

Abstract. Determining the complexity of the reachability problem for vector addition systems with states (VASS) is a long-standing open problem in computer science. Long known to be decidable, the problem to this day lacks any complexity upper bound whatsoever. In this paper, reachability for two-dimensional VASS is shown PSPACE-complete. This improves on a previously known doubly exponential time bound established by Howell, Rosier, Huynh and Yen in 1986. The coverability and boundedness problems are also noted to be PSPACE-complete. In addition, some complexity results are given for the reachability problem in two-dimensional VASS and in integer VASS when numbers are encoded in unary.  

En esta presentación se ve claramente en que consiste el problema para el caso bidimensional.

Las VASS son computacionalmente equivalentes a las Redes de Petri que me interesaron hace años.

6. Go (el juego) versus redes neuronales.

Para los computadores el ajedrez ya está dominado. Pruebe el lector a intentar ganar a cualquier programa de ordenador en su nivel máximo y sabrá de lo que hablo.

Sin embargo el Go otro juego de tablero aparentemente similar es todavía un reto para el ordenador. En este artículo revisan los algoritmos de tipo redes neuronales diseñados para jugar  este juego y explican porqué es tan complicado ganarlos.

Teaching Deep Convolutional Neural Networks to Play Go.

7. Los grafos de De Bruijn y su uso en compresión de datos genéticos.

Los grafos de De Bruijn son una de las familias paramétricas de grafos.

Título. Compression of high throughput sequencing data with
probabilistic de Bruijn graph

Abstract.

Motivation: Data volumes generated by next-generation sequencing technologies is now a major concern, both for storage and transmission. This triggered the need for more efficient methods than general purpose compression tools, such as the widely used gzip. Most reference-free tools developed for NGS data compression still use general text compression methods and fail to benefit from algorithms already designed specifically for the analysis of NGS data. The goal of our new method Leon is to achieve compression of DNA sequences of high throughput sequencing data, without the need of a reference genome, with techniques derived from existing assembly principles, that possibly better exploit NGS data redundancy.

Results: We propose a novel method, implemented in the software Leon, for compression of DNA sequences issued from high throughput sequencing technologies. This is a lossless method that does not need a reference genome. Instead, a reference is built de novo from the set of reads as a probabilistic de Bruijn Graph, stored in a Bloom filter. Each read is encoded as a path in this graph, storing only an anchoring kmer and a list of bifurcations indicating which path to follow in the graph. This new method will allow to have compressed read files that also already contain its underlying de Bruijn Graph, thus directly re-usable by many tools relying on this structure. Leon achieved encoding of a C.

¡¡ Muy interesante por su relación indirecta con los resultados de la patente !!

8. Una nueva clase de complejidad en computación cuántica.

Modificaciones en algunos aspectos de la mecánica cuántica (no linealidad, no unitariedad etc…) modifican el “poder computacional ” de la computación cuántica.

Hasta la publicación de este artículo todas las modificaciones (no realistas) generaban modelos muy potentes, casi con superpoderes, capaces de resolver problemas NP-duros en tiempo polinómico.

En el artículo enlazado presentan una modificación de la mecánica cuántica (medir el estado sin que éste colapse, modificación que tampoco es realistas, por sus consecuencias) que está asociada a un modelo estrictamente más poderoso (en términos computacionales) que BQP pero que todavía no contiene a NP. Ambas inclusiones, oraculares.

Te interesará si te interesa la computación cuántica y sus límites.

(Actualización 31 de diciembre 2014. De publicación posterior pero relacionado:

Computation in generalised probabilistic theories

From the general difficulty of simulating quantum systems using classical systems, and in particular the existence of an efficient quantum algorithm for factoring, it is likely that quantum computation is intrinsically more powerful than classical computation. At present, the best upper bound known for the power of quantum computation is that BQP ⊆ AWPP, where AWPP is a classical complexity class (known to be included in PP, hence PSPACE). This work investigates limits on computational power that are imposed by simple physical, or information theoretic, principles. To this end, we define a circuit-based model of computation in a class of operationally-defined theories more general than quantum theory, and ask: what is the minimal set of physical assumptions under which the above inclusions still hold? We show that given only an assumption of tomographic locality (roughly, that multipartite states and transformations can be characterised by local measurements), efficient computations are contained in AWPP. This inclusion still holds even without assuming a basic notion of causality (where the notion is, roughly, that probabilities for outcomes cannot depend on future measurement choices). Following Aaronson, we extend the computational model by allowing post-selection on measurement outcomes. Aaronson showed that the corresponding quantum complexity class, PostBQP, is equal to PP. Given only the assumption of tomographic locality, the inclusion in PP still holds for post-selected computation in general theories. Hence in a world with post-selection, quantum theory is optimal for computation in the space of all operational theories. We then consider whether one can obtain relativised complexity results for general theories. It is not obvious how to define a sensible notion of a computational oracle in the general framework that reduces to the standard notion in the quantum case. Nevertheless, it is possible to define computation relative to a ‘classical oracle’. Then, we show there exists a classical oracle relative to which efficient computation in any theory satisfying the causality assumption does not include NP. This provides some degree of evidence that NPcomplete problems cannot be solved efficiently in any theory satisfying tomographic locality and causality.

Fin de actualización).

9. Un blog sobre neurociencia computacional.

Las neurociencias me interesaron hace (¿ más de 20 años ?) y leí bastante sobre ello. Finalmente perdí el interés por considerar que el estado del arte era todavía inmaduro y por lo tanto sus resultados proporcionaban un conocimiento poco sólido. Desde entonces he regresado a ellas puntualmente.

Recientemente me han vuelto a interesar y estoy dedicándoles algo de  tiempo. La impresión, de momento, es la misma. Entre los especialistas en neurociencias no existe ya un modelo sino una descripción sencilla del cerebro, sólo narraciones interminables sobre su anatomía, neuro-química, fisiología etc… con muchos nombres imposibles de memorizar. Esto es típico de las ciencias inmaduras: no se conocen las teclas importantes de la materia y en las narraciones aparecen juntos grano y paja, árbol  y bosque, piel de oso y cazador y un largo etc…todos juntos y mezclados, sin orden ni concierto, como en las buenas sopas caseras, no vaya a ser que nos dejemos algún detalle importante en el tintero.

Cuando especialistas de otros campos (por ejemplo de las ciencias de la computación) miran a este complejo objeto, los modelos que proponen (por ejemplo redes neuronales) no son,  en mi modesta opinión, del todo realistas. Se mueven a un nivel de abstracción demasiado elevado (lo cierto es que tengo pendiente leer sobre el tema en breve y es posible que cambie de opinión;  una entrada relevante en wikipedia, sobre el conexionismo y un extracto relevante también: The neural network branch of connectionism suggests that the study of mental activity is really the study of neural systems. This links connectionism to neuroscience, and models involve varying degrees of biological realism. Connectionist work in general need not be biologically realistic, but some neural network researchers, computational neuroscientists, try to model the biological aspects of natural neural systems very closely in so-called “neuromorphic networks“. Many authors find the clear link between neural activity and cognition to be an appealing aspect of connectionism.).

Finalmente no existe un enfoque teórico claro sobre la conexión entre cerebro (con semántica celular, y por lo tanto biológica) y mente (con semántica en base a estados mentales de seres humanos,es decir psicológica). Mucha casuística  sobre funcionamiento anormal (enfermedades mentales y otro  tipo de fenómenos) causados por alteraciones anatómicas, neuroquímicas etc…pero que no permite de momento llegar a conclusiones firmes: muchas pueden ser las causas de que un coche no arranque. Damasio es un autor (seguramente entre muchos otros) que ha realizado esfuerzos en este sentido, dentro del campo de la neurociencias materiales. Pero si no existe una teoría satisfactoria de ninguno de los dos niveles, difícilmente podrá haber una buena de la conexión entre los dos…(Actualización 28 de diciembre. De interés sobre esto este artículo dónde presentan un modelo que dicen ser satisfactorio de la visiónAlthough there has been enormous experimental and theoretical progress on understanding brain or mind in the fields of neuroscience and psychology, establishing a mechanistic link between them has been very difficult, if only because these two levels of description often seem to be so different. Yet establishing a link between brain and mind is crucial in any mature theory of how a brain or mind works. Without such a link, the mechanisms of the brain have no functional significance, and the functions of behavior have no mechanistic explanation. Throughout the history of psychology and neuroscience, some researchers have tried to establish such a link by the use of metaphors or the application of classical concepts to the brain. These have included hydraulic systems, digital computers, holograms, control theory circuits, and Bayesian networks, to name a few. None of these approaches has managed to explicate the unique design principles and mechanisms that  characterize biological intelligence. The present chapter summarizes aspects of a rapidly developing theory of neocortex that links explanations of behavioral functions to underlying biophysical,neurophysiological, and anatomical mechanisms. Progress has been particularly rapid towards understanding how the laminar circuits of visual cortex. This progress illustrates the introduction of qualitatively new computational paradigms, as might have been expected, given how long these problems have remained unsolved. Estos paradigmas son complementary computing y laminar computing. Ignoro si los neurocientíficos comparten el optimismo de este autor, uno de los pioneros  de las redes neuronales pero que aparentemente huye de la pura abstracción. Fin actualización).

Este campo genera también mucha noticia disconexa sobre novedades de investigación interesantes pero que finalmente no superan, para el lector, la categoría de anécdota (un ejemplo, este interesante blog de la plataforma de yahoo). Muchas veces la neurociencia, o la manera en la que ésta se difunde a través de los medios parece una combinación de circo y zoo, dónde lo exótico y lo monstruoso encuentran su lugar.

Pese a los grandes avances que sin duda se han ido  experimentando en las últimas décadas, en esta Ciencia todavía no se ha vivido un momento de ¡¡ EUREKA !! que nos haga ver la materia con total o al  menos parcial claridad. Cuando esto suceda, es de esperar que los expertos dejen de una vez de iniciar sus artículos con la coletilla clásica tantas veces repetida: “el cerebro es el objeto más complejo del Universo etc…”.

En fin, con este renovado interés en esta materia he buscado algunos blogs interesantes sobre neurociencias y he encontrado éste al que hemos enlazado  que se mueve entre ésta materia y las ciencias computacionales.  Se lleva editando desde 2008, pero no se actualiza muy a menudo.

[Nota al margen. Es posible que desde la psiquiatría, que es neurociencia aplicada, todo esto se vea de otra manera. El otro día un experto en este campo, en un contexto no de consulta sino de evento festivo, ante mi pregunta sobre  si su campo era cada vez más parecido a cualquier otro campo de la medicina, con una práctica basada en el par diagnóstico-estudio de sensibilidad a fármacos-receta para comprar medicación, me confirmaba que así era y que en general la medicación era “probablemente aproximadamente eficiente” (más sobre este adjetivo en el siguiente punto).

Yo personalmente sigo siendo escéptico y nunca tomaría (nunca he tomado) este tipo de medicación (y creo  que tampoco lo necesito de momento🙂; en realidad, en general, salvo cuestión de vida o muerte, no tomo medicación de ningún tipo, posición radical no racionalizada que quizás debería de revisar). No digo que no funcione a corto plazo, pero estás interviniendo en un objeto que no conoces bien y no puedes calcular todas las consecuencias de estas intervenciones a un plazo más largo. Salvando las distancias, en su momento las lobotomías parecían perfectamente aceptables e incluso se concedió un Premio Nobel por su descubrimiento; hoy se  conocen mejor sus consecuencias y que yo sepa ya no se practican (wikipedia: En última instancia, entre 45 000 y 50 000 pacientes fueron lobotomizados, con poco o sin cualquier estudio de seguimiento para considerar si el tratamiento era eficaz. Las lobotomías como forma de tratar la enfermedad mental eran una barbarie, que solo pudo ser frenada con el desarrollo de antipsicóticos y hoy en día se practican procedimientos lesivos de núcleos cerebrales localizados mediante técnicas menos invasivas. La era de la lobotomía ahora se observa generalmente como episodio bárbaro en la historia psiquiátrica. La última lobotomía legal se practicó en 1967). Es posible que en un futuro si esta Ciencia tiene avances tangibles, vuelva su práctica de una  manera mucho más ajustada. Eliminando por ejemplo una neurona en concreto…De interés sobre medicación relacionada con una de las enfermedades mentales más conocidas].

10. Una entrada en el blog anterior relacionada con la complejidad computacional.

Extracto.

Leslie Valiant (1949-) es uno de los más grandes especialistas mundiales en aprendizaje automático y en complejidad computacional. Recipiendario del premio Turing en 2010, no solo está interesado en el estudio del problema de la inclusión estricta entre las clases de complejidad P y NP, sino que también desarrolla interesantes modelos computacionales del cerebro. Sin duda, un testigo muy reciente es su libro divulgativo (http://people.seas.harvard.edu/~valiant/PAC-%20Summary.pdf), que fue publicado por Basic Books en 2012, y en el que explica su concepto de “ecoalgoritmo”.

Como me estoy interesando por modelos computacionales del cerebro, paso inmediatamente a hojear el libro sobre el que nos informa  este bloguero…:-).

Extracto.

Algorithms are the step-by-step instructions used in computing for
achieving desired results, much like recipes in cooking. In both cases the recipe designer has a certain controlled environment in mind for realizing the recipe, and foresees how the desired outcome will be achieved. The algorithms I discuss in this book are special. Unlike most algorithms, they can be run in environments unknown to the designer, and they learn by interacting with the environment how to act effectively in it. After sufficient interaction they will have expertise not provided by the designer, but extracted from the environment. I call these algorithms ecorithms. The model of learning they follow, known as the probably approximately correct model, provides a quantitative framework in which designers can evaluate the expertise achieved and the cost of achieving it.

Creo que los defensores del determinismo genético deberían de leer estas líneas que hemos extractado. Que el genoma contenga instrucciones para construir un cerebro no quiere decir que el genoma determine todo lo que este objeto pueda realizar. Las instrucciones podrían dar vida a un objeto completamente autónomo cuyo comportamiento ya no pueden (los genes) controlar. De ser esto correcto el nivel psicológico sería irreducible al nivel biológico (genético), lo cual  no quiere decir que este nuevo nivel carezca de patrones o  reglas que se puedan estudiar. Los genes podrían explicar una construcción defectuosa y quizás algunas variaciones del cerebro normal, pero poco más dentro de la acción humana.

Finalmente recordar que aunque la idea de los algoritmos PAC del autor del libro citado (Probably Approximately Correct: Nature’s Algorithms for Learning and Prospering in a Complex World; el enlace es a un pdf con el índice y el primer capítulo, en inglés) tiene ya sus años (de los 80 del siglo pasado), entiendo que  su intento de aplicación a ciencias como la biología y neurociencias es más reciente.

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: