W dniu 2010-09-09 20:17, bartekltg pisze:
> Bardziej bym sie zastanawiał nad statystycznym sensem
> takiej aproksymacji. Ale skoro mowisz, ze jest..
>
Sens może być jeśli ograniczy się aproksymator, np. drugą pochodną.
To się nazywa regularyzacja i działa całkiem nie najgorzej.

Pozdrawiam,
Wit

do góry

On 9 Wrz, 20:17, bartekltg <b...@g...com> wrote:

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

Ja bym to tak rozwiązywał jak w poniższym przykładzie. Uakutalnia
się po jednej zmiennej w każdej iteracji. W tym przykładzie, jeśli
ilość iteracji >= ilość parametrów * 3 to błąd praktycznie już nie
spada.

Dokładność praktycznie taka sama jak z solvera.

Niepokojące jest że różne wartości parametrów dają
taki sam błąd - czyżby rozwiązanie było na rozległym
płaskim dnie i z powodu małej precyzji obliczeń
algorytm zatrzymuje się zawsze w innym miejscu?

Co z czasem obliczeń?
Załóżmy że mamy 10^9 danych i trzeba znaleźć 10^6
parametrów. Daje to 10^9 * 10^6 * 3 ~=~ 10^16 operacji.
Czyli tak czy siak odpada.

Chyba będę musiał zrobić inne mapowanie nielinowe, np.
takie że jeden wektor będzie miał dokładnie jedną jedynkę i
resztę zer.

Link do przykładu:
http://www.przeklej.pl/plik/eq-xls-0020nk38s5a5

Pozdrawiam

do góry

On 14 Wrz, 20:31, Mariusz Marszałkowski <m...@g...com> wrote:


> Link do przykładu:http://www.przeklej.pl/plik/eq-xls-0020nk3
8s5a5

Ześ sobie format znalzal;) Ściagnalem dane, makr nie ruszam:)

> Ja bym to tak rozwiązywał jak w poniższym przykładzie. Uakutalnia
> się po jednej zmiennej w każdej iteracji. W tym przykładzie, jeśli
> ilość iteracji >= ilość parametrów * 3 to błąd praktycznie już nie
> spada.
>
> Dokładność praktycznie taka sama jak z solvera.
>
> Niepokojące jest że różne wartości parametrów dają
> taki sam błąd - czyżby rozwiązanie było na rozległym
> płaskim dnie i z powodu małej precyzji obliczeń
> algorytm zatrzymuje się zawsze w innym miejscu?

Moj wynik (z solvera matalbowskiego) wrzucam na koncu.
Jest jeszcze inny, ale norma residuum taka jak podajesz.
Metody iteracyjnej nie sprawdzalem, bo problem jest gdzie indziej.

Zanim zaczniesz szukaszukać błędów w stabilnosci numerycznej
i prezycji obliczeń, zerknij na niezalesnosc wektorów;)

Twoje wektroki(pionowe z macierzy data) _nie_ są liniowo niezalezne!
Rank (data) = 13. A wymiar 16. Masz trzy stopnie swobody w zapisaniu
wyniku:)

> Co z czasem obliczeń?
> Załóżmy że mamy 10^9 danych i trzeba znaleźć 10^6
> parametrów. Daje to 10^9 * 10^6 * 3 ~=~ 10^16 operacji.
> Czyli tak czy siak odpada.

A czego sie spodziwałeś? Magii:) I tak masz mniej niz dane^2.
Nie do konca wierze, ze ten wspolczynnik 3 jest niezalezny od
rozmiaru.

> Chyba będę musiał zrobić inne mapowanie nielinowe, np.
> takie że jeden wektor będzie miał dokładnie jedną jedynkę i
> resztę zer.

Pewnie tak. Trudno mi zgadywać co chcesz zrobic, ale
Wit zgadywał i cos madrego podsuwał.

pozdrawiam
bartekltg

x=
0.38278
0.12799
0.12701
0
0.0055893
0
0.030901
-0.03097
-0.21941
-0.29912
-0.26385
-0.22057
0.19002
0
0.097905
0.1147

norm(Ax-b) = 575.38

do góry

On 15 Wrz, 03:52, bartekltg <b...@g...com> wrote:
> On 14 Wrz, 20:31, Mariusz Marszałkowski <m...@g...com> wrote:
>
> > Link do przykładu:http://www.przeklej.pl/plik/eq-xls-0020nk3
8s5a5
>
> Ześ sobie format znalzal;) Ściagnalem dane, makr nie ruszam:)
Makra to tylko copy-paste z komórki do komórki i przeliczenie arkusza.
Nie sądzę abym miał jakiegoś wirusa który dokleił coś samemu.

> Zanim zaczniesz szukaszukać błędów w stabilnosci  numerycznej
> i prezycji obliczeń, zerknij na niezalesnosc wektorów;)
>
> Twoje wektroki(pionowe z macierzy data) _nie_ są liniowo niezalezne!
> Rank (data) = 13. A wymiar 16. Masz trzy stopnie swobody w zapisaniu
> wyniku:)
Danych jest (było gdy wysyłałem) 10tys.


> A czego sie spodziwałeś? Magii:) I tak masz mniej niz dane^2.
> Nie do konca wierze, ze ten wspolczynnik 3 jest niezalezny od
> rozmiaru.
Magii to nie, ale... jeśli tylko jedna niezerowa dana pojawia się
na 1000 zer i w dodatku jest zawsze jedynką i w dodatku
charakteryzyje się równomiernym rozkładem, to zastanawiam się
na ile ten fakt można wykorzystać.

pozdrawiam

do góry

On 15 Wrz, 21:42, Mariusz Marszałkowski <m...@g...com> wrote:
> On 15 Wrz, 03:52, bartekltg <b...@g...com> wrote:> On 14 Wrz, 20:31, Mariusz
Marszałkowski <m...@g...com> wrote:
>
> > > Link do przykładu:http://www.przeklej.pl/plik/eq-xls-0020nk3
8s5a5
>
> > Ześ sobie format znalzal;) Ściagnalem dane, makr nie ruszam:)
>
> Makra to tylko copy-paste z komórki do komórki i przeliczenie arkusza.
> Nie sądzę abym miał jakiegoś wirusa który dokleił coś samemu.
>
> > Zanim zaczniesz szukaszukać błędów w stabilnosci  numerycznej
> > i prezycji obliczeń, zerknij na niezalesnosc wektorów;)
>
> > Twoje wektroki(pionowe z macierzy data) _nie_ są liniowo niezalezne!
> > Rank (data) = 13. A wymiar 16. Masz trzy stopnie swobody w zapisaniu
> > wyniku:)
>
> Danych jest (było gdy wysyłałem) 10tys.

Nie zrozumiales. Macierz jest 10 000 na 16. Ale jej
rząd to 13. Maceirz ejst osobliwa, liniowo zalezna.
To stad w pierwszej kolejnosci biorą sie zypelnie
rozne wektroy dajace ten sam wynkik.

BTW, kopnales sie w wyliczaniach:

> Co z czasem obliczeń?
> Załóżmy że mamy 10^9 danych i trzeba znaleźć 10^6
> parametrów. Daje to 10^9 * 10^6 * 3 ~=~ 10^16 operacji.
> Czyli tak czy siak odpada.

Mamy M(10^9) wektorkow dlugośći N=(M/1000), kazdy ma (k=4)
niezerowych skladowych. Daje to S=4*10^9 liczb (satrczy dwa bajty
całkowitoliczbowej;) w data i 10^9 na wektor wyników(tu juz float/
double).

Co prawda Wykonanie mnozenia A*x zajmuje rzędu S operacji,
ale nie trzeba tego robić co iteracje! A interesujace nas (A*e_i, b)
da sie policzyć w zlozonosci k*(M/N) (*powiedzmy 8 operacji).

Moze poznym wieczorkeim wrzuce kod (od razu ostrzegam,
z lenistwa matlabowski;)

pozdrawiam
bartekltg

do góry

On 15 Wrz, 21:57, bartekltg <b...@g...com> wrote:
> > Danych jest (było gdy wysyłałem) 10tys.
>
> Nie zrozumiales. Macierz jest 10 000 na 16. Ale jej
> rząd to 13. Maceirz ejst osobliwa, liniowo zalezna.
> To stad w pierwszej kolejnosci biorą sie zypelnie
> rozne wektroy dajace ten sam wynkik.
Zrozumiałem ale nie mogłem uwierzyć.
Dane generowałem funkcją Rand z excela,
jak to możliwe że dla 10tys losowych wektorów
układ równań nie jest jednoznaczny?

> BTW, kopnales sie w wyliczaniach:
Masz rację, ponieważ nie trzeba mnożyć przez zera.
Danych jest 10^9 rekordów.
Rekord ma długość 10^6
Rekord zawiera np. tylko 4 jedynki i resztę zer.
Czyli aby ustalić to co w excelu nazwałem
"poprawką", wystarczy średnio 10^9/10^6*4
operacji, czyli zaledwie około 4tys.
"poprawek" jest 10^6, czyli 10^6*4tys...
Może to się jednak da policzyć dla 4
niezerowych :)

> Moze poznym wieczorkeim wrzuce kod (od razu ostrzegam,
> z lenistwa matlabowski;)
Chętnie zobaczę, ale w zupełności wystarczy mi jeśli
potwierdzisz/zaprzeczysz że mówisz o takiej samej
metodzie jak w excelu.

Pozdrawiam

do góry

On 16 Wrz, 03:08, Mariusz Marszałkowski <m...@g...com> wrote:
> On 15 Wrz, 21:57, bartekltg <b...@g...com> wrote:> > Danych jest (było gdy
wysyłałem) 10tys.
>
> > Nie zrozumiales. Macierz jest 10 000 na 16. Ale jej
> > rząd to 13. Maceirz ejst osobliwa, liniowo zalezna.
> > To stad w pierwszej kolejnosci biorą sie zypelnie
> > rozne wektroy dajace ten sam wynkik.
>
> Zrozumiałem ale nie mogłem uwierzyć.
> Dane generowałem funkcją Rand z excela,
> jak to możliwe że dla 10tys losowych wektorów
> układ równań nie jest jednoznaczny?

Ktoś tu niedawno ładnie powiedział, ze pomiedzy osobliwoscia
a nieosobliwoscia jest obszar 'numerycznej osobliwosci':)

Ale tu problem jest bardziej algebraiczny.
Patrzmy na wektorki wierszowe. Są dlugości N i mają
k 'przedziałow' o tej własnosci, ze jest w nim dokladnie
jedna jedynka. Popatrzmy na przestrzen rozpieta przez
wszytkie takie wektory (jest ich mniej niz 10tys, dla N=12,
k=4 81, ogolnie, (N/k)^k ).

Popatrzmy teraz na nastepujecy wektor: w jednym przedziale
(całm) +1, w drugim -1, a w pozostalych 0. Taki wektor nie
lezy w naszej przestrzeni (jest prostopadly do wszytkich innych).

[1;1;1; 0;0;0; -1; -1; -1; 0;0;0;] czy
[ 0;0;0; -1; -1; -1; 0;0;0; 1;1;1] sa prostopadle do kazdego

[ X;Y;V;Z ] gdzie XYVZ za trojwymairowymi wektorami z jedna jedynka.

Wymiar takiej przestrzeni to k-1.

Niezaleznie, ile wektorkow wylosujesz, Twoje pokrycie
ma wymiar co najwyzej N- (k-1).

Skoro taka jest struktura zadania, widac, tak być musi:)
Od biedy mozna sie zastanawiać nad usunieciem
niektorych kolumn (rownowaznie, pewne parametry
stale zero), ale ni ma wielkiej potrzeby jesli godzimy
sie na niejednoznacznosc parametrow.

> > BTW, kopnales sie w wyliczaniach:

> Masz rację, ponieważ nie trzeba mnożyć przez zera.
> Danych jest 10^9 rekordów.
> Rekord ma długość 10^6
> Rekord zawiera np. tylko 4 jedynki i resztę zer.
> Czyli aby ustalić to co w excelu nazwałem
> "poprawką", wystarczy średnio 10^9/10^6*4
> operacji, czyli zaledwie około 4tys.
> "poprawek" jest 10^6, czyli 10^6*4tys...
> Może to się jednak da policzyć dla 4
> niezerowych :)

Oszacowanie na ilosc operacji w celu pojedynczej
poprawki zgadza sie. Ale z tym excelem to dowcip rozumiem;)
Ja wole za podstawową jednostke mieć sprasowany wektor
kolumnowy macierzy A (a nie wierszowy) wiec mam
10^6 rekordow po średnio 10^9/10^6*4 wartosci.
Dzieki temu mam wszytko na widelcu.

Pewnie co jakis czas jednak warto policzyc od nowa Ax-b,
bo poprawki moga nam sie rozjezdzać.

> > Moze poznym wieczorkeim wrzuce kod (od razu ostrzegam,
> > z lenistwa matlabowski;)
>
> Chętnie zobaczę, ale w zupełności wystarczy mi jeśli
> potwierdzisz/zaprzeczysz że mówisz o takiej samej
> metodzie jak w excelu.

Wesja dość robocza, duzo smieci. Wiecej czasu poswieca
na wygenerowanie odpowiedniej postaci danych (w jezykach
blisko bebechow nie bedzie to problemem) niz na same obliczenia.

'Dokłaność' 10^-10, wykonal 25 duzych iteacji
(tu panuje duzy rozrzut) w minute.

Dla N=1000; M=100000; 5 sekund.

Kasujac odpowiedni komentarz dostajesz macierz rzadką
ktora mozna potestowac neizbyt duze zadania.

Pozdrawiam
bartekltg
PS. byly jakies serwisy do umieszczania kodu,
oczywiscie zapomnailem i nie moge znalesc..


function [x,b,y,A ] = main( tol )
%MAIN Summary of this function goes here
% Detailed explanation goes here

N=1000;
M=1000000;
k=4;
N=floor(N/k)*k;

tic
%wygenerowalismy nasza macierz, wiersz to nasz k jedynkowy
%wektor zapisany w postaci sprasowanej: same indeksy,
%gdzie znajduje sie jedynka. Bardziej przyda sie nam inna postać.
%wektor to sprasowany wektor macierza A z zadania.
wA = floor((1+rand(M,k)*(N/k))+ ones(M,k)*diag(0:k-1)*N/k);
toc
tic
wiersz =(1:M)'*ones(1,k);
% kA{j} to sprasowana j-ta _kolumna_ macierzy A
% z zagadnienia min(norm(Ax-b))
%tworzenie kA dalekie od optymalnego, ale dydaktyczne
% a2 to <a*a>, gdzie a to wektor z kA.
A=[];
%A= sparse((1:M)'*ones(1,k),wA,1,M,N); %nie potrzeba, ale porosciej
wygenerowac kA
kA={};
a2 = [];
toc
tic
for j=1:N, % to jest zle, trwa dwa razy dluzej niz wlasciwe
obliczenia.
r=wiersz(wA==j);
kA{j}=r;
a2(j)=length(r);
end;
toc
disp('...for')
tic

clear wA; %szkoda pamieci,

b=rand(M,1); %wektor wynikow.

x=zeros(N,1); %wektorki

y=-b; %w residuum Ax-b
toc

disp('ognia');
tic
popr=1;
cykli=0;
while popr>tol, %powtarzaj, az suma wzglednych poprawek bedzie mala.
%nie do konca dobre kryterium, ale popr >= sum( A'*y ) po wykonaniu
wewn. pętli

perm=randperm(N); % w kazdym duzym obiegu poprawimy kazdy
wspolczynnik.
popr=0;
for j=1:N,
a=perm(j); % a - indeks poprawianego wspolczynnia
v=kA{a}; % sprasowany wektor kolumnowy odpowiadajacy
indeksowi a
delta=sum(y(v))/a2(a); % <y, A(:,a)>/||A(:,a)||^2
x(a)=x(a)-delta;
y(v)=y(v)-delta;
popr=popr+abs(delta/x(a));
end;
popr
cykli=cykli+1;

end;
toc
cykli %a tak dla ciekawosic.

do góry

On 16 Wrz, 07:11, bartekltg <b...@g...com> wrote:

> Skoro taka jest struktura zadania, widac, tak być musi:)
> Od biedy mozna sie zastanawiać nad usunieciem
> niektorych kolumn (rownowaznie, pewne parametry
> stale zero), ale ni ma wielkiej potrzeby jesli godzimy
> sie na niejednoznacznosc parametrow.
Racja, można rozwiązanie przesuwać po prostopadłym
wektorze.


> Oszacowanie na ilosc operacji w celu pojedynczej
> poprawki zgadza sie. Ale z tym excelem to dowcip rozumiem;)
Tzn nie zamierzam w excelu przechowywać 10^9 danych ;)
Chodziło mi tylko i wyłącznie o poprawność/skuteczność wzoru
na poprawkę parametru w kolejnych iteracjach.

> Ja wole za podstawową jednostke mieć sprasowany wektor
> kolumnowy macierzy A (a nie wierszowy) wiec mam
> 10^6 rekordow po średnio 10^9/10^6*4 wartosci.
> Dzieki temu mam wszytko na widelcu.
Na razie też nie widzę nic lepszego jak spakowany
wektor kolumnowy.

> Wesja dość robocza, duzo smieci.  Wiecej czasu poswieca
> na wygenerowanie odpowiedniej postaci danych (w jezykach
> blisko bebechow nie bedzie to problemem) niz na same obliczenia.
>
> 'Dokłaność' 10^-10, wykonal 25 duzych iteacji
> (tu panuje duzy rozrzut) w minute.
>
> Dla N=1000; M=100000; 5 sekund.
Napiszę zaraz prototyp w C i zobaczymy.

> PS. byly jakies serwisy do umieszczania kodu,
> oczywiscie zapomnailem i nie moge znalesc..
Może chodzi o ten serwis:
http://pastebin.com/

Pozdrawiam i dzięki serdeczne

do góry

On 16 Wrz, 07:11, bartekltg <b...@g...com> wrote:
[...]
Na razie nie wiem ile błędów tam narobiłem. Na oko wydaje
się że dość sprawnie liczy. 10tys parametrów to bez problemu
liczy.

http://pastebin.com/bry3Gfp4

Pozdrawiam

do góry

On 17 Wrz, 03:33, Mariusz Marszałkowski <m...@g...com> wrote:


> > Oszacowanie na ilosc operacji w celu pojedynczej
> > poprawki zgadza sie. Ale z tym excelem to dowcip rozumiem;)
>
> Tzn nie zamierzam w excelu przechowywać 10^9 danych ;)
> Chodziło mi tylko i wyłącznie o poprawność/skuteczność wzoru
> na poprawkę parametru w kolejnych iteracjach.

Do takich 'rozpoznń pola' polecam jednak klony matalba
(darmowe scilab, octave).

> > Ja wole za podstawową jednostke mieć sprasowany wektor
> > kolumnowy macierzy A (a nie wierszowy) wiec mam
> > 10^6 rekordow po średnio 10^9/10^6*4 wartosci.
> > Dzieki temu mam wszytko na widelcu.
>
> Na razie też nie widzę nic lepszego jak spakowany
> wektor kolumnowy.

Dojrzewa u mnie algorytm praktycznie nie rozniacy sie
od poprzedniego, ale wykorzystujac spakowanie wierszami,
ktory bedzie znacznie mniej 'skakal' po pamieci.

Spostrzezenie: wektory pionowe w swoim 'dziale' (k dzialów)
sa parami prostopadle. Kolejnosc poprawek w dziale nie mz
znaczenia (w artmetyce dokładnej). Mozna niezaleznie liczyc
wszytkie iloczyny skalarne, a dopeiro pozniej naniesc wszytkie
250 tys poprawek;) Przyda sie przy zrownolegleniu.

Powoduje to tez zjawisko, ktore zobaczylem dzisiaj.
Jesli nie losuje wektorow, ale bierze wspolczynniki do
poprawiania po kolei, algorytm znacznie przyszpiesza.
Potrzeba mniej 'duzych' iteracji by osiagnac zalozona
dokladnosc.

Zabawa zacznie sie, jak zaczniesz uzywać dysku;)

pozdrawiam
bartekltg

do góry