Czy twierdzenie Mercer'a działa odwrotnie?


11

Kolega ma funkcję i dla naszych celów jest to czarna skrzynka. Funkcja mierzy podobieństwo dwóch obiektów.s ( a , b )ss(a,b)

Wiemy na pewno, że ma następujące właściwości:s

  1. Podobieństwa są liczbami rzeczywistymi od 0 do 1 włącznie.
  2. Tylko obiekty, które są identyczne, mają wyniki równe 1. Zatem implikuje i odwrotnie.a = bs(a,b)=1a=b
  3. Gwarantujemy, że .s(a,b)=s(b,a)

Teraz chce pracować z algorytmami, które wymagają odległości jako danych wejściowych i zależą od danych wejściowych spełniających aksjomaty odległości.

Myślałem, że możemy traktować wyniki podobieństwa, jakby były wynikiem jądra RBF z pewną odległością (może to być norma euklidesowa lub inna odległość), tj. Możemy po prostu zmienić kolejność za pomocą algebry i założyć, że wyniki podobieństwa odnoszą się do jądro RBF dla pary punktów w jakimś (nieznanym) układzie współrzędnych.

s(xi,xj)=exp(d(mi,mj)2r)rlogs(xi,xj)=d(mi,mj)

Gdzie to jakiś nieznany wektor, a jest przedmiotem zainteresowania, a to pewna odległość.x α dmαRnxαd

Oczywiste właściwości sprawdzają się, jeśli chodzi o przestrzeganie aksjomatów odległości. Wyniki muszą być nieujemne, a odległości wynoszą tylko 0 dla identycznych obiektów. Ale nie jest oczywiste, że ten raczej ogólny zestaw okoliczności jest wystarczający, aby sugerować, że przestrzegana jest nierówność trójkąta.

Z drugiej strony brzmi to trochę szalone.

Więc moje pytania brzmią: „czy istnieje takie, że dla pewna metryka odległości, biorąc pod uwagę te właściwości na , i co to jest ?”f ( s ( a , b ) ) = d ( a , b ) d s fff(s(a,b))=d(a,b)dsf

Jeśli nie istnieje w tych ogólnych okolicznościach na , to czy istnieje dodatkowy zestaw wymagań, dla których istnieje ?s ffsf


3
Należy pamiętać, że nawet jeśli dany zbiór parami odległości , które spełniają aksjomaty odległości, to nie gwarantuje, że istnieje przestrzeń euklidesowa z punktów realizacji tych dystansach. Takie osadzenie nie zawsze jest możliwe. Zobacz np . Math.stackexchange.com/questions/1000006 . d(a,b)
ameba

To bardzo interesujący wątek! Dziękujemy za udostępnienie. Nie miałem zamiaru ograniczać się do określonej odległości. (Ponieważ poruszając się w przeciwnym kierunku, można użyć jądra RBF z odległością inną niż euklidesowa.)
Sycorax mówi Przywróć Monikę

Więc twoje pytanie dotyczy tylko tego, jak przekonwertować na d ( a , b ) = f ( s ( a , b ) ) tak, aby d spełnia nierówność trójkąta? To, czy macierz odległości jest osadzona w przestrzeni euklidesowej, nie ma dla ciebie znaczenia. Poprawny? Moja intuicja jest taka, że dla dowolnego y nie będzie możliwe. s(a,b)d(a,b)=f(s(a,b))ds
ameba

To jest poprawne. Podejrzewam, że nie jest to możliwe, przynajmniej nie bez dodatkowych ograniczeń dotyczących . s
Sycorax mówi Przywróć Monikę

zawsze prowadzi do metryki dyskretnej (en.wikipedia.org/wiki/Discrete_space), ale prawdopodobnie nie jest to zamierzone, więc należy dodać pewne warunki (?)f:f(x)=Ix>0
Juho Kokkala

Odpowiedzi:


6

Czy twierdzenie Mercer'a działa odwrotnie?

Nie we wszystkich przypadkach.

Treść: „w matematyce, analizy szczególnie funkcjonalny twierdzenie Mercer jest przedstawienie o symetrycznej funkcji dodatniego określony na placu jako sumy sekwencji zbieżnego funkcji produktu Twierdzenie przedstawiony w (Mercer 1909), jeden z. najbardziej znaczące wyniki pracy Jamesa Mercera. Jest ważnym narzędziem teoretycznym w teorii równań całkowych; jest wykorzystywany w kosmicznej teorii procesów stochastycznych Hilberta, na przykład w twierdzeniu Karhunena – Loève'a, a także służy do charakteryzowania symetryczne dodatnie półokreślone jądro.

Jest to mapowaniejeden na jednego ” na przestrzeni Hilberta . - rażącym uproszczeniem byłoby opisanie go jako skrótu lub sumy kontrolnej, którą można przetestować na pliku w celu ustalenia tożsamości lub nie.

Więcej wyjaśnień technicznych: twierdzenie o dezintegracji

„W matematyce twierdzenie o dezintegracji jest wynikiem teorii miary i teorii prawdopodobieństwa. Rygorystycznie określa ideę nietrywialnego„ ograniczenia ”miary do podzbioru miary zerowej w omawianej przestrzeni miar. istnienie warunkowych miar prawdopodobieństwa. W pewnym sensie „rozpad” jest procesem odwrotnym do konstrukcji miary produktu. ”.

Zobacz także: „ Twierdzenie Fubiniego-Tonellego ”, „ Utrata zawiasu ”, „ Funkcja utraty ” oraz „ Jak dobre jest jądro, gdy jest używane jako miara podobieństwa? ” (Czerwiec 2007) Nathana Srebro, streszczenie:

Streszczenie. Ostatnio Balcan i Blum zasugerowali teorię uczenia się opartą na ogólnych funkcjach podobieństwa zamiast pozytywnych półokreślonych jąder. Badamy różnicę między gwarancjami uczenia się opartymi na uczeniu się opartym na jądrze, a tymi, które można uzyskać za pomocą jądro jako funkcja podobieństwa, która została pozostawiona otwarta przez Balcana i Bluma. Zapewniamy znacznie lepszą zależność od tego, jak dobra jest funkcja jądra, gdy jest używana jako funkcja podobieństwa, i rozszerzamy wynik również na bardziej praktycznie istotną utratę zawiasów następnie wskaźnik błędu zero-jeden. Co więcej, pokazujemy, że granica ta jest ścisła, a zatem ustalamy, że faktycznie istnieje prawdziwa luka między tradycyjnym pojęciem marginesu opartym na jądrze a nowszym pojęciem opartym na podobieństwie. ”.

s

Zobacz: jądra i podobieństwo (w R)

Jest to czarna skrzynka, więc nie wiesz na pewno, które jądro jest używane, jeśli jest oparte na jądrze, i nie znasz szczegółów implementacji jądra, gdy tylko pomyślisz, że to jądro. Zobacz: Równanie rbfKernel w kernlab różni się od standardu? .

Z drugiej strony brzmi to trochę szalone.

Jest szybki i skuteczny w ograniczonych okolicznościach. Jak młot, jeśli nosisz ze sobą młotek, czy ludzie nazywają cię szalonym?

Metody jądra zawdzięczają swoją nazwę wykorzystaniu funkcji jądra, które umożliwiają im działanie w wielowymiarowej, niejawnej przestrzeni cech bez obliczania współrzędnych danych w tej przestrzeni, ale po prostu przez obliczanie wewnętrznych produktów między obrazami wszystkich par danych w przestrzeni cech. Ta operacja jest często obliczeniowo tańsza niż jawne obliczanie współrzędnych. Takie podejście nazywa się „sztuczką jądra”. Funkcje jądra zostały wprowadzone dla danych sekwencji, wykresów, tekstu, obrazów, jak oraz wektory. ”.

Lekcja: Ty (czasami) dostajesz to, za co płacisz.

ff(s(a,b))=d(a,b)dsf

Wiele, patrz linki powyżej, „ Popularne funkcje jądra ”, RBF , a oto jeden (drogi) przykład: „ Miara odległości wskaźnika wiarygodności dla podobieństwa między transformacją Fouriera szeregów czasowych ” (2005), autor: Janacek, Bagnall i Powell.

Jeśli nie istnieje w tych ogólnych okolicznościach na , to czy istnieje dodatkowy zestaw wymagań, dla których istniejefsf

Różne przestrzenie i metody mogą lepiej celować w porównanie (i rozpad) określonych problemów, istnieje wiele metod dla samej przestrzeni Hilberta .

Tak, lista jest duża, zobacz linki powyżej i (na przykład): Reprodukcja przestrzeni jądra Hilberta .


-1

Ale nie jest oczywiste, że ten raczej ogólny zestaw okoliczności jest wystarczający, aby sugerować, że przestrzegana jest nierówność trójkąta.

d(a,b)=1s(a,b)x,y,zd(x,y)=13d(y,z)=13d(x,z)=1d(x,z)>d(x,y)+d(y,z)


1
Nie rozumiem, jak to cokolwiek dowodzi.
ameba

d

2
f(α)=1α

1
sfdfmsdf

1
m1s(a,b)xαmαs
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.