AI, algorytmy

Odpowiedz Nowy wątek
2018-09-14 14:20
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?

Pozostało 580 znaków

2018-09-14 14:28
2

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

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


Na PW przyjmuje tylko (ciekawe!) zlecenia. Masz problem? Pisz na forum, nie do mnie.

Pozostało 580 znaków

2018-09-14 14:40
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.

edytowany 2x, ostatnio: vpiotr, 2018-09-14 14:41
Evolijava? Możesz rozwinąć? - yarel 2018-09-14 14:45

Pozostało 580 znaków

2018-09-14 14:43
1

Hej,
co nieco było rozważane: https://en.wikipedia.org/wiki/Non-deterministic_Turing_machine

Pozostało 580 znaków

2018-09-14 14:48
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.

Pozostało 580 znaków

2018-09-14 14:50
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.

Pozostało 580 znaków

2018-09-14 14:56
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:

Pozostało 580 znaków

2018-09-14 15:06
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[...]ode-with-genetic-programming/

Pozostało 580 znaków

2018-09-16 01:36
0

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 ;)

edytowany 5x, ostatnio: superdurszlak, 2018-09-16 09:33

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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