W dniu 2010-09-06 11:51, Mariusz Marszałkowski pisze:
> Muszę ułożyć pełny układ równań, czy da się
> jakoś prościej/szybciej albo na mniejszej pamięci?
>
Poszukaj tutaj: http://www.cise.ufl.edu/research/sparse/

Pozdrawiam,
Wit

do góry

On 9 Wrz, 12:11, bartekltg <b...@g...com> wrote:
> Mówiłem to ostatnio, mialem to raz jeszcze napisać
> w odpowiedzi ktorą powolitku pisze dla drugiej odnogi wątku,
> ale wspomne o tym teraz: moze jednak zatrudnijcie jakiegos
> matematyka/numeryka.
Żałuję, ale to nie przejdzie z dwóch powodów:
1) nie ma funduszy choćby na przeciętne wynagrodzenie
2) bardzo specyficzne wymagania co do poufności

> Cormen nie jest podręcznikiem do numerkow;)
Ale Cormena najłatwiej trawię. W Cormenie jest
probabilistyczny algorytm mnożenia macierzy
bolowskich, może to nasunie jakieś rozwiązanie.

> Nazywasz dwie macierze ta samną literką? To sie nie dogadamy;)
> Nazwijmy B=A^t*A.
>
> B rzeczywiscie jest gęsta, ale A jest rzadka.
Teraz wszystko jasne.

> Dla przypomnienia, zagadnienie jest n*N  n>N (n=1000N)
> N=K*M.
> A ma n*K niezerowych elementow.
Zgadza się

> Nie kazda metoda zminimalizowania norm(Ax-b)
> opiera sie na operacjach na maczierzy B.
Świetnie, tego szukam.

> Jest druga 'szkolna' metoda, przez rozklad QR.
>
> A=QR
> R=[R_1; 0]
> liczymy Q^t *b, powstaly wektor obcianmy
> no N wspolrzednych (wektor w) i rozwiazujemy
> uklad trojkatny
>
> R_1 x = w.
>
> Jako zalazek do poszukiwan:http://en.wikipedia.org/wiki/Numerical_me
thods_for_linear_least_squar...
>
> QR jest czasem lepsze, bo  "operujemy na A" a nie na "A kwadarat".
Dokładnie czegoś takiego potrzebuję.

> Uwarunkowanie!
> No, ta metoda (ani SVD) do tego zagadnienia tez sie nie specjalnie nie
> nadadza.
Hmmmm

> > On 6 Wrz, 17:33, bartekltg <b...@g...com> wrote:> Ile jest wektorów?
powiedzmy n >> N.
> > A jeśli N jest równe milion? :)
>
> Hmm, to ciezko bedzie:) Skąd wezmiesz 8 pata(10^15) bajtow dysku:)
Nawet 10^15 by nie starczyło :)

> > Oryginalny wektor ma niecałe 100 wartości ze małego zbioru
> > liczb całkowitych, np. <-7,+7>. Wektor ten będzie mapowany
> > przy pomocy nieliniowej funkcji  w dużo większy wektor
> > zero-jedynkowy o takich własnościach jak napisałem - tylko
> > jedna jedynka w każdej części.
>
> A nie działa to dlagtego, ze jest ladnie losowo i na kazdą
> z grup przypada 'tele samo wektora'?
Całkiem możliwe.

> Są algorytmy 'iteracyjne', w tym 'randomizowane'.
> mozna pojsc w tym kierunku, zwlaszcza, ze dane
> naplywają stopniowo.
>
> Mozna 'na raz' optymalizować wiecej niz jeden skladnik
> wektora wspolczynnikow x, ale na oko nie jest to oplacalne.
Można próbować gradientów sprzężonych, ale to się
skończy ogromną ilością iteracji...

> Uzywamy wlasciwie tylko mnozenia przez rzadką A
> (musisz ja zapisać rozsadnie, aby nie iterowc po zerach).
> ilosc potrzebnych interacji to juz inna sprawa, jesli masz
> gigabajty, to nie spodziewaj sie szybko wyniku;)
Jeśli nie da się szybko, to będę musiał zrobić inne mapowanie
wektorów, nie będzie wyjścia.


> Powinno sie wygoglac bardziej zaawansowane tego typu metody,
> poszukaj po least squares, sparse, moze cos o iterowaniu i wariacje.
>
> Zupelnie inna metoda. Reszta r=Ax-b spełnia dla optymalnego x
> A^t * r =0.
> Uklad rownan mozemy zapisać lacznie jako
> [    I     A]  [x]
> [ A^t    0 ]  [r]
>                        =
> [b]
> [0]
>
> I -macierz jednostkowa. Zagadnienie jest znacznie wieksze,
> ale macierz jest nadal rzadka (rzedu n*(2*K+1) elementow ).
> Jesli K jest małe, jakaś sprytniejsza metoda iteracyjna rozwiazywania
> rownan liniowych da wynik szybko (pewnei precondicioner by sie
> przydal)
Hmmmm wygląda sensownie. W pamięci tylko dane, a dane dadzą
się skompresować 1000 krotnie. Może to dobry kierunek.


> Zaletą jest, ze (w wersji bez prec.) nie trzymamy w pamieci zadnej
> macierzy,
> tylko iterowany wektor (rozmiar n+N). A mnozenie, jesli odpowqiednio
> zapiszesz swoją macierz (wektory z pomiarow), zajmuje tylko tyle
> czasu,
> ile jest niezerowych elementow.
Będę musiał to sprawdzić.


> Bardzo mozliwe, ze w tym przypadku da sie zastosowac albo wymyslic
> jakis prosty (aby dal sie w biegu liczyc, byl oparty na A etc, aby nie
> trzymac
> duzej macierzy w pamieci) precondiconer, przez co mozemy dostać
> przyzwoite
> rozwiązania przy niewielkiej ilosci iteracji. Ale to juz na dłuzsze
> głowkowanie.
> Zaletą metod iteracyjnych bedize tez to, ze jesli dojdą nowe wektory
> (skladniki A)
> to juz mamy obliczony wczesniej przyzwoity punkt startowy.
Ta zaleta się nie przyda, przy nowym mapowaniu nieliniowym wszystkie
całkowicie się zmienia i metoda musi liczyć na nowo :)

> Przy okazji, Y. Saad na swojej stronie wystawił wielka ksiązke do
> matod iteracyjnych:)
Ok, dzięki może to dobry ślad :)

> pozdrawiam
również

do góry

On 9 Wrz, 15:06, Wit Jakuczun <w...@g...com> wrote:
> W dniu 2010-09-06 11:51, Mariusz Marszałkowski pisze:>
> Muszę ułożyć pełny układ równań, czy da się
> > jakoś prościej/szybciej albo na mniejszej pamięci?
>
> Poszukaj tutaj:http://www.cise.ufl.edu/research/sparse/
Dzięki, sprawdzę.

do góry

On 9 Wrz, 16:08, Mariusz Marszałkowski <m...@g...com> wrote:
> On 9 Wrz, 12:11, bartekltg <b...@g...com> wrote:> Mówiłem to ostatnio,
mialem to raz jeszcze napisać
> > w odpowiedzi ktorą powolitku pisze dla drugiej odnogi wątku,
> > ale wspomne o tym teraz: moze jednak zatrudnijcie jakiegos
> > matematyka/numeryka.
>
> Żałuję, ale to nie przejdzie z dwóch powodów:
> 1) nie ma funduszy choćby na przeciętne wynagrodzenie
> 2) bardzo specyficzne wymagania co do poufności

A opoznienia w projekcie to są za darmo;-)

To przymysł czy szeroko rozumiana nauka?

> > Cormen nie jest podręcznikiem do numerkow;)
>
> Ale Cormena najłatwiej trawię. W Cormenie jest

Instrukcja do silników co prawda nie traktuje o układzie
sterowania, ale dobrze instrukcje do silnika trawie;)

Chwyc i przekartkuj jakikolwiek podrecznik do numerkow,
da duzo wiecej.


> > Dla przypomnienia, zagadnienie jest n*N  n>N (n=1000N)
> > N=K*M.
> > A ma n*K niezerowych elementow.
>
> Zgadza się


> > QR jest czasem lepsze, bo  "operujemy na A" a nie na "A kwadarat".
>
> Dokładnie czegoś takiego potrzebuję.
>
> > Uwarunkowanie!
> > No, ta metoda (ani SVD) do tego zagadnienia tez sie nie specjalnie nie
> > nadadza.
>
> Hmmmm

Bo to wszytko nie jest _ąż_ takie proste;)
Q z rozładu QR bedzie miało n*n (czyli 1000 razy wiecej niz macierz A)
i będzie pałna. Zły wybór.
Mozna uzyć sprytniejszej implementacji.
[c,R]= qr(A,b)
gdzie A,R jak poprzednio, b to wyraz 'wynikow pomiaru' z zagadnienia
min(norm(Ax-b)) a C to Q'*b. Algorymt nie wylicza macierzy Q!
Tak jest np w MATLAbie (zastosowana skladnia) i na pewno znajdziesz
coś takiego w linkach podeslanych przez Wita.

Ale.. nadal masz pełną (trojkątną) R rozmairu N*N.

No i wiekszosc tych implementacji chce jednak macierz
w RAM, a nie na calym dysku:)

> > > On 6 Wrz, 17:33, bartekltg <b...@g...com> wrote:> Ile jest wektorów?
powiedzmy n >> N.
> > > A jeśli N jest równe milion? :)
>
> > Hmm, to ciezko bedzie:) Skąd wezmiesz 8 pata(10^15) bajtow dysku:)
>
> Nawet 10^15 by nie starczyło :)

Zaczynam mieć wrazenie, ze nie bardzo wiecei co i jak chcecie robic:-)


> > Mozna 'na raz' optymalizować wiecej niz jeden skladnik
> > wektora wspolczynnikow x, ale na oko nie jest to oplacalne.
>
> Można próbować gradientów sprzężonych, ale to się
> skończy ogromną ilością iteracji...

W ogole nie tan kierunek. Zadnego nieliniowego badziewie,
przeciez po to ograniczyleś sie do algebry liniowej, zeby
mieć szybkie i scisłe metody.

Podalem przepis, wzorek jak to zrobic gdy poprawiasz na raz
masz jedną zmienną. Liczysz dwa iloczyny skalarne.
I sugestie, ze to nadal jest zagadnienie najm. kwadratow, ino
malutkie,
wiec umiemy je zrobic poprawiajac na raz wiecej paramwetrow.
Ale to _chyba_ nie przyszpieszy (tak mi sie wydaje po przemysleniu).


> Jeśli nie da się szybko, to będę musiał zrobić inne mapowanie
> wektorów, nie będzie wyjścia.

Calkiem w ciemno strzelacie?
Wiesz, ile jest funkcji nieliniowych;)


> > Jesli K jest małe, jakaś sprytniejsza metoda iteracyjna rozwiazywania
> > rownan liniowych da wynik szybko (pewnei precondicioner by sie
> > przydal)
>
> Hmmmm wygląda sensownie. W pamięci tylko dane, a dane dadzą
> się skompresować 1000 krotnie. Może to dobry kierunek.

Maly test pokazał, ze precondicioner jest bardzo potrzebny.
CG dla A rozmairu 10000*100 sie poddaje.


Z tych wszytkich polecalbym na razie to losowe (mozna wspomagac)
poprawianie kolejnych elementow wektora x. Najprostrze do napisania
i najlatwiejze do zaprzegnięcia do pracy z dyskiem.

pozdrawiam
bartekltg

do góry

On 9 Wrz, 17:43, bartekltg <b...@g...com> wrote:
> On 9 Wrz, 16:08, Mariusz Marszałkowski <m...@g...com> wrote:
>
> > On 9 Wrz, 12:11, bartekltg <b...@g...com> wrote:> Mówiłem to ostatnio,
mialem to raz jeszcze napisać
> > > w odpowiedzi ktorą powolitku pisze dla drugiej odnogi wątku,
> > > ale wspomne o tym teraz: moze jednak zatrudnijcie jakiegos
> > > matematyka/numeryka.
>
> > Żałuję, ale to nie przejdzie z dwóch powodów:
> > 1) nie ma funduszy choćby na przeciętne wynagrodzenie
> > 2) bardzo specyficzne wymagania co do poufności
>
> A opoznienia w projekcie to są za darmo;-)
> To przymysł czy szeroko rozumiana nauka?
Kolejny eksperyment, jest sprzęt do obliczeń,
trzeba na nim coś uruchomić żeby nie zardzewiał, a
jak wyniki przez przypadek okażą się przydatne, to
będzie więcej pieniędzy na normalne etaty i więcej
sprzętu.

> Chwyc i przekartkuj jakikolwiek podrecznik do numerkow,
> da duzo wiecej.
Chyba mam coś na półce, mógłbym zobaczyć, ale szukam
tylko jednej prostej informacji: czy się da czy nie, bo jak
nie to inne rozwiązanie.

> Bo to wszytko nie jest _ąż_ takie proste;)
> Q z rozładu QR bedzie miało n*n (czyli 1000 razy wiecej niz macierz A)
> i będzie pałna. Zły wybór.
> Mozna uzyć sprytniejszej implementacji.
> [c,R]= qr(A,b)
> gdzie A,R jak poprzednio, b to wyraz 'wynikow pomiaru' z zagadnienia
> min(norm(Ax-b)) a C to Q'*b. Algorymt nie wylicza macierzy Q!
> Tak jest np w MATLAbie (zastosowana skladnia) i na pewno znajdziesz
> coś takiego w linkach podeslanych przez Wita.
>
> Ale.. nadal masz pełną (trojkątną) R rozmairu N*N.
Czyli dla dużej ilości parametrów odpada, pewnie
max 10tys.

> Zaczynam mieć wrazenie, ze nie bardzo wiecei co i jak chcecie robic:-)
Bo nie wiemy, a z tego co wiem nikt na świecie nie
wie. Trzeba dobrego pomysłu a w ramach pomysłu mocy
obliczeniowej do testów różnych wariantów.

>
> > > Mozna 'na raz' optymalizować wiecej niz jeden skladnik
> > > wektora wspolczynnikow x, ale na oko nie jest to oplacalne.
>
> > Można próbować gradientów sprzężonych, ale to się
> > skończy ogromną ilością iteracji...
>
> W ogole nie tan kierunek. Zadnego nieliniowego badziewie,
> przeciez po to ograniczyleś sie do algebry liniowej, zeby
> mieć szybkie i scisłe metody.

> Podalem przepis, wzorek jak to zrobic gdy poprawiasz na raz
> masz jedną zmienną. Liczysz dwa iloczyny skalarne.
> I sugestie, ze to nadal jest zagadnienie najm. kwadratow, ino
> malutkie,
>  wiec umiemy je zrobic poprawiajac na raz wiecej paramwetrow.
> Ale to _chyba_ nie przyszpieszy (tak mi sie wydaje po przemysleniu).
Przyspieszy ale za mało.

> > Jeśli nie da się szybko, to będę musiał zrobić inne mapowanie
> > wektorów, nie będzie wyjścia.
>
> Calkiem w ciemno strzelacie?
> Wiesz, ile jest funkcji nieliniowych;)
I w dodatku nieciągłych :)

> Maly test pokazał, ze precondicioner jest bardzo potrzebny.
> CG dla A rozmairu 10000*100 sie poddaje.
>
> Z tych wszytkich polecalbym na razie to losowe (mozna wspomagac)
> poprawianie kolejnych elementow wektora x. Najprostrze do napisania
> i najlatwiejze do zaprzegnięcia do pracy z dyskiem.

Muszę to przemyśleć i przeczytać linki do Wita, za dużo informacji
na raz i mi się obwody przegrzały :)

A jakby... wektor miał długość 10^6 i miał tylko 4 części
po 250tys elementów i w każdej części tylko jedna jedynka i
reszta zer? Jakby nie patrzeć też trzeba znaleźć milion
parametrów, ale dane są cholernie rzadkie?

Pozdrawiam i dzięki :)

do góry

On 9 Wrz, 18:46, Mariusz Marszałkowski <m...@g...com> wrote:

> > Chwyc i przekartkuj jakikolwiek podrecznik do numerkow,
> > da duzo wiecej.
>
> Chyba mam coś na półce, mógłbym zobaczyć, ale szukam
> tylko jednej prostej informacji: czy się da czy nie, bo jak
> nie to inne rozwiązanie.

Dać się da. Tylko ile to czasu zajmie;)


> > W ogole nie tan kierunek. Zadnego nieliniowego badziewie,
> > przeciez po to ograniczyleś sie do algebry liniowej, zeby
> > mieć szybkie i scisłe metody.
> > Podalem przepis, wzorek jak to zrobic gdy poprawiasz na raz
> > masz jedną zmienną. Liczysz dwa iloczyny skalarne.
> > I sugestie, ze to nadal jest zagadnienie najm. kwadratow, ino
> > malutkie,
> >  wiec umiemy je zrobic poprawiajac na raz wiecej paramwetrow.
> > Ale to _chyba_ nie przyszpieszy (tak mi sie wydaje po przemysleniu).
>
> Przyspieszy ale za mało.


A skąd to przypuszczenie, ze przyszpieszy?

Dlaczego mowisz, ze za malo? Juz testowane?


> A jakby... wektor miał długość 10^6 i miał tylko 4 części
> po 250tys elementów i w każdej części tylko jedna jedynka i
> reszta zer? Jakby nie patrzeć też trzeba znaleźć milion
> parametrów, ale dane są cholernie rzadkie?

I 10^8 takich wektorkow. To tylko 1600MB danych.
Sprawdz jak szybko proponowana metoda zbiegnie.

Do testowania jakosci przyblizenia mozesz uzyc zaleznosci
A' (Ax-b)=0. Iloczyny skalarne i mnozenia macierzy * e_i
są blyskawiczne.

pozdr
bartekltg

do góry

> > A jakby... wektor miał długość 10^6 i miał tylko 4 części
> > po 250tys elementów i w każdej części tylko jedna jedynka i
> > reszta zer? Jakby nie patrzeć też trzeba znaleźć milion
> > parametrów, ale dane są cholernie rzadkie?
>
> I 10^8 takich wektorkow. To tylko 1600MB danych.
> Sprawdz jak szybko proponowana metoda zbiegnie.
>
> Do testowania jakosci przyblizenia mozesz uzyc zaleznosci
> A' (Ax-b)=0. Iloczyny skalarne i mnozenia macierzy * e_i
> są blyskawiczne.

Skupmy sie na tym że wektor składa się tylko z 4 częsci.
Każda część ma 250tys elementów. Każda część ma
jedną jedynkę i reszta zer. To dobrze obrazuje miejsce
potencjalnego zysku - taki wektor można skompresować
do czterech liczb - każda liczba wskazuje położenie jedynki
w części. 10^9 wektorów danych to zaledwie 12GB danych,
nawet w RAM się zmieszczą.

Niemniej parametrów do ustalenia nadal jest 10^6 i żeby
zbudować równanie, trzeba macierz kwadratowa o rozmiarze
10^6 x 10^6 - i tu jest problem :)

Pozdrawiam

do góry

On 9 Wrz, 19:49, Mariusz Marszałkowski <m...@g...com> wrote:
> > > A jakby... wektor miał długość 10^6 i miał tylko 4 części
> > > po 250tys elementów i w każdej części tylko jedna jedynka i
> > > reszta zer? Jakby nie patrzeć też trzeba znaleźć milion
> > > parametrów, ale dane są cholernie rzadkie?
>
> > I 10^8 takich wektorkow. To tylko 1600MB danych.
> > Sprawdz jak szybko proponowana metoda zbiegnie.
>
> > Do testowania jakosci przyblizenia mozesz uzyc zaleznosci
> > A' (Ax-b)=0. Iloczyny skalarne i mnozenia macierzy * e_i
> > są blyskawiczne.
>
> Skupmy sie na tym że  wektor składa się tylko z 4 częsci.
> Każda część ma 250tys elementów. Każda część ma
> jedną jedynkę i reszta zer. To dobrze obrazuje miejsce
> potencjalnego zysku - taki wektor można skompresować
> do czterech liczb - każda liczba wskazuje położenie jedynki
> w części. 10^9 wektorów danych to zaledwie 12GB danych,
> nawet w RAM się zmieszczą.

Czytaleś co pisalem. Nawet przez chwile nie chzialem mieć
nieskompresowanej wersji:)

> Niemniej parametrów do ustalenia nadal jest 10^6 i żeby
> zbudować równanie, trzeba macierz kwadratowa o rozmiarze
> 10^6 x 10^6 - i tu jest problem :)

No nie trzeba:) W paru ostatnich postach zarysowalem
procedurke ktora powolutku dziubdzia coraz lepsze przyblizenia.
Przeciez nie bede na grupie dokladnego kodu pisal:)

Bardziej bym sie zastanawiał nad statystycznym sensem
takiej aproksymacji. Ale skoro mowisz, ze jest..

pozdr
bartekltg

do góry

On 9 Wrz, 20:17, bartekltg <b...@g...com> wrote:
> On 9 Wrz, 19:49, Mariusz Marszałkowski <m...@g...com> wrote:
>
>
>
> > > > A jakby... wektor miał długość 10^6 i miał tylko 4 części
> > > > po 250tys elementów i w każdej części tylko jedna jedynka i
> > > > reszta zer? Jakby nie patrzeć też trzeba znaleźć milion
> > > > parametrów, ale dane są cholernie rzadkie?
>
> > > I 10^8 takich wektorkow. To tylko 1600MB danych.
> > > Sprawdz jak szybko proponowana metoda zbiegnie.
>
> > > Do testowania jakosci przyblizenia mozesz uzyc zaleznosci
> > > A' (Ax-b)=0. Iloczyny skalarne i mnozenia macierzy * e_i
> > > są blyskawiczne.
>
> > Skupmy sie na tym że  wektor składa się tylko z 4 częsci.
> > Każda część ma 250tys elementów. Każda część ma
> > jedną jedynkę i reszta zer. To dobrze obrazuje miejsce
> > potencjalnego zysku - taki wektor można skompresować
> > do czterech liczb - każda liczba wskazuje położenie jedynki
> > w części. 10^9 wektorów danych to zaledwie 12GB danych,
> > nawet w RAM się zmieszczą.
>
> Czytaleś co pisalem. Nawet przez chwile nie chzialem mieć
> nieskompresowanej wersji:)
Dziś mi mogło coś umknąć, ale przeczytam wątek jeszcze
raz :)

>
> > Niemniej parametrów do ustalenia nadal jest 10^6 i żeby
> > zbudować równanie, trzeba macierz kwadratowa o rozmiarze
> > 10^6 x 10^6 - i tu jest problem :)
>
> No nie trzeba:) W paru ostatnich postach zarysowalem
> procedurke ktora powolutku dziubdzia coraz lepsze przyblizenia.
Mniej więcej rozumiem, jeszcze wczytam się dokładniej.

> Bardziej bym sie zastanawiał nad statystycznym sensem
> takiej aproksymacji. Ale skoro mowisz, ze jest..
Raczej nie mam lepszego pomysłu :)
Zrobię mieszankę liniowej i nielinowej klasyfikacji..
za kilka miesięcy będę wiedział na ile pomysł był
dobry.

Dzięki

do góry

W dniu 2010-09-09 21:00, Mariusz Marszałkowski pisze:

>> Bardziej bym sie zastanawiał nad statystycznym sensem
>> takiej aproksymacji. Ale skoro mowisz, ze jest..
> Raczej nie mam lepszego pomysłu :)
> Zrobię mieszankę liniowej i nielinowej klasyfikacji..
> za kilka miesięcy będę wiedział na ile pomysł był
> dobry.
>
Z tego co właśnie napisałeś wygląda, że może powinieneś zaprzyjaźnić się
z support vector machines (SVM).
Tworzenie klasyfikatorów opartych na dużej liczbie cech jest dość znanym
problemem.

Pozdrawiam,
Wit

do góry