Алгоритмы принятия решения :)

Stanislav Latishko написал(а) к All в Oct 06 17:52:12 по местному времени:

Нi, All!

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

Задача - фильтрация спама. Дано: имеется несколько десятков
"элементарных" признаков спама, среди них как логические "да/нет" (напр.:
письмо пришло с dialup'ного ip, в To: содержится "undisclosed recepients",
отправитель значится в нашей адресной книге), так и численные (напр. число
слов "виагра" в теле письма, число url, и т.п.) При этом ни один из
известных признаков не является надежным, позволяющим принять абсолютно
верное решение относительно того является ли письмо спамом.

Требуется: хотя бы обозначить подходы к решению этой задачи :) -
т.е., принятие верного решения на основании совокупности признаков.

"Ответственность": за зачисление в спам письма, спамом не являющимся,
админа 2.71бут больно :) Просачивание спама в "не-спам" - не так страшно, но
скажем 5% просочившегося спама при 1000 писем в день дают нам 50 штук спама
в ящике, что эквивалентно потере 10-15 минут рабочего времени, за что админа
то же самое, хотя и чуть менее больно :)

Современное состояние: наилучшие из "жестких" алгоритмов вылавливают
85-90%. (Исходя из "стоимости ошибки", сомнение толкуется в пользу обвиняемого,
то-есть "сомнительные" письма не удаляются, а оставляются в отдельном ящике
для ручной фильтрации) Недостаток жестких алгоритмов: они "устаревают" -
спамеры постоянно учатся обходить существующие фильтры, поэтому процент про-
пущенного спама со временем растет. Наиболее "успешным" на сегодня считается
т.н. "байесовский фильтр", относящийся к обучающимся . ("Обучение" состоит
в том, что человек вручную просматривает результаты фильтрации и выстваляет
признаки "правильно/неправильно") Его недостатки: 1) без "начального обучения"
его эффективность хуже чем у жесткого алгоритма 2) в процессе работы, необхо-
димо постоянно контролировать правильность фильтрации (т.е. все равно прос-
матривать ящик "спам" на предмет ошибочно туда попавших писем) 3) долго
работающий фильтр становится "слишком умным" :) и качество фильтрации падает;
поэтому рекомендуется периодически обнулять его "базу знаний" и проводить
"начальное обучение".

Вуаля - задача на сегодняшний день не решена .

Придумать более простой пример задачи с принятием решения я не могу.
Итак: кто в состоянии данную задачу решить - только тот и имеет право гово-
рить "скрипач не нужен". Иначе - звать его звиздюком по жизни ...

Агрументированные возражения есть ? ;)
--
Stanislav Latishko

@@ sl @ sl . spb . su ; 2:5030/949 @@
--- ifmail v.2.14

Ilya Anfimov написал(а) к Stanislav Latishko в Oct 06 00:47:18 по местному времени:

From: Ilya Anfimov <ilan@astelecom.ru>

2006-10-11, Stanislav Latishko <Stanislav.Latishko@f949.n5030.z2.fidonet.org> пишет:
> Нi, All!
>

[skipped]

> Агрументированные возражения есть ? ;)

Есть. Это -- война щита и копья. С той стороны -- тожэ сидят
люди и под страхом смертной 2.71бли думают, как это всё обойти.

В самолётовождении мы имеем дело с более стацыонарными законами
природы, которым в общем пофиг -- долетишь ты или нет. И методы
доведения шансов долететь до единицы в общем доработаны, и дажэ
более-менее работают.

--- ifmail v.2.15dev5.3

Aleksey Tkachenko написал(а) к Stanislav Latishko в Oct 06 05:18:04 по местному времени:

From: "Aleksey Tkachenko" <walnut@online.ru>


"Stanislav Latishko" <Stanislav.Latishko@f949.n5030.z2.fidonet.org> wrote in message news:827615520@sl.spb.su...
> Нi, All!
skip
>
> Задача - фильтрация спама. Дано: имеется несколько десятков
> "элементарных" признаков спама, среди них как логические "да/нет" (напр.:
> письмо пришло с dialup'ного ip, в To: содержится "undisclosed recepients",
> отправитель значится в нашей адресной книге), так и численные (напр. число
> слов "виагра" в теле письма, число url, и т.п.) При этом ни один из
> известных признаков не является надежным, позволяющим принять абсолютно
> верное решение относительно того является ли письмо спамом.

1) Проблема спама - в отсутствии ответственности, т.е. электронной подписи под
каждым письмом.
2) Знаю один алгоритм и он у меня работал, но не скажу. :-)
3) К самолётовождению это не относится, т.к. в действительно сложных ситуациях
автоматы и люди ошибаются одинаково часто - автоматы от непонимания процесса
в целом, а лётчики от волнения, упрямства и суицидальных наклонностей. :-)

Алексей.


--
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5.3

Dmitry Chistyakov написал(а) к Stanislav Latishko в Oct 06 08:35:58 по местному времени:

From: "Dmitry Chistyakov" <dema@katren.ru>

Нello, Stanislav!
You wrote to All on Wed, 11 Oct 2006 16:52:12 +0400:

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


С уважением
Dmitry Chistyakov, Nsk, RF


--- ifmail v.2.15dev5.3

Stanislav Latishko написал(а) к Ilya Anfimov в Oct 06 13:20:10 по местному времени:

Wed, 11 Oct 06 23:47:18 +0400 Ilya Anfimov (IA) писАл[а] :

IA> Есть. Это -- война щита и копья. С той стороны -- тожэ сидят
IA> люди и под страхом смертной 2.71бли думают, как это всё обойти.

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

Я заострю ваше внимание на противоречии: с одной стороны - мы
имеем всю (!!!) информацию, необходимую для принятия верного решения,
с другой - мы не можем формализовать этот процесс ... (Выделение любых
мыслимых признаков - no problem, все делается буквально за 2 вечера,
остается только "центральная" логическая функция, которая эти признаки
сожрет и выдаст результат "да/нет") Скрипач с задачей справляется, но
рассказать компьютеру как он это делает - не может.

Причем, я вас уверяю, 99% достижимо по анализу признаков
только заголовка (без анализа текста) ! Причем "жестким" алгоритмом !
Но попытка связать признаки путем присвоения "весовых коэффициентов"
- это примитивизация, и результат выходит посредственным. Между призна-
ками сложная связь: грубо говоря, P17=1 делает незначимыми P25,P26, а
P21 инвертирует значение P43, и тому подобное... Связи между отдельными
парами я расписать могу, а все вместе связать - мозгов не хватает...
Но не только у меня :)
--
Stanislav Latishko

@@ sl @ sl . spb . su ; 2:5030/949 @@
--- ifmail v.2.14

Valentin Davydov написал(а) к Stanislav Latishko в Oct 06 17:25:52 по местному времени:

From: Valentin Davydov <val@sqdp.trc-net.co.jp>

> From: Stanislav Latishko <Stanislav.Latishko@f949.n5030.z2.fidonet.org>
> Date: Wed, 11 Oct 2006 16:52:12 +0400
>
> Задача - фильтрация спама. Дано: имеется несколько десятков
>"элементарных" признаков спама, среди них как логические "да/нет" (напр.:
>письмо пришло с dialup'ного ip, в To: содержится "undisclosed recepients",
>отправитель значится в нашей адресной книге), так и численные (напр. число
>слов "виагра" в теле письма, число url, и т.п.) При этом ни один из
>известных признаков не является надежным, позволяющим принять абсолютно
>верное решение относительно того является ли письмо спамом.
>
> Вуаля - задача на сегодняшний день не решена .

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

Вал. Дав.
--- ifmail v.2.15dev5.3

Ilya Anfimov написал(а) к Stanislav Latishko в Oct 06 18:17:12 по местному времени:

From: Ilya Anfimov <ilan@astelecom.ru>

2006-10-12, Stanislav Latishko <Stanislav.Latishko@f949.n5030.z2.fidonet.org> пишет:
> Wed, 11 Oct 06 23:47:18 +0400 Ilya Anfimov (IA) писАл[а] :
>
> IA> Есть. Это -- война щита и копья. С той стороны -- тожэ сидят
> IA> люди и под страхом смертной 2.71бли думают, как это всё обойти.
>
> Их в данном случае можно рассматривать как добросовестных тестеров
> (тестер "обычный" опробует изделие в "обычном" режиме и напишет отчет, а
> добросовестный постарается создать условия когда все баги повылезают:)

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

>
> Я заострю ваше внимание на противоречии: с одной стороны - мы
> имеем всю (!!!) информацию, необходимую для принятия верного решения,

Не знаю -- я её как минимум не имею.

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

Мы много чего не можэм формализовать. Из этого не следует,
что мы не можэм формализовать ничего.

--- ifmail v.2.15dev5.3

Stanislav Latishko написал(а) к Valentin Davydov в Oct 06 21:32:00 по местному времени:

Thu, 12 Oct 06 16:25:53 +0400 Valentin Davydov (VD) писАл[а] :

VD> Стало быть, проблема в формулировке задачи. На самом деле, критерий спама
VD> один - "это спам" или "это не спам". А задача состоит в формализации этого
VD> критерия.

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

Я говорил о признаках . Если ты считаешь что можешь переформули-
ровать задачу так чтоб решение стало очевидным - флаг в руки. Разбогатеешь
быстро, обещаю.
--
Stanislav Latishko

@@ sl @ sl . spb . su ; 2:5030/949 @@
--- ifmail v.2.14

Vladimir Ilushenko написал(а) к Stanislav Latishko в Oct 06 18:59:52 по местному времени:

Нello Stanislav!

Среда Октябрь 11 2034 16:52, Stanislav Latishko wrote to All:
SL> предмет ошибочно туда попавших писем) 3) долго работающий фильтр
SL> становится "слишком умным" :) и качество фильтрации падает; поэтому
SL> рекомендуется периодически обнулять его "базу знаний" и
SL> проводить "начальное обучение".

SL> Вуаля - задача на сегодняшний день не решена .
Это хоpоший пpимеp попытки pешения нетехнической пpоблемы техническими методами
:)
SL> Придумать более простой пример задачи с принятием решения я не
SL> могу. Итак: кто в состоянии данную задачу решить - только тот и имеет
SL> право гово- рить "скрипач не нужен". Иначе - звать его звиздюком по
SL> жизни ...

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


Vladimir

--- GoldED/W32 3.00.Beta2+

Stanislav Latishko написал(а) к Ilya Anfimov в Oct 06 22:10:46 по местному времени:

Thu, 12 Oct 06 17:17:13 +0400 Ilya Anfimov (IA) писАл[а] :

>> Их в данном случае можно рассматривать как добросовестных тестеров

IA> При большом жэлании -- можно. Не вижу как эта возможность что-то
IA> рассматривать влияет на выводы.

Влияет очевидным образом. Программы с багами тоже работают, как
это ни странно. И эти баги могут не вылезать 5 лет, а потом посыплются.

За всю свою жизнь я видел 4 или 5 экземпляров спама, сделанных
настолько тщательно, что можно, положа руку на сердце, сказать "фильтр
не виноват, ТАКОЕ ни один фильтр не выловит!" (Т.е. в процентном отношении
такого спама - меньше чем 0.01%) Весь остальной спам обладает явными
признаками спама в большом количестве. Так что речь не идет о борьбе
замков с отмычками, речь именно о поисках "багов" в фильтрах. Например,
для обхода тех же байесовских фильтров, некоторые спамеры включают в тело
письма просто набор слов из словаря, страницы из Пушкина :) итд. Очевидно,
что такое включение, успешно "обманывая" некую конкретную разновидность
фильтра, само по себе становится почти достоверным признаком спама :)

Короче, это именно что "боевое тестирование": из всего множества
возможных условий работы, программе специально подсовывают неблагопри-
ятные. Я неверно употребил слово "можно"; здесь должно быть слово "нужно".

>> имеем всю (!!!) информацию, необходимую для принятия верного решения,

IA> Не знаю -- я её как минимум не имею.

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

IA> Мы много чего не можэм формализовать. Из этого не следует,
IA> что мы не можэм формализовать ничего.

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

@@ sl @ sl . spb . su ; 2:5030/949 @@
--- ifmail v.2.14