plakhov: (Default)
Лесли Валиант получил Turing Award - самую почетную награду в области Computer Science. Ура!

Что сделал Валиант:
- создал PAC-learning framework
- показал (вместе с Вазирани), что NP полиномиально сводится к UNIQUE-SAT, а значит, и к PARITY-SAT; это стало первым шагом для доказательства теоремы Тода, а еще это источник некоторых несбыточных мечт для меня лично
- заметил, что умение считать перманент матрицы (почти то же, что детерминант, только все коэффициенты при слагаемых - плюс единицы) означает умение решать #P; это очень странно - интуитивно совершенно не ясно, почему эти две операции настолько отличаются по своей вычислительной сложности
- написал несколько отличных (к сожалению, боюсь, сильно недооцененных) работ о том, как некоторые вопросы теории эволюции или neuroscience (вот опять, как это по-русски? нейронауки?) оказываются на самом деле вопросами чистой вычислительной сложности, и как они решаются с этой точки зрения
- умудрился придумать noninteracting-fermion quantum circuits из чисто математических соображений, не понимая (по крайней мере, так утверждает Ааронсон), что он на самом деле придумывает

И наверняка еще кучу всего, о чем я не в курсе.
plakhov: (Default)
http://www.wolframalpha.com/input/?i=average+penis+length

Я вот не понимаю, а как Вольфрам себе представляет процесс озарения "действительно, не ввести ли мне в математический поисковик такой вот запрос"? То, что на него будет дан ответ, отличный от "Wolfram|Alpha does not yet know how to respond to your exact query", это тайное знание, которое должно передаваться из уст в уста (чёрт, какие-то не те коннотации)?

Когда они запускались, я был уверен, что у Стивена есть хитрый план, и постепенно простым смертным вроде меня станет понятно, что на самом деле Альфой офигенно удобно пользоваться, и что она в чем-то потеснит традиционные поисковики. Не может ведь быть такого, чтобы автор New Kind of Science и Mathematica не понимал очевидных вещей.

Черт, я даже повелся "на слабо", и научился парсить википедию и "умно" отвечать на запросы вроде [самый низкий баскетболист] (из тех, рост которых указан в википедии, но об этом мы вслух не будем говорить). Убил месяц, наверное. Как вы думаете, какое количество пользователей задает такие запросы, насколько надежные получаются ответы, и стоит ли это количество внедрения хрупкой и экзотической "базы знаний"? Праавильно.

В итоге у меня лично получалось извлечь пользу из wolphram|alpha только при помощи запросов вроде http://www.wolframalpha.com/input/?i=x^5%3Dx+%2B+1 (таким образом я узнал, на какую именно экспоненту похожа функция f, для которой f(n) = f(n-4) + f(n-5)). Целых три раза! Думаю, это больше среднестатистического количества. И даже так работает, к сожалению, далеко не всегда.

Например, я выяснил для себя, что функция, задаваемая простым рекуррентным соотношением f(n) = f(n/2) + f(n-1) растёт быстрее любого многочлена, но медленнее любой экспоненты. f(1) равно, скажем, 1. Если n не делится на 2, можно округлять в любую сторону, неважно.

Интересный зверь; может быть, про него давно известно больше?
http://www.wolframalpha.com/input/?i=f%281%29+%3D+1%2C+f%28n%29+%3D+f%28n%2F2%29+%2B+f%28n-1%29
(сообщает нам Альфа, попыхивая трубкой)

В общем, как-то я в недоумении.
plakhov: (Default)
...Что Поль Брэгг умер вовсе не в возрасте 95 лет, когда его, катавшегося на серфе, захлестнуло волной, а в возрасте 81 года, от закупорки сосудов (via alenacpp), и что статья о нём в русской википедии вчетверо длиннее, чем в английской.

...И что parity-2-SAT имеет полиномиальную редукцию к monotone-parity-2-SAT без увеличения числа переменных. Насколько я знаю, это новый результат, и довольно неожиданный. Мозг работает очень странно: "узнал" я об этом где-то в полпервого ночи, ровно в момент засыпания. При этом есть стойкое ощущение, что процесс доказательства завершился раньше, но результат поступил в область осознания только тогда, когда та стала освобождаться от дневных впечатлений. Немедленно после этого меня похитили инопланетяне, потому что я придумал еще и полиномиальную редукцию из monotone-parity-2-SAT в parity-2-SAT с меньшим числом переменных (что, кстати, не выглядит невозможным), и, сложив оба результата, получил 42. Думаете, это хиханьки какие-то? Это было очень-очень страшно! Но я вовремя проснулся.
plakhov: (Default)
(научно-непопулярный пост)
"Решения" P-NP проблемы публикуют в основном фрики. Дело не в том, что эти сотни попыток оказываются неудачными, а в том, что они еще и обнаруживают невежество их авторов, какие-то причудливые представления о математике и её методах, безумное самомнение и пр. Раньше то же самое творилось с великой теоремой Ферма. Этим грешат как "положительные" решения (предположительно полиномиальные алгоритмы), так и "отрицательные".

С алгоритмами вообще беда. По идее, если уж человек верит в то, что сейчас перевернет всю computer science, всю криптографию и значительную часть machine learning, то хорошо бы ему все-таки написать тестовую реализацию, и проверить её на каких-нибудь примерах (о сомнениях, которые высказывал, в частности, avva, насчет потенциальной экзотической сложности вроде О(n10100) я помню, но к этим экземплярам они не относятся). Пусть написанная программа, например, отвечает на вопросы, может ли заданное двадцатизначное число быть представлено в виде произведения двух меньших, одно из которых начинается с заданных цифр (достаточно очевидно, как такой вопрос записать в форме инстанса SAT-задачи с небольшим, в общем-то, количеством переменных). Если ей это удастся (но ей этого не удастся), то после этого будет уже неважно, насколько хорошо автор умеет писать статьи, насколько чисто он доказал, что его алгоритм работает, и т.п. Само существование подобной программы уже будет феерической победой: из нее очевидным образом делается быстрая факторизация.

С доказательствами беда немного другая: если они вообще осмысленные (а не состоят из шизофазии), то читатель, как правило, в какой-то момент встречает утверждение "любой алгоритм решения должен быть построен по такой-то схеме, и сейчас мы поймем, почему эта схема не может работать на задачах такого-то класса". Нет, не должен.

Вот сейчас я попробую описать разновидность алгоритмов решения канонической NP-полной задачи, а именно k-SAT. Алгоритмы эти довольно неожиданного типа, содержат красивый трюк, и мне нравится думать, что я изобрел их первым (хотя наверняка я ошибаюсь, и Валиант сделал это раньше). Разумеется, они "не работают": среди них, кажется, нет такого, который работал бы за полиномиальное время (хотя, вообще-то, я не могу этого доказать). Однако они интересны тем, что если сузить на них предполагаемое P!=NP, из этого немедленно следуют довольно неочевидные вещи из области, хм, как бы назвать эту часть математики? Из области матанализа, видимо, пусть это и "школьное" название. Итак.

Трюк с характеристическим(?) многочленом )

:(

Jun. 3rd, 2010 05:01 pm
plakhov: (Default)
Арнольд умер.

Прочитайте его книжку "Что такое математика?"
Она маленькая, 100 страниц всего.
plakhov: (Default)
1 апреля я не шутил.

Но "на халяву" применить его теорию для общего случая пока не получается*. Решил начать с разминки, с малого веса. Строю определение "регулярных языков", носителем которых являются 2d-изображения (а не строки), и параллельно - адаптацию определения "контекста" и "свертки" для этого случая. Цель - сделать это таким образом, чтобы "регулярные языки" и "языки с конечной решеткой концептов" совпали (как и в случае строк).

*Проблема состоит в том, что если определить "контекст" естественным образом, как множество точек, дополнение которого выпукло, то операция свертки окажется не всегда определена. В принципе, это можно объявить "нестрашным", и считать, что свертка области и контекста несовпадающей формы дает фиксированный формальный и "неграмматичный" результат. Но, по-моему, это плохо (как минимум вычислительно, необходимых концептов сразу становится во много раз больше). Можно определять "контексты" как дополнения областей фиксированной формы, тогда неожиданно получается, что такими областями должны быть прямоугольники, а "свертка" должна включать в себя возможное масштабирование по осям. Все это не то, чтобы плохо для задачи middle AI, первое весьма приятно в вычислительном смысле, а второе - в смысле распознавания изображений; но как-то странно и подозрительно, что подобные концепции - прямоугольники и масштабирование - возникают уже на столь фундаментальном уровне.
plakhov: (Default)
Почти дожив до 30 лет, я случайно узнал от [livejournal.com profile] _foreseer, что если мы кинули "нечестную" монету M раз, и решка выпала N раз, то вероятность ее выпадения следует оценивать* как (M+1)/(N+2), а вовсе не так, как все делают. Интересно, если я в матстате такие открытия делаю, наверное, надо и Пёрышкина перечитать, или природоведение за 3 класс.

*assuming uniform prior
plakhov: (Default)
функционального программирования, теории категорий, и прочая матана. Подскажите, какие существуют средства, пригодные для проверки того, что бинарная операция является ассоциативной (не обязательно имеющие доказательную силу, лишь бы работали). Про операцию известно "вообще всё" (грубо говоря, можно изучать ее код, если это потребуется). Придумано ли что-нибудь лучше, чем "проверить на имеющихся данных"?

Тот же вопрос про унарную операцию и идемпотентность.
plakhov: (Default)
Господа математики, матлингвисты, machine learner'ы и прочие естественные интеллекты.

Расскажите мне, как искать би-клики в двудольных графах.
На эту тему есть всякая литература, например, Makino "New Algorithms for Enumerating All Maximal Cliques".
Проблема в том, что в ней везде предполагается, что граф нам известен в точности.

А на самом деле известно, что граф двудольный, и известен набор его вершин; но информация о наличии или отсутствии ребра не обязательно точна. По наблюдаемым данным можно, например, для каждого потенциального ребра вычислить оценку вероятности того, что оно присутствует в исходном графе, и доверительный интервал для этой оценки (для каждого ребра свой). Хочется уметь перечислять в нем все структуры, которые с высокой вероятностью являются bi-cliques.

Естественно, эта постановка не фиксирована жестко, умение решать какие-то «похожие задачи» тоже пригодилось бы.

Кто расскажет, тому пиво, или цветы, или ку, или еще что-нибудь, в зависимости от. А то что-то решать ее всякими наивными хаками надоело.
plakhov: (Default)
Вот это настоящий старый добрый avva.
http://avva.livejournal.com/2174151.html
А я-то от него чуть не отписался.

Жаль только, что оппоненты - полнейшие клоуны. Могло бы быть гораздо интереснее.
Интересно, насколько подобные "дискуссии" типичны для выпускников РЭШ?

WAIT WHAT?

Dec. 9th, 2009 03:09 pm
plakhov: (Default)
O SHI~. Гуглевцы пишут, что в их экспериментах квантовые компьютеры уже работают лучше классических. Даже если зачеркнуть последние два слова, это все равно unbelievable.

http://googleresearch.blogspot.com/2009/12/machine-learning-with-quantum.html
It was trained with adiabatic quantum optimization using a D-Wave C4 Chimera chip. There are still many open questions but in our experiments we observed that this detector performs better than those we had trained using classical solvers running on the computers we have in our data centers today.

Я еще не добрался статьи прочитать. Но в любом случае, я правильно понимаю, что тут написано? Мне это не приснилось, нет?

Besides progress in engineering synthetic intelligence we hope that improved mastery of quantum computing will also increase our appreciation for the structure of reality as described by the laws of quantum physics.
Если бы это тов. Петрик написал, все было бы ок, никаких проблем. Но это же official Google research blog.

A.M.A.

Oct. 2nd, 2009 04:04 pm
plakhov: (Default)
Если кто-нибудь о чем-нибудь хотел меня спросить, или что-нибудь сказать, или о чем-нибудь поговорить, но повода не было, можете сделать это сейчас. А то я подумываю, не бросить ли ЖЖ нафиг в пользу RL. Да и вообще, жизнь коротка.

Изначально комментарии скрываются, но только на всякий случай (ну мало ли о чем вы там спрашивать собираетесь).

Ask me anything.
plakhov: (Default)
По мотивам.

Вот не знаю, как вам, а нам на мехмате рассказывали громоздкое и не особенно понятное доказательство основной теоремы алгебры. Я его пересказывать не буду, конечно.

Сама теорема такая, если кто забыл. У любого многочлена одной переменной с комплексными коэффициентами, не являющегося константой, есть комплексный корень.

Когда Аркаша Скопенков был моложе, чем я сейчас, он рассказал мне простое и красивое "топологическое доказательство". Вот такое.

Доказательство. Обозначим наш многочлен Р(х). Давайте посмотрим, как ведет себя PR(phi) = P(R·ei·phi), где phi - вещественное. То есть х "ездит" по кругу радиуса R, а P(x), соответственно, проезжает какой-то замкнутый контур на комплексной плоскости. Посмотрим на вектор, соединяющий начало координат и PR(phi) при phi, изменяющемся от 0 до 2·pi, и при фиксированном R. Это такая "стрелка часов", которая делает какое-то целое число оборотов вокруг начала координат. Если R очень близко к 0, то она делает 0 оборотов (мы считаем, что P(0) != 0, иначе доказывать нечего). Если R очень велико, то P(x) ведет себя как своя старшая степень const·xN, то есть стрелка делает N оборотов вокруг начала координат (в принципе, это нужно расписать подробнее, но, думаю, это и "на пальцах" понятно). Давайте непрерывно менять R от 0 до бесконечности. Внимание, вопрос: R меняется непрерывно, так в какие же это моменты времени наше целое число оборотов, зависящее от R, разрывно меняется? Если сразу не дошло, то тут стоит нарисовать картинку и на нее некоторое время посмотреть.

Вот и все. А теперь представьте, каково будет излагать это доказательство так, чтобы его можно было "автоматически верифицировать", или хотя бы преподавать в скучном правильном стиле.

Как я понимаю, все серьезные результаты доказываются именно так, почти что неформально. Важна именно конструкция, новое понимание задачи, а строгость наведут уже потом. Естественно, "в принципе" путь к формализации должен просматриваться, но это не главное вовсе.
plakhov: (Default)
1а) (широко известная) Есть очень большой файл, в котором лежит очень много (точнее, 2N+1) целых 64-битных чисел. Известно, что в нем N пар одинаковых чисел, и еще одно "непарное". Требуется найти это самое "непарное" число за O(N) времени и O(1) памяти. Естественно, числа в паре не обязательно идут подряд - иначе было бы слишком просто.

1б) То же самое, но чисел 2N+2, и непарными являются два из них. Требуется найти оба.

2) (из другой оперы) Есть шахматная доска 8х8, любая клетка которой может быть покрашены в черный или в белый цвет. Разрешается взять любой квадрат 3х3 или 4х4, и перекрасить каждую клетку внутри этого квадрата в противоположный цвет. Верно ли, что из любой начальной раскраски таким образом можно получить одноцветную доску?
plakhov: (Default)
А мы этого до сих пор не знаем. Например, при определенных предположениях (несовместимых, к сожалению, с P=NP) возможно создание совершенно безумных объектов: "квантовых денег", и даже "квантового copy-protected software".

Квантовые деньги - это штука, которую принципиально (по законам природы) невозможно подделать или скопировать, хотя подлинность экземпляра может проверить любой человек (то есть, они не требуют, например, взаимодействий с некоторым защищенным центральным сервером, как теперешние пластиковые карты). Я пишу штука, поскольку нужно понимать, что ее будущий внешний вид пока что абсолютно неизвестен. Это примерно как рассуждать о банкоматах в 1930 году. Может быть, обычные (на вид) банкноты в 2060 году уже будут обладать этими свойствами. А может, "деньги" будут микроскопическими количествами инертного газа в магнитной ловушке, а кошельками для них будут служить устройства, похожие на железные орехи.

Квантовое copy-protected software - это, согласно определению, штука, которая умеет вычислять некоторую функцию f, и которую при этом невозможно (опять же принципиально, по законам природы) использовать для того, чтобы соорудить вторую такую же штуку. С точки зрения математики явления, это обобщение квантовых денег: такая программа, решающая произвольную достаточно сложную задачу, автоматически обладает всеми их свойствами.

Таким способом можно будет защитить от копирования только именно программу, то есть инструмент, выполняющий какую-то полезную работу, а не результат этой самой работы. Запретить копировать книгу, музыку или фильм, будет ничуть не проще, чем сейчас: пусть квантовый объект, содержащий эти данные, скопировать невозможно, но сам по себе он никому и не нужен; всех интересует именно результат воспроизведения, который можно прямо в процессе чтения-прослушивания-просмотра записать на более привычный носитель и тиражировать со спокойной совестью.

На прошедшем ССС (Computational Complexity Conference) Scott Aaronson рассказал о двух своих продвижениях в этой области. Во-первых, он придумал потенциальную схему создания таких штук. Доказательство ее криптографической стойкости он пока не придумал (в его оправдание: на современном уровне развития математики подобные задачи вообще никто решать не умеет). С другой стороны, то, как могла бы выглядеть атака на нее, тоже неизвестно. Во-вторых, он представил некоторый теоретический результат, говорящий в пользу того, что такие устойчивые к атакам схемы вообще возможны. Как и многие важные результаты в области computational complexity, этот имеет вид "если Икс и неправда, то по совершенно непонятной причине, поскольку невозможно доказать не-Икс, пользуясь методами весьма широкого класса". Это, честно говоря, выглядит довольно сомнительно, и, по меркам других областей математики, является очень слабым утверждением, но на фоне того, что вообще известно о квантовой криптографии, и такое уже ого-го.

По аналогичной схеме, если она действительно окажется возможной, можно будет изготавливать всякие другие интересные объекты. Например, неподделываемые штуки-"подписи", которые в нормальной ситуации однозначно свидетельствуют, что документ подписали а) именно вы, б) именно этот (с точностью до бита) текст, в) именно такого-то числа такого-то месяца такого-то года. В предположении, что такой объект есть только у вас, подпись на документе абсолютно надежна, поскольку подделать или скопировать ее нельзя. К сожалению, объект-"подпись" можно будет у вас отобрать, используя грубую силу, после чего с его помошью "подделать" ваше согласие. Данная проблема, кажется, решения не имеет, если не запутывать квантовые состояния непосредственно с вами; но это пока совсем уж фантастика.

Насколько это все далекое будущее? Думаю, если с нами не случится сингулярность, лет сорок от момента создания работающего прототипа квантового компьютера, то есть где-нибудь 2050-2060 год.
plakhov: (Default)
"We describe the Maple [23] implementation of multivariate factorization over general finite fields. Our first implementation is available in Maple V Release 3. We give selected details of the algorithms and show several ideas that were used to improve its efficiency"

Зашибись, казалось бы. То, что мне и нужно было.
Запускаю Maple 11 (со времени написания статьи почти 15 лет прошло). Чисто в качестве теста вбиваю:

> Factor(x2+y2) mod 2
(x+y)2

Клево, работает! Ну тогда еще один небольшой тест:

> expand((x2+y+z2+x*y+z*x+y2+1)*(y2+1+x+z*x)) mod 2
1+y*x2*z+y3*x+y*x2+z2*x2+x3+y3+x2*z+x2*y2+x3*z+z2*y2+z2*x+z3*x+x+z2+y*z*x+y+x2+y4+y2*x

> Factor(%) mod 2
Error, (in F[Domains:-Output]) modp1: attempt to call modp1/domains/Modp1Polynomial/badge0 failed; function does not exist

Ну ваашу мааать...
plakhov: (Default)
Почти год назад я спрашивал: "В современных IDE есть такая удобная вещь, как умный autocomplete. В момент, когда он выбирает подсказку, то, с чем он работает - это ведь не код; это текст, похожий на код, но он некорректен. Но autocomplete все-таки понимает, о чем речь, и предлагает свои варианты, почти всегда правильно. Это просто набор хаков, или за этим все-таки стоит какая-то теория?"

Один из разработчиков IDEA ответил: "На самом деле, из недописанного кода отлично делается AST. Просто в некоторых местах этого AST висят маркеры "здесь ошибка - не нашли того, чего ожидали", которые никак не влияют на большинство операций".

А два года назад я писал вот что: "Описывать грамматику естественных языков при помощи каких-то расширений BNF оказалось крайне неэффективным занятием, и так никто не делает. Правильным способом оказывается совсем другой.

А именно, оказывается, что предложения в языке удобно разделять на два типа: "канонические" и все остальные. "Канонические" предложения абсолютно правильны: в них соблюдается четкий порядок слов, нет пропущенных или лишних слов и т.п. Например, предложение "Он пошел в лес" - каноническое, а предложение "В лес, вот куда он пошел" - нет.

Грамматика "канонических" предложений очень хорошо описывается при помощи BNF. Остальные предложения получаются из "канонических" набором трансформаций. Трансформация может поменять порядок слов, возможно, какие-то убрать, какие-то добавить. Трансформация может изменить смысл предложения, а может не менять (то есть, трансформация - не только грамматическое понятие, но и семантическое тоже)".


И сегодня наткнулся на статью, при помощи которой можно обобщить два этих случая на основе довольно простой теоретической базы. Расстояние Левенштейна между двумя строками формального языка - это минимальное число символов, которые нужно вставить, удалить, заменить, или переставить местами, чтобы из одной строки получить другую (несложно понять, что это именно метрика, то есть р. Л. симметрично, для него выполняется правило треугольника и т.п.) Пусть у нас есть некоторый формальный язык, слова которого заданы или в виде trie, или в виде распознающего конечного автомата. Тогда существует очень дешевый алгоритм, который по строке W и по числу N выдает все слова формального языка, находящиеся от W на расстоянии не более N. Здесь, правда, возникает ограничение на язык - получается, что он должен быть регулярным, что не особенно круто (тем более в случае IDE). Я не разобрался пока, нельзя ли этот алгоритм на халяву обобщить на следующие уровни в иерархии Хомского (ну скажем, вместо конечного автомата pushdown automaton какой-нибудь подставить), но на самом деле это на практике не очень важно: можно представить при помощи trie словарь всех слов языка вплоть до какой-то длины, а на все остальное спокойно забить.

Вот статья на citeseer.
(Перед прочтением статьи стоит удостовериться, что вы знаете все, что по этому поводу написано в википедии).

В нахождении косвенным образом помогли туториалы Юры Лившица, посвященные методу ближайших соседей, за что ему спасибо, если он вдруг это прочитает.

Так вот это все присказка была, а сказка в том, что вот когда поисковики/роботы научатся находить такие статьи (в том числе и особенно в междисциплинарном контексте) и оставлять ссылки на них в ответ на посты в блоге вроде моих (причем сразу, а не через два года), вот именно тогда-то сингулярность и наступит. Не раньше и не позже.
plakhov: (Default)
Здесь можно построить свой Яндекс, с блек-джеком и шлюхами.

Тем, кто занимается (или интересуется) машинным обучением, рекомендую заглянуть. Если что-то в формулировке задачи окажется непонятным - отвечу на вопросы здесь в комментариях.

У участников конкурса есть Данные, основанные на реальных событиях. Это некие признаки пары (запрос к поисковой машине, web-страница). Такие признаки вычисляются Яндексом в процессе обработки запроса, после чего на их основании наша яша решает, хорошо эта страница отвечает на запрос, и ее надо поставить на первое место, или плохо, и ее надо поставить на 82-ю страницу.

Такие ранжирующие признаки в Данных приведены для нескольких десятков тысяч пар (запрос, web-страница). Среди них есть что-то вроде PageRank, есть числа, имеющие смысл "насколько текст документа похож на текст запроса", есть классификаторы потенциального спама, ну и всякие другие числа, которые, по идее, в совокупности должны с какой-то точностью дать ответ на вопрос "насколько хорошо документ отвечает на запрос, и почему мы так считаем". Чтобы не раскрывать всякое мерзким поисковым оптимизаторам, в табличке, которую скачивают участники конкурса, приводятся "просто числа", без каких-либо объяснений. То есть нет ни текстов запросов, ни url'ов, ни названий признаков - только цифры. Примерно для половины пар приводится также оценка, которую паре выставил человек. Это тестовая выборка, по которой следует обучать свои алгоритмы.

В итоге каждой команде нужно придумать некую формулу или правило, согласно которому приписать каждой паре (запрос, документ) в тестовой выборке некоторое число (ранг). Документы затем ранжируются в соответствии с этим числом, и для каждого запроса получается "выдача". Ее качество оценивается: чем больше в топе разумных ответов, тем лучше. Нам всем тут кажется, что ранжирующие формулы лучше все-таки не "придумывать", а обучать при помощи тех или иных методов machine learning'а; но в принципе, правила не запрещают сделать все вручную.

В конкурсе побеждает тот, кто припишет парам (запрос, документ) числа, ранжирующие документы наиболее разумным образом.

Простейший подход - попытаться (при помощи регрессии или еще как-то) научиться "угадывать", какую оценку поставил бы человек данной паре. Но это вовсе не единственный, и даже не обязательно самый правильный метод. Мы тут в отделе качества поиска думаем, что знаем несколько способов, которые работают гораздо лучше. Можете попробовать нас разубедить.

Итак, последовательность действий:
1. Регистрируетесь
2. Скачиваете данные
3. Учитесь парсить их формат, смотрите на них "глазками", используете голову и разные мощные тулзы
4. ?????????????
5. Формируете результаты и отсылаете их (это можно делать несколько раз). Видите в режиме "почти реального времени" свою оценку и оценки других участников. При необходимости повторяете пп.3-5 любое количество раз.
6. PROFIT!

Бонусные хинты для тех, кто дочитал аж до сих пор.
1) Прежде чем кодить, почитайте интернеты, чтобы убедиться, что по крайней мере все термины, упомянутые в правилах, вам ясны.
2) Не переобучайтесь. Если оценка на learn'е улучшается, это вовсе не значит, что улучшится оценка на test'е. Даже если улучшается оценка и на learn'е, и на public-test'е, это все еще не говорит о том, что вы действительно научились ранжировать, а не обманываете сами себя каким-то хитрым образом. Если это вдруг так, то final test при подведении итогов это покажет. Если вы не знакомы с проблемой переобученности, см п.1
3) Не переусложняйте. Прежде чем перебирать утонченные ядра в экзотических вариантах SVM, попробуйте сначала какую-нибудь простую регрессию, ковариационный анализ, ну или кластеризуйте все по-быстренькому. Это недолго, а у вас появится и вменяемый результат, и baseline для понимания того, какой результат хорош, а какой не очень.
4) Некоторые переменные зависят только от документа (например, PageRank), некоторые - только от запроса (например, классификатор: "хотел ли пользователь найти порно"), некоторые - и от того, и от другого. Не игнорируйте это.

Удачи.

Update. Пропустили epic fail. В чем он состоял, не скажу, но данные пришлось поменять на новую порцию, соответственно, текущий рейтинг был сброшен. Смысл соревнования не изменился, новые данные доступны для скачивания, можно продолжать.
plakhov: (Default)
Не понимаю журналистов. Вот они выдумывают какие-то бредовые псевдосенсации, а между тем пару дней назад произошло событие, которое, конечно, станет главным как минимум в этом десятилетии - и о нем до сих пор нигде и ничего не пишут, даже в интернете, не говоря уж о традиционных СМИ. Еще неделька - и я начну верить в теории заговора.

Итак, два дня назад с информации о немоидах (они же skyseids) был снят гриф "совершенно секретно" (по крайней мере, в России). В результате каких непонятных игр это произошло прямо сейчас, а не через несколько лет, сказать не берусь, но это и неважно. Важно то, что теперь я могу написать подобный пост, и ко мне не придут люди в погонах. Я более чем уверен, что многие читатели уже знают, о чем речь (особенно это касается математиков и, возможно, биологов). Тем не менее, вообще говоря, раньше нельзя было даже узнать у кого-то, знает ли он, не разгласив государственную тайну. То есть все, конечно, понимали, что "тайну" и так знает полмира; взять хотя бы тот факт, что русская и английская транскрипции Шеннона совпадают с точностью до переобозначений - очевидно, не само собой так получилось; конечно, группы, которые их разрабатывали, делали это сообща. Тем не менее, все было типа как секретно, и даже до сих пор информация как-то не распространяется.

Итак, что мы знаем о немоидах? В общем-то, мало. Живут они сейчас в океане Европы; существует гипотеза, что это не первый их дом, и что они явились туда не так давно из-за пределов солнечной системы; нашего знания тоне (он же tasy) и их мировоззрения не хватает для того, чтобы однозначно интерпретировать их собственные утверждения на этот счет. Как может быть устроено общество высокоразвитых негуманоидных подводных обитателей, произошедших, предположительно, от стайных хищников, нам сейчас абсолютно неизвестно. Каков их технологический уровень в сравнении с нашим, мы тоже не знаем (но они явно не первобытные твари, раз могут посылать и принимать радиосигналы на расстоянии порядка 5 астрономических единиц). Какого черта они в 2004 вдруг стали беспрерывно болтать, хотя раньше хранили мертвое молчание, тоже неизвестно (собственно, упомянутая выше гипотеза опирается в основном на этот факт).

По большому счету все, что мы о них пока знаем - это их язык. Поскольку открытой информации по этой теме в интернете сейчас практически нет, я попробую дать пару первых уроков томо-тоне прямо тут.
Томо-тоне )

Upd. Комментарии скринятся. По понятным причинам я буду расскринивать только содержательные вопросы и дополнения. На комментарии вида "дай пруфлинк", "какова твоя роль в происходящем" и "ах, не завоюют ли нас" отвечать не буду, так что лучше сразу от них воздержаться.
plakhov: (Default)
Давно хотел об этом написать, наконец нашел время.

У меня вот уже ровно три года есть глупое хобби. Я пытаюсь придумать эффективный метод решения NP-полных проблем (если точнее, пытаюсь включить NP в Randomized P),. Те, кто знает, о чем речь, понимают, почему я назвал это хобби глупым, почему оно такое увлекательное, и почему бросить его очень сложно. Остальных кратко введу в курс дела.

Тэгами в этом журнале я условно "назначил" технологическую сингулярность (переход человечества в полубожественное состояние) на 2017 год. Это как-то подозрительно недалеко, да? Почему бы? Ведь закон Мура, кажется, перестал действовать (fj, я помню, что ты с этим не согласен, но сейчас это неважно); в освоении космоса и в фундаментальных медицинских исследованиях что-то ничего интересного не наблюдается; и не особенно человечество поумнело со времен античности.

Между тем вполне возможно, что человечество в его текущем состоянии от сингулярности отделяет меньше десятилетия.Далее... )
Page generated Jul. 25th, 2017 06:52 pm
Powered by Dreamwidth Studios