Lepsze filtrowanie Bayesa

Styczeń 2003

(Ten artykuł został wygłoszony jako prezentacja na konferencji Spam Conference w 2003 roku. Opisuje pracę, którą wykonałem nad poprawą wydajności algorytmu opisanego w "A Plan for Spam" [1], oraz moje plany na przyszłość.)

Pierwszym odkryciem, którym chciałbym się tu podzielić, jest algorytm leniwego przetwarzania artykułów naukowych. Po prostu pisz, co chcesz, i nie cytuj żadnych wcześniejszych prac, a oburzeni czytelnicy sami wyślą Ci odnośniki do wszystkich prac, które powinieneś był zacytować. Odkryłem ten algorytm po tym, jak "A Plan for Spam" [1] trafił na Slashdot.

Filtrowanie spamu jest podzbiorem klasyfikacji tekstu, która jest dobrze ugruntowaną dziedziną, ale pierwsze artykuły dotyczące filtrowania spamu oparte na metodach Bayesa wydają się pochodzić z tej samej konferencji w 1998 roku, jeden autorstwa Pantela i Lina [2], a drugi grupy z Microsoft Research [3].

Gdy usłyszałem o tej pracy, byłem nieco zaskoczony. Skoro ludzie zajmowali się filtrowaniem Bayesa już cztery lata temu, dlaczego nie wszyscy z tego korzystali? Kiedy przeczytałem artykuły, zrozumiałem dlaczego. Filtr Pantela i Lina był bardziej efektywny z tych dwóch, ale przechwytywał tylko 92% spamu, z 1,16% fałszywych pozytywów.

Kiedy próbowałem napisać filtr spamu oparty na metodach Bayesa, przechwytywał 99,5% spamu z mniej niż 0,03% fałszywych pozytywów [4]. Zawsze niepokojące jest, gdy dwie osoby przeprowadzające ten sam eksperyment uzyskują diametralnie różne wyniki. Jest to szczególnie alarmujące, ponieważ te dwa zestawy liczb mogą prowadzić do sprzecznych wniosków. Różni użytkownicy mają różne wymagania, ale myślę, że dla wielu osób wskaźnik filtrowania na poziomie 92% z 1,16% fałszywych pozytywów oznacza, że filtrowanie nie jest akceptowalnym rozwiązaniem, podczas gdy 99,5% z mniej niż 0,03% fałszywych pozytywów oznacza, że jest.

Dlaczego więc uzyskaliśmy tak różne liczby? Nie próbowałem odtworzyć wyników Pantela i Lina, ale czytając artykuł, widzę pięć rzeczy, które prawdopodobnie tłumaczą tę różnicę.

Jedną z nich jest po prostu to, że trenowali swój filtr na bardzo małej ilości danych: 160 spamów i 466 wiadomości niebędących spamem. Wydajność filtra powinna nadal rosnąć przy tak małych zbiorach danych. Zatem ich liczby mogą nawet nie być dokładnym pomiarem wydajności ich algorytmu, nie mówiąc już o filtrowaniu spamu Bayesa w ogóle.

Ale myślę, że najważniejsza różnica polega prawdopodobnie na tym, że zignorowali nagłówki wiadomości. Dla każdego, kto pracował nad filtrami spamu, będzie to wydawać się perwersyjną decyzją. A jednak w pierwszych filtrach, które próbowałem napisać, również ignorowałem nagłówki. Dlaczego? Ponieważ chciałem utrzymać problem w ryzach. Wtedy niewiele wiedziałem o nagłówkach poczty i wydawały mi się one pełne losowych rzeczy. Jest tu lekcja dla piszących filtry: nie ignoruj danych. Można by pomyśleć, że ta lekcja jest zbyt oczywista, by o niej wspominać, ale musiałem się jej nauczyć kilka razy.

Po trzecie, Pantel i Lin stosowali stemming tokenów, co oznacza, że redukowali np. zarówno "mailing", jak i "mailed" do rdzenia "mail". Mogli czuć się zmuszeni do tego przez mały rozmiar swojego korpusu, ale jeśli tak, to jest to rodzaj przedwczesnej optymalizacji.

Po czwarte, obliczali prawdopodobieństwa inaczej. Używali wszystkich tokenów, podczas gdy ja używam tylko 15 najbardziej znaczących. Jeśli użyjesz wszystkich tokenów, będziesz miał tendencję do pomijania dłuższych spamów, tych, w których ktoś opowiada swoją historię życia do momentu, gdy wzbogacił się dzięki jakiemuś schematowi marketingu wielopoziomowego. I taki algorytm byłby łatwy do podrobienia przez spamerów: wystarczy dodać duży fragment losowego tekstu, aby zrównoważyć terminy spamowe.

Na koniec, nie stosowali pochylenia przeciwko fałszywym pozytywom. Myślę, że każdy algorytm filtrowania spamu powinien mieć wygodne pokrętło, które można przekręcić, aby zmniejszyć wskaźnik fałszywych pozytywów kosztem wskaźnika filtrowania. Robię to, licząc wystąpienia tokenów w korpusie niebędącym spamem dwukrotnie.

Nie sądzę, aby traktowanie filtrowania spamu jako prostego problemu klasyfikacji tekstu było dobrym pomysłem. Można używać technik klasyfikacji tekstu, ale rozwiązania mogą i powinny odzwierciedlać fakt, że tekst jest e-mailem, a spam w szczególności. E-mail to nie tylko tekst; ma strukturę. Filtrowanie spamu to nie tylko klasyfikacja, ponieważ fałszywe pozytywy są znacznie gorsze niż fałszywe negatywy, więc należy je traktować jako inny rodzaj błędu. A źródłem błędu nie jest tylko losowe odchylenie, ale żywy ludzki spamer aktywnie działający na rzecz pokonania Twojego filtra.

Tokeny

Kolejny projekt, o którym usłyszałem po artykule na Slashdot, to CRM114 Billa Yerazunisa [5]. Jest to przykład przeciwny do właśnie wspomnianej zasady projektowania. Jest to prosty klasyfikator tekstu, ale tak oszałamiająco skuteczny, że udaje mu się filtrować spam niemal doskonale, nawet nie wiedząc, co robi.

Gdy zrozumiałem, jak działa CRM114, wydawało się nieuniknione, że w końcu będę musiał przejść od filtrowania opartego na pojedynczych słowach do podejścia takiego jak to. Ale najpierw pomyślałem, że zobaczę, jak daleko mogę zajść z pojedynczymi słowami. A odpowiedź brzmi: zaskakująco daleko.

Głównie pracowałem nad inteligentniejszą tokenizacją. W przypadku obecnego spamu udało mi się osiągnąć wskaźniki filtrowania zbliżone do CRM114. Te techniki są w większości ortogonalne do technik Billa; optymalne rozwiązanie może je obie uwzględniać.

"A Plan for Spam" używa bardzo prostej definicji tokenu. Litery, cyfry, łączniki, apostrofy i znaki dolara są znakami składowymi, a wszystko inne jest separatorem tokenów. Ignorowałem również wielkość liter.

Teraz mam bardziej skomplikowaną definicję tokenu:

1. Wielkość liter jest zachowana.
2. Wykrzykniki są znakami składowymi.
3. Kropki i przecinki są składowymi, jeśli występują między dwiema cyframi. Pozwala mi to zachować adresy IP i ceny w całości.
4. Zakres cenowy, taki jak $20-25, daje dwa tokeny: $20 i $25.
5. Tokeny występujące w liniach To, From, Subject i Return-Path, lub w adresach URL, są odpowiednio oznaczane. Np. "foo" w linii Subject staje się "Subject*foo". (Gwiazdka może być dowolnym znakiem, którego nie dopuszczasz jako składowego.)

Takie środki zwiększają słownictwo filtra, co czyni go bardziej dyskryminującym. Na przykład, w obecnym filtrze "free" w linii Subject ma prawdopodobieństwo spamu wynoszące 98%, podczas gdy ten sam token w treści ma prawdopodobieństwo spamu wynoszące tylko 65%.

Oto niektóre z obecnych prawdopodobieństw [6]:

SubjectFREE 0.9999 free!! 0.9999 Tofree 0.9998 Subjectfree 0.9782 free! 0.9199 Free 0.9198 Urlfree 0.9091 FREE 0.8747 From*free 0.7636 free 0.6546

W filtrze "Plan for Spam" wszystkie te tokeny miałyby to samo prawdopodobieństwo, 0,7602. Ten filtr rozpoznawał około 23 000 tokenów. Obecny rozpoznaje około 187 000.

Wadą posiadania większego uniwersum tokenów jest większe ryzyko przeoczenia. Rozłożenie korpusu na więcej tokenów ma taki sam efekt, jak jego zmniejszenie. Jeśli na przykład traktujesz wykrzykniki jako składowe, możesz nie mieć prawdopodobieństwa dla "free" z siedmioma wykrzyknikami, mimo że wiesz, że "free" z zaledwie dwoma wykrzyknikami ma prawdopodobieństwo 99,99%.

Jednym z rozwiązań tego problemu jest to, co nazywam degeneracją. Jeśli nie możesz znaleźć dokładnego dopasowania dla tokenu, traktuj go tak, jakby był mniej specyficzną wersją. Uważam końcowe wykrzykniki, wielkie litery i występowanie w jednym z pięciu oznaczonych kontekstów za czyniące token bardziej specyficznym. Na przykład, jeśli nie znajdę prawdopodobieństwa dla "Subjectfree!", szukam prawdopodobieństw dla "Subjectfree", "free!" i "free", i biorę to, które jest najdalej od 0,5.

Oto alternatywy [7], które są brane pod uwagę, jeśli filtr napotka "FREE!!!" w linii Subject i nie ma dla niego prawdopodobieństwa.

SubjectFree!!! Subjectfree!!! SubjectFREE! SubjectFree! Subjectfree! SubjectFREE SubjectFree Subjectfree FREE!!! Free!!! free!!! FREE! Free! free! FREE Free free

Jeśli to robisz, pamiętaj o uwzględnieniu wersji z wielką literą na początku, a także wszystkich wielkich liter i wszystkich małych liter. Spamy mają tendencję do posiadania większej liczby zdań w trybie rozkazującym, a w nich pierwsze słowo jest czasownikiem. Zatem czasowniki z wielką literą na początku mają wyższe prawdopodobieństwo spamu niż w przypadku wszystkich małych liter. W moim filtrze prawdopodobieństwo spamu dla "Act" wynosi 98%, a dla "act" tylko 62%.

Jeśli zwiększysz słownictwo swojego filtra, możesz skończyć licząc to samo słowo wielokrotnie, zgodnie z twoją starą definicją "tego samego". Logicznie rzecz biorąc, nie są to już te same tokeny. Ale jeśli to nadal Ci przeszkadza, pozwól mi dodać z doświadczenia, że słowa, które wydają się być liczone wielokrotnie, to właśnie te, które chciałbyś liczyć.

Innym efektem większego słownictwa jest to, że gdy analizujesz przychodzącą pocztę, znajdujesz więcej interesujących tokenów, czyli tych z prawdopodobieństwami znacznie odbiegającymi od 0,5. Używam 15 najbardziej interesujących, aby zdecydować, czy poczta jest spamem. Ale można napotkać problem, gdy używa się stałej liczby, takiej jak ta. Jeśli znajdziesz wiele maksymalnie interesujących tokenów, wynik może zostać zdeterminowany przez jakiś losowy czynnik określający kolejność równie interesujących tokenów. Jednym ze sposobów radzenia sobie z tym jest traktowanie niektórych jako bardziej interesujących niż innych.

Na przykład, token "dalco" pojawia się 3 razy w moim korpusie spamu i nigdy w moim korpusie legalnych wiadomości. Token "Url*optmails" (oznaczający "optmails" w adresie URL) pojawia się 1223 razy. A jednak, gdyby obliczał prawdopodobieństwa dla tokenów, oba miałyby takie samo prawdopodobieństwo spamu, próg 0,99.

To nie wydaje się właściwe. Istnieją teoretyczne argumenty za przypisaniem tym dwóm tokenom znacznie różnych prawdopodobieństw (Pantel i Lin to robią), ale jeszcze tego nie próbowałem. Wydaje się przynajmniej, że jeśli znajdziemy więcej niż 15 tokenów, które występują tylko w jednym z korpusów, powinniśmy nadać priorytet tym, które występują często. Zatem teraz istnieją dwie wartości progowe. Dla tokenów występujących tylko w korpusie spamu, prawdopodobieństwo wynosi 0,9999, jeśli występują więcej niż 10 razy, a 0,9998 w przeciwnym razie. Tak samo po drugiej stronie skali dla tokenów znalezionych tylko w korpusie legalnych wiadomości.

Mogę później znacząco skalować prawdopodobieństwa tokenów, ale ta niewielka skalacja przynajmniej zapewnia, że tokeny są sortowane we właściwy sposób.

Inną możliwością byłoby rozważenie nie tylko 15 tokenów, ale wszystkich tokenów powyżej pewnego progu interesowności. Steven Hauser robi to w swoim statystycznym filtrze spamu [8]. Jeśli używasz progu, ustaw go bardzo wysoko, inaczej spamerzy mogą Cię oszukać, wypełniając wiadomości większą liczbą niewinnych słów.

Na koniec, co należy zrobić z html? Próbowałem wszystkich opcji, od ignorowania go po analizowanie go w całości. Ignorowanie html jest złym pomysłem, ponieważ jest pełen użytecznych oznak spamu. Ale jeśli analizujesz go w całości, Twój filtr może zdegenerować się do zwykłego rozpoznawacza html. Najskuteczniejszym podejściem wydaje się być środek, czyli zauważanie niektórych tokenów, ale nie innych. Patrzę na tagi a, img i font, a resztę ignoruję. Linki i obrazy zdecydowanie powinieneś analizować, ponieważ zawierają adresy URL.

Prawdopodobnie mógłbym być sprytniejszy w radzeniu sobie z html, ale nie sądzę, aby warto było poświęcać na to dużo czasu. Spamy pełne html są łatwe do filtrowania. Sprytniejsi spamerzy już ich unikają. Zatem wydajność w przyszłości nie powinna zależeć od tego, jak radzisz sobie z html.

Wydajność

Pomiędzy 10 grudnia 2002 a 10 stycznia 2003 otrzymałem około 1750 spamów. Z nich 4 się przedostały. To wskaźnik filtrowania około 99,75%.

Dwa z czterech spamów, które przegapiłem, przedostały się, ponieważ przypadkowo użyły słów, które często pojawiają się w moich legalnych e-mailach.

Trzeci był jednym z tych, które wykorzystują niezabezpieczony skrypt cgi do wysyłania wiadomości do stron trzecich. Trudno je filtrować na podstawie samej treści, ponieważ nagłówki są niewinne, a oni dbają o używane słowa. Nawet tak, zazwyczaj udaje mi się je złapać. Ten przeszedł z prawdopodobieństwem 0,88, tuż poniżej progu 0,9.

Oczywiście, analiza sekwencji wielu tokenów łatwo by go wyłapała. "Poniżej znajduje się wynik Twojego formularza kontaktowego" jest natychmiastowym sygnałem ostrzegawczym.

Czwarty spam był tym, co nazywam spamem przyszłości, ponieważ tak właśnie spodziewam się, że spam będzie ewoluował: całkowicie neutralny tekst, po którym następuje adres URL. W tym przypadku pochodził od kogoś, kto mówił, że w końcu ukończył swoją stronę domową i czy mógłbym ją zobaczyć. (Strona była oczywiście reklamą strony pornograficznej.)

Jeśli spamerzy dbają o nagłówki i używają świeżego adresu URL, w spamie przyszłości nie ma nic, na co filtry mogłyby zwrócić uwagę. Możemy oczywiście odpowiedzieć, wysyłając robota, aby obejrzał stronę. Ale to może nie być konieczne. Wskaźnik odpowiedzi na spam przyszłości musi być niski, inaczej wszyscy by to robili. Jeśli jest wystarczająco niski, nie będzie się opłacał spamerom [wfks.html], a my nie będziemy musieli zbytnio się martwić o jego filtrowanie.

A teraz naprawdę szokująca wiadomość: w tym samym jednomiesięcznym okresie otrzymałem trzy fałszywe pozytywy.

W pewnym sensie ulgą jest otrzymanie kilku fałszywych pozytywów. Kiedy pisałem "A Plan for Spam", nie miałem żadnych i nie wiedziałem, jakie będą. Teraz, gdy miałem ich kilka, jestem ulżony, że nie są tak złe, jak się obawiałem. Fałszywe pozytywy generowane przez filtry statystyczne okazują się być wiadomościami, które brzmią bardzo podobnie do spamu, a te zazwyczaj są tymi, których najmniej szkoda pominąć [9].

Dwa z fałszywych pozytywów to biuletyny od firm, od których coś kupiłem. Nigdy nie prosiłem o ich otrzymywanie, więc można argumentować, że były to spamy, ale liczę je jako fałszywe pozytywy, ponieważ wcześniej nie usuwałem ich jako spamów. Powodem, dla którego filtry je wyłapały, było to, że obie firmy w styczniu przeszły na komercyjnych dostawców usług e-mail zamiast wysyłać wiadomości z własnych serwerów, a zarówno nagłówki, jak i treść stały się znacznie bardziej spamerskie.

Trzeci fałszywy pozytyw był jednak zły. Pochodził od kogoś z Egiptu i był napisany wielkimi literami. Było to bezpośrednim wynikiem uczynienia tokenów wrażliwymi na wielkość liter; filtr "Plan for Spam" by go nie wyłapał.

Trudno powiedzieć, jaki jest ogólny wskaźnik fałszywych pozytywów, ponieważ statystycznie jesteśmy w szumie. Każdy, kto pracował nad filtrami (przynajmniej skutecznymi), będzie świadomy tego problemu. W przypadku niektórych e-maili trudno powiedzieć, czy są spamem, czy nie, a są to te, na które zwracasz uwagę, gdy filtry są naprawdę dopasowane. Na przykład, do tej pory filtr wyłapał dwa e-maile, które zostały wysłane na mój adres z powodu literówki, i jeden wysłany do mnie w przekonaniu, że jestem kimś innym. Można argumentować, że nie są to ani moje spamy, ani moje legalne wiadomości.

Inny fałszywy pozytyw pochodził od wiceprezesa Virtumundo. Pisałem do nich, udając klienta, a ponieważ odpowiedź wróciła przez serwery pocztowe Virtumundo, miała najbardziej obciążające nagłówki, jakie można sobie wyobrazić. Można argumentować, że to również nie jest prawdziwy fałszywy pozytyw, ale rodzaj efektu nieoznaczoności Heisenberga: dostałem go tylko dlatego, że pisałem o filtrowaniu spamu.

Nie licząc tych, do tej pory miałem łącznie pięć fałszywych pozytywów, z około 7740 legalnych e-maili, co daje wskaźnik 0,06%. Dwa pozostałe to powiadomienie o opóźnieniu zamówienia i przypomnienie o imprezie z Evite.

Nie sądzę, aby tej liczbie można było ufać, częściowo dlatego, że próbka jest tak mała, a częściowo dlatego, że myślę, że mogę naprawić filtr, aby nie wyłapywał niektórych z nich.

Fałszywe pozytywy wydają mi się innym rodzajem błędu niż fałszywe negatywy. Wskaźnik filtrowania jest miarą wydajności. Fałszywe pozytywy traktuję bardziej jak błędy. Poprawę wskaźnika filtrowania traktuję jako optymalizację, a zmniejszanie fałszywych pozytywów jako debugowanie.

Zatem te pięć fałszywych pozytywów to moja lista błędów. Na przykład, wiadomość z Egiptu została wyłapana, ponieważ wielkie litery sprawiły, że filtr uznał ją za egipski spam. To naprawdę jest rodzaj błędu. Podobnie jak w przypadku html, fakt, że e-mail jest napisany wielkimi literami, jest koncepcyjnie jedną cechą, a nie jedną dla każdego słowa. Muszę obsługiwać wielkość liter w bardziej wyrafinowany sposób.

Co więc można powiedzieć o tym 0,06%? Niewiele, myślę. Można to traktować jako górną granicę, pamiętając o małej wielkości próbki. Ale na tym etapie jest to bardziej miara błędów w mojej implementacji niż jakiś wewnętrzny wskaźnik fałszywych pozytywów filtrowania Bayesa.

Przyszłość

Co dalej? Filtrowanie to problem optymalizacji, a kluczem do optymalizacji jest profilowanie. Nie próbuj zgadywać, gdzie Twój kod jest wolny, bo zgadniesz źle. Sprawdź, gdzie Twój kod jest wolny i napraw to. W filtrowaniu oznacza to: spójrz na spamy, które przegapiłeś, i dowiedz się, co mogłeś zrobić, aby je wyłapać.

Na przykład, spamerzy obecnie agresywnie pracują nad unikaniem filtrów, a jedną z rzeczy, które robią, jest dzielenie i błędne pisanie słów, aby zapobiec ich rozpoznawaniu przez filtry. Ale praca nad tym nie jest moim priorytetem, ponieważ nadal nie mam problemów z łapaniem tych spamów [10].

Istnieją dwa rodzaje spamów, z którymi obecnie mam problemy. Jeden to typ, który udaje e-mail od kobiety zapraszającej do rozmowy lub obejrzenia jej profilu na stronie randkowej. Te przechodzą, ponieważ są jedynym rodzajem oferty sprzedażowej, którą można złożyć bez używania języka sprzedażowego. Używają tego samego słownictwa co zwykłe e-maile.

Drugi rodzaj spamów, które mam problemy z filtrowaniem, to te od firm np. z Bułgarii oferujących usługi programowania kontraktowego. Te przechodzą, ponieważ ja też jestem programistą, a spamy są pełne tych samych słów co moje prawdziwe wiadomości.

Prawdopodobnie najpierw skupię się na typie ogłoszeń towarzyskich. Myślę, że jeśli przyjrzę się bliżej, będę w stanie znaleźć statystyczne różnice między nimi a moimi prawdziwymi wiadomościami. Styl pisania jest z pewnością inny, chociaż może to wymagać filtrowania wielowyrazowego, aby to wychwycić. Zauważyłem również, że mają tendencję do powtarzania adresu URL, a ktoś, kto umieszcza adres URL w legalnej wiadomości, nie zrobiłby tego [11].

Typy outsourcingowe będą trudne do wyłapania. Nawet jeśli wyślesz robota na stronę, nie znajdziesz tam statystycznego dowodu winy. Być może jedyną odpowiedzią jest centralna lista domen reklamowanych w spamach [12]. Ale tego typu wiadomości nie może być aż tak wiele. Jeśli jedynymi pozostałymi spamami byłyby niechciane oferty usług programowania kontraktowego z Bułgarii, wszyscy moglibyśmy przejść do pracy nad czymś innym.

Czy filtrowanie statystyczne faktycznie doprowadzi nas do tego punktu? Nie wiem. W tej chwili, osobiście dla mnie, spam nie jest problemem. Ale spamerzy jeszcze nie podjęli poważnych wysiłków, aby oszukać filtry statystyczne. Co się stanie, gdy to zrobią?

Nie jestem optymistą co do filtrów działających na poziomie sieci [13]. Kiedy istnieje statyczna przeszkoda warta ominięcia, spamerzy są dość wydajni w jej omijaniu. Istnieje już firma o nazwie Assurance Systems, która przepuści Twoją pocztę przez Spamassassin i powie Ci, czy zostanie odfiltrowana.

Filtry na poziomie sieci nie będą całkowicie bezużyteczne. Mogą wystarczyć do wyeliminowania całego spamu "opt-in", czyli spamu od firm takich jak Virtumundo i Equalamail, które twierdzą, że faktycznie prowadzą listy opt-in. Możesz je filtrować na podstawie samych nagłówków, niezależnie od tego, co mówią w treści. Ale każdy, kto jest gotów fałszować nagłówki lub używać otwartych przekaźników, w tym prawdopodobnie większość spamerów pornograficznych, powinien być w stanie przepuścić jakąś wiadomość przez filtry na poziomie sieci, jeśli tylko zechce. (Chociaż bynajmniej nie wiadomość, którą chcieliby wysłać, co jest czymś.)

Rodzaj filtrów, co do których jestem optymistą, to te, które obliczają prawdopodobieństwa na podstawie poczty każdego indywidualnego użytkownika. Mogą one być znacznie skuteczniejsze, nie tylko w unikaniu fałszywych pozytywów, ale także w filtrowaniu: na przykład, znalezienie zakodowanego w base64 adresu e-mail odbiorcy w dowolnym miejscu wiadomości jest bardzo dobrym wskaźnikiem spamu.

Ale prawdziwą zaletą indywidualnych filtrów jest to, że wszystkie będą różne. Jeśli filtry każdego będą miały różne prawdopodobieństwa, sprawi to, że pętla optymalizacyjna spamerów, którą programiści nazwaliby cyklem edycja-kompilacja-testowanie, będzie przerażająco powolna. Zamiast po prostu dostosowywać spam, aby przeszedł przez kopię jakiegoś filtra, który mają na swoim pulpicie, będą musieli przeprowadzić testową wysyłkę dla każdej poprawki. Byłoby to jak programowanie w języku bez interaktywnego środowiska wykonawczego, a nikomu tego nie życzę.

Przypisy

[1] Paul Graham. "A Plan for Spam." Sierpień 2002. http://paulgraham.com/spam.html.

Prawdopodobieństwa w tym algorytmie są obliczane przy użyciu zdegenerowanego przypadku Reguły Bayesa. Istnieją dwa upraszczające założenia: że prawdopodobieństwa cech (tj. słów) są niezależne, i że nic nie wiemy o prawdopodobieństwie a priori, że e-mail jest spamem.

Pierwsze założenie jest powszechne w klasyfikacji tekstu. Algorytmy, które je wykorzystują, nazywane są "naiwnymi Bayesa".

Drugie założenie przyjąłem, ponieważ proporcja spamu w mojej przychodzącej poczcie tak bardzo się wahała z dnia na dzień (a nawet z godziny na godzinę), że ogólny stosunek a priori wydawał się bezwartościowy jako predyktor. Jeśli założysz, że P(spam) i P(nie-spam) wynoszą oba 0,5, to się znoszą i możesz je usunąć z formuły.

Gdybyś przeprowadzał filtrowanie Bayesa w sytuacji, gdy stosunek spamu do nie-spamu był konsekwentnie bardzo wysoki lub (szczególnie) bardzo niski, prawdopodobnie mógłbyś poprawić wydajność filtra, uwzględniając prawdopodobieństwa a priori. Aby zrobić to poprawnie, musiałbyś śledzić stosunki według pory dnia, ponieważ zarówno spam, jak i legalna poczta mają wyraźne wzorce dobowe.

[2] Patrick Pantel i Dekang Lin. "SpamCop-- A Spam Classification & Organization Program." Proceedings of AAAI-98 Workshop on Learning for Text Categorization.

[3] Mehran Sahami, Susan Dumais, David Heckerman i Eric Horvitz. "A Bayesian Approach to Filtering Junk E-Mail." Proceedings of AAAI-98 Workshop on Learning for Text Categorization.

[4] W tym czasie miałem zero fałszywych pozytywów z około 4000 legalnych e-maili. Jeśli następny legalny e-mail byłby fałszywym pozytywem, dałoby to 0,03%. Te wskaźniki fałszywych pozytywów są niewiarygodne, jak wyjaśniam później. Cytuję liczbę tutaj tylko po to, aby podkreślić, że niezależnie od wskaźnika fałszywych pozytywów, jest on mniejszy niż 1,16%.

[5] Bill Yerazunis. "Sparse Binary Polynomial Hash Message Filtering and The CRM114 Discriminator." Proceedings of 2003 Spam Conference.

[6] W "A Plan for Spam" używałem progów 0,99 i 0,01. Wydaje się uzasadnione używanie progów proporcjonalnych do wielkości korpusów. Ponieważ mam teraz około 10 000 każdego rodzaju poczty, używam 0,9999 i 0,0001.

[7] Jest tu pewna wada, którą prawdopodobnie powinienem naprawić. Obecnie, gdy "Subjectfoo" degeneruje do samego "foo", oznacza to, że uzyskujesz statystyki dla wystąpień "foo" w treści lub w nagłówkach innych niż te, które oznaczam. Powinienem śledzić statystyki dla "foo" ogólnie, a także dla konkretnych wersji, i degenerować z "Subjectfoo" nie do "foo", ale do "Anywhere*foo". Tak samo z wielkością liter: powinienem degenerować z wielkich liter do dowolnej wielkości liter, a nie do małych.

Prawdopodobnie byłoby korzystne zrobić to samo z cenami, np. degenerować z "$129.99" do "$--9.99", "$--.99" i "$--".

Można również degenerować ze słów do ich rdzeni, ale to prawdopodobnie poprawiłoby tylko wskaźniki filtrowania na wczesnym etapie, gdy masz małe korpusy.

[8] Steven Hauser. "Statistical Spam Filter Works for Me." http://www.sofbot.com.

[9] Fałszywe pozytywy nie są sobie równe i powinniśmy o tym pamiętać, porównując techniki zatrzymywania spamu. Podczas gdy wiele fałszywych pozytywów spowodowanych przez filtry będzie bliskimi spamami, których nie będziesz chciał otrzymywać, fałszywe pozytywy spowodowane na przykład przez czarne listy będą po prostu wiadomościami od ludzi, którzy wybrali niewłaściwego dostawcę usług internetowych. W obu przypadkach przechwytujesz wiadomości, które są bliskie spamowi, ale dla czarnych list bliskość jest fizyczna, a dla filtrów tekstualna.

[10] Jeśli spamerzy staną się na tyle dobrzy w ukrywaniu tokenów, że stanie się to problemem, możemy odpowiedzieć, po prostu usuwając spacje, kropki, przecinki itp. i używając słownika do wyodrębniania słów z powstałej sekwencji. A oczywiście znalezienie słów w ten sposób, które nie były widoczne w oryginalnym tekście, samo w sobie byłoby dowodem spamu.

Wyodrębnianie słów nie będzie trywialne. Będzie wymagało więcej niż tylko rekonstrukcji granic słów; spamerzy zarówno dodają ("xHot nPorn cSite"), jak i pomijają ("P#rn") litery. Badania nad widzeniem mogą być tu przydatne, ponieważ ludzkie widzenie jest granicą, do której takie sztuczki będą się zbliżać.

[11] Ogólnie rzecz biorąc, spamy są bardziej powtarzalne niż zwykłe e-maile. Chcą wbić tę wiadomość do głowy. Obecnie nie dopuszczam duplikatów w 15 najlepszych tokenach, ponieważ można uzyskać fałszywy pozytyw, jeśli nadawca przypadkowo użyje jakiegoś złego słowa wielokrotnie. (W moim obecnym filtrze "dick" ma prawdopodobieństwo spamu 0,9999, ale jest to również imię.) Wydaje się, że powinniśmy przynajmniej zauważyć duplikację, więc mogę spróbować zezwolić na maksymalnie dwa wystąpienia każdego tokenu, tak jak robi to Brian Burton w SpamProbe.

[12] To jest to, w co zdegenerują się podejścia takie jak Brightmail, gdy spamerzy zostaną zmuszeni do używania technik "mad-lib" do generowania wszystkiego innego w wiadomości.

[13] Czasami argumentuje się, że powinniśmy pracować nad filtrowaniem na poziomie sieci, ponieważ jest to bardziej wydajne. Ludzie zazwyczaj mają na myśli: obecnie filtrujemy na poziomie sieci i nie chcemy zaczynać od nowa. Ale nie możesz narzucić problemu, aby pasował do Twojego rozwiązania.

Historycznie rzecz biorąc, argumenty dotyczące ograniczonych zasobów przegrywały w debatach na temat projektowania oprogramowania. Ludzie zazwyczaj używają ich tylko do uzasadnienia wyborów (szczególnie bezczynności) dokonanych z innych powodów.

Podziękowania dla Sarah Harlin, Trevora Blackwell i Dana Giffina za przeczytanie wersji roboczych tego artykułu, a dla Dana ponownie za większość infrastruktury, na której działa ten filtr.

Powiązane: