by Vas Mylko
We are visiting National University Lviv Polytechnic to tell the story about our vision and achievements with the Evolutionary AI.
Head of Department of Artificial Intelligent Systems Sc.D., Prof. Natalia Shakhovska invited us to a seminar about the perspectives of AI. We started to work with Natalia several years ago, since I was a Director of R&D at SoftServe. I still remember tailoring the curriculum — moved the majority of stuff from the last years to the sophomore and freshman years, added 3x more stuff focused on the width of vision and versatile programming.
This time it is the seminar with postgraduates, teachers, PhDs, researches, and their guests. Our mission is to show where the scientists could dig in for potential breakthroughs, show how science comes from technology in the case of Curiosio (Ingeenee vertical AI engine). This post is about the story we are going to tell there so that you also can learn something new here. We will share the lecture if they film it.
PART 1. NATURAL OPPORTUNITIES
How does nature compute? It looks like there is computation everywhere on different computing fabrics. The better we understand nature, the less energy we need to compute for our purposes. And vice versa — what we don’t understand takes enormous energy and time to be computed.
This part of the post is about attempts to understand the hidden order in nature, to unlock energy & time efficient computing. The emphasis will be on the evolution, probably the slowest but the most powerful kind of computation. Evolution is adaptation. Evolution is a complex adaptive explore and exploit strategy. Exploration is linear, exploitation is accelerated. Evolutionary programming and evolutionary computing are the tools to the hidden order.
Reverse-engineering the Strange
Less than a decade ago Michael Schmidt and Hod Lipson reverse-engineered double pendulum and other kinds of similar behavior in simple and energy efficient way. They reconstructed the Lagrangian from the primitive math operations using evolutionary programming.
The algorithm is called Eureqa. It runs on the ordinary laptop without GPU (I asked Michael about the hardware details when he delivered a lecture at Ukrainian Catholic University in 2019). Check out Michael’s demo in the episode of Through the Wormhole series with Morgan Freeman.
Chaos always attracted people. What is the difference between chaotic and random? What is the formula of chaos? Nowadays it is quite popular to reverse-engineer the strange attractors (e.g. Lorenz) and other attractors using Deep Learning. The practical use is obvious — until physicists don’t know the elegant equation, we can capture the order and use it for prediction.
Below are extracts from Deep Learning of Dynamical Attractors by William Gilpin from NSF-Simons Center for Mathematical & Statistical Analysis of Biology, Harvard University. Double pendulum is also present.
What was the biggest difference between evolutionary programming and deep learning (LSTM and MLP were used in Gilpin’s experiment)? It is energy consumption, training time, and the equipment. Eureqa trained in real-time during Schmidt’s lecture on a common laptop not using co-processor or accelerator.
Self-awareness
Let’s take a population of the simplest cells that could be only white or black within a generation. Can such a population figure out which color prevails? How many generations required to reach color awareness?
Below are two examples where the initial population has more whites (left) and blacks (right). Time goes top-down. The population is the binary string of 0 and 1, zero for black, one for white. Computing happens generation by generation. When all cells of the population are of the same color, then the computing is finished. From that point, the generations remain in the prevailing color.
What kind of algorithm is it? How the algorithm is encoded into the initial population? How many such algorithms (combinations of 0 and 1) exist? While those questions are very interesting, there is even more interesting observation. Let’s remove the filling (white, black, grey) from the triangles, look at the lines and their combinations. There are patterns, there is similarity to particle equations. Some particles decay, some interact and convert, some emerge… and it goes on and on — it is a such computing fabric.
Those plots are extracts from Evolving Cellular Automata with Genetic Algorithm by Melanie Mitchell & Co.
Morphogenesis
Ever wondered how our wounds heal? Or how the body developed? How a lizard regenerates its tail? How a salamander regenerates the most complicated organ — the eye? Where the self-awareness and self-replication are encoded and how?
Alexander Mordvintsev, Ettore Randazzo & Co published Growing Neural Cellular Automata — an interactive differentiable self-organizing cellular automata of morphogenesis, able to grow and regenerate specific two-dimensional patterns. Just click & play with the lizard.
Imagine this in three dimensions. Think of the evolution of stem cells. Are stem cells the cellular automata? Are hormones and neighbors the rules? What such evolution could produce in multiple dimensions?
Strings Eating Strings
There was an old research Artificial Selection in a System of Self-Replicating Strings by Wolfgang Banzhaf. The most important molecule of life was the inspiration — the RNA. The molecule could be of different length, encode different sequence, remain an information sequence aka food, or fold into the nano-machine and eat the food, producing new molecule. The new molecule can fold and eat others of remain the unfolded food.
Below is the extract from his work. Soup of strings is encircled on the left. There are primitive folding rules and operators on the strings. Three folding rules are on the right.
Banzhaf observed self-balanced system, where the soup of pseudo-RNA primitives ate and produced each other, folded into two dimensions, remained in one dimension. The main works were published in early 1990s in Biological Cybernetics as “Self-replicating sequences of binary numbers. Foundations I: General” and “Self-replicating sequences of binary numbers. Foundations II: Strings of length N=4”.
How such advanced behavior emerges? Imagine what could be emerging from the more complicated non-binary strings. Literally, think of the RNA in us and all living creatures…
Mathematicians vs. Physicists
There are two big classes of computational complexity. First class of problems is easy to compute, but difficult to verify. It is P. Second is difficult to compute, but easy to verify. It is NP. There are more classes, those two are just the most important today and tomorrow.
Example of the P problem is multiplication of two numbers. Very easy to multiply even on a smart watch. It is easy even if both numbers have many digits, e.g. 600+ or if they are both prime numbers. The whole cryptography is based on the difficulty to verify which numbers were multiplied to get the product. If the numbers are prime then this is tough.
Example of NP problem is TSP (aka Traveling Salesman Problem). It is easy to recognize a chimera route, but it is hard to find the elegant route. NP problems that consist of other NP are NP-Complete (aka NP-C or NPC). TSP in decision mode in NP-Complete. The distinctive characteristics of NP-C is unpredictability of the solving time, independent on computing capacity.
What goes on in no matter how tiny a region of space and no matter how tiny a region of time, according to the laws as we understand them today, takes a computing machine an infinite number of logical operations to figure out.
Now, how could all that be going on in that tiny space? Why should it take an infinite amount of logic to figure out what one stinky little bit of space-time is going to do?
— Richard Feynman, lecture
The opportunity: can NP problem be solved as fast as P? Can NP-C be solved predictably fast? Which solver can do that? Shall it go beyond the modern math closer to the nature?
PART 2. HOW WE BUILD CURIOSIO
This part of the post describes the details of Curiosio, from scientific to user friendly manner. Our vision is that Evolutionary AI extends Machine Learning to Machine Doing and that shall solve NP problems in predictable time as fast as P. This is the science coming from the technology. This is what we do in Curiosio for the independent travelers.
The Math
Simplified model in pseudo-code is listed below. The real model is more complicated. The purpose of the simplified model is showing the entanglement of multimodal optimization, multi-objective optimization, constraint satisfaction and routing.
There is more sophisticated model in the lab that handles duration and firm dates at the points, custom placeholders (useful for bleisure type of trips).
High-Level System Architecture
Curiosio consists for the knowledge graph, optimizer and web site. Optimizer uses our own AI engine called Ingeenee. You could think of Ingeenee as the genetically engineered ingenious engine.
Ingeenee looks and works like the black monoliths from the Space Odyssey. Wherever they appear — intelligence is emitted to the environs. Quiz: find the black monoliths in the United States, Canada, India, Australia, France, Italy imagery.
Curiosio Concept
When you’re traveling for leisure, you go for what happens between sitting on the planes and sleeping in the beds: experience. Planning a journey that maximizes quality of experience is more valuable than getting a good deal on a flight, room or tour. Mathematically, to get this information quickly is equivalent to solving Millennium Problem P vs. NP. Each time.
I go to https://curiosio.com and enter what I want. I’d like to see what else is within the reach for my time & money. Got route and itinerary with even more points: Genoa, Stelvio Pass, Pienza. See & Do proposed for each point. Entire itinerary fits to duration and budget.
What Works Today?
Use case 1: Turn any travel idea to the journey by points, time, money. Get educated as you search. Research until you are satisfied with the search results.
Use case 2: Take a travel story you love and bend it by points, time, money to the journey you want. Take a travel log of your favorite travel influencer and build your own journey on top of it. Research until you are satisfied.
What Will Work Tomorrow?
In one sentence — users want kind of Google Maps driven by curiosity. I drive from point A to point B, show me the interesting alternative routes with interesting points on-the-route and interesting See & Do at those points if there are enough time and money. Many users search for a short duration (a few days) but long distances.
This is even more complicated than what works today. But infinity multiplied by ten remains infinity. The computational complexity class remains the same NP-C. Hence the same solver must tame the same complexity. We are working on the version with the literally “driven by curiosity” routing. We will publish the analysis of the searches and our testing on those cases in a separate post entitled User Voice.
