AI, algorytmy

0

Przypuścmy, że mamy maszynę virtualną z pamięcią mieszczącą dane wejściowe naszego problemu oraz mieszczącą rozwiązanie.
Czy możliwe jest maszynowe wygenerowanie bytecode realizującego algorytm rozwiązujący nasz problem?

To co znamy, to dane wejściowe i wyjściowe dla pewnego (raczej małego) podzbioru danych, np. na wejściu mamy graf, na wyjściu cykl Hamiltona.
Wiemy też, że wykonanie bytecodu:

  • powinno skończyć się w czasie nie dłuższym niż <X (raczej ograniczenia praktyczne, sekundy, minuty, a nie lata)
  • powinno wygenerować poprawną odpowiedź
  • powinien zajmować nie więcej niż N bajtów kodujących operacje VM

Dodatkowo jesteśmy w stanie generować coraz to większe rozmiary problemów (graf + ścieżka), tak by zweryfikować poprawność wygenerowanego byte codu.

Przestrzeń wszystkich możliwych bytecodów jest ogromna, ale w czasie cloudów i algorytmów genetycznych może fizycznie wykonalne :-)
Taka implementacja o ile istnieje, mogłaby być poddana procesowi reverse-engineeringu i mielibyśmy 'algorithm mining' :-)

Może coś takiego już było rozważane akademicko i jakaś konkluzja się pojawiła, albo ktoś jakieś odnośniki ciekawe ma?

2

https://en.wikipedia.org/wiki/Program_synthesis

Generalnie bardzo trudno to zrobić nawet dla bardzo prostych problemów.

0

Rozumiem, że z jakichś przyczyn evolijava to za mało?
Takie problemy mają szerokie spektrum trudności, od banalnych typu Corewar do niemożliwych do realizacji.

0
Shalom napisał(a):

https://en.wikipedia.org/wiki/Program_synthesis

Generalnie bardzo trudno to zrobić nawet dla bardzo prostych problemów.

Dzięki za linka, teraz już wiem jak się to fachowo nazywa ;-) O ile dobrze rozumiem, to "synteza programów" ma jednak dodatkową "warstwę" specyfikacji, efektem końcowym powinien być program, który się gdzieś wykona. W takim "ewolucyjnym" podejściu (lub jak kto woli, formie sprytnego brtue-forca/random-searcha) wydaje mi się, że nie byłoby takiej konieczności, po prostu szukanie implementacji. Tylko maszyna wirtualna powinna mieć jakiś mega minimalistyczny zestaw instrukcji, żeby przestrzeni poszukiwań nie rozdmuchiwać jeszcze bardziej.

0

Jeżeli masz testy, które musi przejść kod, losowo wszystkie kombinacje danego zbioru funkcji, to wcześniej czy później dla małych funkcji znajdziesz rozwiązanie.

1
yarel napisał(a):

Evolijava? Możesz rozwinąć?

To była zła nazwa (byłem za firewall), chodziło mi o to:
https://cs.gmu.edu/~eclab/projects/ecj/

Od razu przyznaję że takie rzeczy robiłem w C++, w Javie powinno być 100x łatwiej (bytecode).

Oprócz tego są bardziej praktyczne tematy:

2

Warte przeczytania, trochę teorii + przykłady jak wygenerować kod rozwiązaując konkretne równanie albo przykład jak program uczy się wypisać "Hello world!" :)
http://www.primaryobjects.com/2018/09/03/creating-self-assembling-code-with-genetic-programming/

1

TL;DR heresy alert, miałem wenę na fantazjowanie o abstrakcjach i abstrakcyjnym znajdowaniu abstrakcyjnych rozwiązań abstrakcyjnych problemów ¯\_(ツ)_/¯

Myślę, że sporo też zależy od sposobu, w jaki dostarczałbyś algorytmowi danych wejściowych i oczekiwanych wyjściowych.

Podasz na wejściu macierz sąsiedztwa jako ciąg liczb, na wyjściu listę węzłów tudzież krawędzi jako ciąg liczb, i możesz sobie zaprząc do pracy całe TOP500, a i tak AI nauczy się zwracać śmieci - bo i do przetworzenia dostało śmieci. Jeszcze się okaże, że jak dodasz odpowiednie liczby z wejścia na odpowiednich pozycjach, to dostaniesz te numerki, co trzeba... w danym przypadku. Będzie szybkie, dla znanych danych da wynik, dla AI będzie good enough ;)

Co innego, gdyby danymi wejściowymi dla AI generującego rozwiązanie był jakiś sformalizowany słowno-muzyczny opis problemu, który dałoby się przetworzyć. Algorytm mógłby znać z góry tylko najbardziej podstawowe "klocki" w postaci danych, struktur danych i operacji na nich, a dostawać wymagania dotyczące uzyskiwanego rozwiązania. Definiowałbyś, co program przyjmuje na wejściu (graf) a co podaje na wyjściu (cykl Hamiltona) i jakie warunki ma spełniać wyjście (unikalność węzłów, każdy węzeł z grafu jest w cyklu dokładnie raz poza pierwszym, na którym cykl się zamyka itd) i pozwolić AI składać klocki choćby i BF, aż znajdzie prawidłowy sposób - nadal byłby to twardy orzech do zgryzienia, ale przynajmniej nie operowałbyś na poziomie pojedynczych rozkazów, adresów/referencji i prymitywnych danych, tylko jakichś podstawowych abstrakcji. Nie byłoby to pewnie ani łatwiejsze, ani bardziej wykonalne od opierania się na suchych danych, ale przynajmniej pozwoliłoby wyeliminować czynnik przeuczenia ;)

Gdyby dołączyć do tego bazę wiedzy, AI mogłaby sprawdzić najpierw, czy nie zna już czegoś, co przekształca dane wejściowe w wyjściowe spełniając wymagania. Jak nie, zaczynałaby zabawę w szukanie takiego DAG operacji, który finalnie dawałby spełnione wymagania. Jest jeszcze kwestia ustalenia, jakie wymagania są w danym momencie spełniane przez proponowane rozwiązanie, co pozwoliłoby określać, czy np. błędne rozwiązanie jest całkowicie błędne, czy już prawie dobre bo nie spełnia np. 2 z 8 wymagań - dla "gołych danych" AI nadal plułoby śmieciami. Na pewno wymagałoby to zdefiniowania, jakie wymagania są spełniane przez poszczególne podstawowe elementy całej tej układanki i budowanie z tego całościowego obrazu sytuacji. Na dobrą sprawę żeby budowanie rozwiązań nie było całkowicie przypadkowe, to w przypadku nieznalezienia w bazie wiedzy klocka spełniającego wymogi w 100%, można by rozważyć rozpoczęcie od takiego, który spełnia tylko część.

Weźmy taką sytuację:
Chcemy, aby AI znalazła algorytm zwracający liczbę przeciwną do danej. Możemy zdefiniować sobie wymagania:

  • mod(in) = mod(out)
  • sgn(in) = -sgn(out)

W bazie wiedzy nie ma jeszcze operacji spełniającej te wymogi, ale jest mnożenie spełniające wymogi m.in.:

  • sgn(x) * sgn(y) = sgn(x * y)
  • mod(x) * mod(y) = mod(x * y)

Oraz dana -1 spełniająca wymogi:

  • sgn(-1) = -1
  • mod(x * -1) = mod(x)

AI dowolną metodą dochodzi w pewnym momencie do takiego rozwiązania: out = mul(in, -1). Analizuje wymagania:

  • mod(in) = mod(out) - OK, bo mod(x * -1) = mod(x)
  • sgn(in) = -sgn(out) - OK, bo sgn(-1) = -1 oraz sgn(x * -1) = sgn(x) * sgn(-1) = -sgn(x)

Okazuje się, że operacja out = mul(in, -1) faktycznie daje nam liczbę przeciwną, więc jest podawana jako odpowiedź a ponadto ląduje w bazie wiedzy. Innym razem może się okazać, że ta operacja spełnia jeszcze jakiś wymóg, nieistotny przy pierwszym jej wykorzystaniu - baza wiedzy zostałaby jedynie zaktualizowana o informację o spełnianych wymaganiach.

Na koniec można by uzbroić AI w mechanizm upraszczania rozwiązania, np. wycinania z DAG operacji tych wzajemnie znoszących się, upraszczania operacji zastępując ciąg prymitywnych jakąś znaną złożoną o analogicznym skutku dla danego przypadku itd. Nawet jeszcze w trakcie budowania rozwiązania, żeby te DAGi nie rozbudowywały się nadmiernie bo trudniej będzie poszukiwać rozwiązania gdy będą nadmiernie skomplikowane ;)

PS. w sumie to wymyśliłem te głupoty na poczekaniu, a jest po 1 w nocy, więc potraktujcie je proszę w przymrużeniem oka ;)

1 użytkowników online, w tym zalogowanych: 0, gości: 1