Tuesday, December 16, 2008

NLParser architecture

A typical NLP program faces lots of tasks. They include tokenization, lemmatization, dealing with word order, resolving ambiguities, building some structure, etc. The parser suggested here will deal with only one of those problems: word order. The task will be to convert token stream to the simplest structure, independent of it. It appears that functional composition is a perfect example of such a structure. For the sentence 'A kiss is a terrible thing to waste' this structure will look like

(is (a kiss) ((to waste) (a (terrible thing))))

or, in a more usual notation:

is(a(kiss))(to(waste)(a(terrible(thing))))

This would be the result of parser: just an expression, where some functions are invoked being passed another invocations' results as arguments. Functions can be of any kind, it depends of an interpreter. The parser may not only combine the tokens it gets into function calls, but also insert some auxiliary functions, e.g. to mark the missing word order info. In free word order languages like Russian where some meanings are expressed solely by word order this will be the case.

Basically the parser will deal with two interpreters. One will be syntactic, where the result of '(terrible thing)' will be almost the same as simple 'thing' (a noun phrase). This result will be used by parser itself, to help constructing the functional tree. The parser will known about all the possible values he syntactic interpreter could produce.

The syntactic evaluator will probably produce single result for any functional composition, i.e. it will not support alternative word meanings. The parser will probably concurrently support several different functional compositions until it can make a choice. It should also be able to rollback any choice it had made and reparse from that moment based on new information, if at some moment all the interpretations it has prove to be false.

The second evaluator will be of semantic nature, problem-dependent and replaceable. It will appear to the parser as a black box. It will be also invoked by the parser, but only to see whether an application (A B) will produce any results, i.e. it will have some semantic sense. The other thing we could do with anything is to compare by equality. So we'll see whether the results of two different compositions are in fact the same. For example, with several adjectives accompanying one noun it often doesn't matter in which order they go, so '(green (colorless ideas))' and '(colorless (green ideas))' will produce the same result in such tasks. This would mean that our parser won't have to maintain these two variants, one of them will be sufficient.

At each moment the parser is going to produce new function application, say, having A and B, to bind them via (A B), it evaluates '(A B)' syntactically and semantically. If both results are good, then the tree '(A B)' will certainly live further. In other cases, the parser has to choose the most promising variants from the set it has (remember, it maintains several concurrent trees). The variant that has only syntactic interpretation (but no semantic) will be better than the semantic-only variant. The variant having no interpretations will also have no chance of survival. Some psycholinguists say this is really similar to what the human brains do.

That's it, in short. The only thing left is to invent some semantics interpreter and implement this parser.

Thursday, December 11, 2008

Academic officers: top-down contextual ambiguity resolution

'The officers taught at the academy'. This sentence appears unambiguous to us until we are presented with an upgraded version: 'The officers taught at the academy were very demanding'. Functional structures for them will be:

(1) ((at (taught (the officers))) (the academy))
(2) ((were ((at (taught (the officers))) (the academy))) (very demanding))

These structures share common part, namely the whole first sentence. But this common part should be evaluated to different results: in (1) it would be complete clause - sentence, while in (2) it's only a noun phrase. So it appears that the first sentence should actually have two valid interpretations, but we've already understood it unambiguously!

This can be resolved by implying that the whole construction should always have clause type. So when we assume 'taught' having two alternatives and calculate the (1) expression value with both, we could safely remove the noun phrase since it can't be final result. This top-level clausal implication can be even explicated by introducing one more function here, whose name could be '.' (dot). The only thing for it to do could be just to filter clauses out of all its argument's alternatives. But there's another way.

Let's assume that every functional language expression has only one interpretation. It's simple and it looks like humans do the same. So when (1) is considered in its standalone version, it will be unambiguously a clause. But then it appears that the sentence is not finished, and we get 'were' applied to this complex expression, which can't take clauses as arguments. So we now have to evaluate (1) in a different way, knowing now that its context requires it to be noun phrase. It should be not hard to find another alternative of 'taught' that will suit these new requirements: a passive participle.

At the top, a clause type will be expected, on other levels it will depend on a particular function. Function 'were' will want a noun phrase (and so will 'at' and 'the' do), the resulting function '(were ...)' will need a gerund ('very demanding').

Technically, the evaluator has to get the context requirements from somewhere. We can't calculate the expression result part-by-part, starting with '(the officers)' and then applying other functions to it, we should have the whole expression in our hands. It also means that functions don't take arguments as eagerly computed values any more, they take arguments as data instead and evaluate that data by themselves in a right context. Hello, LISP's macros.

Wednesday, December 10, 2008

Time flies like an arrow: an ambiguity resolution example

Let's suppose we have to analyze a well-known ambiguous phrase 'Time flies like an arrow'. Here all three first words can be sentence predicates. Presented as a function composition, these alternatives will look as follows (in LISP notation, with function separated from its argument by space, both inside parentheses):

(1) 'Time' is a verb: ((like (an arrow)) (time flies))
(2) 'Flies' is a verb: ((like (an arrow)) (flies time))
(3) 'Like' is a verb: ((like (time flies)) (an arrow))

All of these applicative representations are self-disambiguating. Let's list the lexical word ambiguities. 'Time' can be either singular noun or a verb, 'flies' - plural noun or a singular third-person finite verb, 'like' - a verb or an adverb.

The result of '(an arrow)' occurring in all three alternatives is always the same, it means some object (it may be ambiguous, but the context doesn't provide more information, and the fact it's inanimate noun should satisfy us now).

We see 'time' being applied to 'flies' in the first and third variants. The result is ambiguous, it's either an order to time some flies (e.g. measure the time of their flight) or a description of some flies (maybe they fly through time from future to past).

If we exchange the function-argument roles, we get '(flies time)' from the second variant. Here the situation is better: 'flies' as noun doesn't have actants, therefore can't be a function, so only its verb-alternative remains. The latter also can't be applied to verbs in any way, so 'time' is noun there now, and '(flies time)' has clause type.

As for the '(like (an arrow))' construction, of course 'like' here can be an adverb describing the similarity of something to an arrow, but it can also be a verb. It can't be a usual narrative sentence predicate, since then it would require a subject, which should be passed to it as first argument by parser. And '(an arrow)' can't be this subject since it's 3d person singular requiring the verb to end with 's'. But 'like' here can still be imperative or infinitive verb. Both can't be applied then to clause '(flies time)', which disambiguates the second variant completely, giving the usual proverb about time which is flying too fast.

The verb 'like' also has only one direct object, which will be filled by '(an arrow)', so the resulting construction can't be applied to '(time flies)': we remember, it's either an imperative clause, or a noun phrase. This leaves only adverbial alternative for 'like'. It can modify only clause, so '(time flies)' must be really an imperative clause. Congratulations, we've disambiguated (1). We have to measure the flight time of some flies, and do this in a precise way, like an arrow, whatever this could mean.

Only the third variant is left. Here 'like' is applied to '(time flies)' and the result is applied to '(an arrow)' then. Imperative variant of '(time files)' can't be an argument of both verb and noun variants of 'like', and the noun 'like' doesn't have actants. This leaves us with verb 'like' eating noun phrase '(time flies)', which can be its subject when the verb is finite or its object when the verb is imperative or infinitive. An attempt to eat also '(an arrow)' then removes the non-evident imperative and infinitive alternatives, making this interpretation also unambiguous. We will know that all the future-to past flies are fond of some arrow.

Saturday, December 6, 2008

Статейко

Проект статьи про представление текста в виде композиции функций

Sunday, June 15, 2008

Comments

Поездили по Германии. Rezultoj

Friday, May 30, 2008

Развод

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

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

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

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

Saturday, April 19, 2008

Вредно

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

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

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

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

Thursday, February 7, 2008

Промо

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

Tanz der Vampire (Jim Steinman & Michael Kunze). Конечно же, Tanzsaal со Стивом Бартоном.

Норд-Ост (Иваси). Нарезка из тур-версии (трафик).

Billy Elliot (Elton John). Нарезка.

Rebecca (Sylvester Levay & Michael Kunze). Нарезка.

Whistle Down The Wind (Andrew Lloyd Webber & Jim Steinman). Тут отрывков из шоу в нормальном качестве нет, да и постановки неважнецкие, поэтому два концертных видео. Tire tracks and broken hearts с юбилейного концерта Лорда в исполнении Бонни Тайлер. Клип A kiss is a terrible thing to waste, поет Meat Loaf.

Elisabeth (Sylvester Levay & Michael Kunze). Нарезка под Mijn Leven Is Van Mij из голландской постановки с Пиушкой Дауэс.

Chess (Benny Andersson, Bjorn Ulvaeus, Tim Rice). Нифига. Только странная штука с одного из концертов.

Rent (Jonathan Larson). Из шоу опять же ничего, остается пара трейлеров к фильму.

Mozart! (Sylvester Levay & Michael Kunze) Нарезка из венгерской постановки.

Monday, February 4, 2008

Афихеть

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

И вот когда, наконец, в релизе еще один юзер заметил еще одну неподдерживаемую фичу в языке, я таки решил посмотреть, как же такую неоднозначную грамматику парсят сами создатели. Скачал исходники, нашел там парсер их Джавы, и... Что я вижу? Классы PrefixParser и InfixParser, метод ExprParser#parse с параметром-приоритетом, ну и вааще. Итого, они используют Пратта! При этом в коде он нигде не упоминается, но это типичный он. Ну, чуть измененный, притом не так, как у меня... Возможно, они его сами изобрели. Возможно, нет. Не знаю. Но сам факт!

Ложка дегтя. Так они парсят только Жаву. Сам аоп парсится обычным рекурсивным спуском.

Saturday, January 5, 2008

Развлекся

Есть у нас в Идее язык по имени QL, эдакая упрощенная версия SQL, диалекты которой используются в EJB и Hibernate. На вид несложный, однако в парсере периодически приходится туговато. Парсер, естественно, написан рекурсивным спуском, двумя с половиной разными людьми, и выглядит достаточно страшно. Я, в качестве добровольного каникулярного развлечения, попытался написать то же самое с использованием Праттовского метода. Тожесамовость измеряется duck-критерием: есть 141 тест, и на них нужно выдавать такое же дерево, что и старый парсер. В код старого парсера я смотрел нечасто, поэтому то, что незатестировано, соответственно, не воспроизведено.

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

Код парсера занимает меньше места: 1032 строки в старом против 620 в новом. При этом есть 14 стандартных постфиксных субпарсера и 21 инфиксный, все они выражаются здесь одной строчкой, в оригинальном парсере - побольше (строчек 5 в среднем, я думаю).

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

Теперь почему читать проще. Потому что поток управления проще. Интереса ради я сравнил количество управляющих ключевых слов, которые смог придумать. Итак:

keyword old new
------------------------------
if >107 57
else if 28 1
else 12 6
while (все) 16 15
while (true) 3 11 (типа простой цикл)
break 6 11
for (java 5) 0 3
return 65 35

Переменные 47 37
Вызовы mark() 28 13


Максимальный уровень блочной вложенности в новом парсере 4, в старом - 7 (к счастью, только в одном месте, в среднем же примерно одинаково).

Вообще, конечно, Пратту такое и не снилось. Он статью писал вообще-то даже не про парсеры, а про языки. Что если придумать язык, который таким вот парсером парсится легко и без проблем, то и человеку он будет совсем понятным. А когда нетерминалы не определяются одним-единственным токеном однозначно, то это есть плохо и непонятно. Отсюда мораль - QL - это не самый понятный для человека язык (согласен, особенно joins).