Rozpoznawanie wzorców

Większość uczestników letniego projektu Dartmouth była zainteresowana naśladowaniem wyższych poziomów ludzkiej myśli. Ich praca polegała na pewnej introspekcji dotyczącej tego, jak ludzie rozwiązują problemy. Jednak wiele naszych zdolności umysłowych wykracza poza naszą zdolność introspekcji. Nie wiemy, jak rozpoznajemy dźwięki mowy, czytamy kursywę, odróżniamy filiżankę od talerza lub identyfikujemy twarze. Robimy te rzeczy automatycznie, nie myśląc o nich. Nie mając wskazówek z introspekcji, wcześni badacze zainteresowani automatyzacją niektórych naszych zdolności percepcyjnych oparli swoją pracę na intuicyjnych pomysłach dotyczących postępowania, na sieci prostych modeli neuronów i na technikach statystycznych. Później pracownicy uzyskali dodatkowe informacje z badań neurofizjologicznych dotyczących widzenia zwierząt. W tej części opiszę pracę z lat 50. i 60. XX wieku nad tzw. rozpoznawaniem wzorców. To zdanie odnosi się do procesu analizy obrazu wejściowego, segmentu mowy, sygnału elektronicznego lub innej próbki danych i zaklasyfikowanie go do jednej z kilku kategorii. Na przykład do rozpoznawania znaków kategorie odpowiadałyby kilkudziesięciu literom alfanumerycznym. Większość prac nad rozpoznawaniem wzorów w tym okresie dotyczyła materiałów dwuwymiarowych, takich jak drukowane strony lub zdjęcia. Można było już skanować obrazy w celu przekształcenia ich w tablice liczb (zwanych później "pikselami"), które następnie mogły być przetwarzane przez programy komputerowe, takie jak Dinneen i Selfridge. Russell Kirsch i współpracownicy z National Bureau of Standards (obecnie Narodowy Instytut Standardów i Technologii) również był jednym z pierwszych pionierów przetwarzania obrazu. W 1957 r. Kirsch zbudował skaner bębnowy i wykorzystał go do zeskanowania zdjęcia swojego trzymiesięcznego syna Waldena. Mówi się, że jest to pierwsza zeskanowana fotografia, mierząca 176 pikseli z boku. Za pomocą swojego skanera eksperymentował z programami do obróbki zdjęć działającymi na komputerze SEAC (Standards Eastern Automatic Computer).

Rozpoznawanie znaków

Wczesne starania o postrzeganie obrazów wizualnych koncentrowały się na rozpoznawaniu znaków alfanumerycznych na dokumentach. Pole to stało się znane jako "optyczne rozpoznawanie znaków". Sympozjum poświęcone informowaniu o postępach w tym temacie odbyło się w Waszyngtonie w styczniu 1962 r. Podsumowując, w tym czasie istniały urządzenia umożliwiające dość dokładne rozpoznawanie czcionek stałych (pisanych na maszynie lub drukowanych) na papierze. Być może stan rzeczy najlepiej wyraził jeden z uczestników sympozjum, J. Rabinow z Rabinow Engineering, który powiedział: "W naszej firmie myślimy, że możemy przeczytać wszystko, co jest drukowane, a nawet niektóre rzeczy, które są napisane. Jedynym haczykiem jest to, ile dolarów trzeba wydać? ". Znaczącym sukcesem w latach 50. był system rozpoznawania atramentu magnetycznego (MICR) opracowany przez naukowców z SRI International (zwany wówczas Stanford Research Institute) do czytania stylizowanych znaków atramentu magnetycznego na dole czeków. MICR był częścią systemu SRI ERMA (Electronic Recording Method of Accounting) służącego do automatyzacji przetwarzania czeków oraz zarządzania rachunkami i zarządzania księgowaniem. Według strony internetowej SRI "W kwietniu 1956 r. Bank of Ameryka ogłosiła, że General Electric Corporation została wybrana do produkcji modeli produkcyjnych ... W 1959 r. General Electric dostarczył pierwsze 32 systemy obliczeniowe ERMA do Bank of America. ERMA służył jako komputer księgowy i system obsługi czeków do 1970 r" . Większość metod rozpoznawania w tym czasie polegała na dopasowaniu znaku (po jego wyizolowaniu na stronie i przekonwertowaniu go na tablicę zer i jedynek) z prototypowymi wersjami znaku zwanymi "szablonami" (również przechowywanymi jako tablice na komputerze) . Jeśli znak pasuje do szablonu dla "A", powiedzmy, wystarczająco lepiej niż inne szablony, dane wejściowe zostały zadeklarowane jako "A." Dokładność rozpoznania uległa pogorszeniu, jeśli znaki wejściowe nie były prezentowane w standardowej orientacji, nie były tej samej czcionki co szablon lub miały niedoskonałości. Artykuły z 1955 r autorstwa Selfridge i Dinneen zaproponowały kilka pomysłów na wyjście poza dopasowywanie szablonów. Praca Olivera Selfridge'a i Ulricha Neissera z 1960 r. posunęła tę pracę dalej. Ten artykuł jest ważny, ponieważ był udaną, wczesną próbą użycia przetwarzania obrazu, ekstrakcji funkcji i wyuczonych wartości prawdopodobieństwa w rozpoznawaniu znaków odręcznie wydrukowanych. Znaki zostały zeskanowane i przedstawione na "siatkówce" 32 x 32 lub tablicy zer i jedynek. Zostały one następnie przetworzone przez różne operacje odnawiania (podobne do tych, o których wspominałem w związku z artykułem Dinneena z 1955 r.) W celu usunięcia przypadkowych kawałków szumu, luk, linii pogrubienia i wzmocnienia krawędzi. "Oczyszczone" obrazy zostały następnie sprawdzone pod kątem występowania "cech" (podobnych do cech, o których wspomniałem w związku z artykułem Selfridgea z 1955 r.). W sumie użyto 28 funkcji -takich jak maksymalna liczba przypadków linia pozioma przecinała obraz, względne długości różnych krawędzi i czy obraz miał "wklęsłość skierowaną na południe". Przywołując system Pandemonium Selfridge′a, możemy myśleć o procesie wykrywania cech jako wykonywanym przez "demony". Na wyższym poziomie hierarchii niż demony cechowe były "demony rozpoznające" - po jednym na każdą literę. (Wersja tego systemu przetestowana przez Worthie Doyle z Lincoln Laboratory została zaprojektowana do rozpoznawania dziesięciu różnych ręcznie drukowanych znaków, a mianowicie: A, E, I, L, M, N, O, R, S i T.) Każde rozpoznanie demon otrzymał jako dane wejściowe od każdego z demonów wykrywających cechy. Ale po pierwsze, dane wejściowe do każdego demona rozpoznającego zostały pomnożone przez wagę, która uwzględniała znaczenie wkładu odpowiedniej cechy w podejmowaniu decyzji. Na przykład, jeśli cecha 17 była ważniejsza niż cecha 22 przy podejmowaniu decyzji, że znakiem wejściowym jest "A", wówczas dane wejściowe do rozpoznającego "A" z cechy 17 byłyby ważone bardziej niż dane wejściowe z cechy. Po tym, jak każdy demon rozpoznania zsumował sumę swoich ważonych danych wejściowych, ostateczny "demon decyzyjny" zdecydował na korzyść tego, że postać ma największą sumę. Wartości wag zostały określone w procesie uczenia się, podczas którego analizowano 330 obrazów "treningowych". Zliczenia zestawiono w tabelach, ile razy wykryto każdą cechę dla każdej innej litery w zestawie szkoleniowym. Te dane statystyczne wykorzystano do oszacowania prawdopodobieństwa wykrycia danej cechy dla każdej litery. Te oszacowania prawdopodobieństwa wykorzystano następnie do ważenia cech sumowanych przez rozpoznające demony. Po szkoleniu system został przetestowany na próbkach ręcznie drukowanych znaków, których jeszcze nie widział. Według Selfridge′a i Neissera: "Ten program sprawia, że tylko około 10 procent mniej jest poprawnych identyfikacji, niż czytelnicy ludzcy robią {na pewno przyzwoitą wydajność."

Sieci neuronowe

Perceptrony

W 1957 r. Frank Rosenblatt (1928-1969, psycholog z Cornell Aeronautical Laboratory w Buffalo w stanie Nowy Jork) rozpoczął pracę nad sieciami neuronowymi w ramach projektu o nazwie PARA (Perceiving and Recognizing Automaton). Motywował go wcześniejsza praca McCullocha. Pitts i Hebb zainteresowali się tymi sieciami, które nazwał perceptronami, jako potencjalnymi modelami ludzkiego uczenia się, poznania i pamięci. Kontynuując na początku lat 60. jako profesor na Cornell University w Ithaca w Nowym Jorku, eksperymentował z wieloma różnych rodzajów perceptronów. Jego praca, bardziej niż Clarka i Farleya oraz innych pionierów sieci neuronowych, była odpowiedzialna za zainicjowanie jednej z głównych alternatyw dla metod przetwarzania symboli w AI, a mianowicie sieci neuronowych. Perceptrony Rosenblatta składały się z McCulloch {Elementy neuronowe w stylu Pittsa, takie jak ten pokazany poniżej



Każdy element miał dane wejściowe (przychodzące od lewej strony w górę), \ wagi "(pokazane przez wybrzuszenia na liniach wejściowych) i jedno wyjście (wychodzące w prawo). Dane wejściowe miały wartości 1 lub 0, i każde wejście zostało pomnożone przez związaną z nim wartość wagi. Element neuronowy obliczył sumę tych ważonych wartości. Na przykład, jeśli wszystkie dane wejściowe do elementu neuronowego na rysunku były równe 1, suma wynosiłaby 13. Gdyby suma była większa niż (lub po prostu równa) "wartość progowa", powiedzmy 7, powiązana z elementem, wówczas dane wyjściowe elementem neuronowym będzie 1, co byłoby w tym przykładzie. W przeciwnym razie wynik wyniósłby 0. Perceptron składa się z sieci tych elementów neuronowych, w których wyjścia jednego elementu są danymi wejściowymi dla innych. (Jest tu analogia do Pandemonium Selfridge'a, w którym demony średniego poziomu otrzymują "krzyki" demony niższego poziomu. Ciężary na liniach wejściowych elementu neuronowego można traktować jako analogiczne do "kontroli siły" zwiększającej lub zmniejszającej siłę w Pandemonium.) Przykładowy perceptron pokazano poniżej.



[Rosenblatt narysował schematy perceptronów w formacie poziomym (styl elektrotechniczny), z wejściami po lewej i wyjściami po prawej. Tutaj używam stylu pionowego ogólnie preferowanego przez informatyków do hierarchii, z najniższym poziomem u dołu i najwyższym u góry. Aby uprościć schemat, wybrzuszenia wagi nie są pokazane.] Chociaż przedstawiony perceptron, z tylko jedną jednostką wyjściową, jest zdolny tylko do dwóch różnych wyjść (1 lub 0), wiele wyjść (zestawy 1 i 0) można uzyskać przez ułożenie dla kilku jednostek wyjściowych. Warstwa wejściowa, pokazana na dole rysunku, była zazwyczaj prostokątnym układem 1 i 0 odpowiadających komórkom zwanym "pikselami" czarno-białego obrazu. Jedną z aplikacji, którymi interesowała się Rosenblatt, było, podobnie jak Selfridge, rozpoznawanie znaków. Użyję prostej algebry i geometrii, aby pokazać, jak elementy neuronowe w sieciach perceptronowych można "szkolić" w celu uzyskania pożądanych wyników. Rozważmy na przykład pojedynczy element neuronowy, którego danymi wejściowymi są wartości x₁, x₂ i x₃ i których powiązanymi wartościami wagowymi są w₁, w₂ i w₃. Gdy suma obliczona przez ten element jest dokładnie równa jego wartości progowej, powiedzmy t, mamy równanie w₁x₁ + w₂x₂ + w₃x₃ = t: W algebrze takie równanie nazywa się równaniem "liniowym. "Określa granicę liniową, czyli płaszczyznę, w przestrzeni trójwymiarowej. Płaszczyzna oddziela te wartości wejściowe, które spowodowałyby, że element neuronowy miałby wynik 1 z tych, które spowodowałyby, że miałby wynik 0. Pokazuję typową płaską granicę na rysunku



Wejście do elementu neuronowego może być przedstawione jako punkt (to znaczy wektor) w tej trójwymiarowej przestrzeni. Jego współrzędne to wartości x ₁ , x ₂ i x ₃ , z których każda może wynosić 1 lub 0. Gure pokazuje sześć takich punktów, trzy z nich (powiedzmy małe kółka) powodujące, że element ma moc wyjściową 1, a trzy (powiedzmy małe kwadraty) powodujące, że ma moc wyjściową 0. Zmiana wartości progu powoduje, że płaszczyzna poruszać się na boki w kierunku równoległym do siebie. Zmiana wartości ciężarów powoduje obrót płaszczyzny. Tak więc, zmieniając wartości ciężaru, punkty, które kiedyś znajdowały się po jednej stronie płaszczyzny, mogły skończyć się po drugiej stronie. "Szkolenie" odbywa się poprzez wykonanie takich zmian. Będę miał więcej do powiedzenia na temat procedur szkoleniowych. W wymiarach większych niż trzy (co zwykle ma miejsce), liniowa granica nazywana jest "hiperpłaszczyzną". Chociaż nie jest możliwe zwizualizowanie tego, co dzieje się w przestrzeniach o dużych wymiarach, matematycy wciąż mówią o punktach wejściowych w tych przestrzeniach oraz obrotach i ruchach hiperpłaszczyzn w odpowiedzi na zmiany wartości wag i progów. Rosenblatt zdefiniował kilka rodzajów perceptronów. Nazwał ten pokazany na schemacie "czteropowłokowym perceptronem sprzężonym szeregowo". (Rosenblatt liczył dane wejściowe jako pierwszą warstwę.) Nazywano to "sprzężeniem szeregowym", ponieważ moc wyjściowa każdego elementu neuronowego przekazywana była do elementów neuronowych w kolejnej warstwie. W najnowszej terminologii zamiast wyrażenia "sprzężony szeregowo" użyto wyrażenia "informacje zwrotne". Natomiast perceptron "sprzężony krzyżowo" może mieć wyjścia elementów neuronowych w jednej warstwie jako dane wejściowe do elementów neuronalnych w tej samej warstwie. Perceptron sprzężony "krzyżowo" może mieć dane wyjściowe elementów neuronowych w jednej warstwie elementy neuronowe w warstwach o niższych numerach. Rosenblatt pomyślał o swoich perceptronach jako o modelach okablowania części mózgu. Z tego powodu nazwał elementy neuronowe we wszystkich warstwach, ale w warstwie wyjściowej, "jednostkami asocjacji" (A-units), ponieważ zamierzał je modelować asocjacje wykonywane przez sieci neuronów w mózgu. Szczególnie interesujące były badania Rosenblatta to, co nazwał "perceptronem alfa". Składało się z trójwarstwowej sieci sprzężenia zwrotnego z warstwą wejściową, warstwą asocjacyjną i jedną lub więcej jednostkami wyjściowymi. W większości jego eksperymentów dane wejściowe miały wartości 0 lub 1, odpowiadające czarnym lub białym pikselom na obrazie wizualnym przedstawionym na tak zwanej "siatkówce". Każda jednostka A otrzymała dane wejściowe (które nie zostały pomnożone przez wartości masy) z jakiegoś losowo wybranego podzbioru pikseli i wysłała swój wynik , poprzez zestawy regulowanych wag, do końcowych jednostek wyjściowych, których wartości binarne można interpretować jako kod dla kategorii obrazu wejściowego. Próbowano zastosować różne "procedury szkoleniowe" w celu dostosowania wag jednostek wyjściowych perceptronu alfa , W najbardziej dla tych (dla celów rozpoznawania wzorców) wagi prowadzące do jednostek wyjściowych wynosiły korygowane tylko wtedy, gdy jednostki te popełniły błąd w klasyfikacji danych wejściowych. Korekty były takie, aby wymusić na wyjściu prawidłową klasyfikację dla tego konkretnego wejścia. Ta technika, która wkrótce stała się standardem, została nazwana "procedurą korekcji błędów". Rosenblatt z powodzeniem wykorzystał ją w szeregu eksperymentów do szkolenia perceptronów do klasyfikowania sygnałów wizualnych, takich jak znaki alfanumeryczne lub sygnałów akustycznych, takich jak dźwięki mowy. Profesor H. David Block, matematyk Cornell współpracujący z Rosenblattem, był w stanie udowodnić, że procedura korekcji błędów gwarantuje znalezienie hiperpłaszczyzny, która doskonale oddzieli zestaw danych treningowych, gdy taka hiperpłaszczyzna istniała. wykonane za pomocą symulacji komputerowych, Rosenblatt wolał budować wersje sprzętowe swoich perceptronów (symulacje były wczesne na wczesnych komputerach, co wyjaśniało zainteresowanie budowaniem specjalnego sprzętu perceptronowego). MARK I był alfa-perceptronem zbudowanym w Cornell Aeronautical Laboratory pod sponsorowanie Oddziału Systemów Informatycznych Offce of Naval Research i Rome Air Development Center. Zostało to publicznie zademonstrowane 23 czerwca 1960 r. MARK I używał regulatorów głośności (zwanych przez inżynierów elektryków "potencjometrami") do ważenia. Mają one przymocowane do nich małe silniki w celu wykonania regulacji w celu zwiększenia lub zmniejszenia wartości masy. W 1959 roku Frank Rosenblatt przeniósł swoją pracę perceptronową z Cornell Aeronautical Laboratory w Buffalo w stanie Nowy Jork na Cornell University, gdzie został profesorem psychologii. Wraz z Blockiem i kilkoma studentami Rosenblatt kontynuował eksperymentalne i teoretyczne prace nad perceptronami. Jego książka Principles of Neurodynamics szczegółowo opisuje jego teoretyczne pomysły i wyniki eksperymentów. Ostatni system Rosenblatta, zwany Tobermory, został zbudowany jako urządzenie do rozpoznawania mowy. [Tobermory to imię kota, który nauczył się mówić w The Chronicles of Clovis, grupie opowiadań Saki (H. H. Munro).] Kilka doktorantów studenci, w tym George Nagy, Carl Kessler, R. D. Joseph i inni, ukończyli projekty perceptronowe pod Rosenblattem w Cornell. W ostatnich latach pobytu w Cornell Rosenblatt zajął się badaniem transferu pamięci chemicznej u robaków i innych zwierząt {temat całkowicie usunięty z pracy nad perceptronem. Niestety, Rosenblatt zginął w wypadku podczas żeglugi w zatoce Chesapeake w 1969 roku. Mniej więcej w tym samym czasie co alfa-perceptron Rosenblatta, Woodrow W. (Woody) Bledsoe (1921 {1995) i Iben Browning (1918-1991), dwaj matematycy z Sandia Laboratories w Albuquerque w Nowym Meksyku, również prowadzili badania nad rozpoznawaniem znaków, które wykorzystywały losowe próbki obrazów wejściowych. Eksperymentowali z systemem, który wyświetlał obrazy znaków alfanumerycznych na mozaice 10 x 15 fotokomórek i próbkował stany 75 losowo wybranych par fotokomórek. Wskazując, że pomysł można rozszerzyć na próbkowanie większych grup pikseli, powiedzmy N z nich, nazwali swoją metodę metodą "N-krotki". Wykorzystali wyniki tego próbkowania do podjęcia decyzji o kategorii litery wejściowej

ADALINESY I MADALINES

Niezależnie od Rosenblatt, grupa kierowana przez profesora inżynierii elektrycznej Stanforda Bernarda Widrowa również pracowała nad systemy sieci neuronowych na przełomie lat 50. i 60. XX wieku. Widrow niedawno dołączył do Stanford po ukończeniu doktoratu z teorii sterowania na MIT. Chciał wykorzystać systemy sieci neuronowej do czegoś, co nazwał "kontrolą adaptacyjną". Jedno z urządzeń zbudowanych przez Widrow nazwano "ADALINE "(dla adaptacyjnej sieci liniowej). Był to pojedynczy element neuronowy, którego regulowane ciężary były realizowane przez przełączalne (w ten sposób regulowane) obwody rezystorów. Widow i jeden z jego uczniów, Marcian E. "Ted" Hoff Jr. (który później wynalazł pierwszy mikroprocesor w firmie Intel), opracowali regulowaną wagę, którą nazywali "a" "memistor". Składał się z grafitowego pręta, na którym warstwa miedzi mogła być powlekana i nieplaterowana - zmieniając w ten sposób jej opór elektryczny. Widrow i Hoff opracowali procedurę szkolenia dla ich elementu neuronowego ADALINE, który nazwano algorytmem adaptacyjnym najmniejszych średnich kwadratów Widrowa-Hoffa. Większość eksperymentalnych prac Widrowa została wykonana przy użyciu symulacji na komputerze IBM1620. Ich najbardziej skomplikowany projekt sieci nazwano "MADALINE" (dla wielu ADALINE). Procedurę szkoleniową opracował dla niego w Stanford student William Ridgway.

Systemy MINOS w SRI

Sukces Rosenblatta z perceptronami w problemach z rozpoznawaniem wzorców doprowadził do wzmożenia wysiłków badawczych innych osób w celu powielenia i rozszerzenia jego wyników. W latach sześćdziesiątych być może najbardziej znaczące prace w zakresie rozpoznawania wzorców z wykorzystaniem sieci neuronowych zostały wykonane w Stanford Research Institute w Menlo Park w Kalifornii. Tam Charles A. Rosen (1917-2002) kierował laboratorium, które próbowało wytrawić mikroskopijne lampy próżniowe na podłożu półprzewodnikowym. Rosen spekulował, że obwody zawierające te lampy mogą być ostatecznie "podłączone" do wykonywania przydatnych zadań przy użyciu niektórych procedur szkoleniowych opisanych przez Franka Rosenblatta. SRI zatrudniło Rosenblatta jako konsultanta do pomocy w projektowaniu eksploracyjnej sieci neuronowej. Kiedy w 1960 roku przeprowadziłem wywiad na stanowisko w SRI, zespół w laboratorium Rosen pod kierownictwem Alfreda E. (Teda) Brain (1923-2004) właśnie zakończył budowę małej sieci neuronowej o nazwie MINOS. (W mitologii greckiej Minos był królem Krety i synem Zeusa i Europy. Po śmierci Minos był jednym z trzech sędziów w podziemiu). Brain uważał, że symulacje komputerowe sieci neuronowych są zbyt wolne do praktycznych zastosowań, co prowadzi do decyzji o budowie zamiast programowania. (Komputer IBM 1620 używany w tym samym czasie przez grupę Widrowa w Stanford do symulacji sieci neuronowych miał podstawowy cykl maszynowy wynoszący 21 mikrosekund i maksymalnie 60 000 "cyfr "pamięci o swobodnym dostępie.) W celu regulacji ciężarów MINOS zastosował magnetyczny urządzenia zaprojektowane przez Brain. Rosenblatt pozostawał w bliskim kontakcie z SRI, ponieważ był zainteresowany wykorzystaniem tych urządzeń magnetycznych jako zamienników swoich potencjometrów napędzanych silnikiem. Entuzjazm i optymizm Rosen odnośnie potencjału sieci neuronowych pomógł mu dołączyć do SRI. Po moim przybyciu w lipcu 1961 r. dostał szkic książki Rosenblatta do przeczytania. Zespół Brain dopiero zaczynał prace nad budową dużej sieci neuronowej, zwanej MINOS II, kontynuacją mniejszego systemu MINOS. wspierany przede wszystkim przez Korpus Sygnałowy Armii USA w latach 1958-1967. Celem pracy MINOS było "przeprowadzenie badań naukowych i eksperymentalnych badań technik i sprzętu cechy odpowiednie do praktycznego zastosowania w graficznym przetwarzaniu danych dla potrzeb wojskowych. "Głównym celem projektu było automatyczne rozpoznawanie symboli na mapach wojskowych. Podjęto również próby innych zastosowań - takich jak rozpoznawanie pojazdów wojskowych, takich jak czołgi, na zdjęciach lotniczych i rozpoznawanie ręcznie drukowanych znaków - w pierwszym etapie przetwarzania przez MINOS II obraz wejściowy był replikowany 100 razy za pomocą matrycy plastikowej 10 x 10. Każdy z tych identycznych obrazów został następnie przesłany przez własną optyczną maskę wykrywającą cechy, a światło przez maskę zostało wykryte przez fotokomórkę i porównane z progiem. Rezultatem był zestaw 100 wartości binarnych (wyłączone - włączone). Wartości te stanowiły dane wejściowe do zestawu 63 elementów neuronowych ("jednostek A" w terminologii Rosenblatta), każdy o 100 zmiennych wagach magnetycznych. 63 wyjścia binarne z tych elementów neuronowych zostały następnie przetłumaczone na jedną z 64 decyzji dotyczących kategorii oryginalnego obrazu wejściowego. (Zbudowaliśmy 64 równie odległe "punkty" w sześćdziesięciu trójwymiarowych przestrzeniach i przeszkoliliśmy sieć neuronowa, dzięki czemu każdy obraz wejściowy tworzy punkt bliższy własnemu punktowi prototypu niż innemu. Każdy z tych prototypowych punktów był jedną z 64 "sekwencji rejestru przesuwnego o maksymalnej długości" o 63 wymiarach). W latach 60. grupa sieci neuronowych SRI, zwana wówczas „ Grupa Learning Machines badała wiele różnych organizacji sieciowych i procedur szkoleniowych. Ponieważ komputery stały się zarówno bardziej dostępne, jak i potężniejsze, coraz częściej korzystaliśmy z symulacji (w różnych centrach komputerowych) na komputerach Burroughs 220 i 5000 oraz na IBM 709 i 7090. W połowie lat 60. otrzymaliśmy własny edytowany komputer, SDS 910 (SDS 910, opracowany w Scienti c Data Systems, był pierwszym komputerem, w którym zastosowano tranzystory krzemowe). Użyliśmy tego komputera w połączeniu z najnowszą wersją naszego sprzętu sieci neuronowej (teraz z wykorzystaniem zestawu 1024 soczewek wstępnego przetwarzania), połączenie nazwaliśmy MINOS III. Jednym z najbardziej udanych rezultatów w systemie MINOS III było automatyczne rozpoznawanie ręcznie drukowanych znaków na arkuszach kodujących FORTRAN. (W latach 60. programy komputerowe były zwykle pisane ręcznie, a następnie konwertowane na karty dziurkowane przez operatorów uderzeń kluczowych). Pracami tymi kierowali John Munson (1939–1972), Peter Hart i Richard Duda. Neuronowa część MINOS III została wykorzystana do stworzenia rankingu możliwych klasyfikacji dla każdej postaci z miarą siły dla każdej postaci. Na przykład, pierwszy znak napotkany w ciągu znaków może zostać rozpoznany przez sieć neuronową jako „D” o sile 90 i jako „O” o sile 10. Ale akceptując najbardziej pewną decyzję dla każdego znaku nie może powstać ciąg znaków, który jest prawnym oświadczeniem w języku FORTRAN {wskazując, że co najmniej jedna decyzja była błędna (przy założeniu, że ktokolwiek napisał oświadczenie na arkuszu kodowym napisał oświadczenie prawne). Zaakceptowanie drugiego lub trzeciego najbardziej bezpiecznego wyboru dla niektórych znaków może być wymagane do utworzenia prawidłowego ciągu znaków. Całkowitą stęSenie pełnego ciągu znaków obliczono, dodając stany poszczególnych znaków w ciągu. Następnie potrzebny był sposób uszeregowania tych liczb liczb całkowitych dla każdego z możliwych ciągów wynikających ze wszystkich różnych wyborów dla każdego znaku. Spośród tego rankingu wszystkich możliwych ciągów system następnie wybrał najbardziej pewny ciąg prawny. Jednak, jak napisał Richard Duda, „Problem znalezienia pierwszego, drugiego, trzeciego… najbardziej złożonego ciągu znaków nie jest wcale trywialnym problemem”. Kluczem do skutecznego obliczenia rankingu było zastosowanie metody zwanej programowaniem dynamicznym. Ilustracja próbki oryginalnego źródła i ostatecznego wyjścia pokazano poniżej.



Po przeszkoleniu części sieci neuronowej systemu, cały system (który zdecydował się na najbardziej pewny ciąg prawny) był w stanie osiągnąć dokładność rozpoznawania wynoszącą nieco ponad 98% na dużej próbce materiału, który nie był częścią tego, na co szkolono system. Rozpoznawanie odręcznych postaci z takim poziomem dokładności było znaczącym osiągnięciem w latach sześćdziesiątych. Rozszerzając swoje zainteresowania poza sieci neuronowe, Learning Machines Group ostatecznie przekształciło się w Centrum Sztucznej Inteligencji SRI, które do dziś jest wiodącym przedsiębiorstwem badawczym zajmującym się AI.

Metody statystyczne

W latach pięćdziesiątych i sześćdziesiątych istniało kilka zastosowań metod statystycznych do problemów z rozpoznawaniem wzorców. Wiele z tych metod było bardzo podobnych do niektórych technik sieci neuronowych. Przypomnij sobie, że wcześniej wyjaśniłem, jak zdecydować, który z dwóch tonów będzie obecny w głośnym sygnale radiowym. Podobną technikę można zastosować do rozpoznawania wzorów. Do klasyfikowania obrazów (lub innych danych percepcyjnych) zwykle reprezentowano dane wejściowe za pomocą listy wyróżniających "cech", takich jak te używane przez Selfridge'′a i jego współpracowników. Na przykład w rozpoznawaniu znaków alfanumerycznych jedną z pierwszych cech wyodrębniono z obrazu znaku, który ma zostać sklasyfikowany. Zazwyczaj cechy miały wartości liczbowe, takie jak liczba razy, gdy linie o różnych kątach przecinały znak lub długość obwodu najmniejszego koła, które całkowicie otaczało znak. Wybór odpowiednich funkcji był często bardziej sztuką niż nauką, ale miał kluczowe znaczenie dla dobrej wydajności. Potrzebujemy trochę elementarnej notacji matematycznej, aby pomóc opisać te statystycznie zorientowane metody rozpoznawania wzorców. Załóżmy, że lista funkcji wyodrębnionych ze znaku to {f₁; f₂; … ; f_i;… :; f_N}. Skrócę tę listę za pomocą pogrubionego symbolu X. Załóżmy, że istnieje k kategorii, C₁; C₂;… ; C_i; … ; C_k, do którego może należeć znak opisany przez XUżywając reguły Bayesa w sposób podobny do opisanego wcześniej, reguła decyzyjna jest następująca: Zdecyduj na korzyść tej kategorii, dla której p(X |C_i)p(C_i) jest największe, gdzie p(C_i jest prawdopodobieństwem a priori kategorii C_i i p(p(C_ii) to prawdopodobieństwo X dla C_i. Prawdopodobieństwa te można wywnioskować, zbierając dane statystyczne z dużej próbki znaków. Jak wspomniałem wcześniej, badacze w rozpoznawaniu wzorów często opisują proces decyzyjny w kategoriach geometrii. Wyobrażają sobie, że wartości cech uzyskanych z próbki obrazu można przedstawić jako punkt w przestrzeni wielowymiarowej. Jeśli mamy kilka próbek dla każdej powiedzmy dwóch znanych kategorii danych, możemy reprezentować te próbki jako rozproszenie punktów w przestrzeni. W rozpoznawaniu znaków rozproszenie może wystąpić nie tylko dlatego, że obraz postaci może być hałaśliwy, ale także dlatego, że postacie z tej samej kategorii mogą być rysowane nieco inaczej. Pokazuję dwuwymiarowy przykład z funkcjami f₁ i f₂ na rysunku.



Na podstawie rozproszenia punktów w każdej kategorii możemy obliczyć oszacowanie prawdopodobieństw potrzebnych do obliczenia prawdopodobieństw. Następnie możemy wykorzystać prawdopodobieństwa i wcześniejsze prawdopodobieństwa do podjęcia decyzji. Pokazuję tutaj granicę, obliczoną na podstawie prawdopodobieństw i wcześniejszych prawdopodobieństw, która dzieli przestrzeń na dwa regiony. W jednym regionie decydujemy się na kategorię 1; z drugiej wybieramy kategorię 2. Pokazuję także nowy punkt funkcji, X, który ma zostać sklasyfikowany. W tym przypadku pozycja X względem granicy narzuca, że klasyfikujemy X jako członka kategorii 1. Istnieją również inne metody klasyfikacji punktów charakterystycznych. Ciekawym przykładem jest metoda \ najbliższego sąsiada. W tym schemacie, wynalezionym przez E. Fixa i JL Hodgesa w 1951,nowy punkt cechy jest przypisany do tej samej kategorii, co ten przykładowy punkt cechy, do którego jest najbliżej. na powyższym rysunku nowy punkt X zostałby sklasyfikowany jako należący do kategorii 2. przy użyciu metody najbliższego sąsiada. Ważne opracowanie metody najbliższego sąsiada przypisuje nowy punkt do tej samej kategorii co większość k najbliższych punktów. reguła decyzyjna wydaje się prawdopodobna (w przypadku, gdy istnieje wiele, wiele punktów próbnych każdej kategorii), ponieważ istnieje więcej punktów próbnych kategorii C_i bliżej nieznanego punktu, X, niż punkty próbne kategorii C_j jest dowodem, że p(X | Ci) p (C_i) jest większy niż p(X | C_j)) p (C_j) W oparciu o tę ogólną obserwację Thomas Cover i Peter Hart rygorystycznie przeanalizowali skuteczność metod najbliższego sąsiedztwa. Każda technika rozpoznawania wzorców, nawet wykorzystująca sieci neuronowe lub najbliższych sąsiadów, może być uważana za konstruowanie granic oddzielających w wielowymiarowej przestrzeni cech. Inną metodę konstruowania granic przy użyciu "funkcji potencjalnych" zasugerowali rosyjscy naukowcy M. A. Aizerman, E. M. Braverman i L. I. Rozonoer w latach 60. Niektóre ważne wczesne książki na temat stosowania metod statystycznych w rozpoznawaniu wzorców to George Sebestyen, Richard Duda i Peter Hart. Technologia rozpoznawania wzorów pod koniec lat 60. XX wieku została dobrze oceniona przez George'a Nagy'a (który wcześniej był jednym z doktorantów Franka Rosenblatta).

Zastosowania rozpoznawania wzorów w rozpoznaniu lotniczym Sieć neuronowa i metody statystyczne rozpoznawania wzorców przyciągnęły wiele uwagi w wielu firmach z branży lotniczej i lotniczej na przełomie lat 50. i 60. XX wieku. Firmy te miały duży budżet na badania i rozwój wynikające z umów z Departamentem Obrony USA. Wiele z nich było szczególnie zainteresowanych problemem zwiadu powietrznego, tj. lokalizacją i identyfikacją "celów" na zdjęciach lotniczych. Wśród firm prowadzących szeroko zakrojone programy badawcze poświęcone temu zagadnieniu i powiązanych z nimi problemami był Dział Aeronutronic Ford Motor Co., Douglas Aircraft Company (jak wtedy było znane), General Dynamics, Lockheed Missiles and Space Division oraz Philco Corporation (Philco został później przejęty przez Forda pod koniec 1961 r.) Wspomnę o niektórych pracach w Philco , Laveen N. Kanal, Neil C. Randall i Thomas Harley pracowali zarówno nad teorią, jak i metodami statystycznego rozpoznawania wzorców. Opracowane przez nich systemy służyły do przeglądania zdjęć lotniczych pod kątem interesujących celów wojskowych, takich jak czołgi. ilustracja jednego z ich systemów pokazano na rysunku



Aparat Philco zeskanował materiał z 9-calowych negatywów zebranych przez samolot rozpoznawczy U2 podczas manewrów czołgów armii amerykańskiej w Fort Drum w Nowym Jorku. Niewielka część zeskanowanego zdjęcia, prawdopodobnie zawierająca czołg M-48 (w standardowej pozycji i rozmiarze), została najpierw przetworzona w celu wzmocnienia krawędzi, a wynik został przedstawiony systemowi wykrywania celu jako układ zer i jedynek. Pierwszy z ich systemów używał tablicy 22 x 12; później używali tablicy 32 x 32, jak pokazano na powyższym rysunku. Tablica została następnie podzielona na 24 nakładające się 8 x 8 "bloków cech". Dane w każdym bloku obiektów są następnie poddawane testowi statystycznemu, aby zdecydować, czy mały obszar obrazu reprezentowany przez ten blok zawiera część zbiornika. Testy statystyczne oparto na "próbce szkoleniowej" 50 obrazów zawierających zbiorniki i 50 próbek terenu niezawierającego zbiorników. Dla każdego bloku cech 8 x 8 opracowano parametry statystyczne z tych próbek w celu ustalenia (liniowej) granicy w sześćdziesięciu - czterowymiarowa przestrzeń, która najlepiej rozróżnia próbki zbiorników od próbek nieczołgowych. Korzystając z tych granic, system został następnie przetestowany na innym zestawie 50 obrazów zawierających zbiorniki i 50 obrazów niezawierających zbiorników. Dla każdego obrazu testowego liczba cech bloki decydujące o "obecności czołgu" zostały obliczone, aby uzyskać końcowy "wynik" liczbowy (np. 21 z 24 bloków zdecydowało, że czołg był obecny). Wynik ten może być następnie wykorzystany do podjęcia decyzji, czy obraz zawiera czołg. Autorzy stwierdzili, że "wyniki eksperymentalne procedury klasyfikacji statystycznej przekroczyły wszelkie oczekiwania". Prawie połowa próbek testowych miała doskonałe wyniki (to znaczy, wszystkie 24 bloki cech prawidłowo rozróżniały zbiornik i zbiornik). Ponadto wszystkie próbki testowe zawierające zbiorniki miały wynik większy lub równy 11, a wszystkie próbki testowe niezawierające zbiorników miały wynik mniejszy lub równy 7. System wczesnego wykrywania zbiorników w Philco został zbudowany z analogowym zespół obwodów - nie zaprogramowany na komputerze. Jak później opracował Thomas Harley, lider projektu tego systemu, ważne jest, aby pamiętać o technologicznym kontekście epoki, w której ta praca została wykonana. Wdrożony przez nas system nie miał wbudowanych możliwości obliczeniowych. Ciężarami liniowej funkcji dyskryminacyjnej były rezystory, które kontrolowały prąd pochodzący z (binarnego) źródła napięcia w elementach rejestru przesuwnego. Prądy te zostały zsumowane i każda cecha została rozpoznana lub nie w zależności od tego, czy suma tych prądów przekroczyła wartość progową. Te decyzje dotyczące funkcji binarnych zostały następnie zsumowane, ponownie w analogowym obwodzie elektrycznym, a nie w komputerze, i ponownie podjęto decyzję [zbiornik lub brak zbiornika] w zależności od tego, czy suma przekroczyła wartość progową W innym systemie klasyfikacja statystyczna została wdrożona przez program o nazwie MULTINORM, działający na komputerze Philco 2000. W innych eksperymentach Philco zastosował dodatkowe testy statystyczne, aby w większym stopniu obliczyć niektóre bloki cech niż inne przy obliczaniu wyniku końcowego. Kanal powiedział, że te eksperymenty z ważeniem wyników bloków charakterystycznych "przewidywały ideę klasyfikacji maszyny wektorów nośnych (SVM) [...] przy użyciu pierwszej warstwy do identyfikacji próbek szkoleniowych blisko granicy między zbiornikami i innych czołgi." Oczywiście systemy te miały dość łatwe zadanie. Wszystkie czołgi były w standardowej pozycji i były już odizolowane na zdjęciu. (Autorzy wspominają jednak o tym, w jaki sposób system można dostosować do radzenia sobie z czołgami występującymi w dowolnej pozycji lub orientacji na obrazie. System uważam za interesujący nie tylko ze względu na jego wydajność, ale także ponieważ jest to system warstwowy (podobny do Pandemonium i do alfa-perceptronu) i ponieważ jest to przykład, w którym oryginalny obraz jest podzielony na nakładające się podobrazy, z których każdy jest przetwarzany niezależnie. Jak wspomnę później, nakładające się podobrazy odgrywają znaczącą rolę w niektórych modelach obliczeniowych kory nowej. Niestety raporty Philco zawierające szczegóły tej pracy nie są łatwo dostępne. Co więcej, Philco i niektóre inne grupy zaangażowane w tę pracę zniknęły. Oto, co napisał mi Tom Harley o raportach Philco i o samym Philco: Większość prac związanych z rozpoznawaniem wzorów wykonanych w Philco w latach 60. XX wieku była sponsorowana przez Departament Obrony, a raporty nie były dostępne do publicznej dystrybucji. Od tego czasu sama firma naprawdę rozpłynęła się w powietrzu. Firma Phil Motor została kupiona przez Ford Motor Company w 1961 r., A do 1966 r. Wyeliminowali laboratoria badawcze Philco, w których pracował Laveen Kanal. Ford próbował przenieść tą małą grupę do rozpoznawania wzorów do Newport Beach w Kalifornii [lokalizacja firmy Aeronutronic Division, której grupa do rozpoznawania wzorów również się później złożyła], a kiedy wszyscy postanowili nie iść, przenieśli ich do działu komunikacji i powiedzieli aby zamknąć nasze projekty rozpoznawania wzorców. Laveen ostatecznie przeszedł na University of Maryland. W późniejszych latach to, co było Philco, zostało sprzedane Loralowi, a większość z nich została później sprzedana Lockheedowi Martinowi. Podejście do problemów AI związanych z sieciami neuronowymi i technikami statystycznymi nazwano "niesymbolicznymi" w celu zestawienia ich z pracą "przetwarzania symboli" przez osoby zainteresowane udowodnieniem twierdzeń, graniem w gry i rozwiązywaniem problemów . Te niesymboliczne podejścia znalazły zastosowanie głównie w rozpoznawaniu wzorców, przetwarzaniu mowy i widzeniekomputerowe. Warsztaty i konferencje poświęcone szczególnie tym tematom zaczęły się w latach 60. XX wieku. Podgrupa IEEE Computer Society (podkomitet ds. Rozpoznawania wzorców w komitecie ds. Pozyskiwania i przekształcania danych) zorganizowała pierwsze "rozpoznawanie wzorców" Warsztat ", który odbył się w Puerto Rico w październiku 1966 r. Drugi (w którym uczestniczyłem) odbył się w Delft w Holandii w sierpniu 1968 r. W 1966 r. Ta podgrupa stała się IEEE Computer Society Pattern Analysis and Machine Intelligence (PAMI) ) Komitet techniczny, który nadal organizował konferencje i warsztaty. Tymczasem pod koniec lat 50. i na początku lat 60. ludzie przetwarzający symbole wykonywali swoją pracę głównie na MIT, na Carnegie Mellon University, IBM i na Uniwersytecie Stanforda. przejdź dalej do opisu niektórych z tego, co zrobili.