Układ „równań stochastycznych”

11

Rozważmy wykres z wierzchołkami i krawędziami m . Wierzchołki są oznaczone zmiennymi rzeczywistymi x i , gdzie x 1 = 0 jest ustalone. Każda krawędź reprezentuje „pomiar”: dla krawędzi ( u , v ) otrzymuję pomiar z ≈ x u - x v . Dokładniej, z jest naprawdę losową wielkością w ( x u - x v ) ± 1 , równomiernie rozmieszczoną i niezależną od wszystkich innych pomiarów (krawędzi).nmxix1=0(u,v)z≈xu−xvz(xu−xv)±1

Dano mi wykres i pomiary, z obietnicą dystrybucji dla powyższego. Chcę „rozwiązać” systemu i uzyskania wektor „s. Czy jest jakaś praca nad problemami tego typu?xi

Właściwie chcę rozwiązać jeszcze prostszy problem: ktoś wskazuje mi wierzchołki i t , i muszę obliczyć x s - x t . Jest wiele rzeczy do wypróbowania, na przykład znalezienie najkrótszej ścieżki lub znalezienie jak największej liczby niepowiązanych ścieżek i ich uśrednienie (ważone odwrotnością pierwiastka kwadratowego długości). Czy istnieje „optymalna” odpowiedź?stxs−xt

Problem obliczania sam w sobie nie jest w pełni zdefiniowany (np. Czy powinienem założyć wcześniejszy o zmiennych?)xs−xt

ds.algorithms graph-algorithms Mihai
źródło
podczas gdy nie jest to odpowiedź, użycie filtru Kalmana wzdłuż ścieżki od s do t przychodzi na myśl jako sposób na uzyskanie dobrego opanowania długości ścieżki.
Suresh Venkat
Może to nie pomóc lub może być o wiele więcej technologii niż jest to potrzebne, ale istnieje rozwijająca się teoria stochastycznej topologii algebraicznej, która ma na celu rozwiązywanie problemów w robotyce i biologii molekularnej dotyczących kompleksów, których krawędzie są nieprecyzyjnie mierzone. Istnieją twierdzenia dotyczące asymptotyków losowych połączeń (połączenie = wykres z wagami krawędzi). Na przykład, myślę, że wyniki w tym artykule pozwoliłyby uzyskać oczekiwane liczby Betti na wykresie: arxiv.org/abs/0708.2997
Aaron Sterling
Czy fakt, że błędy są równomiernie rozłożone w [-1, 1], a nie jakaś inna dystrybucja, jest nieodłącznym elementem twojego problemu lub decyzji o dowolnym modelu? Jeśli to drugie, możesz prawdopodobnie uprościć sprawę, używając zamiast tego Gaussian.
Warren Schudy,
Model błędu jest z pewnością nieodłączny od problemu. ±1
Mihai,

Odpowiedzi:

3

Obszarem, na który chcesz szukać odpowiedzi, jest uczenie maszynowe. Opisałeś model graficzny. Myślę, że w tym przypadku metody tak proste, jak propagacja przekonań powinny wystarczyć.

Raphael
źródło
Propagacja przekonań nie jest dokładna na ogólnych wykresach. Wydaje się, że problem Mihai można rozwiązać za pomocą metod bardziej opartych na zasadach niż propagowanie przekonań.
Warren Schudy,
3

x

Warren Schudy
źródło
st
xxs-xtxs-xtxs-xt=do
Warren Schudy,
Oczywiście obliczenie objętości danego polytopu może potencjalnie być znacznie łatwiejsze. Musiałbym o tym pomyśleć.
Warren Schudy,
Podejrzewam, że Gaussianie lepiej się zachowują, ponieważ MLE rozkładu połączeń daje również MLE każdej zmiennej. Ale musiałbym się zastanowić i / lub sprawdzić, żeby się upewnić.
Warren Schudy,
Twój szereg / równoległy przykład sugeruje, że minimalizacja sumy kwadratów reszt może być skuteczną heurystyką dla niektórych wykresów, nawet jeśli twoje błędy nie są gaussowskie.
Warren Schudy,