мне нужно сравнить два текстовых файла (каждый 1мил. слов), но я пока тестирую на небольшом кол-ве. Где моя ошибка, выдает мне $counter=1100 при сранении файлов, где только 2 слова одинаковы,надо, чтобы выдавало общее кол-во одинаковых слов, а не рез-т для каждой строки 

пробовала также с if ( index($zeile,$suche) > -1 ) вместо $zeile eq $suche

спасибо за помощь




Это сообщение отредактировал(а) LisaST - 13.1.2007, 11:11

LisaST, Ваша программа напечатала на самом деле не число 1100, а четыре раза по одной цифре, означающих, что первые две строки файла perltest.txt присутствуют в perltest1.txt, а следующие две - нет. Хотя весьма странно, как так смогло получиться, учитывая, что над строками второго файла был chomp, а над строками первого - нет: все строки должны были бы отличаться (за исключением, может быть, последней).

И еще не понятно, что в Вашем понимании означает "сравнить файлы".
Например, следующая программа подсчитывает кол-во строк файла perltest.txt, присутствующих в perltest1.txt.Это не то, что нужно?

Это сообщение отредактировал(а) amg - 13.1.2007, 11:59

спасибо за ответ, да я потом поняла, что обозначают цифры 1 и 0. задача у меня сравнить какие слова из файла 1 встречаются в файле 2 и подсчитать их кол-во (в файле 1 на строке может быть предожение или одно слово, а в файле 2 на каждой строке одно слово). первоначально идея была представить файл 1 как array и сравнивать его каждый элемент с каждой строкой в файле 2, но у меня все висло,т.к. я пыталась тестировать на 1 мил слов, потом потестировала на маленьком файле, но выдает то, что в моем первом посте вместо всего кол-ва одинаковых слов

сейчас попробую ваш вариант

Думаю в вашем случае нужно как раз наоборот...

Второй список загоняем в массив, и сортируем его, для скорости поиска.

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

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

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


Это сообщение отредактировал(а) Nab - 13.1.2007, 21:23

спасибо за помощь, я прогнала программу amg на оригинальном файле с большим кол-вом слов, число одинаковых слов было слишком велико, тогда я решила разбить файл, где есть предложения на токен (исключить все знаки препинания етц) для простоты сравнения (разделитель в обоих файлах \n), еще раз прогнала программу amg, теперь рез-т, мне кажется достоверен, мне одинаковые слова нельзя удалять,т.к. потом рез-т будет использоваться для recall и precision 

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

Не совсем понял по поводу повтора слов, хотя думаю так как второй файл скорее всего словарь, то там повторений то и нет. 

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

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

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

в общих чертах задача такая, я сравниваю performance 3 статистических taggers. Протестировала их на Browncorpus (> 1мил. токен). Есть также "goldstandard" корпус с тегами, на который я ориентируюсь при определении Recall i Precision.
1 проблема в том, что все теггеры используют разные тэги (для goldstandard их кол-во~85, а для других теггеров меньше). 

Сейчас я пытаюсь найти Recall i Precision для существительных. Я экстрагировала сущ. из моего tagged text и из goldstandard в 2 файла, теперь надо определить (грубо не затрагивая вопрос семантики), какие слова были определны верно тестируемым теггером, для этого просто хочу сравнить сущ. из 2 файла с сущ из 1 файла, но возникает проблема одинаковых слов, допустим одно и тоже слово встречается неск. раз в обоих файлах, каждый раз, когда в ф2 будте встречаться это слово- будут ли в counter  суммироваться все occurences в ф1 и так при следующем повоторе этого слова (или я не права? см. прог amg)

я так и разобралась, почему в меом вар-те counter не суммировал occurences, а выдавал boolishe значения?

спасибо

 

Упс, я конечно извиняюсь, но большинство употребленных Вами терминов мне знакомы, и перевод я их знаю, но в контексте они никак не вяжуться...  
Возможно для Вас они что-то и означают, но для простого программиста мало понятны 
Вы не могли бы изложить задачу по-русски, и желательно дайте определение, что Вы понимаете под терминами:
performance - производительность
tagger - чет не понятно, типа заметок? и про теги вообще в Вашем понимании...
Токен - нужно определение
Recall - повторный вызов (чего?)
Precision - точность (чего?)

И что такое goldstandart? Я подозреваю для Вас это имя собственное...

У меня такое впечатление что текст Ваших постов - это не полный, правленный перевод оригинальных текстов... 

sorry, если сумбурно получилось, простым языком выражаясь теггер, это программа, кот присваивает каждому слову текста соотв. часть речи (подготовительная ступень для linguistic parsing), есть различные теггеры, я тестирую те, кот. работают по принципу марковской модели (статистические теггеры), вот здесь описано хорошо http://en.wikipedia.org/wiki/Part-of-speech_tagging
precision i recall на русский не переводятся, вот тут нашла их описание http://en.wikipedia.org/wiki/Information_retrieval,
в общих чертах, надо определить "качество" теггера, основываясь на кол-ве верно определенной им информации....да, что-то запутанно получается...но вот, в общих чертах. теперь мне надо эти R i P для основных категорий слов (сущ, глагол, прил етц) определить

goldstandard, это файл, в котором теги каждому слову были присвоены мануально, т.е. P i R максимально приближены к 100% (простым языком, вероятность того, что часть речи определа верно очень высока), т.е. это как бы эталон, на который я равняюсь при анализе "моих" теггеров 

токен- просто слово

Это сообщение отредактировал(а) LisaST - 14.1.2007, 21:35

Потому что в Вашем варианте зануление и печать счетчика $counter делались для каждой строки. Нужно просто эти операции (зануление и печать) вынести за пределы цикла while (и обязательно убрать конци строк (chomp)). 

Другими словами, частота употребления словарных слов (файл 2) в тексте (файл 1)? 

спасибо большое на ответ на вопрос про $counter и особенно за предложенную программу. Возникает такая проблема, Файл 1 не совсем словарь, там слова тоже могут повторяться и, например одно и тоже слово может повторятся в Ф1 3 раза и в Ф2 4 раза, мне надо вклучить это в статистику...например сейчас , если в файле-эталоне 3 одинаковых слова, а в Ф2 4, то каждый раз, когда будет происходить сверка со словарем все 3 occurences будут суммироваться или нет?
 

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

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

пример результата:


всего  uniq слов 25615, по идее это очень мало, плюс всех слов с повторениями 528720, тоже странный результат, с Вашей первой программой получилось 259227 существительных,что довольно приближено к истине, тогда для Precision i Recall получаются нормальные результаты.

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

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

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

Итак, описание.

Пусть:

W - множество тестируемых элементов - слов. p(W) - количество (число) элементов в этом множестве. Двух одинаковых элементов-слов во множестве нет, Будем считать, что, если мы во множество добавляем элемент-слово, которое уже было в этом множестве, множество не изменяется (классическое опредеделние множества).

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

tagger() - некая процедура, которая для всякому (любому) w из W ставит в соответствие некий один c из C. Или, говоря, по-русски, для каждого слова (из тестируемых слов) определяет, к какой части речи оно принадлежит. Или, вернемся к математике, каждому w из W ставит в соответсвие двойку (w, c): w -> (w,c)  (здесь снова не список-массив, а обозначение упорядоченной двойки! будьте внимательны, господа программисты!)

Как работает эта процедура внутри - да нам по-барабану! Самое главное - ставит в соответсвие и все!

goldStandart - а это вот супер-таггер! Он не только ставит в соответствие (т.е. по сути является тэггером), но и делает это ПРАВИЛЬНО. Мало того, он должен быть определен для каждого w из W или, говоря по-русски, раз уж ты супер-тэггер - будь добр, выдай правильный результат для любого слова из нашего словаря.

Что же такое качество тэггера? Осмелюсь предположить, что это некое отношение кол-ва правильно определенных частей речи (для каждого w из W) к общему кол-ву вариантов, или, что то же самое, к кол-ву элементов-слов в нашем множестве W или p(W). Вспомните мое замечание про то, как мы условились определять разные элементы во множестве!

Как определить правильность работы тэггера для каждого конкретного слова? Да просто! Сравнить двойки, которые породил наш, исследуемый тэггер и goldStandart. Если эти двойки равны (т.е. первые элементы двоек и вторые элементы двоек попарно равны между собой - вспомните определение равенства векторов из математики!), то наш тэггер выдал правильный результат - ему плюс!

Считаем кол-во правильных вариантов, делим на число слов в исходном массиве - получаем характеристику тэггера.

Все. Славно, правда?

LisaST, на уровне описания модели все правильно?


Это сообщение отредактировал(а) Zuzu - 19.1.2007, 15:44

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




tagger_to_test.txt

goldstandard.txt

Стоп!

Где указано, к какой части речи принадлежит каждое слово?  tagger, по описанной выше модели должен сопоставить слову часть речи! Или tagger выбирает из исходного множества слов только те слова, которые он считает существительными (а про остальные слова нам ничего не скажет) и записывает в файл? В проектировании ПО это называется нарушением начальных условий и обычно приводит к неверному результату работы ПО. Как и здесь, собственно, произойдет.

Поясню.

Мы вообще правильной оценки работы tagger'a не получим! Я опираюсь только на описанную выше модель и элементарную математику. Приведу пример:



LisaST, опиши, пожалуйста, как получаются представленные тобой файлы. Может я чего неверно понял/ 

P.S. LisaST! Я ушел достаточно далеко от твоего алгоритма и того вопроса, который ты задавала. Если это тебе здесь не нужно, а нужно просто помочь решить (запрограммировать) конкретную задачу сравнения двух файлов по какому-то алгоритму - скажи, мне, пожалуйста, об этом. Никто не обидется!




Это сообщение отредактировал(а) Zuzu - 19.1.2007, 11:36

то, что находится в 2 тестируемых файлах - это только сущ.(были помечены теггерами как сущ), кот. я экстаргировала из текста,обработанного теггером, смотри пример, вот их кол-во и надо сравнить, потом я экстаргирую глаголы, прил. етц. Пример: 1 программа амг посчитала, что одинаковых слов в файлах с сущ 259227, по формуле получается, что Precision 0.93, а Recall 0.96 для моего тестируемого теггера, но я просто сомневаюсь насчет одинаковых слов (см мои посты выше)

iz goldstandard.txt

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

Мысли одну от другой лучше отделять абзацами - так понятнее.

Прости за замечание. Правда, очень тяжело твои тексты читать - я же не лингвист!

А теперь к делу.

LisaST, давай подождем с экстрагированием, а? (т.е. c извлечением из всего массива слов только тех, которые tagger пометил, как существительное, в частности). 

Итак, ура! Двойки есть. Двойки от goldStandart! Очевидно, подобный файл есть и от испытываемого tagger'a? Да?

1. LisaST, напомни пожалуйста, что такое 
Precision 
Recall

(одним словом, можно формулой, например: Precision = good_words / all_words, где good_words - количество правильно определенных слов, all_words - общее количество слов в нашем множестве.

Чтобы проверить, правильно ли это считает программа amg, нужно знать их определения (формулы).

2. Выходит, я зря потребовал отношения порядка на нашем множестве слов W. Из приведенных примеров мне стало видно, что оно нам не поможет в оптимизации. А жаль. И неверно определил, какие слова на нашем множестве необходимо считать разными. Будем пользоваться классическим определением. Если слово "собака" встречается два раза, то это одно слово. Каюсь, был неправ. Испправлю в своем первом топике.

было: 


С правильным определением множества исчезнут проблемы в повторяющимися элементами. Исчезнут на корню! Поверь!


Это сообщение отредактировал(а) Zuzu - 19.1.2007, 15:48

sorry, если непонятно, сложно аналог каких-то терминов podobrat'

ответы на вопросы:

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

- если одно слово встречается 2 раза, то  нужно это учитывать

- формулы расписываются след. образом:
N - число одинаковых слов (помеченных как сущ в нашем случае) в Ф1 и Ф2 
G - число слов, помеченных как сущ в goldstandard
C - число слов, помеченных как сущ в тестфайле (обработан теггером, кот. я тестирую)

Precision = N/C     Recall =N/G
проясняет ситуацию?

LisaST, спасибо за ответ.

Заставило задуматься. Думал, ответ (в виде готовой программы) найдем уже сегодня. А вот нет... Появляются новые артефакты... Формулы заставили задуматься... Если так, модель определена не совсем корректно.

1. Можешь ли ты указать взаимно однозначное соответствие обозначений в файле-результате работы taggera и в файле от golgStandart? Хотя бы для тех частей речи, которые тебя интересуют. 

Пример: 
Пусть в файле, полученном в результате работы tagger'a части речи обозначены по-русски, тогда, сможешь ли ты указать взаимно однозначное соответсвие между ними в виде например:

артикль - at
глагол   - vb
глагол_в_прошедшем_времени - vbd

2. Может взаимно однозначного соответсвия совсем нет? 

Например, tagger помечает все существительные, а goldStandart различает существительные множественного и единственного числа.

3. Тебе для оценки таггера нужно объединить глаголы прошедшего времени с глаголами настоящего времени (назовем их просто_глаголы) или они должны быть разделены?

Пожалуйста, расскажи, как ты эти вопросы (1. 2. 3.) решила на этапе экстрагирования - извлечения нужных данных.

4. Если не трудно, кусок файла - результата работы taggera.

.... Еще пара вопросов будет по формулам... Чуть позже....

LisaST, вот еще одна программка, может, пригодится. Она вычисляет 8 чисел: общее кол-во слов и кол-во уникальных слов в файлах goldstandard.txt и tagger_to_test.txt, а также те же самые величины, которые получатся после того как из этих файлов убрать общие слова (с учетом повторений). Может, из этих величин Вам удастся вычислить какие-нибудь Precision и Recall.

LisaST, давай вернемся к формулам. 

Пусть хороший tagger (good_tagger) выдал:

Мама/сущ. мыла/гл. раму/сущ. ./.  Мама/сущ. любит/гл. Лизу/сущ. ./.

goldStandart выдал:

Мама/сущ. мыла/гл. раму/сущ. ./. Мама/сущ. любит/гл. Лизу/сущ. ./.

(я не ошибся с частями речи? мои знания - только из средней школы, а это было давно!)

bad_tagger выдал:

Мама/сущ. мыла/гл. раму/гл. ./.  Мама/сущ. любит/гл. Лизу/гл.  ./.


Посчитай (на бумажке, пользуясь только определениями) значения N, G, C,  всех разумных частей речи (сущ., гл.) для случая good_tagger + goldStandart и bad_tagger + goldStandart. Всего должно быть 12 чисел 

Это сообщение отредактировал(а) Zuzu - 20.1.2007, 14:43

LisaST, Стоп! Не нужно ничего считать! Но этот пример нам понадобится!

Секунду, дамы и господа! По второй ссылке, указанной LisaST, (  http://en.wikipedia.org/wiki/Information_retrieval)  сходить настоятельно рекомендую тем, кто интересуется работой всяких поисковых движков (типа яндекса, например)! В статье теоретическая чаcть всего этого, описанная на нормальном, математическом языке. Это круто!

Надеюсь сегодня у меня будет время прочитать и понять это и адекватно задать вопрос.

Вот еще славная ссылка, тут все объяснено на картинках:

http://www.hsl.creighton.edu/hsl/Searching...-Precision.html




Это сообщение отредактировал(а) Zuzu - 20.1.2007, 17:50

да, ты прав, полного взаимного соответствия нет, в голдстандард примерно 85 тегов, а в тестуруемом файле намного меньше, но различие по мн и ед. числу сущ существует. 

Я эту проблему никак не решала, т.к. это бы неймоверно усложнило задачу, я просто экстрагирую все! виды сущ из обоих файлов не разделяя их по группам, конечно будут какие-то отклонения, например, если тег в test.txt определен неверно kak сущ и это был глагол с s на конце и это слово совпадает с сущ мн/ч в goldstandard.




глаголы я пока еще не экстрагировала, но тут задача будет посложнее, чем с сущ, т.к. надо подумать, разделить ли например обычные гл. и гл to be, т.к. в голдстандард почти для каждого вида гл. существуют разные теги. 


test.txt

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

LisaST,  

1. Напиши, пожалуйста, описания (тэги) для существительных для нашего тестируемого таггера и для goldStandart

должно быть что-то типа:

tagger:  сущ1 сущ2 сущ3 суще
goldStandart: susch-1 su_1 s===

2. Как принято поступать со словали (английского языка - его немного знаю...) которые могут быть разными частями речи и goldStandart честно об этом должен сказать.

Например: 

Computer (прил.) system -  Компьютерная система
My computer (сущ.) - мой компьютер

Или в английском языке computer - всегда существительное, вне зависимотси от контекста? И goldStandart так и скажет?



Это сообщение отредактировал(а) Zuzu - 20.1.2007, 16:10

на этом примере ничего не удастся определить, т.к. для расчета P i R требуется большая выборка.

В этом случае для bad tagger получится P = 1, R = 0.5, но это не показательно, т.к. чем больше текст, тем тожнее можно определить P i R.

 


  

для goldstandard


http://www.comp.leeds.ac.uk/amalgam/tagsets/brown.html
------------------------------------------------
для testfile немного видоизменненный

http://www.ims.uni-stuttgart.de/projekte/C...TreebankTS.html




это будет зависеть от контекста, т.к. goldstandard был проверен вручную встречаются оба варианта, хотя Executive тоже может быть сущ, а state прил. Обычно такие проблемы решаются в теггерах с помощью вероятностей, напр вероятность, что перед сущ стоит артикл' выshе, чем для прил. и это учитывается в процессе обработки текста, но в моем случае это не суть важная проблема

Executive/jj-tl Committee
State/nn-tl Welfare

Страннно, по определениям описанным в указанных тобой источниках, у меня получилось:

Для существительных: Recall: 33,33% Precision: 100%
Для глаголов:  Recall: 100% Precision: 66,66%

Мы пользуемся разными формулами?

Для существительных: 
Recall:  есть отношение кол-ва правильно выбранных tagger'ом существительных к количеству всех существительных в нашем множестве (сколько сущ. показал goldStandart).

Presision: есть отношение кол-ва правильно выбранных tagger'ом существительных к общему кол-ву сущ., которые выбрал tagger

( http://www.hsl.creighton.edu/hsl/Searching...-Precision.html )






В определение Recall и Precision включено понятие релевантности, т.е. правильности выбора. Как ты решила определить правильно ли испытуемый tagger определил слово Computer, например. Он говорит, что это сущ., а в goldStandart - сущ и прил. ?

LisaST, про формулы. 

Эти определения полностью эквивалентны (я проверял) описанным в 
( http://en.wikipedia.org/wiki/Information_retrieval )

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


Это сообщение отредактировал(а) Zuzu - 20.1.2007, 18:02

мы пользуемся одинаковыми формулами, 

у меня Precision dlja "bad tagger" = 2/2  Recall = 2/4, (4 здесь число сущ в goldstandard)



проблема в том, что я могу определить релевантность с точностью до 100% только вручную, но на текстах в 9 мегабайт это нереально. Поэтому тот алгоритм сравнения, кот. я хочу использовать довольно "груб", но пока ничего лучшего в голову не приходит. 
Напр, если в голдстандард комьютер встречается 4 раза и 3 раза определен как сущ, а 1 раз как прилагательное, а тестируемый теггер определили этоже слово как сущ 4 раза, то при сравнении должно получится, что в тестфайл на 1 occurrence of computer больше (будет учитываться в знаменателе Precision формулы)

LisaST, 


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

Еще пара вопросов:

1. Можно ли понятие "контекст" определить, как "взаимное расположение текущего слова по отношению к другим словам в тексте".

2. Реально ли взять текст от goldStandart (как вариает, убрав из него все тэги) и "скормить" tagger'у, чтобы онн выдал результат по такому же тексту, как и goldStandart?

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

Если нет, никакого нормального результата ты вообще не получишь! Грубо говоря, нужно скормить текст tagger'у и goldstandart и только затем сравнивать файлы!  В обратном случае, сомневаюсь, что по случайным, даже большим выборкам, можно получить правдивый результат. Т.к. из четырех чисел, участвующих в формуле, только одно значение (а именно, кол-во слов, которое наш tagger считает сущ.) можно определить. Слишком велика неопределенность, чтобы говорить о достоверном результате.




Это сообщение отредактировал(а) Zuzu - 22.1.2007, 13:21

1. можно

2. так я только потому и могу применять такое грубое сравнение , т.к. это один и тот же текст (голдстандард берется , т.к. в нем теги определены почти на 100%верно), только обработанный разными теггерами, по-другому вообще невозможно было бы определить что-либо

LisaST, понятно. Не сочти за нудность, но ответь, пожалуйста, на второй вопрос в другом, более сторогом математическом варианте.

Т.е. реально можно считать, что таггеру и goldStandart "скармливается" в точности один и тот же текст. 
А именно:

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

2. Слова в первом тексте идут в друг за другом в одном и том же порядке (т.е., если пронумеровать слова с начала текста от 1 до N, где N - общее количество слов, для всякого n от 1 до N word1(n) = word2(n). Так?

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

P.S. Я думал дела обстоят намного хуже и тексты разные! На одном и том же тексте можно применить абсолютно точное сравнение!

P.P.S. О разном множестве тэгов, генерируемым taggeром и GoldStandart можно не беспокоится. Простой кусок кода, приведенный ниже,  решит эту проблему. С помощью хэша. Таги приводятся к тому типу, который нужен! Уменьшить кол-во значений множества - не увеличить. Это задача проста до тривиальности.



P.P.P.S Держись! Осталось совсем немного!

1. авторы голдстандард утверждают, что у них использовался brown corpus , я пользовалась им же, только когда до обработки я удалила все пустые строки из голдстандард, там все-равно было на несколько сотен строк больше, но мне кажется из-за некоторых небуквенных знаков типа "./." , которые в их варианте были помещены на отдельную строку, я конечнно могу удалить из обоих текстов все знаки кроме слов и сравнить кол-во слов еще раз для проверки.

2. нет, этот большой текст состоит из отдельных рубрик и порядок расположения "кусков" текста неодинаков  в моем тексте и голдстандард

3. но если, например, экстрагировать все сущ в отсортированном виде, то должны получится файлы, подходящие для сравнения или?

не совсем поняла, здес'

 мы печатаем все теги через "-->" ?

LisaST, 

1. Вопрос: tagger - это такая программа (или механизм, web-интерфейс и т.п.), который тебе доступен. Ему можно скормить любой текст и получить результирующий текст, им обработанный (c тэгами, расставленными tagger'ом после каждого слова), так? Если так, то можно просто взять текст от goldStandart?

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



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

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

Про мой код. 

Он "сузит" определения существительных. Про те части речи, которым его "не научили", вернет "undefined". Вот результат работы:



P.S. Понятие "артефакт" в определении Рационального Унифицированного Процесса (проектирования и разработки ПО, в частности) есть закон, описание, модель, документ и т.п. - нечто описывающее определенное понятие предметной области.

Это сообщение отредактировал(а) Zuzu - 23.1.2007, 16:36

1. 
это программа, внизу ссылка на первый из тестируемых теггеров, текст можно "скормит" любой на англ языке, для других языков надо тренировать модель. Использовать голдстандард очень хорошая идея, только надо удалить все теги (~85) и затем тестировать. 

crf Tagger

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

LisaST, все! Наступило счастье! Все сложилось в стройную, математически правильную модель!

(ссылку не смотрел -  достаточно того, что ты сказала, что это возможно)

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



Во-вторых, составь (на листочке) соответствие между "разными тэгами", для tagger и goldStandart. Для замены "многих тэгов, на один нужный". Для всех интересующих тебя частей речи. Запись не имеет значения. Достаточно, чтобы тебе было понятно.
Типа: 

tagger: (сущ-ед-числ, сущ-мн-числ) => сущ.
goldStandart: (существ-ед, существ-множ) => сущ.

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

Это то легко сделать. Чтобы заменить разные виды тегов, можно из командной строки исполнить При этом, например, все NNP, NNS и NNPS заменятся на NN и результат запишется в new_file.pos (нужно только заменить одинарные кавычки на двойные, если у Вас Windows). Проделать эту операцию с двумя файлами, полученными от разных теггеров над одинаковым текстом (если у теггеров обозначения тегов разные, то модифицировать регулярные выражения, чтобы результат получился единообразным). Затем, чтобы сделать построчное сравнение, просто напустить на эти файлы команду diff (это в *nix, в win* не знаю, как она называется, есть соответствующие модули для Perl). 

Это сообщение отредактировал(а) amg - 24.1.2007, 12:55

...

P.S. Для нетерпеливых подскажу "сырой" алгоритм сразу:

1. Считывать слова и тип строго по одному из каждого текста.

2. Для считанного слова приводить его тип к каноническому виду
3. Релевантность опрелелять по простому равенству канонических типов. (получим  кол-во правильно определенных таггером слов для каждого типа)
4. Прибавить 1 к кол-ву кол-во слов определенного канонического типа для таггера (в итого получим общее кол-во слов для определенного канонического типа, которое определил таггер)
5. Прибавить 1 к кол-ву слов определенного канонического типа для goldStandart (в итого получим общее кол-во слов для определенного канонического типа, которое определил goldStandart

6. Считать еще по одному слову и его типу из каждого файла, перейти к п.2

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

7. посчитать Recall Precision для каждого канонического типа слова
8. Выдать результат.

Итого - все значения для всех канонических типов слов за один проход сверху вниз по двум файлам. Как вам, а?



Это сообщение отредактировал(а) Zuzu - 29.1.2007, 10:55

алгоритм makes sense. спасибо. тебе потребуется список соответствий наподобие

tagger: (сущ-ед-числ, сущ-мн-числ) => сущ.
goldStandart: (существ-ед, существ-множ) => сущ.

у меня есть такое соответствие для сущ, теги, используемые в голдстандард немного отличаются от тех, кот. я дала по ссылке "amalgam". 


Я думаю определять Precision i Recall для основных категорий, сущ, глагол, прилагательное, предлог, наречие, для всех , кроме сущ надо составить соответствия. 

- кроме этох категорий еще есть множество тегов, кот. не будут учавствовать в анализе, напр. вопросительные слова who, whom, числительные етц, их программа будет пропускать?

- не совсем поняла, что имеется ввиду в п.4 и 5 под прибавить 1.

- в п. 7 имеется ввиду, когда все слова в обоих текстах были считаны? (в принципе Precision i Recall можно определять при 20% 40% 60% етц считанного текста, тогда можно построить график изменения этих величин по отношению к увеличеню выборки слов), но я думаю для простоты лучше определить их для всех слов, принадлежащих к опред. категории


-  с вашими перл regex выражениями я удалила почти все теги, но такие вещи как ?!" не удалились, теггер им тоже присваивал тег: например ./.  ?/? "/" етц

- ещё проблемы
т.к. в голдстандард намного больше тегов и ещё такого типа как
ppss+bem:    pronoun, personal, nominative, not 3rd person singular + verb "to be", present tense, 1st person singular

т.е. глаг + местоимение связаны, то что расценивать как эквивалент в тестируемом теггере, в кот. нет таких объединённых тегов
  конечно, можно их просто анализировать как местоимение, но тогда в голдстандард не будет защитан этот сокращенный глагол to be 


Это сообщение отредактировал(а) LisaST - 25.1.2007, 01:28

LisaST, сначала отвечу на вопросы.

Определение соответствия между тэгами - твоя, как специалиста-лингвиста, забота  Я пока выступаю в роли аналитика и мне, как аналитику, достаточно знать, что такое соответствие есть. 

Тебе здесь, к сожаленю, ничем помочь не могу. Я просто не знаю предметной области. (Если у кого-то складывается обратное впечатление, когда я пользуюсь терминами типа Recall и Precision - оно обманчиво! Я пользуюсь только теми понятиями, которые ты мне сообщила! При этом стараясь изо всех сил не увеличивать объем своих знаний в области лингвистики - так быстрее будет найдено решение! )



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

Пусть tagger (неверно) определил "двадцать"  как глагол, в то время как goldStandart это слово (правильно) определил как числительное. Пусть числительные нас не интересуют. 

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

Как бы ты анализировала это результат "руками"? Наверно так, в три шага:

1. В рамках модели (а именно, для определения Recall для глаголов) необходимо посчитать сколько слов в тексте наш tagger определил как глагол. Наш tagger определил слово, как глагол. Поэтому к количеству глаголов, которое определил tagger в тексте, прибавим 1. Идем дальше...

2. По идее, если бы мы считали числительные, нам нужно было посчитать (для определения Precision числительных), сколько реальных числительных у нас в тексте. Но числительные нас не интересуют - значит информация о том, что в тексте найдено реальное числительное (слово-то goldStandart определил, как числительное!) просто теряется. Ничего никуда не прибавляем... И последний шаг...

3. Для определения и Recall и Precision глаголов необходимо знать, правильно ли tagger определил слово, как глагол. Он определил неправильно, т.к. то значение (типа слова), которое он выдал не совпадает со значением от goldStandart. Единичку к кол-ву правильно определенных tagger'ом глаголов прибавлять не будем. Все, со словом разобрались. Можно переходить к другому слову.

Собственно, это и написано в "сыром" алгоритме. Написано, но не описано, поэтому он и назван "сырым".

Аналогично, если хочешь, можешь самостоятельно рассмотреть три других случая (глагол-глагол, числительное-глагол, числительное-числительное). Случаи аналогичные.



Думаю, после ответа на предыдущий вопрос, стало все понятно 



Легко! Этот исходный артефакт (дополнительное условие) усложняет задачу только на этапе реализации! Математической модели не противоречит ни вычисление Recall и Precision на любом этапе обработки слов, ни постороение графиков, ни занесение этих промежуточных результатов в базу данных, ни что либо еще, связанное с извлечением результатьв в любой момент обработки! Мы же имеем дело с множеством, на котором определено отношение порядка! 
Как это решить - задача проектировщика, а скорее реализатора, а не аналитика.  




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

Если бы я, как реализатор, удалил знаки припинания, ты, как лингвист, могла бы мне сазать: "Дорогой друг! Ты удалил все знаки препинания! У слов, в связи с этим поменялся контекст и, как результат, весь мой труд по опредеделню качества таггера пошел коту под хвост! Это, по крайней мере, обидно..."



Не совсем понял, т.к. в грамматике английского не силен, но этот артефакт настораживает, т.к. потенциально может нарушить целостность математической модели. Приведи, пожалуйста, пример, одного (короткого) предложения, обработанного tagger и goldStandart для этого случая.

Два слова (to be) определены одним тэгом или каждому приписан свой тэг?

С полным математическим описанием модели повременю до разрешения этого вопроса....





Это сообщение отредактировал(а) Zuzu - 25.1.2007, 12:18

Собственно, вопрос с to be, ИМХО, не особенно важен - можно и проигнорировать этот артефакт на этапе (объектной) реализации 

Предлагаю вашему вниманию, дамы и господа, скелет программы, как бы я это все реализовывал. Предвидя вопросы типа, "почему так сложно", "можно написать по-другому" - да ради бога! Перл предлагает массу способов реализации одной идеи! Каждый выбирает для себя сам то, что ему ближе. Лично мне "ближе" мыслить объектами, в рамках тех реальных объектов (сущностей) для которых пишется задача. И в своей работе я готов смириться с тем, что придется писать больше кода (ведь каждый класс необходимо реализовать!). Тем более, как показал предыдущий пост от LisaST, внести коррективы в код в связи с появлением нового артефакта, который укладывается в математическую модель, не представляет большого труда (hазговор про подсчет промежуточных результатов).



P.S. Код, естественно, не тестировал. Классы-то не созданы и их свойства, методы и интерфейсы не определены!

Вот так. Спасибо тем, к то осилил чтение кода до конца!


Это сообщение отредактировал(а) Zuzu - 25.1.2007, 14:13

Ух ты! Zuzu, это круто!

Я, собственно, вклиниваюсь в обсуждение, чтобы предложить простенький вспомогательный скрипт, предназначение которого - навести статистику тэгов. Надеюсь, пригодится, хотя бы затем, чтобы получить список всех употребленных тэгов. Тестировался этот скрипт над результатом работы CRFTagger, для других тэггеров, возможно, придется немного поменять код. Печатает он сам тэг и сколько раз этот тэг встретился в файле. Если нужна статистика по словам, помеченным этим тэгом, то нужно в 3-й строке заменить 0 на 1. Файл скрипту нужно подавать в качестве параметра.

Zuzu, респект! Благодаря твоим стараниям даже мне стали примерно понятны условия задачи. Еще бы кусочек пресловутого goldStandart...

amg, спасибо за отзыв! Рад, что "пролил свет" на задачу. Самому было интересно разобраться. Неравнодушен я к поянтиям типа "релевантность".

Кстати, я там, как разработчик, немного слукавил с подсчетом промежуточных результатов. Считаю их для каждых 1000 строк, а не для обозначенных процентов. Дело вот в чем. Если нужно реально считать именно по процентам, то нужно знать количество строк (или слов) в исходном тексте. Для этого его необходимо пройти сверху вниз еще один раз перед тем, как анализировать сами слова. Как говорится, дополнительный проход по файлу в 9Mb.. Оправдано ли это? 

Если бы таковы были начальные условия, то при реализации хранилища (класса Storage, от которого, собственно, порождены классы TagStorage и GoldStorage) я бы, конечно, это сделал, но написал бы в коде ехидный комментарий типа: "Эх вы! Горе-заказчики! Если бы вы убрали из начальной спецификации это условие, программа бы работала в 2 раза быстрее!".

;)

я не имела ввиду полностью удалить знаки препинания, просто "/" удалился , а знаков везде по 2 осталось например:

надо будет просто дополнить <regex>




к проблеме объединенных тегов:
iz goldstandard

-------------------------------------------------------------------------
iz test 


The irregular present tense forms "am" and "are" are tagged as VBP in the Penn Treebank (see section ), just like any other non-third person singular present tense form.
----------------------------------------------------------------------------
<I'm> в тестфайле (CRFTagger) вообще не встречается, видимо программа заменяет все эти сокращенные формы на обычные перед присваиванием теггов-- это все усложняет задачу, предлагаю тогда глагол <to be> не анализировать, а объединенные формы в голдстандард считать за местоимение




т.е., если встречается глагол <to be> в любой форме, то исключить его в обоих файлах из статистики
-------------------------------------------------------
код прочитала до конца, логически очень все красиво написано, но я с такими понятиями как модули и интерфейсы в перле совсем не знакома, больше уже яву напоминает, создание новых объектов итц.

спасибо вам обоим с <amg>

моя задача сейчас определить соответствия 
------------------------------------------------------------
помещаю кусок голдстандард для<amg>






Это сообщение отредактировал(а) LisaST - 25.1.2007, 21:55

Напиши, пожалуйста, что было до обработки этого предложения  (там, возможно, были пробелы)

Про <to be>.

Приведи, пожалуйста, точный пример: 

Исходное предложение:
То же предложение, "обработанное" goldStandart:
То же предложение, обработанное tagger:

Математическая модельтребует, чтобы тексты (для tagger и goldStandart) были абсолютно, слово в слово, одинаковые. 

Проблему с I'm можно решить, путем переведения "I'm" в "I am" (для goldStandart) либо обратно "I am"  в I'm для (tagger).  По этому поводу можно либо написать маленькую программку и обработать ей goldStandart (или tagger) - текст  Затем, для первого случая, - по накатанной дорожке (убрать тэги, скормить tagger'у, скормить програмрамме - считальщику качества тэггера). После этого было бы неплохо сравнить "пословно" файлы. В принципе, программа-анализатор, в качестве бесплатного приложения, это сделает.

Третий способ (в моем случае) - взять данные "как есть" и возложить эту непосильную задачу (по приведению I'am r I am) на объект GoldStorage или TaggerStorage Как чувствовал, что будут проблемы с исходными данными! Поэтому при проектировании не воспользовался одним классом Storage, а породил от него два класса: GoldStorage и TaggerStorage!

LisaST, спасибо за отзыв по коду. Если по каким-то причинам нет возможности (или, как вариант, времени на изучение) ООП-механизмов на Perl, напиши, как тебе удобнее. Тем более, что с "трансформерами" я несколько перемудрил. В принципе, для "приведения диалекта тэга к каноническому виду", достаточно такого механизма, как хэш.

P.S. По терминологии ООП, которую я использовал: интерфейс класса (или порожденного от  него объекта) - есть множество (или совокупность) методов и свойств, которые разрешены к использованию по отношению к объекты (в терминологии классического ООП - public методы и свойства). Понятия свойство и метод - аналогичны классическим определениям. Понятия "пакет" и "модуль" вроде не использовал. Уж очень отличаются эти понятия в контексте UML и perl, например. Но это здесь offtopic.

 Вот с этим, кажется, будут проблемы: смотрите сами, что мне навыдавал CRFTagger, даже на нескольких предложениях уже несколько несоответствий с GoldStandard в количестве слов. 

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

Повторю (скорее для себя) что уже предлагал Zuzu:

• 1. Взять GoldStandard (gold.pos) и удалить из него все тэги.
• 2. Полученный текст пропустить через тестируемый тэггер. Получим tagger.pos
• 3. В gold.pos и из tagger.pos сделать обозначения тэгов единообразными.

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

Мысли по поводу решения задачи в связи с появлением такого артефакта, как "разные слова". 

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

 Вроде, CRFTagger так и делает (могу ошибаться).

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

Хорошая мысль. Это легко реализовать. Хотя из тех 6-ти предложений GoldStandard'а, что приводила LisaST, для 3-х CRFTagger дает другое кол-во слов.

1. нет, пробелов не было, самое интересное, что двойные точки не остались, а ?, !, :,; остались в двойном варианте, но мы знаки препинания все равно будем игнорировать, я удалила двойные с помощью sed и протестировала таггер на этом голдстандард тексте

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

ps Еще в голдстандард варианте с тегами видимо проводили chunking, поэтому на теги иногда навешаны дополнительные теги к части речи не имеющие ничего общего (-tl, -hl, -tl-hl),  мне их надо удалить, чтобы упростить нахождение соотв. тегов. 

 

 

goldstandard.txt





очень хорошая идея, хотя я не совсем точно препологаю, что здесь можно сделать.

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

Это сообщение отредактировал(а) LisaST - 26.1.2007, 21:47

По поводу "предложений с разными словами" есть такая сырая идея. 

Основная мысль, собственно, проста. Исходные тексты у нас нормальные - мы их сами такими старались-готовили. И, наверно, даже проверяли, чтобы они изначально были "пословно равны"!.  Если собака-тэггер попортил наши данные, путем "вставления в предложения" нового слова, то удаление этого слова может только улучшить ситуачию, т.к. приводит ее к тому виду, который был раньше.   

Опять-же, сильно он напортить не мог. Ему ведь отдали "нормальное предложение", его задача не "испортить предложение", а тэги расставить! А то, что предложения испортилоси это получилось у него так, случайно, случайно. 

1. Пусть предложения равны, если они "пословно" равны.

2. Пронумеруем предложения сверху вниз по двум текстам (от tagger и goldStandart).

3. По построению (т.е. текст-то мы делали сами!) у нас получается, что кол-во предложений в первом тексте и во втором - одинаковое. 

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

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

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

6. Итак, взяли двойку предложений, пронумеровали слова, сравнили их пословно, выяснили, что предложения не равны.

7. Находим в предложениях то слово, по которому они не сошлись. Т.е. находим такое n (слова), что w1(n) ne w2(n), где w1(n), w2(n) - слова с номером n в первом и втором предложении соответственно, "ne" - операция сравнения строк на неравенство от Perl.

8. Считаем исходный "критерий равенства предложений", запоминаем его в c0. 

9. Из исходного первого предложения выбрасываем слово с номером n, считаем "критерий равенства предложений" для "поправленного первого" и "исходного второго" предложения, запоминаем в c1

10. Аналогично поступаем со вторым предложением, запоминаем значение в c2

11. Выбрасываем слово с номером n и из первого (исходного) и из второго (исходного) предложения, считаем "критерий равенства", запоминаем значение в с3

12. По максимальному значению из с0, c1, с2, с3 выбираем тот способ, которые "лучше уравнивает предложения", его и пременяем к двойке предложений. Т.е. выбрасываем слово либо из первого предложения, либо слово из второго либо слово с номером n из первого и из второго предложения. Либо ничего ниоткуда не выбрасываем. 

13. Если что-то выбросили , сравниваем предложения. Если не равны - переходим к п. 7.

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



Как определить "критерий равенства предложений"? С этим сложнее... Надо смотреть... Пока четкой мысли нет.

P.S. Разговор про локальный максимум функции. Наверно вспоминается (кому-то пресловутый) курс математического анализа. Как находили локальный экстремум (минимум, максимум, перегиб) функции в мат. анализе? Правильно, путем двойного последовательного дифференцирования функции, приравнивания первой  производной для нахождения точек экстремума и выяснения знака второй производной в этой точке для выяснения типа точек экстремума. 

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

К чему я все это? Так вот. Если вдруг удастся построить функцию "критерия равенства" таким образом, что бы она была непрерывна, то можно будет решить задачу "выбрасывания лишних слов" аналитически, т.е. не перебирая все варианты. В чем прикол? А в том, что затем ее можно будет применить к какому угодно большому тексту и время которое будет необходимо для "выбрасывания" слов будет зависеть только от количества "плохих слов", а не от размера самого текста. Вот так. Высшая математика (а пока мы коснулись только ее основ - на уровне первого курса вуза) РУЛИТ!


Это сообщение отредактировал(а) Zuzu - 27.1.2007, 10:29

LisaST, и еще. Как бы я реализовывал все это дело (программу в целом). С учетом разных слов.

Следал бы объект "предложение". Он бы запрашивам предложения у объекта "хранилище".

(см. мой код)

Написал бы метод, который бы "нормализовал" два предложения.  Т.к. пока непонятно как он должне работать - он бы просто ничего интеллектуального не делал. Разве что предложения друг с другом сравнивал пословно и возводил в обоих объектах-предложениях флажок, если предложения не равны.

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

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

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

Это сообщение отредактировал(а) Zuzu - 27.1.2007, 11:02

Но может же встретиться, например, дата в формате 2007/1/27 ? Лучше, возможно, подсчитывать кол-во слов:



Это сообщение отредактировал(а) amg - 27.1.2007, 12:01

LisaST, предлагаю Вам набор скриптов. К сожалению, совсем некогда сейчас подробно расписывать, что они делают. Если что не понятно будет, то позже поясню. Собственно, осталось только реализовать алгоритм подсчета индексов, который Вы с Zuzu обсуждали, на "нормализованных" файлах это должно быть легко.
Первые 4 скрипта используют конструкцию while (<>) {} и печатают на stdout, т.е. можно использовать конвейеры:
tag-good GoldStandart.pos | tag-uni -G > GoldStandart.pos.uni
tag-good CRFTagger.pos | tag-uni -С > CRFTagger.pos.uni
tag-norm GoldStandart.pos.uni CRFTagger.pos.uni






Это сообщение отредактировал(а) amg - 30.1.2007, 10:02

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



согласна, "/" в голдстандард без тегов не встречается, но в другом тексте вполне вероятно 


--------------------------------
к коду от амг, я там многого не понимаю, конечно

1. ($good_word = qr/^[^\W\d_]+$/; # Only letters ->  я так поняла, что "[^\W\d_]" = \w
^ перед [, это начало сроки? 
   #$good_word = qr/^[[:^punct:]]+$/; # Except punctuations) -> 
в этом отрывке кода мы пытаемся удалить -tl, -hl etc? оставив только слово и тег после него, кот. тоже является словом?


!возникает проблема, т.к. существуют "нормальные теги" , которые заканчиваются на $, например pp$


2.  

не совсем понимаю, что в $TAG keys, a что values?


3. 


не понятно, что имелось ввиду с digits (\d) здесь?
и вот с этим выражением не разобралась :
sprintf("%03d",$i++)
-------------------------------------------------------------------------
sorry за простые вопросы, но я в модулях перл никак и вообще дальше user не забредала

Обещанная полное описание требований и определений для задачи:


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

Два слова равны, если они побуквенно, слева направо, равны.

Слово обозначим за wrd.

Контекст (слова) - взаимное расположение слова относительно слов в преджложении.

Тип слова  - часть речи, к которой принадлежит слово.

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

Наречие таггера, названия типов слов, которое возвращает таггер. Обозначим также как тип слова от таггера.

Таггер (tagger) - некая процедура, которая ставит слову в соответствие его тип из множества типов из наречия таггера. Различают тестируемый таггер - тот качество которого мы оценивает, назовем его собственно таггер() (или tagger()) и tagger - образец, который сопоставляет слову его тип заведомо правильно. Назовем его goldStandart() . Результатом работы таггера является тип слова в соответствии с наречием таггера.

Трансформация наречия (таггера)  - некий механизм приведения наречия таггера к каноническому виду. Возможно реализуется в виде отношения много (типов от таггера) к одному (каноническому типу). Обозначим соответственно trT() и trG() для tagger() и goldStandart() соответственно. Возможен вариант, когда элемент наречия таггера не имеет значения в каноническом типе.

Для определения равенства предложений, будем считать предложение также упорядоченным множеством слов, его составляющим. Для этого пронумеруем слова в предложении слева направо.

Предложения равны, если слова с одинаковыми номерами в первом и втором предложении равны. 

Для определения равенства текстов пронумеруем предложения в тексте с начала до конца тектса.

Тексты равны, если предложения первого и второго текста с одинаковыми номерами равны. 

Множество слов W - определим как упорядоченное множество троек (p, n, wrd), где p - порядковый номер предложения в тексте, n - порядковый номер слова в предложении, w слово. p(W) - количество (число) элементов в этом множестве. Двух одинаковых элементов-слов в (одном) множестве нет! Элемент множества (тройку (p, n, wrd)) обозначим за w

Дополнительно заметим, что tagger() и goldStandart() должны быть определены на всем этом множестве W. 

Релевантность - правильность определения tagger()'oм типа слова. Может принимать только значения "да" или "нет". Для w из W релевантность считается истиной, если trT(tagger(w)) == trG(goldStandart(w)). 

Заметим, если слова, (в общем случае) взяты из разных текстов, то релевантность для слов (не для тройки w!) имеет смысл только если эти слова (как слова) равны и взяты в одинаковом контексте (т.е. из одинаковых (равных) предложений, слова с одинаковыми номерами). Это уменьшение строгости , в принципе, позволяет применять определение релевантности к "неравным" текстам и по ним считать Recall и Precision (естественно, для этого, множество W должно быть специальным построено по этим двум текстам!).

Напомним, что t - некоторый канонический тип слова. Общее кол-во отпределенных слов одного типа - количество элементов w из всего W, тип которым тэггер определил как t (правильно или нет - нас не интересует). Обозначм как NT(t) (для типа t).

Общее кол-во правильных слов одного типа - количество элементов w из всего W, тип которым goldStantart определил как t (обязательно правильно - по построению goldStandart) Обозначм как NG(t) (для типа t).

Общее кол-во правильно определенных слов одного типа - количество элементов w из всего W, тип которым тэггер определил как t  правильно (т.е. так же как goldStandart) или, другими словами, релевантно. Обозначим N(t) (для типа t).

И, собственно, самое главное (наконец-то!)

Еще раз: t - тип слова.

Precision (насколько точно выбирает) Отношение кол-ва правильно выбранных (релевантных) слов к общему кол-ву выбранных тэггером для определенного типа.  Precision(t) = (N(t) / NT(t)) * 100%

Recall (как вообще выбирает) Отношение кол-ва релевантно выбранных тэггером слов к общему кол-ву правильных слов для определенного типа.  Recall(t) = (N(t) / NG(t)) * 100%

Вроде все. За границами остался алгоритм "нормализации" предложений. если они не равны.

Смтрите, может где ошибся - немаленький текст получился. 


Это сообщение отредактировал(а) Zuzu - 31.1.2007, 11:42

[^\W\d_] - это \w без \d и _, т.е. только буква

Не так. У меня $good_word - это то, что в конструкции word/tag находится до последнего экземпляра "/". Если хочется обработать тэги, то нужно что-то вроде


В выражении $TAG{$2}{$1}++ while m/(\S+)\/(\S+)/g; %TAG - это хэш хэшей. Его ключи - это тэги, значения - ссылки на хэши. У последних ключи - это слова, значения - кол-во слов. Например, $TAG{nn}{work} == 12 означает, что среди слов, помеченных тэгом "nn", слово "work"  встретилось 12 раз. LisaST, обратите, пожалуйста внимание, насколько хорошо perl приспособлен для подобного рода задач! Одно короткое выражение разбирает строку и создает довольно нетривиальную структуру данных (все остальное - лишь представление результатов).

Пользуясь случаем, расскажу, как реализована нормировка. Суть нормировки в том, чтобы сравнить две строки и "уникальные" элементы в каждой из строк выкинуть. Элемент - это word/tag. Элементы совпадают, если у них совпадают части "word". 

1. Сортируем элементы каждой строки по алфавиту. Если в пределах одной строки нет совпадающих элементов, то этого достаточно. Соответствие строк не нарушится. Но строки могут выглядеть так:
aaa/xx  work/nn  bbb/xx  work/vb
aaa/xx  work/vb  bbb/xx  work/nn
и простая сортировка по алфавиту даст
aaa/xx  bbb/xx  work/nn  work/vb
aaa/xx  bbb/xx  work/nn  work/vb
Это неправильно. Поэтому сначала элементы нумеруются, затем сортируются и нумерация удаляется.
aaa/xx  work/nn  bbb/xx  work/vb  =>  aaa/001xx  work/002nn  bbb/003xx  work/004vb
aaa/xx  work/vb  bbb/xx  work/nn  =>  aaa/001xx  work/002vb  bbb/003xx  work/004nn
sprintf("%03d",$i++) как раз для вставки номера: это выражение возвращает номер с нулями и затем этот номер инкрементирует.
Кстати, после внимательного прочтения perldoc -f sort выяснилось, что для perl 5.7 и выше функцию, возвращающую сортированный массив, можно упростить. Дело в том, что в этой версии perl ввели алгоритм сортировки, который в случае, если с точки зрения sort элементы совпадают, то сохраняется тот порядок элементов, который был в источнике.


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

Добавлено @ 11:20 
Zuzu, как во-время твой пост! Я как раз собрался листать все 4 страницы этого топика, чтобы точно понять, что такое Recall & Precision. А тут все в одном месте с четкими определениями. 

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

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

Сам код пока не смотрел. 

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

Для проверки можно использовать такой способ:
Это, конечно, не достаточное, но необходимое условие




Это сообщение отредактировал(а) amg - 29.1.2007, 13:18

amg, здраво, конечно. К сожалению, строго не доказывает, что удалены именно "неправильные" слова. Могут быть с таким же успехом быть удалены и "нормальные" слова (попарно) из обоих текстов.

Для дополнительной проверки можно посчитать кол-во удаленных слов. По специфике построения текста от tager, из него должно быть удалено слов в два раза больше, чем из текста от goldStandart. Это условие должно выполняться для каждого (неверного) предложения текста и, следовательно, для всего текста в целом. LisaST поправит, если это не так.

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

LisaST, во-первых, у меня была дурацкая ошибка в скрипте tag-uni. Исправил (см. соответствующий пост); во-вторых, была небольшая ошибка в tag-norm (исправил, см. там же). И наконец, скрипт, подсчитывающий в нормализованных файлах Recall & Precision. Его нужно проверять, не напутал ли я чего. Успехов!