Исследовательский инструментарий

Это первый из серии постов о программных средствах или сервисах, используемых мною для различных целей. В этом сообщении привожу обзор программных инструментов, которые упрощают (надеюсь!) повседневную исследовательскую работу.

1. Программирование
2. Обработка данных
3. Анализ данных
4. Работа с онтологическими моделями
5. Создание схем данных
6. Создание научных статей и презентаций
7. Поиск информации
8. Структурирование информации

Программирование

После нескольких лет метаний между ведущими средами для Java программирования - IntelliJ IDEA и Eclipse - все-таки остановился на второй. JetBrains тогда еще не выпустил community edition своей среды - это было одним из основных мотивов выбора. Да и с ростом производительности железа, имеющегося под рукой, прежняя медлительность Eclipse как-то перестала замечаться вовсе. А функционально Eclipse представляет собой, как известно, чрезвычайно мощную интегрированную среду разработки. Среди массы полезных плагинов выделю, пожалуй, следующие: Google Plugin (с поддержкой GWT, GAE), интеграция с Maven (импорт проектов, поиск зависимостей) и Subclipse (SVN).

Обработка данных

Для сопутствующих задач, связанных с чтением/трансформацией/записью (extract/transform/load - ETL) данных, использую Pentaho Data Integration CE. Этот кроссплатформенный инструмент содержит удобные средства для редактирования процесса трансформации с помощью графического интерфейса, а также позволяет читать/писать данные, работая с различными форматами (CSV, XML, Excel, СУБД). На рисунке - пример простой трансформации:

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


Анализ данных

Для анализа, связанного с обработкой естественного языка, пожалуй, ведущей платформой является архитектура GATE, основная мощь которой представлена в многочисленных плагинах: чтение данных разных форматов, токенайзеры, стеммеры, POS тэггеры, синтаксические анализаторы, работа с тезаурусом WordNet, онтологиями и много другого. Кроме того, удобный графический интерфейс, унифицированный формат аннотаций и система управления корпусами документов. Конечно, у всей функциональности имеется серьезное смещение в сторону английского языка, но, в принципе, сама по себе архитектура продумана очень гибко.
Для анализа данных средствами машинного обучения использую RapidMiner CE. Это мощное решение с реализацией широкого ряда различных моделей для обучения, тестирования, валидации, визуализации. Также имеется удобный графический интерфейс. Пример дерева процесса:

Некоторые алгоритмы из самых популярных в академическом мире библиотек, таких как Weka и R, также представлены в RapidMiner. Впрочем, указанные фреймворки заслуживают пристального внимания и сами по себе.
Еще одна мощная библиотека - LingPipe. В части компьютерной лингвистики функционал данной библиотеки пересекается с возможностями GATE (неслучайно существует LingPipe плагин для GATE). Но помимо этого, есть реализация и других интересных вещей: вычисление SVD (например, для латентно-семантического анализа), LDA (для задач кластеризации) и др.  Кроме того, поддерживается интересный блог и имеется набор полезных туториалов.


Работа с онтологическими моделями

Для этой цели лучше всего подходит редактор Protege. Среди его возможностей, поддерживаемых различными плагинами: просмотр/редактирование онтологий основных форматов (OWL, RDFS), загрузка механизмов логического вывода (DL reasoner), визуализация, редактирование правил логического вывода. Пример отображения иерархии классов:

Создание схем данных

Для визуализации графовых структур очень подходит язык DOT. Кстати, его используют в основе некоторые из уже приведенных программ. Например, Protege делает это через библиотеку Graphviz.  Ниже пример синтаксиса для простого ориентированного графа:

digraph relations {
Доказательство -> Теорема [label="доказывает"];
Теорема ->  Теория [label="принадлежит"];
Пример -> Теорема [label="относится"];
}

При наличии утилиты dot легко скомпилировать этот код в следующую картинку:

Естественно, DOT позволяет поиграться с цветами, формами вершин и ребер, вообщем, всячески настроить выводимый граф.
Для создания UML диаграмм очень подходит Dia, юниксовый аналог MS Visio (впрочем, согласно их сайту, имеется и версия под Windows). Здесь все просто: графический интерфейс позволяет редактировать атрибуты и операции, также нет проблем с экспортом диаграмм в различные форматы.


Создание научных статей и презентаций

Ни для кого не секрет, что LaTeX является де-факто стандартом языка для написания научных статей во всем мире, особенно это касается публикаций по естественным наукам. Более того, использование LaTeX зачастую диктуется самим процессом принятия материалов для публикации на уровне программных комитетов конференций или журналов. Можно привести пример стилевых файлов Springer LNCS или ACM. Традиционные преимущества LaTeX следующие: переносимость, расширяемость, поддержка математической нотации, механизм ссылок и цитат.
Что касается цитат, то их поиск - один из самых частых сценариев. Дело в том, что при создании LaTeX документов принято выделять цитаты в отдельные BibTeX файлы, где каждая цитата согласно своему типу (статья, книга, тезис, онлайн ресурс) представлена набором полей (ключ, автор, название, издатель, год публикации и т.д.).  Собственно, не так давно узнал о функции импорта цитат в Google Scholar (можно настроить в Scholar Preferences).  До этого искал по таким ресурсам, как DBLP, CiteULike и BibSonomy.
Безусловно, стоит отметить несколько пакетов LaTeX, которые особенно полезны при написании статей. Помимо традиционного AMS, выделяются:

• PGFPlots - создание графиков и диаграмм;
• algorithmic - форматированный вывод описания алгоритмов на псевдокоде;
• beamer - создание слайдов презентаций;
• todonotes - маленький, но полезный пакет для создания пометок.

Для редактирования меня устраивает Kile - TeX/LaTeX редактор для оболочки KDE с возможностями традиционной подсветки синтаксиса, механизмом автодополнения, WYSIWYG редактирования, быстрого просмотра скомпилированного документа и навигации по структуре документа.
В заключение отмечу еще вот это обсуждение по данной тематике. В ходе него перечисляется множество средств, далеко не все из которых удалось апробировать самому. Так весьма многообещающим выглядит использование распределенных систем контроля версий, таких как Git, в процессе колаборативного создания статьи. Это позволило бы работать с версионным репозиторием документов и в оффлайн режиме.


Поиск информации

Для поиска научных статей среди открытых и бесплатных средств особенно выделяется Google Scholar, который индексирует различные научные коллекции, находящиеся не только в открытом, но и ограниченном доступе. Помимо традиционного полнотекстового поиска по содержимому и метаданным документов, Google Scholar содержит неплохие дополнительные сервисы: поиск среди похожих статей или статей, ссылающихся на данную. Вообщем, это надежный, стабильно работающий продукт от мирового лидера в области поиска. Еще один тип ресурсов, который сейчас набирает обороты - это Q&A сайты. В известном смысле, они начинают составлять конкуренцию Wikipedia. Их принцип таков, что любой желающий может задать вопрос по соответствующей тематике и в довольно короткий срок получить адекватный ответ. У этих ресурсов есть продуманный механизм продвижения хороших вопросов и ответов, поощрения "экспертов" (людей, которые дают большое количество качественных ответов). Тенденция последних лет - это развитие тематических сайтов, посвященных, в том числе, научным или техническим областям. В частности, отмечу:

• MetaOptimize Q+A - машинное обучение и обработка естественного языка;
• Theoretical Computer Science - теоретические основания информатики;
• Stack Overflow - программирование.

Отдельный пункт - отслеживание актуальной информации в динамично развивающихся исследовательских областях. В этой связи, особый интерес представляют публикации R&D подразделений ведущих IT компаний. Ниже приведен список RSS каналов некоторых из них:

• Recent Google Publications
• Microsoft Research Publications
• Yahoo! Research
• IBM Research| Technical paper search | Last Thirty Days
• HP Labs Technical Reports

Структурирование информации

Для хранения материалов, документации и связанных заметок используется ПО на базе wiki технологии. Наверно, это самый простой способ хранить и аннотировать такую информацию. Также удобно, когда такой ресурс доступен онлайн на работе и дома.
С недавнего времени осваиваю технологию создания диаграмм связей (mind mapping). Например, бывает удобно фиксировать темы обсуждения или идеи из только что прочитанной статьи в форме таких диаграмм. FreeMind - вполне удобная программа, служащая этим целям. Пример диаграммы для одной из научных статей:

-------------

Пожалуй, все. А какие средства используете вы?

Рекомендую сайт для изобретателей, инноваторов и для тех, кто ищет партнеров и инвесторов для продвижения своих идей и ноу-хау.

Попробуй Guice на вкус

В этом посте хотел бы вкратце описать возможности одной полезной Java библиотеки от Google. Естественно, только те из них, которые использовал непосредственно.
Guice - фреймворк, заточенный, по сути, только под одну задачу, которая в русскоязычной Википедии называется несколько неуклюже: "внедрение зависимости" (dependency injection - DI). Аналогичную функциональность реализуют в своих подмодулях и другие фреймворки вроде Spring или Seam. Guice - облегченная версия подобных библиотек и его применение позволяет для необходимой функциональности не "тащить" за собой вышеуказанных монстров. Ниже, собственно, о возможностях Guice.

1. DI и модульность приложения
2. Элементы AOP
3. Unit тесты
4. Интеграция с Servlet API

DI и модульность приложения

Рассмотрим простой пример зависимости класса Main от некоторого функционала класса HelperImpl, реализующего интерфейс Helper.
UML диаграмма:

Helper.java:

public interface Helper {
void doSomething();
}

HelperImpl.java:

public class HelperImpl extends Helper {
public void doSomething() {
// useful code here
}
}

Тогда зависимость внедряется с помощью аннотации @Inject.
Main.java:

public class Main  {
@Inject
private Helper helper;
public Helper getHelper() {
 return helper;
} 
}

Контекст приложения инкапсулируется в Guice в так называемых модулях. Как правило, это наследники от класса AbstractModule. Связывание интерфейса с классом настраивается в методе configure c помощью вызова методов bind и to.
ExampleModule.java:

public class ExampleModule extends AbstractModule {
protected void configure() {
bind(Helper.class).to(HelperImpl.class);
}
}

В принципе, все готово. Остальное зависит от того, где в приложении поднимается сконфигурированный Guice контекст. Пока пример в случае консольного приложения (далее будут примеры сервлетов веб-приложения и Unit-тестов).
Application.java:

public class Application {

 public static void main(String[] args) {
  Application app = new Application();
  Injector injector = Guice.createInjector(new ExampleModule());
  Main main = injector.getInstance(Main.class);
  main.getHelper();
 }
}

К моменту вызова getter-метода поле helper будет проинициализировано.

Элементы AOP

Элементы аспекто-ориентированного программирования представлены в Guice, как минимум, механизмом "перехватывания" (interception). Рассмотрим, это на примере валидации параметра, передаваемого в метод. Пусть есть функционал по работе с пользователями, для исполнения которого необходимо проверять корректность передаваемых данных.
UserDAO.java:

public class UserDAO {
@ValidateUser
public void saveUser(User user) {
// a code to save user
}
@ValidateUser
public void deleteUser(User user) {
// a code to delete user
}
}

@ValidateUser - аннотация, на которую мы настроим объект-перехватчик.
ValidateUser.java:

@Target(ElementType.METHOD)
@Retention(RetentionPolicy.RUNTIME)
public @interface ValidateUser {
}

Код перехватчика будет проверять наличие id у пользователя.
ValidateUserInterceptor.java:

public class ValidateUserInterceptor
implements MethodInterceptor {

        @Override
        public Object invoke(MethodInvocation invocation)
        throws Throwable
        {
                Object[] args = invocation.getArguments();
  boolean isValid = false;
                for (Object arg : args) {
                        if (arg instanceof User) {
                                User user = (User) arg;
                                if (user.getId() != null) {
                                    isValid = true;break;
                                }
                        }
                }
  if (isValid) return invocation.proceed();
throw new IllegalArgumentException
("validation of user failed");
        }
}

Осталось настроить перехватчик на аннотацию в модуле приложения:
UserModule.java:

public class UserModule extends AbstractModule {

        @Override
        protected void configure() {
ValidateUserInterceptor validateUserInterceptor = new
 ValidateUserInterceptor();
                bindInterceptor(Matchers.any(),
Matchers.annotatedWith(ValidateUser.class),
validateUserInterceptor);
        }

}

Unit-тесты

Под Guice есть готовый фреймворк для написания Unit-тестов - MycilaGuice. Эта библиотека умеет самое главное - поднимать Guice контекст при запуске JUnit тестов. Делается это тоже с помощью аннотаций.
UserDAOTest.java:

@RunWith(MycilaJunitRunner.class)
@GuiceContext(UserModule.class)
public class UserDAOTest {
@Inject
private UserDAO userDao;
@Test
public void testSave() {
userDao.save(new User("1"));
}
@Test
public void testDelete() {
userDao.delete(new User("2"));
}

}

Интеграция с Servlet API

Наконец, Guice можно интегрировать в веб-приложение. Для этого необходимо создать класс-слушатель, который наследуется от класса GuiceServletContextListener.
WebGuiceContextListener.java:

public class WebGuiceContextListener extends GuiceServletContextListener {

        @Override
        protected Injector getInjector() {
                return Guice.createInjector(new WebModule());
        }

}

WebModule - модуль веб-приложения, где можно настраивать мэппинг сервлетов, не считая рассмотренных выше возможностей Guice модулей.
WebModule.java:

public class WebModule extends ServletModule {

        @Override
        protected void configureServlets() {
                serve("/webapplication/download").with(DownloadServlet.class);
        }
}

Осталось поправить конфигурационный файл веб-приложения web.xml и - бинго! - можно пользоваться всеми преимуществами Guice.
web.xml:

<web-app>
        <filter>
                <filter-name>guiceFilter</filter-name>
<filter-class>com.google.inject.servlet.GuiceFilter</filter-class>
        </filter>

        <filter-mapping>
                <filter-name>guiceFilter</filter-name>
                <url-pattern>/*</url-pattern>
        </filter-mapping>
        <listener>
                <listener-class>somepackage.WebGuiceContextListener</listener-class>
        </listener>

</web-app>

Посвящение учителю

Следующее стихотворение было написано мной в 2004 году как прощание с учителем для школьного "последнего звонка". Пусть будет опубликовано также здесь.

Вы кладезь мудрости открыли
И провели стезей добра,
Советником и другом были,
Но расставаться нам пора.

Печален я: так трудно мне прощаться.
Молю, что б повернулось время вспять.
От слез горючих мне не удержаться
И на ногах так трудно устоять.

Но память воскресила те мгновенья,
Когда прекрасный голос Ваш звучал.
Он чудо сотворил, он вывел из забвенья
И взор мой обратил к началу всех начал.

***
В интернет-магазине Центр Сейф - качественная продукция: оружейный сейф Aiko Кречет.

Исторические аналогии и их связь с выборами в России 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% вполне приемлема для этого рода задачи.

Встреча с П. Рагаваном

18 июня в 16.00 на кафедре теоретической кибернетики Казанского (Приволжского) федерального университета состоялась встреча с Прабакаром Рагаваном (Prabhakar Raghavan). Глава подразделения Yahoo! Labs в течение часа отвечал на вопросы участников и дал краткий обзор научных направлений, которым уделяется особое внимание в одной из ведущих интернет-компаний.

Прабакар Рагаван (глава Yahoo! Research) с визитом в Казанском федеральном университете

Затрагивались такие темы как: предоставление ученым больших объемов тестовых данных для исследований в области распознавания речи (проект Yahoo! Webscope); семантический поиск в математических коллекциях; принципы ранжирования поисковых результатов с применением аппарата машинного обучения; применение социологии при моделировании двухсторонних рынков; соглашение с Microsoft о сотрудничестве в области поиска в Вебе; подход Yahoo! для представления поисковых результатов; концепция Веба данных; научное сотрудничество; планы развития Yahoo! в России и др.
Фото встречи в альбоме на Facebook.
Текст новости на сайте лаборатории.

Поездка на Крит (Херсонниссос, Греция)

В продолжение предыдущего поста в этом опишу впечатления от самого места проведения конференции ESWC 2010 - о. Крит, поселок Херсонниссос. Первое, что замечаешь сразу, это количество русскоговорящих туристов. Подмечая такую тенденцию местные жители, преимущественно задействованные в персонале отелей, ресторанов, магазинов и прочих заведений, стараются немного говорить по-русски. А так большинство из них знают неплохо английский, многие - немецкий, благо туристов из Германии тоже немало. Также стараются дублировать многие надписи на русском языке, что иногда доходит до смешного. Как например, на этом рекламном стенде:

Из этой же серии: вертикальная надпись "ШУБЫ" с переносом буквы Ы как Ь и I. Причем русских туристов удавалось встретить как в моем 3-звездочном отеле, так и на обеде в 5-звездочном отеле конференции. Вообщем, все слои отдыхают так, что остается только порадоваться за них.
На экскурсии времени выкроить не получилось, поэтому в основном неформальные мероприятия связаны с походом в кафе и общению с коллегами. Одно из таковых заведений - кафе Argo на набережной, которое запомнилось представлением одного из официантов. Этот опытный человек умудрялся угадывать откуда посетитель с одной только фразы-заказа. Например, от меня потребовалось произнести только "orange juice", что бы он угадал, что я из России. Так в нашей англоязычной компании этот человек угадал трех немцев, двух финнов, двух русских и одну грузинку, ошибившись только единственный раз. Он же и познакомил нас с традиционной процедурой потребления ракии - местного самогонного напитка - с предварительным возгласом "Ямас!" Вообщем, эвхаристо ему за это:-)

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

Жара (немногим более 30 градусов) переносится легко, хотя пик достигается здесь все-таки позже, в июле. К часам пяти вечера уже заметно прохладнее и загорать можно без солнцезащитного крема.
Безусловно одним из популярных местных сервисов является сдача в аренду различной движимой техники - легковых автомобилей, скутеров, квадроциклов и т.д. Минимум проблем с оформлением страховки и прочего, остается только захватить права. Многие берут машину напрокат за 40-50 евро в день и успевают объехать многие достопримечательности, экскурсионная поездка на которые стоит заметно дороже. Тот же Кносский дворец всего в 20 минут езды отсюда.
Ну и, конечно же, море. Впрочем, море как море. Наверно, оно везде одинаковое. Стоит отметить, что пляжи на Крите муниципальные. И любой желающий может разложиться прямо на песке или с комфортом, арендовав шезлонг за несколько евро.

Наконец, завершая панорамой Херсонниссоса, можно подвести итог: Крит довольно уютное место, которое располагает как приятному отдыху, так и проведению интересных международных форумов.

Собираетесь путешествовать? Получите от меня скидку на Airbnb.

Конференция Extended Semantic Web Conference (ESWC) 2010

С 30 мая по 6 июня довелось побывать на о. Крит (Греция) в местечке Херсонниссос, где проходила очередная, седьмая по счету конференция ESWC (Extended Semantic Web Conference) - одна из крупнейших в области технологий Семантического Веба. Хотелось поделиться впечатлениями от поездки в двух аспектах - официальном (в данном посте) и неформальном (в следующем).

Итак, конференция проходила в пятизвездочном отеле Aldemar Knossos Royal Village.

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

Формат конференции предусматривал три секции докладов - исследовательские, представленные в свою очередь разными "дорожками" (Semantic Web in Use, Web of Data, Ontologies and Reasoning и т.д.); демонстрационные и отдельный блок - соревнование приложений (AI Mashup Challenge).

Наш демонстрационный показ (совместная работа с исследователями из Jacobs University Bremen - см. постер) состоялся уже вечером первого дня и прошел довольно неплохо: участники конференции подходили, интересовались, задавали вопросы о реализации. Правда, каких-либо существенных замечаний или пожеланий получить не удалось.

Тем временем, исследовательские доклады проходили в обычном режиме с жестким лимитом по времени (20 мин. + 5 мин. на вопросы). Из тех, что удалось посетить запомнились: доклад o LESS - функциональном языке и движке шаблонов для представления Linked Data на веб-страницах, в котором явно прослеживается аналогия с PHP и представлением содержимого баз данных; доклад "A Node Indexing Scheme for Web Entity Retrieval" о новом семантическом поисковике SIREn, его авторы также предлагают интересную двухуровневую адаптацию меры PageRank для облака Linked Data; любопытное исследование удобства пользовательских интерфейсов для формулирования поисковых запросов ("Usability of Keyword-Driven Schema-Agnostic Search").

Вне конкурса были презентации крупных проектов, поддержанных грантами Европейского Союза. Довольно любопытны такие инициативы как LarKC - платформа для распределенного выполнения "бесконечного" логического вывода, INSEMTIVES - инструментарий для автоматизации семантического аннотирования данных - одна из важнейших мотивационных проблем для перехода к Вебу нового поколения, SEALS - проект, посвященный оценке различных инструментов для создания и интеграции онтологий, семантических поисковых систем, средств логического вывода и т.д.

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