Журнал «Компьютерра» № 11 от 20 марта 2007 года - Компьютерра. Страница 22

Лично я думаю, что это вполне решаемая в течение пяти-десяти лет задача, а когда она будет решена, это полностью изменит существующую практику вступительных экзаменов.

Недавно Ларри Пейдж, сооснователь Google, объявил, что Google серьезно работает над ИИ, а использование сосредоточенной там вычислительной мощности и базы знаний может серьезно ускорить движение в сторону ИИ.

Для продвижения в биологии (протеомике, геномике) критически важно понимание предметной области. Однако и без инновационных алгоритмов датамайнинга прогресс там невозможен.

Как устроены системы датамайнинга? Много ли общего у этих технологий с технологиями поисковых машин типа Гугла?

— Системы датамайнинга устроены не так, как системы поиска по вебу (Google, Yahoo), поскольку датамайнинг работает обычно с цифровыми базами данных и задает другие вопросы, нежели Google. Обычно эти системы реализуют различные методы очистки и препроцессинга, а затем применяется основное ядро алгоритмов. Самые важные задачи, решаемые этими алгоритмами, — классификация, кластеризация, визуализация. Процесс датамайнинга требует множества итераций, как показано на рисунке. Важнейшая алгоритмическая часть — использование алгоритмов машинного обучения, то есть построение модели; для датамайнинговой системы это так же важно, как двигатель для спортивного автомобиля. Однако основные усилия обычно уходят на подготовку данных. Заинтересованных читателей приглашаю познакомиться с моими (свободно доступными) лекциями.

На конференции KDD-2006 несколько известных исследователей в области извлечения знаний из данных предложили задачи, которые в будущем могут претендовать на роль «великих вызовов», бросаемых повседневной практикой.

• Провести аннотацию 1000 Часов цифрового видео в течение одного часа. Согласно автору предложения Шабану Джерабе (Chabane Djeraba), в настоящее время это требует тысяч человеко-часов при ручной работе. Под аннотацией подразумевается краткое описание происходящего. Например, сегодня невозможно без выполненной человеком аннотации выделить в записи баскетбольного матча эпизоды атаки и обороны каждой команды. Ручная аннотация одной фотографии для Национального географического общества требует двадцать минут.

• ВикипедиЯя-тест (Lise Getoor, Лиз Гетур). По сборнику статей, созданному либо в режиме партисипативной журналистики (то есть по принципу наполнения Википедии), либо с использованием автоматических инструментов поиска линков по требуемой тематике, определить, какой из этих двух методов использовался: то есть составлен ли сборник машиной или людьми (и в каком случае качество оказалось выше)? Автор предложения указывает на связь этого вызова с другим, брошенным специалистам по сжатию информации: сжать 100 мегабайт Википедии до 18 мегабайт, не потеряв ни единого бита (за это уже назначен приз Хаттера в 50 тысяч долларов).

• Оценить миллиард прогнозирующих моделей (Robert Grossman, Роберт Гроссман). В ходе многолетней практики датамайнинга было построено великое множество статистических моделей для различных типов и конкретных ансамблей данных. Во многих случаях для одних и тех же массивов данных строится несколько моделей, чтобы ухватить их характеристики разных видов. Пример: имеется информация от 833 датчиков движения транспорта в Чикаго. Задача состоит в автоматическом определении ситуаций, когда в транспортном потоке возникают аномалии, происходит что-то необычное (но не простая пробка!). Данные сегментировались по дням, часам и участкам дороги, что приводило к появлению 7х24х250 = 42000 автоматически генерируемых статистических моделей — хотелось бы значительно сократить их число! Подобная ситуация возникает и в онлайновом маркетинге (отдельная модель поведения для каждого клиента), в перспективных подходах к оценке эффективности лекарств на основе индивидуального генотипа и т. д. Так что миллиард набирается легко — вопрос в том, как радикально уменьшить это число.

• Разработка систем анализа текстов (text mining), способных сдать обыЧные экзамены на понимание текста SAT, GRE, GMAT (Ronen Feldman, Ронен Фелдман). Эту задачу с оптимизмом комментирует в своих ответах Григорий Пятецкий-Шапиро. Она покруче даже стандартного теста Тьюринга (определить, машина или человек отвечает на ваши вопросы), по поводу которого тоже было много оптимизма, в том числе и у его гениального автора. Однако не будем забывать, что этот вызов — лишь планка, которую автор предложения поднимает так высоко в надежде на достижение более приземленных практических целей: довести точность реализации реляционных запросов с нынешних 70—80% до 98—100%, причем в самой общей ситуации.

Кроме этого, был предложен еще один весьма важный вызов — функциональная аннотация белков. Однако формулировка здесь так сложна, а задач так много, что мы ограничимся лишь констатацией — это направление, датамайнинг в геномике и протеомике, тоже служит источником великих вызовов (напомним, кстати, что недавно назначен приз X PRIZE за снижение стоимости сканирования генома до 10 тысяч долларов при повышении производительности до ста геномов за десять дней).

Ну а для полноты картины упомянем и конкурс, который состоится на конференции KDD-2007. Участникам предоставляется тренировочный массив данных Netflix, в котором собрано больше 100 млн. рейтингов (по пятибалльной шкале) по 18 тысячам фильмов от 480 тысяч случайно выбранных анонимных пользователей Netflix (то есть людей, бравших у Netflix DVD напрокат), с 1998 по 2005 год. Вот одна из двух задач, по которым будет проводиться состязание:

Дан список из 100 тысяч пар вида «номер_пользователя, номер_фильма», относящийся к 2006 году (то есть не входящий в тренировочный массив). Для каждой такой пары нужно указать вероятность, что данный пользователь хоть как-то рейтинговал данный фильм в 2006 году.

Денежные призы не предусмотрены — в отличие от основного конкурса Netflix. Там, чтобы заработать миллион долларов, требуется превзойти точность действующей сейчас на фирме системы рекомендаций Cinematch™ всего лишь на 10% (на исторических данных); ежегодно разыгрывается приз в скромные 50 тысяч долларов просто за самое большое уточнение прогноза. Прогноз состоит в том, чтобы угадать по предшествующим оценкам фильмов клиентами, какие из фильмов они высоко оценят в будущем. По состоянию на 14 марта 2007 года лучший результат в конкурсе Netflix уже 6,75%, то есть две трети пути к миллиону пройдено.

ЦИФРА ЗАКОНА: Письмо несчастья: Может ли «покаянное письмо» спасти системного администратора?

Автор: Павел Протасов

Среди обилия заблуждений, бродящих по умам наших соотечественников, одно из первых мест занимают те, что связаны с законодательством. Об одном из них я и хочу сейчас поговорить. Оно периодически всплывает то тут, то там в ходе разнообразных обсуждений судьбы тех бедолаг, что попали под кампанию борьбы нашего государства с пиратством, однако наиболее активно его начали пропагандировать в связи с недавним судебным процессом по обвинению в «пиратстве» директора сельской школы Александра Поносова. Связано оно с вопросом о том, как обезопасить себя от милицейского «наезда», если на вверенной абстрактному системному администратору территории обнаружилось что-то контрафактное.

Директор школы Поносов — все-таки исключение, а типичной является ситуация, когда за «пиратку» привлекают к ответственности компьютерных дел мастера, обслуживающего какую-нибудь контору. В один прекрасный день приходит проверка, которая обнаруживает на конторских компьютерах пиратские программы и интересуется: а кто же их установил. Такой человек находится довольно быстро, а поскольку речь идет об организации и компьютеров несколько, то контрафакта на «уголовный» размер обычно набирается. Следствие, суд, условный срок, заметка в местной газете об очередной победе борцов с высокими технологиями и о вреде пиратства. Стандартный набор.