Algorytmy i struktury danych :: Algorytmy sortowania :: Grafy :: Drzewa :: Wprowadzenie do sieci neuronowych

Teoria informatyki

Podstawy teoretyczne informatyki to w zasadzie duży dział matematyki poświęcony teorii automatów, teorii informacji, teorii grafów, językom formalnym i gramatykom, algorytmom , itp (w zasadzie informatykę teoretyczną można uznać za dział matematyki). Z bardziej specyficznych dla informatyki działów należy wspomnieć o teorii obliczeń, terorii kompilacji (blisko związanej z językami formalnymi) i strukturach dancyh (blisko związanych z algorytmiką). Informatyka teoretyczna zajmuje się w dużej mierze konstrukcją algorytmów, dowodzeniem ich poprawności i analizą złożoności obliczeniowej. Zobacz także: Logika Hoare'a, Niezmiennik pętli, Analiza składniowa, Parser LR, LL parser. Często do teorii informatyki zalicza się także zagadnienia związane z projektowaniem systemów operacyjnych i oprogramowania.

Algorytmy i struktury danych

Klasy złożoności:

Zauważalny jest ogromny wzrost czasu dla algorytmów o złożoności gorszej niż wielomianowa wraz z wzrostem wielkości problemu

metody:

Algorytm wyszukiwania przez podział polega na dzieleniu posortowanej tablicy na części i próbie oszacowania w którym rejonie jest interesujący element

Algorytmy sortowania

Algorytm sortowania nazywamy stabilnym gdy dane o jednakowym kluczu sortowania nie zamieniają się miejscami.

Grafy

Graf to zbiór wierzchołków V i krawędzi L.

Drzewa

Drzewem nazywamy graf acykliczny skierowany.

Przechodzenie przez drzewa:

Drzewa zrównoważone z definicji:

Znajdowanie MST:

Znajdowanie najkrótszej ścieżki w grafie:

bisekcja grafu - Kernighnan-Lin - konstrukcja do wstępnego podziału:

Wprowadzenie do sieci neuronowych

Sieci neuronowe są systemami zdolnymi do przetwarzania danych w problemach trudno algorytmizowalnych. Cechują się odpornością na zniekształcenia danych, zdolnością do uczenia w oparciu o przykłady, zdolnością generalizacji (uogólniania). Dane przetwarzane są w sposób równoległy. Zobacz też: Sztuczna inteligencja.

Budowa sieci wielowarstwowych nie ma sensu w przypadku sieci liniowych, czyli takich w których wektor odpowiedzi y jest liniowo zależy od wektora wejściowego x. Dla pojedynczego neuronu wygląda to w sposób następujący - wyjście jest sumą iloczynu wartości wejścia i wagi odpowiedniego wejścia:
$$y^{(m)} = W^{(m)} \ast x = \sum_{i=1}^n w_i^{(m)} x_i$$

Dzieje się tak dlatego że każde odwzorowanie liniowe możemy zapisać jako macierz, a wynikiem mnożenia dwóch macierzy przez siebie (co odpowiada kolejnemu wykonaniu pierwszej i drugiej warstwy) jest macierz (czyli pojedyncza warstwa). Uczenie neuronu polega na modyfikacji macierzy wag W tak aby uzyskiwać lepszą odpowiedź. W przypadku uczenia z nauczycielem w oparciu o regułę delta chcemy minimalizować funkcję błędu w sensie najmniejszych kwadratów). Musimy zatem zmieniać wagi w kierunku przeciwnym do gradientu funkcji błędu:
$$W' = W + \eta \delta X \qquad  \delta = z -y$$
$$\frac{\partial Q}{\partial y} = -(z-y) = - \delta \qquad \frac{\partial y}{\partial W} = x \qquad \frac{\partial Q}{\partial W} = \frac{\partial Q}{\partial y} \frac{\partial y}{\partial W} = - \delta x_i$$

Możliwe jest także uczenie bez nauczyciela (bez wiedzy o tym jaki powinien być wynik), w metodzie tej wzmocnieniu ulegają wagi dla których odpowiedź jest duża gdy sygnał pobudzający jest duży.

Celem możliwości tworzenia bardziej zaawansowanych odwzorowań wprowadza się elementy nieliniowe, w których wyjście jest funkcją ważonej sumy elementów wejściowych). Najprostszą realizacją nieliniowości jest y = {1, 0} w zależności od znaku pobudzenia.Uczenie odbywa się na podobnej zasadzie jak w przypadku sieci liniowej. Jednowarstwowa sieć nie jest na przykład w stanie realizować odwzorowania XOR, jednak trój-warstwowa sieć (a kolejne warstwy mają sens tylko dla sieci nieliniowych) jest w stanie reprezentować dowolny podział płaszczyzny, zatem także funkcję XOR. Uczenie sieci wielowarstwowych odbywa się poprzez rzutowanie błędu na wszystkie neurony stanowiące wejście mnożąc go przez wagę danego wejścia. Należy zaznaczyć iż więcej neuronów w warstwach ukrytych daje więcej płaszczyzn decyzyjnych, jednak nie zawsze przyczynia się to do lepszego wyniku. W uczeniu sieci nieliniowych spotkać się możemy także z problemem lokalnych minimów do których będą zbiegały wektory wag (pomimo iż nie jest to właściwe rozwiązanie).

Celem usprawnienia procesu uczenia stosuje się różne metody dodatkowe takie jak:

Szczególnym rodzajem są sieci przesyłające żetony (CP) - jest to dwuwarstwowa sieć, w której pierwsza warstwa klasyfikuje otrzymany wektor (z pierwszej warstwy wybieramy tylko wynik z jednego neuronu - największy), każdy neuron drugiej warstwy na swoim wejściu dostaje tylko jedyną liczbę i produkuje w oparciu o nią wektor skojarzony. Sieć taka działa jak tablica przeglądowa. Sieci tego typu stosowane są np. do kompresji danych, analizy statystycznej, rozpoznawania mowy, itp.

Kolejnym typem sieci są sieci RBF. Sieci te posiadają pola receptorowe, trafienie w które powoduje aktywacje danej jednostki wejściowej, oczywiście pola te mogą na siebie nachodzić wtedy pobudzeniu ulega kilka jednostek. Warstwa wejściowa dokonuje klasyfikacji bodźców, a wyjściowa wykonuje operację liniową. Sieci te charakteryzują się dobrą interpolacją lecz kiepską ekstrapolacją.

Ostatnim omówionym tutaj rodzajem sieci są sieci Hopfielda. Są to sieci o połączeniach każdy z każdym (wektor wyjść podawany na wejścia). Sieci te mogą służyć do realizacji pamięci adresowanej treścią, do realizacji takiej koncepcji korzystamy z symetrycznych wag, wyjść mających wartości 1 i -1 i danych zależnością:
$$S_i' = \textrm{sgn} \left( \sum_j w_{ij} s_j \right)$$

Aktualizacja stanów jest asynchroniczna i realizowana poprzez aktualizację (losowo wybrana jednostka dokonuje aktualizacji). Sieci te korzystają z funkcji energetycznej danej zależnością:
$$H=- {1 \over 2} \sum_{ij} w_{ij} s_i s_j$$

Zobacz też: Logika rozmyta, Artificial Neural Networks.



Copyright (c) 1999-2015, Robert Paciorek (http://www.opcode.eu.org/), BSD/MIT-type license


Redystrybucja wersji źródłowych i wynikowych, po lub bez dokonywania modyfikacji JEST DOZWOLONA, pod warunkiem zachowania niniejszej informacji o prawach autorskich. Autor NIE ponosi JAKIEJKOLWIEK odpowiedzialności za skutki użytkowania tego dokumentu/programu oraz za wykorzystanie zawartych tu informacji.

This text/program is free document/software. Redistribution and use in source and binary forms, with or without modification, ARE PERMITTED provided save this copyright notice. This document/program is distributed WITHOUT any warranty, use at YOUR own risk.

Valid XHTML 1.1 Dokument ten (URL: http://www.opcode.eu.org/programing/more/theory_of_computer_science) należy do serwisu OpCode. Autorem tej strony jest Robert Paciorek, wszelkie uwagi proszę kierować na adres e-mail serwisu: webmaster@opcode.eu.org.
Data ostatniej modyfikacji artykulu: '2015-10-10 11:33:49 (UTC)' (data ta może być zafałszowana niemerytorycznymi modyfikacjami artykułu).