Исторические аналогии и их связь с выборами в России 2011-12 годов

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

1. Структура социального неравенства. В начале прошлого века было финансово благополучное, привилегированное сословие дворян-чиновников. С оговорками под эту аналогию подпадает номенклатура советской эпохи. И в наше время есть такое меньшинство и, причем, по самому неприятному совпадению это привилегированное меньшинство - тоже чиновники, а не предприниматели, как, скажем, в капиталистических странах. По данным Госстата чиновников в России 1,7 млн., и они, в отличие от предпринимателей, не производят ничего. Причем качество "материала" в смысле преданности интересам государства или лично первому лицу (тогда - императору, сейчас - президенту) просто несопоставимое и явно не в пользу современных чиновников. Перефразируя критику оппозиции в терминах математики, получаем, что целевая функция личной выгоды  произвольного чиновника зависит главным образом от двух факторов: 1) демонстрируемая (то бишь, показная) лояльность непосредственному руководству и 2) уровень собственного обогащения. Для того, чтобы проследить какие приложения находит эта модель, и как она влияет на экономику, деятельность тех же предпринимателей, эффективность управления - достаточно обратиться к передачам на радиостанциях "Эхо Москвы", "Радио Свободы" и независимой прессе. Фактологии у них предостаточно.
2. Сильный предшественник, слабый преемник. Так уж повелось в России, для того чтобы удержаться у власти правитель должен быть если не выдающимся государственным деятелем, то, по крайней мере, человеком, умеющим подбирать нужных людей, проявляя при этом политическую волю и избегая пагубного внешнего влияния. А иначе стоит только допустить ряд промахов в ответственный период времени, все летит в пропасть - страна, власть, народ, территории. И снова пугающая аналогия времен Российской Империи: Александр III,  "гатчинский пленник", державший Россию в необходимом "подмороженном" состоянии, и слабый потомок - Николай II. Следующий пример - долгая  эпоха Л.И. Брежнева, советского руководителя, до сих пор столь любимого среди людей старшего поколения, и крах Советского Союза на фоне политики неспособного действовать в интересах страны нерешительного преемника - М.С. Горбачева (краткосрочное правление Ю.В. Андропова, затем К.У. Черненко - не в счет). Что же сейчас? В.В. Путин - волевой президент, к политике которого масса справедливых претензий, однако его легитимность и личные качества сомнению не подвергались. И слабый преемник - Д.А. Медведев, который, согласно наблюдениям специалистов, мало влияет на сегодняшнюю политику государства за пределами твиттера и ЖЖ. Причем самое важное в этих уроках истории то, что слабые преемники уже объективно не могли справиться с лавиной проблем, которые создавались при их сильных предшественниках. Ключевой момент - сильные предшественники могли отсрочить приход революции, что в царской России, что в советское время. Но они, "заваривая носик у чайника", не проводили необходимых как воздух реформ или, точнее, политическую, социальную, экономическую модернизацию. Их слабые преемники уже не могли справиться ни с чем, и в этом смысле тяжелую ответственность за роковые сценарии развития страны разделяют оба типа руководителей. Роль личности в истории велика, но институты важнее в исторической перспективе, они переживают своих создателей априори.
3. Личное сходство персонажей. Здесь хотелось бы пройти по тонкому льду и указать на поразительные сходства людей без того, что бы задеть их чувства. Для начала то, что не замечал только ленивый - удивительное внешнее сходство Дмитрия Анатольевича Медведева и Николая II:

Д.А. Медведев

Николай II

Другое наблюдение из этого же ряда - у всех правителей были (или есть) достаточно яркие и  неординарные супруги: императрица Александра Федоровна имела известное влияние на императора Николая II; Раиса Максимовна Горбачева была заметным общественным деятелем и разительно отличилась от жен других советских руководителей хотя бы наличием публичного образа; наконец, жена Дмитрия Анатольевича - Светлана Владимировна Медведева также известна, как активный общественный деятель, и, даже с точки зрения обывателей, ее персона гораздо ярче предшественниц - Наины Иосифовны Ельциной и Людмилы Александровны Путиной.
Как вывод:
все это наводит на очень неприятные мысли в связи с президентскими выборами в России в 2012 году. Даже сейчас в 2010 году понятно, что особых альтернатив не предвидится: будет основная кандидатура Путина или Медведева. Недостатки второго прихода Путина на пост президента суммируют одним словом - "застой", которое отсылает к 18 годам (1964-82 гг.) правления Леонида Ильича Брежнева. При увеличенном до 6 лет сроке президентства после недавних поправок в Конституцию РФ в 2018 году (2012+6) Владимир Владимирович будет у власти фактически те же 18 лет, принимая во внимание все замечания по поводу несамостоятельности фигуры Д.А. Медведева. Посмотрим как обстоят дела в том случае, если в 2012 году станет президентом Медведев. Здесь вышеперечисленные исторические аналогии срабатывают почти мистически: конец предполагаемого второго срока Медведева аккурат ложится в столетие Февральской и Великой Октябрьской революций 1917 года. Причем весьма вероятно, что к этому сроку могут срезонировать две следующие опасные тенденции: 1) рост внутренних социальных противоречий, а также эскалация внешних угроз (усиления Китая, предполагаемое падение цен на энергоносители)  и 2) растрачивание способности власти адекватно реагировать на вызовы времени (просто за отсутствием компетентных кадровых резервов). Тогда мы получим очередной распад страны, который может просто поставить крест на историческом проекте под названием "Россия".
Тем не менее, выход, по ощущениям, есть: в России должен быть сильный и независимый парламент. Власть необходимо децентрализовать, должны быть ответственные партии, а не холуи, поставленные одобрять законопроекты правительства и президента, должен быть парламентский контроль за исполнительной властью. В этой связи, хотелось бы призвать граждан проявить интерес к политике в преддверие выборов в 2011 году в Государственную Думу Российской Федерации, грамотно оценить те партии, которые будут на выборах (или которых допустят - неважно). Помните, что ваш голос решает.

Отличные книги по теории и практике Computer Science

Не так давно начал параллельное чтение двух замечательных книг, имеющих отношение к теории алгоритмов и информационному поиску.

1. R. Motwani, P. Raghavan "Randomized algorithms" (Google Books)
2. C. Manning, P. Raghavan, H. Schutze "Introduction to Information Retrieval" (онлайн)

1. Классический учебник по созданию и анализу вероятностных алгоритмов на практике от Раджива Мотвани (научного руководителя С. Брина и Л. Пейджа, одного из самых выдающихся ученых в области Computer Science, трагически ушедшего из жизни в 2009 году) и Прабакара Рагавана (главы Yahoo! Labs и, по совместительству, преподавателя из Стэнфорда). Книга, которая заставит пересмотреть многие сложные детерминистские подходы к решению ваших задач, предлагая более простые, эффективные и не менее надежные алгоритмы.

2. Актуальный учебник по информационному поиску, в котором воедино представлены разные аспекты этой быстроразвивающейся области, - классический информационный поиск (булевский, векторный, вероятностный), методы машинного обучения, анализ структуры Веба и т.д.

А в Leo Wood можно посмотреть библиотеки на заказ.

Извлечение структурных элементов из Latex разметки

На днях закончил заниматься задачей извлечения структурных элементов из Latex документов. Суть в следующем:

1. Есть Latex документ.
2. Есть список структурных элементов.
3. Требуется определить вхождения элементов из списка в исходном документе.

На примере математических документов это выгляд примерно так:

1. Latex документ - научная статья из журнала или материалов конференции
2. Список структурных элементов - некоторое подмножество из онтологии OMDoc. Например, текстовые наименования таких концептов как Теорема ("theorem"), Доказательство ("proof"), Определение ("definition"), Следствие ("corollary") и т.д.

Наиболее прямолинейный подход - использовать Latex разметку, а именно - названия тэгов, и меры близости строк (название тэга - наименование концепта) для анализа. Древовидную модель исходного документа легко получить хотя бы на базе функциональности плагина Texlipse.  Правда, этот подход наталкивается на следующую трудность: в реальных документах названия тэгов часто сокращаются. Например, вместо
\begin{theorem}
...
\end{theorem}
можно увидеть конструкции с сокращенной (или измененной в общем случае) формой - thm, thms, thmnonum и т.д.
В этой связи естественно использовать алгоритмы близости строк, которые часто применяются в таких областях как интеграция данных, поиск дубликатов, биоинформатика и проч. Отобрал 7 наиболее распространенных:

1. Расстояние Левенштейна
2. Soundex
3. N-gram (c n=3)
4. Расстояние Jaro-Winkler
5. Расстояние Monge-Elkan
6. Алгоритм Needleman-Wunsch
7. Алгоритм Smith-Waterman

Природа алгоритмов довольно различна. Расстояние Левенштейна рассматривает количество операций вставки, удаления и замены, необходимых для совпадения строк; алгоритм Needleman-Wunsch приписывает операциям различную "стоимость"; алгоритм Smith-Waterman при этом использует соответствия стоимостей для всего алфавита;  Monge-Elkan различно оценивает стоимости операций согласно длинам несовпадающих подстрок ; Soundex использует звуковые коды символов; N-gram - количество общих n-грамм (чаще триграмм) или подпоследовательной длины n; Jaro-Winkler - количество общих символов при ослабленном ограничении на их позиции.
Реализацию этих и не только алгоритмов можно найти в библиотеке SimMetrics.

В результате анализа коллекции из 26 реальных научных публикаций получилась следующая интересная статистика. Основные показатели - точность и полнота в традиционном смысле.

1. Оптимальные значения мер по отношению к полноте

Levenshtein	0,29
SoundEx	0,77
N-gram	0,26
Jaro-Winkler	0,61
Monge-Elkan	0,34
Needleman-Wunsch	0,5
Smith-Waterman	0,29

Значения всех мер варьируются в диапазоне [0, 1]. При данных значениях получились следующие оценки точности и полноты.

2. Количество релевантных (R) и нерелевантных (N) пар, точность (Precision), полнота (Recall)

		R	N	Precision	Recall
Levenshtein		23	16	0,59	0,96
SoundEx		21	19	0,53	0,88
N-gram		23	4	0,85	0,96
Jaro-Winkler		23	16	0,59	0,96
Monge-Elkan		22	27	0,45	0,92
Needleman-Wunsch		14	38	0,27	0,58
Smith-Waterman		22	24	0,48	0,92

Выделены наиболее успешные алгоритмы. Безусловно, показатели N-gram алгоритма самые убедительные. Объясняется это, по всей видимости, следующими наблюдениями:

1. При именовании авторы склонны сохранять первые 2-3 символа в полном названии: lem - lemma; cor - corollary, assrt - assertion, defn - definition.
2. Из оставшейся части слова чаще выбрасываются гласные, чем согласные: proof - pf, thm - theorem.

Довольно очевидно, что первое наблюдение очень подходит для использования N-gram. В целом, точность на уровне 85% вполне приемлема для этого рода задачи.