October 12th, 2014

тот самый Пух

Алан Милн, автор повестей о «медведе с опилками в голове», и настоящие Кристофер Робин и тот самый медведь Пух.

"Methinks it is like a weasel"

В мире родственников

Я не знаю, кто сказал первым, что при наличии достаточного времени, обезьяна, беспорядочно стучащая по клавишам пишушей машинки, смогла бы когда-нибудь напечатать все произведения Шекспира. Ключевая фраза здесь, конечно "при наличии достаточного времени". Давайте несколько сузим задачу, стоящую перед нашей обезьяной. Предположим, что ей нужно воспроизвести не все произведения Шекспира, а только короткое предложение "Methinks it is like a weasel" ("Сдаётся мне, что оно похоже на горностая"), и облегчим её работу, предоставив ей пишущую машинку с клавиатурой, состоящей только из 26 букв (заглавных), и клавиши пробела. Сколько времени ей потребуется, чтобы написать это небольшое предложение?

Предложение состоит из 28 символов, так что давайте предположим, что обезьяна будет производить серию попыток, состоящих из 28 ударов по клавиатуре. Если она напечатает фразу правильно, то это будет окончанием эксперимента. Если нет, то мы предоставляем ей другую 28-символьную "попытку". У меня нет знакомых обезьян, но к счастью, моя 11-месячная дочь – опытный генератор случайных символов, она лишь продемонстрировала слишком большое нетерпение, чтобы продвигаться в работе обезьяны-машинистки поэтапно. Вот что она напечатала на компьютере:

UMMK JK CDZZ F ZD DSDSKSM

S SS FMCV PU I DDRGLKDXRRDO

RDTE QDWFDVIOY UDSKZWDCCVYT

H CHVY NMGNBAYTDFCCVD D

RCDFYYYRM N DFSKD LD K WDWK

JJKAUIZMZI UXDKIDISFUMDKUDXI

Поскольку у дочери есть другие важные дела, то роль такой машинистки я поручил компьютерной программе, имитирующей беспорядочно печатающего младенца или обезьяну:

WDLDMNLTDTJBKWIRZREZLMQCO P

Y YVMQKZPGJXWVHGLAWFVCHQYOPY

MWR SWTNUXMLCDLEUBXTQHNZVJQF

FU OVAODVYKDGXDEKYVMOGGS VT

HZQZDSFZIHIVPHZPETPWVOVPMZGF

GEWRGZRPBCTPGQMCKHFDBGW ZCCF

И так далее в том же духе. Несложно подсчитать, как долго нам придётся ждать, пока генератор случайных символов (младенец или обезьяна) напечатают "METHINKS IT IS LIKE A WEASEL". Оценим общее количества возможных фраз заданной длины, которые обезьяна, младенец или генератор случайных символов могли бы напечатать. Вычисления будут теми же самыми, какие мы делали для гемоглобина, и приведут к аналогично большому результат. На первой позиции этой строки возможно 27 возможных символов (включая символ пробела). Шанс, что обезьяна, напечатает букву "M" прямо следует из количества символов – 1 из 27. Шанс, что вторая буква будет "E" аналогичен шансу, что первая буква будет "M", а шанс, что первые две буквы будут "ME" равен их произведению 1/27 Ч 1/27, что даст 1/729. Шанс на то, что первое слово будет "METHINKS" – это шанс на появление каждой буквы на своём месте – 1/27 для каждой, итого (1/27) Ч (1/27) Ч (1/27) Ч (1/27) …, и так далее 8 раз, то есть (1/27) в степени 8. Шанс на получение всей этой фразы из 28 символов, есть (1/27) в степени 28, то есть (1/27) умножимое само на себя 28 раз. Это очень маленький шанс, примерно 1 из 10000 миллионов миллионов миллионов миллионов миллионов миллионов. Искомую фразу, таким образом придётся ждать, мягко говоря, долго, не говоря уж о всех произведениях Шекспира.

Так долго получается в случае одноразового отбора случайной вариации. Теперь рассмотрим нарастающий отбор – насколько он будет эффективнее? Очень и очень намного! Гораздо эффективнее, чем мы возможно себе представляем в первый момент, хотя это почти очевидно, если мы подумаем над этим чуть более. Мы снова используем нашу компьютерную обезьяну, но внесём критическое изменение в программу. Она, как и раньше, снова начинает, выбирая случайную последовательность из 28 букв:

WDLMNLT DTJBKWIRZREZLMQCO P

Однако теперь она "размножает" эту случайную фразу. Она реплицирует её неоднократно, но с некоторой вероятностью случайной ошибки – "мутации" при копировании. Компьютер исследует мутировавшую бессмысленную фразу, "потомка" первоначальной, и выбирает ту, которая более всего (хотя бы чуть-чуть) походит на нашу искомую фразу, "METHINKS IT IS LIKE A WEASEL". В данном случае, в следующем поколении победила такая фраза:

WDLTMNLT DTJBSWIRZREZLMQCO P

Улучшение неочевидное! Но процедура повторилась, и снова мутировавший "потомок" "вывелся" от последней фразы, и отобран новый "победитель". И так поколение за поколением. После 10 поколений, фраза, выбранная на роль "производителя" была такой:

MDLDMNLS ITJISWHRZREZ MECS P

А вот что было после 20 поколений:

MELDINLS IT ISWPRKE Z WECSEL

А вот здесь глаз уже не может на заметить некоторого подобия искомой фразе. В 30-м поколении в подобии можно уже не сомневаться:

METHINGS IT ISWLIKE B WECSEL

На 40-м поколении – мы в одной букве от цели:

METHINKS IT IS LIKE I WEASEL

И вот цель наконец достигнута в 43-м поколении.

Второй прогон компьютер начал с фразы:

Y YVMQKZPFJXWVHGLAWFVCHQXYOPY

Результаты прогона были таковы (снова приводится только каждое десятое поколение):

Y YVMQKSPFTXWSHLIKEFV HQYSPY

YETHINKSPITXISHLIKEFA WQYSEY

METHINKS IT ISSLIKE A WEFSEY

METHINKS IT ISBLIKE A WEASES

METHINKS IT ISJLIKE A WEASEO

METHINKS IT IS LIKE A WEASEP

И конечная цель достигнута в поколении 64. Третий прогон компьютер начал с фразы:

GEWRGZRPBCTPGQMCKHFDBGW ZCCF

И достиг "METHINKS IT IS LIKE A WEASEL" в 41-м поколении селективного "размножения".

Точное время, затраченное компьютером на достижение цели, значения не имеет. Но если вы настаиваете, то он закончил весь первый прогон за время, пока я завтракал – то есть, примерно полчаса. (Энтузиасты-компьютерщики могут счесть, что это неправдоподобно долго. Но дело в том, что программа была написана на БЕЙСИКЕ – это язык программирования для младенцев. Когда я переписал её на Паскаль, то она стала выполняться за 11 секунд). Компьютеры в этих делах несколько быстрее обезьян, но разница действительно не имеет значения. Значение имеет разница между временем нарастающей селекции, и временем, потребным тому же самому компьютеру, работающему с той же скоростью, на достижение целевой фразы, если мы заставим его использовать другую процедуру – процедуру одноразового отбора: это примерно миллион миллионов миллионов миллионов миллионов лет. Это в миллион миллионов миллионов раз больше времени существования Вселенной. Фактически разумнее говорить, что в сравнении с временем, потребным, неважно кому – хоть обезьяне, хоть компьютерному генератору случайных символов, для генерации нашей целевой фразы, возраст вселенной – столь ничтожная величина, что на практике утонет в погрешностях данного рода вычислений. В то же время, компьютерному генератору случайных символов, но работающему по алгоритму нарастающего выбора, для выполнения той же самой задачи потребуется совершенно обозримое время – от 11 секунд до длительности спокойного завтрака.

Различие между нарастающим отбором (при котором каждое улучшение, пусть небольшое, используется как фундамент для будущей постройки), и одноразовым выбором (при котором каждая новая "попытка" делается "с нуля"), просто неимоверно огромно. Если бы эволюционный прогресс полагался на одноразовый отбор, то он никогда и нигде не имел бы места. Однако, если где-нибудь и как-нибудь слепые силы природы создадут условия для нарастающего отбора, то необыкновенные и удивительные последствия не заставят себя ждать. Собственно говоря, именно это и произошло на нашей планете, и мы с вами – одно из новейших, и может быть – самое необыкновенное и удивительное из этих последствий. Просто поразительно, как можно всё ещё полагать вычисления, вроде наших вычислений "числа гемоглобина" аргументами против теории Дарвина. Люди, так полагающие, часто эксперты в своей сфере – астрономии или где-то ещё, похоже, вполне искренне полагают, что дарвинизм объясняет организацию живой материи в терминах "спонтанности" – одного только "одноразового отбора". Вера в то, что дарвиновская эволюция "спонтанна", не просто ложна. Это точная антитеза правды. Случай – второстепенный компонент в дарвиновском рецепте, главнейший же – нарастающий отбор, который принципиально неслучаен.

Ричард Докинз, «Слепой часовщик»

p53

No researcher could read all the papers in their field – but machines are making discoveries in their own right by mining the scientific literature

IN MAY last year, a supercomputer in San Jose, California, read 100,000 research papers in 2 hours. It found completely new biology hidden in the data. Called KnIT, the computer is one of a handful of systems pushing back the frontiers of knowledge without human help.

KnIT didn't read the papers like a scientist – that would have taken a lifetime. Instead, it scanned for information on a protein called p53, and a class of enzymes that can interact with it, called kinases. Also known as "the guardian of the genome", p53 suppresses tumours in humans. KnIT trawled the literature searching for links that imply undiscovered p53 kinases, which could provide routes to new cancer drugs.

Having analysed papers up until 2003, KnIT identified seven of the nine kinases discovered over the subsequent 10 years. More importantly, it also found what appeared to be two p53 kinases unknown to science. Initial lab tests confirmed the findings, although the team wants to repeat the experiment to be sure.

KnIT is a collaboration between IBM and Baylor College of Medicine in Houston, Texas. It is the latest step into a weird world where autonomous machines make discoveries that are beyond scientists, simply by rifling more thoroughly through what we already know, and faster than any human can.

In a paper to be presented at the Conference on Knowledge Discovery and Data Mining in New York City this week, the researchers say that society is better at generating new information than at analysing what it already has. "This leads to deep inefficiencies in translating research into progress for humanity," they write. KnIT aims to iron out that inefficiency.

"In general, new p53 kinases are discovered at a rate of one per year," says Olivier Lichtarge, who leads the work at Baylor. "We hope to greatly accelerate that rate of discovery."

Studying kinases is important for cancer research, but the Baylor team thinks the approach can extend beyond biomedical studies to all areas of science. And if KnIT's algorithmic discoveries hold up, they point to a future in which everyone could have a personalised algorithm trawling and making sense of the scientific literature to figure out cures for their ailments, including ones tailored at a genetic level.

Expanding KnIT to other areas of biology or the physical sciences isn't straightforward. "We could run into big problems when we try and generalise to more proteins and genes," Lichtarge says. And in subjects like physics, results tend to be presented using equations and graphs rather than words. However, data-mining groups are working to retrieve information from these too.

The idea that new knowledge can be unearthed by finding links between disparate strands of research was first crystallised in 1986 by information scientist Don Swanson at the University of Chicago. He analysed a database of scientific literature manually to deduce that fish oil might be a good treatment for Raynaud's syndrome, a circulatory disorder, because studies showed that fish oil could reverse certain conditions also seen in Raynaud's. His hunch turned out to be right.

Modern science has given us a far larger and more intricate haystack than the one Swanson picked through, but machine intelligence is now sorting through it to find new connections.

Ross King of the University of Manchester, UK, has developed a different kind of automated system, EveMovie Camera, which he claims has already discovered a novel drug against malaria. Rather than extracting new knowledge from the literature, Eve robotically runs lab experiments focused on finding new drugs to treat neglected diseases. King is keeping the discovery secret until the work is published, but will say that the compound is an ingredient in several brands of toothpaste.

The webs of knowledge that computers create in this automated pursuit of discovery are useful to non-scientists, too. Sophia Ananiadou at the University of Manchester works on Facta+, a searchable database which holds huge amounts of information about cancer, based on data mined from the literature. Although it's designed to help cancer researchers, she says it could be used by the public to learn more about diseases they have been diagnosed with, without having to read scientific papers themselves.

The purpose of data mining can also be flipped. Instead of finding new insights into specialised topics, systems like KnIT can find holes in existing research that need to be plugged.

Natasa Miskov-Zivanov of Carnegie Mellon University, Pittsburgh, is working on using similar techniques to build computational models of cells that can be used to test drugs. Normally, models take time to develop, with input from experimental biologists and theorists. But Miskov-Zivanov's models build themselves quickly and automatically using results in the literature. The models can then be tested by scientists in the lab.

Miskov-Zivanov's work is funded by the US defence agency DARPA as part of its Big Mechanism project, which aims to find new knowledge hidden in big data. "It takes several years to develop a meaningful model of what's going on in a cell, but what we're doing could speed up the process a lot," she says. That would, in turn, speed up drug testing.

New breakthroughs could come by analysing scientific literature across disciplines – physics on the scale of cells and molecular biology, for instance. "I don't think we could ever understand this huge, complicated puzzle without automated help," says King. "There just aren't enough PhDs in the world to do the experiments."

This article appeared in print under the headline "Automated discovery"

If you would like to reuse any content from New Scientist, either in print or online, please contact the syndication department first for permission. New Scientist does not own rights to photos, but there are a variety of licensing options available for use of articles and graphics we own the copyright to...