Autor Wątek: Uniwersalna postać funkcji określonej na podstawie wejścia i wyjścia  (Przeczytany 473 razy)

Offline komorra

  • Użytkownik
    • Blog naszego teamu (o grze Voxelfield)

# Sierpień 09, 2017, 11:45:21
Witam, mam taki problem jak tutaj opisałem: https://math.stackexchange.com/q/2386751/470452

W skrócie
Mamy funkcję której wejście to dowolna liczba całkowita nieujemna (0-MAX), gdzie MAX może być bardzo dużą liczbą, a wyjście to True lub False. Funkcji nie znamy, wiemy jedynie że nie jest "zbyt złożona", oraz możemy testować dowolną wartość wejściową. To czego poszukuję to może nie tyle wzór, formuła tej funkcji co dowolna reprezentacja (może być to równie dobrze maszyna stanu, jakiś inny algorytm - postać nie ma znaczenia), która zwróci poprawny wynik zarówno dla testowanych argumentów jak i kolejnych.

Co zostało zrobione
Próbowałem programowania genetycznego (C#/AForge.NET/SharpGenetic). Spróbuję opisac pokrótce jaki był tego przebieg. Wydaje mi się że najtrudniejsze jest tutaj znalezienie uniwersalnej postaci szukanej funkcji (którą można wyrazić w sekwencji bajtów, tak by łatwo "współgrała" z chromosomami) oraz dobrej funkcji dopasowania (Fitness Function), która to punktuje uzyskane rezultaty. Co do postaci/reprezentacji funkcji, próbowałem ją dobrać "na oko" (a to raczej nie jest dobra metoda naukowa, lecz nie udało mi się znaleźć w necie nic na temat jak taką reprezentację dobrać). Np. jednym z modeli reprezentacji było coś w rodzaju "kaskady" operacji logicznych. Polegało to na tym że np. jak mamy 512 bitów wejściowych, to ustawiałem ich pewną losową kolejność, w każdej parze sąsiednich bitów ustawiałem losową operację logiczną (AND, OR, NOT A, NOT B, A, B, XOR, ALWAYS 1, ALWAYS 0 itd.). Następnie tworzył się drugi stopień kaskady w postaci wyników tych operacji, czyli 256 bitów. I tak stopniowo aż do pojedynczego bitu, który miał być tym wyjściowym. Następnie funkcja dopasowania, polegała na wzięciu 10000 losowych wejść i porównanie ile procent wyjścia jest zgodne (wynik oryginalnej funkcji porównany z wynikiem tej kaskadowej reprezentacji). Ustawiałem zazwyczaj parametry algorytmu genetycznego mnie więcej tak: 2048 populacja, 95% mutacja, 10% crossover, selekcja elitarna + po stagnacji regeneracja (losowo) 20% populacji. To dało pewne rezultaty, ale chyba reprezentacja utknęła w jakimś lokalnym punkcie, ponieważ po wielu godzinach nieustannego processingu, funkcja dopasowania dochodziła do wartości 56-58% i na tym się zatrzymało wszystko.

Na forum Math Stackexchange otrzymałem odpowiedź że jest to nieosiągalne - choć ta odpowiedź akurat nie miała jakieś podstawy lub argumentów, które by ją poparły.

Dlatego z góry dzięki za pomoc w jakikolwiek sposób, może to byc lista haseł do pogoglowania, jakiś "pejper" naukowy w tym temacie. Nawet jakiś dowód matematyczny, który by udowadniał, że jest to nie możliwe - tak aby sprawę tego problemu finalizować, albo w tą albo w drugą stronę. Fajnie też jakby można podyskutować trochę o tym problemie - w końcu od tego mamy forum. Mimo że temat trochę odchodzi od gier, jestem pewien, że ktoś o większym doświadczeniu matematycznym, które w gamedev się bardzo przydaje, będzie w stanie trochę podpowiedzieć.

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Dab

  • Redaktor
    • blog

# Sierpień 09, 2017, 14:04:47
Spróbowałbym potraktować wejście funkcji jako 256 binarnych parametrów i zbudować ANN, chociażby używając TensorFlow. Skoro "chałupniczy" algorytm dał ~60% fitu to znaczy, że funkcja podlega pewnym wzorcom i TF powinien po odpowiednio długim treningu dać sporo więcej.

Ale na stacku nie kłamią, ogólnie nie ma "magicznej metody" na wszystkie możliwe funkcje bo to co opisujesz to po prostu problem kompresji (gdzie masz 2^2^256 różnych możliwych funkcji) i entropia nie pozwala na ich zapis w mniejszej ilości bitów. ;)

Offline mihu

  • Użytkownik
    • mihu

# Sierpień 09, 2017, 14:30:08
Masz 2^256 zamkniętych pudełek. Każde może być puste (false) albo pełne (true). Zostały wypełnione całkowicie losowo (o ile ci wiadomo). Więc choćbyś sprawdził (2^256)-1 pudełek i zobaczył jakiś wzorzec, to nadal nie masz 100% pewności co będzie w tym ostatnim (bo obie funkcje - z pewnym wzorcem, ale różniące się tylko ostatnim pudełkiem - są możliwe).

Offline matheavyk

  • Użytkownik
    • rabagames.com

# Sierpień 09, 2017, 14:37:58
Ja tylko rzucę ogólne przemyślenie, bo matematyka wyższa zadziwiająco szybko wyparowuje z mojej głowy:). (edit: odwołuję, to nie jest żadna matematyka wyższa ;p)

Weźmy dowolną liczbę par wartości (wejście, wyjście). Czy możemy podać co najmniej dwie funkcje, dla których te wartości są prawidłowe? Możemy, chociażby opisując jedną funkcję tymi właśnie parami (po programistycznemu: ifami), a do drugiej dorzucić jakąś inną parę wartości w gratisie. Pytanie, co to znaczy, że funkcja nie jest "zbyt złożona"? Moim zdaniem nałożenie warunków na postać tej funkcji może usprawnić jej liczenie. A później, być może określenie dokładności rozwiązania, bo może nie zależy Ci na tym, żeby znaleziona funkcja zachowywała się idealnie.

Po przeczytaniu stacka i odpowiedzi Daba jestem pewien, że musisz podać jakieś dodatkowe warunki (ograniczenia), jeśli chcesz coś sensownego uzyskać. Bo w tej chwili to nawet właściwie nie wiadomo co Ty liczysz i po co :P. 2 ^ 2 ^ 256 to jest najlepsza odpowiedź na Twój problem jaka istnieje, nie musisz pisać żadnych algorytmów innych niż brute force po wszystkich wartościach.
« Ostatnia zmiana: Sierpień 09, 2017, 14:40:32 wysłana przez matheavyk »

Offline komorra

  • Użytkownik
    • Blog naszego teamu (o grze Voxelfield)

# Sierpień 09, 2017, 14:38:25
@Dab: próbowałem również i tego (choć przyznam, że pobieżnie), ale miałem problem bo 256 wejść reprezentowałem jako 0.0 i 1.0 a wynik również jako jeden double 0.0 lub 1.0, efekt był taki że siec "szalała" jak również i error rate, ale skoro mówisz o sieciach neuronowych, a ja nie wspomniałem o tym w pierwszym poście, to możliwe że jest to coś wartego głębszej uwagi.

@mihu: Zgadza się, ale wzorzec musiałby być bardzo skomplikowany żeby mnie w jednym pudełku oszukać, a ja wiem np. o tej funkcji że złożoność to O(1) (cokolwiek to pomoże tutaj...), i wiem że na pewno ma mniej niż no powiedzmy 1000 operacji logicznych/arytmetycznych. Tak więc jak sprawdzi się dla próbki miliarda losowych wejść to (chyba że się mylę) powinno być ok dla większości pozostałych.

Offline komorra

  • Użytkownik
    • Blog naszego teamu (o grze Voxelfield)

# Sierpień 09, 2017, 14:43:53
@matheavyk: fakt, "nie jest zbyt złożona" nie jest precyzyjne. Może tak, przyjmijmy że ona ma mniej niż 1000 operacji logicznych/arytmetycznych.  Znaleziona funkcja nie musi również byc idealna, wystarczy że będzie satysfakcjonująca dla 99.9% testowanego inputu, już takie coś by mi wystarczyło. Ale przecież nie mogę podac 2^256 x 0.999 wartości, bo nawet samo ich wylistowanie to już "kosmos".

Offline ld

  • Użytkownik

# Sierpień 09, 2017, 14:44:56
Takie moje luźne rozważania (może okażą się pomocne):

1. Rozważmy prostszą funkcję f, która przyjmuje wartość TRUE dla ustalonego argumentu x z kreską oraz wartość FALSE dla pozostałych argumentów. Liczba x z kreską należy do zbioru liczb całkowitych od 0 do MAX.
Zatem wyznaczenie wzoru funkcji sprowadza się do odnalezienia wartości x z kreską. To jest trudne zadanie odkąd wartość funkcji f dla x z kreską nie zależy od wartości pozostałych argumentów (brak też jest innych powiązań). Jedyną metodą, którą dostrzegam to wyznaczanie wartości funkcji f dla wybranych argumentów aż do odnalezienia argumentu, dla którego funkcja przyjmuje wartość TRUE. W najgorszym przypadku będziemy musieli sprawdzić MAX mniej jeden argumentów (ostatni będzie poszukiwanym x z kreską). Konkludując wyznaczenie wzoru funkcji f jest możliwe ale może wymagać wyznaczenie wartości funkcji dla wielu argumentów.

Ogólne zadanie będzie  tak samo trudne lub trudniejsze.

Inne podejście:

2. Rozważmy dowolną  i ustaloną funkcję f. Spróbujmy przewidzieć jaką wartość funkcja będzie miała dla argumentu x=0. Moim zdaniem nie da się tego zrobić inaczej niż podstawić 0 pod wzór funkcji (którego nie znamy). Co składnia do przekonania że podobnie będzie z innymi argumentami. Nie widzę innej metody na określenie wartości funkcji dla zadanego argumentu x inaczej niż wyznaczenie f(x).
Zadanie mogłoby być prostsze gdybyśmy coś wiedzieli o funkcji f.     

3. Podobnie sprawa wygląda gdybyśmy rozważyli  funkcję f z losową przypisanymi wartościami TRUE oraz FALSE. Chodź nie wiem czy nie jest to funkcją zbyt 'złożona' :)

Pozdrawiam

Offline Patrulek

  • Użytkownik

# Sierpień 10, 2017, 00:07:45
Odnośnie programowania genetycznego: próbowałeś może zmienić parametry algorytmu? 95% mutacji brzmi jakby algorytm miał problemy ze stabilizacją populacji przez co ostatecznie mógł wyznaczyć wynik bliski randomowemu wybieraniu. Proporcje mutacji/crossingu powinny być raczej odwrotne. Chyba że pomyliłeś się tylko podczas pisania postu. W dodatku przyjmując, że funkcja składa się z 2^9 operatorów, gdzie każdy z nich jest jednym z, mniej więcej, dziesięciu zdefiniowanych, to masz do wyboru jedną funkcję spośród 10^(2^9). Próbowałeś zmniejszyć zakres liczby wejściowej, liczby zdefiniowanych operatorów lub głębokości drzewa np. pozwalając na większą ilość bitów niż 1 jako operand i zobaczyć jak sobie algorytm wtedy poradzi?

Próbowałeś może sprawdzić statystycznie, czy są jakieś bity które mają znaczący wpływ na wynik? Czy dana sekwencja bitów, niezależnie od położenia, generuje taki sam wynik? A może generuje go według jakiegoś prostego schematu? Różnica w liczbie zer/jedynek? Możliwości jest zbyt dużo, żeby dało się to jakoś sensownie rozwiązać, ale może istnieje jakaś bardzo prosta zależność, którą jesteś w stanie wymyślić i przetestować niewielkim nakładem czasowym?

Ogółem poszedłbym za radą Dab'a i skorzystał z sieci neuronowych, ale poszedłbym raczej w głębokie uczenie. Możesz np. spróbować przyjąć, że cała liczba jest dwukanałowym obrazem 16x16 i spróbować uczyć sieć, tak jak robi się to dla obrazów. Jeśli masz dostęp do mocnych kart graficznych, to może być to jakaś metoda.

Podejście do problemu z innej strony: reverse engineering (o ile masz dostęp do programu).

Offline komorra

  • Użytkownik
    • Blog naszego teamu (o grze Voxelfield)

# Sierpień 10, 2017, 04:32:40
Odnośnie programowania genetycznego: próbowałeś może zmienić parametry algorytmu? 95% mutacji brzmi jakby algorytm miał problemy ze stabilizacją populacji przez co ostatecznie mógł wyznaczyć wynik bliski randomowemu wybieraniu. Proporcje mutacji/crossingu powinny być raczej odwrotne. Chyba że pomyliłeś się tylko podczas pisania postu.

Zgadza się, mam 95% mutacji. Ogólnie jak zapisywałem tą "kaskadę" jako dwie serie bajtów: opers and orders to nie miałem za bardzo pomysłu jak zdefiniowac operację crossoveru tak aby było sensownie. Opers to tablica operatorów (z wartościami od 0 do 10), Orders natomiast to tablica która poprzez swoje wartości sugeruje odpowiednie przemieszanie elementów, jakby permutację, zmianę kolejności na odpowiadającej kaskadzie. Crossover więc zdefiniowałem jak typowy crossover na bajtach poprostu i wziąłem go mało a w pewnych iteracjach rozwiązywania problemu w ogóle dałem go na zero procent.

Próbowałeś może sprawdzić statystycznie, czy są jakieś bity które mają znaczący wpływ na wynik? Czy dana sekwencja bitów, niezależnie od położenia, generuje taki sam wynik? A może generuje go według jakiegoś prostego schematu? Różnica w liczbie zer/jedynek? Możliwości jest zbyt dużo, żeby dało się to jakoś sensownie rozwiązać, ale może istnieje jakaś bardzo prosta zależność, którą jesteś w stanie wymyślić i przetestować niewielkim nakładem czasowym?

Tak, próbowałem. Niestety statystycznie bity na bardzo dużą próbę mają prawdopodobieństwo 50% bit 1 (lub 0) z odchyleniami na poziomie jednych stutysięcznych (+/-)


Powyżej zalinkowałem jak wrzuciłem kolejne liczby zapełniając obrazek tak jak się pisze tekst (od lewej do prawej, z góry na dół, wiersz po wierszu). Wygląda to jak PRNG (tak mi się wydaje), też jak zmieniam wymiary obrazka to pattern (a raczej jego brak) wygląda podobnie, brak wyraźnych wizualnych, wyróżniających się schematów. Na reddicie wczoraj natrafiłem na metodę jakichś sfer szumu, że niby się wolumetrycznie bierze trzy wartości z takiej sekwencji i traktuje jako X,Y i Z i się stawia tam punkt, i tak dalej z kolejnymi trzema, i z następnymi itd. Po takiej operacji, sfera może byc równie gęsto wypełniona, ale jest duża szansa że otrzymamy jakiś patern.

Ogółem poszedłbym za radą Dab'a i skorzystał z sieci neuronowych, ale poszedłbym raczej w głębokie uczenie. Możesz np. spróbować przyjąć, że cała liczba jest dwukanałowym obrazem 16x16 i spróbować uczyć sieć, tak jak robi się to dla obrazów. Jeśli masz dostęp do mocnych kart graficznych, to może być to jakaś metoda.

Próbowałem pójśc za radą Dab'a, ale nie umiem dobrac odpowiedniej liczby warstw ukrytych, i odpowiedniej funkcji aktywacji (wybierałem sigmoidy i z dużą alfą i z małą i z bardzo małą i nic). Cały czas error rate nie schodzi w dół tylko raz spadnie raz wzrośnie. Próbowałem tego z niskimi i wysokimi learning rate i nic.

Co do reverse engineringu, mam kod, ale wole to spróbowac na samym koncu (bo fajnie by miec metodę która to robi na samym wejsciach i wyjsciach, dowolnej blackboxowej funkcji).

Czyli mamy dwie potencjalne ścieżki: neuronowe sieci (ale nie umiem dobrac parametrów sieci), oraz algorytm genetyczny / programowanie ewolucyjne - gdzie blokuje mnie sensowana operacja crossoveru (nie wiem jak to zdefiniowac tak żeby crossover był poprawny), ogólnie reprezentacja funkcji w bajt-kodzie (chromsom) oraz odpowiednia funkcja fitnessu (bo czy odległośc bitowa Hamminga od originalnego outputu wystarcza?).

Offline Patrulek

  • Użytkownik

# Sierpień 11, 2017, 09:45:37
Cytuj
Ogólnie jak zapisywałem tą "kaskadę" jako dwie serie bajtów: opers and orders to nie miałem za bardzo pomysłu jak zdefiniowac operację crossoveru tak aby było sensownie. Opers to tablica operatorów (z wartościami od 0 do 10), Orders natomiast to tablica która poprzez swoje wartości sugeruje odpowiednie przemieszanie elementów, jakby permutację, zmianę kolejności na odpowiadającej kaskadzie. Crossover więc zdefiniowałem jak typowy crossover na bajtach poprostu i wziąłem go mało a w pewnych iteracjach rozwiązywania problemu w ogóle dałem go na zero procent.

Nie bardzo rozumiem co masz na myśli mówiąc o permutacji elementów. Kaskada o której piszesz jest tak jakby drzewem. Operację krzyżowania możesz zdefiniować dzieląc to drzewo na dwie części (niekoniecznie równe) i tworzyć potomków biorąc lewą część z pierwszego rodzica i prawą część z drugiego, i na odwrót. Przy czym robisz to tylko z operatorami. Mógłbyś próbować też dzielić liczbę wejściową, ale wtedy musiałbyś "naprawiać dzieci", tj. usuwać powtarzające się bity i dodawać brakujące. Myślę, że lepiej jakby tym zajął się operator mutacji. Poglądowy rysunek:



Operator mutacji z kolei, zamienia miejscami poddrzewa w drzewie lub kolejność bitów liczby wejściowej. Odległość Hamminga wydaje się sensowną funkcją dopasowania.


Cytuj
Próbowałem pójśc za radą Dab'a, ale nie umiem dobrac odpowiedniej liczby warstw ukrytych, i odpowiedniej funkcji aktywacji (wybierałem sigmoidy i z dużą alfą i z małą i z bardzo małą i nic). Cały czas error rate nie schodzi w dół tylko raz spadnie raz wzrośnie. Próbowałem tego z niskimi i wysokimi learning rate i nic.

Tutaj jest nieduże narzędzie, które być może mogłoby Ci pomóc w doborze topologii sieci. Nie używałem, nie wiem jak to w praktyce wychodzi, ale wygląda ciekawie.
Tutaj z kolei masz slajdy ze Stanfordu odnośnie deep learningu. Nawet jeśli byś nie chciał budować głębokich sieci to jest tam trochę informacji/pojęć, które mogą być przydatne + jest kilka architektur wykorzystanych w konkursie ImageNet.
Ogółem co do doboru parametrów to nie ma dobrej metody na każdy problem. Można na początku się trochę pobawić samemu jeśli masz jakieś przypuszczenia odnośnie tego, co może się sprawdzić, ale najlepiej chyba po prostu puścić automat, który znajdzie odpowiednie parametry.