ТЕОРИЯ ПОДОБИЯ КОНЕЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ В ЗАДАЧАХ ИДЕНТИФИКАЦИИ СООБЩЕНИЙ Н.В. Северин n_severin@ukr.net. - презентация

1 ТЕОРИЯ ПОДОБИЯ КОНЕЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ В ЗАДАЧАХ ИДЕНТИФИКАЦИИ СООБЩЕНИЙ Н.В. Северин

2 Пути выхода на сайты, содержащие запрещенный, аморальный или травмирующий психику контент ввод URL в строке браузера переход по баннеру (реклама) переход по результату запроса в поисковой системе

3 Безопасный поисковый сервис - настройка уровня фильтрации непристойного текста - семейный поиск - интернет ЦЕНЗОР (безопасная поисковая система) другие поисковые системы

4 Надежность безопасных поисковых систем: СЕКС или СЕКИС ???

5

6 NO COMMENTS:

7 СЕКИС – мнение интернет-сообщества

8 порнозвезда или опрнозвезда ???

9

10 Типы ошибок, допускаемых при «ручном» наборе искажения символа (нескольких символов); пропуск символа(ов); вставка «лишнего» символа(ов); перестановки нескольких (часто – рядом стоящих) символов.

11 Краткий обзор теории подобия конечных последовательностей (ТПКП) Пусть M 0 – нулевой уровень представляющий множество букв (например, естественного языка). Тогда объекты 1-го уровня – это слова этого языка, а объекты 2- го уровня – его предложения. Два виды подобий для объектов a и b принадлежащих одному уровню (например, 1-му): подобие в широком смысле ( Fw) : 1) подобие в широком смысле ( Fw) : объекты a и b подобны, если число их подобных суб-объектов достаточно велико; подобие в узком смысле ( Fs) : 2) подобие в узком смысле ( Fs) : a и b подобны, если длиннейшая подпоследовательность их подобных суб-объектов, сохраняющая порядок следования этих суб-объектов в составе как a, так и b, достаточно длинна.

12 Определение численных мер для каждого из двух видов подобия Если a и b – два объекта одного и того же ненулевого уровня, то Fw(a,b) = dw(a,b)/max(|a|,|b|) Fs(a,b) = ds(a,b)/max(|a|,|b|), где dw(a,b)– число сходных суб-объектов у a и b; ds(a,b) – длина длиннейшей подпоследовательности сходных суб- объектов в a и b; |a| – длина (число суб-объектов) объекта a. Например, пусть M 0 – множество букв латинского алфавита a = analogy b = analogia – Fw(a,b) = Fs(a,b) = 6/8 = 0.75; c = naalogia – Fw(a,b) = 0.75; Fs(a,b) = 5/8=0.625.

13 Выбор меры для определения подобия Узкую меру подобия FsУзкую меру подобия Fs, разумно применять к объектам 1-го уровня. Перемешивание символов в слове изменяет его значение Широкая мера подобия FwШирокая мера подобия Fw, более приемлема для объектов 2-го уровня. Так как в большинстве натуральных языков порядок слов в предложении может изменяться без изменения его смысла.

14 Узкая мера подобия Fs Узкая мера подобия Fs хорошо справляется с задачами в которых следует учитывать: искажение символа (нескольких символов); пропуск символа(ов); вставку «лишнего» символа(ов); сдвиг и/или перестановку нескольких символов. (возможность изменения длины слова)

15 Оценки близости слов, полученные при использовании узкой меры подобия Fs(W,W*) W* (искаженное слово) W (правильная форма слова) Оценка сходства W и W* в ТПКП – F s (W, W*) Распознавание MS Word ( « + » – есть замена, «–» – нет) очепяткаопечатка0.625 – очепаткаопечатка потенциаотнопотенциально0.833 – опрелятьсяопределяться0.833 – несовдимостьнесводимость тестсетексте (тесте) констркцуииконструкции0.909 – информационно-посиковыхинформационно-поисковых – кажествсякажется0.778 – мсенноименно0.833+(сменно) сосбенностейособенностей0.927 – произзюстрируемпроиллюстрируем0.867 – сосовупностьсовокупность0.833 – екобходимынеобходимы0.900 – довайтидавайте0.714 – взгяловвзглядов0.875 – фундаметральнойфундаментальной0.933 –

16 Повышение порога оценки мер подобия Занижение порога может приводить к неоправданной идентификации «близких» слов Решение - повышения порога за счет ввода «взвешенных» мер ТПКП. «Взвешенные» меры – ввод различных весов для суб-объектов из объекта a Вес любого суб-объекта - отражение его «существенности» для объекта a сравнительно с другими суб-объектами из a. изобретение При этом степени аналогичности («взвешенного» подобия) будут иметь одно и то же значение 0.92 как для пары слов {изобретение, изобрели}, так и для {изобретение, изобритение}.

17 Оценка меры подобия предложений с учетом (1)веса слов и (2)сплоченности слов в ИГ Вопрос Каково наиболее значительное достижение в области математики конца XVII в.; и кто его автор? Ответ с расставленными весами (эталон): {Ньютон и Лейбниц} {изобрели} {математический анализ} Именные группы (ИГ) выделены фигурными скобками. - Оценка подобия производится с учетом веса слов в предложении - В ожидаемых ответах не учитывается порядок слов внутри именных групп, но чередование слов разных ИГ снижает оценку «подобия» ответа эталону

18 Оценка системой контроля знаний CONTROL Ньютон и Лейбниц изобрели математический анализ -- положительный ответ -- Матем. наализ – это изобритение и Ляйбница, и Невтона. (1.00) Лейбниц и Ньютон – изобретатели матанализа. (1.00) Мат. анализ был создан Ньютоном и Лейбницем. (1.00) Лейбниц, а также Ньютон, открыли анализ. (0.85) Мат. анализ Ньютон открыл, и Лейбниц. (0.80) Матанализ, Лейбниц, Ньютон. (0.95) -- неудовлетворительный -- Математика Ньютона открыла Лейбницев анализ. (0.39) Открыт и Ньютон анализом Лейбница. (0.65) Ньютон придумал Лейбница и создал анализ. (0.63) Ньютон открыл математику, Лейбниц – анализ и. (0.46)

19 Серверы статистики ключевых запросов wordstat.yandex.ru adwords.google.com/select/KeywordToolExternal stat.go.mail.ru adstat.rambler.ru серверы других поисковых систем

20 Выборочная статистика популярности запросов (

21 Спрос и предложения на очепятки

22 Узкая мера подобия для сообщения Узкая мера подобия для сообщения a = сексуально Сообщение bds(a,b)max(|a|,|b|)Fs(a,b) сесуально9100,90 секуально9100,90 ексуально9100,90 сксуально9100,90 скесуально9100,90 есксуально9100,90

23

24

25

26

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

28 Грамматически правильное длинное составное слово эталон a1= порнозвезда при распределении весов (тоже, что и для эталона порнография) порнозвезда будем иметь: Gs(a1, порно-звезда, L) = Gs(a1, порно-звездища, L) = Gs(a1, порно-звездочка, L) = Наличие ожидаемых в ответе (запросе) символов, даже при их нулевых весах, приводит к существенному росту подобия.