Система «стохастических уравнений»

Рассмотрим граф с вершинами и ребрами. Вершины помечены действительными переменными , где фиксировано. Каждое ребро представляет собой «измерение»: для ребра я получаю измерение . Точнее, - действительно случайная величина в , равномерно распределенная и независимая от всех других измерений (ребер). $n$ $m$ $x_i$ $x_1=0$ $(u,v)$ $z \approx x_u - x_v$ $z$ $(x_u - x_v) \pm 1$

Мне дают график и измерения, с обещанием распределения для выше. Я хочу «решить» систему и получить вектор . Есть ли какое-то количество работ по проблемам этого типа? $x_i$

На самом деле, я хочу решить еще более простую проблему: кто-то указывает мне на вершины и , и я должен вычислить . Есть много вещей, которые можно попробовать, например, найти кратчайший путь или найти как можно больше непересекающихся путей и усреднить их (взвешенные по обратному квадратному корню из длины). Есть ли «оптимальный» ответ? $s$ $t$ $x_s - x_t$

Проблема вычисления сама по себе не полностью определена (например, должен ли я предполагать априор относительно переменных?) $x_s - x_t$

ds.algorithms graph-algorithms Михай
источник

хотя это и не ответ, использование фильтра Калмана вдоль пути от s до t приходит на ум как способ получить достойное управление длиной пути.

Суреш Венкат

Это может не помочь, или может быть гораздо больше технологий, чем необходимо, но есть развивающаяся теория стохастической алгебраической топологии, которая решает вопросы в робототехнике и молекулярной биологии о комплексах, грани которых неточно измерены. Существуют теоремы об асимптотике случайных связей (связь = граф с весами ребер). Например, я думаю, что результаты в этом документе позволят вам получить ожидаемые числа Бетти на вашем графике: arxiv.org/abs/0708.2997

Аарон Стерлинг,

Является ли тот факт, что ошибки распределены в [-1,1] равномерно, а не каким-либо другим распределением, присущим вашей проблеме или произвольному решению моделирования? Если последнее, вы, вероятно, можете сделать вещи намного проще, используя вместо этого гауссианцев.

Уоррен Шуди

\pm 1

$\pm 1$

Ответы:

Область, на которую вы хотите посмотреть ответы, это машинное обучение. Вы описали графическую модель. Я думаю, что в этом случае достаточно простых методов распространения убеждений .

Рафаэль
источник

Распространение убеждений не является точным в общих графах. Проблема Михая, кажется, решаема более принципиальными методами, чем пропаганда убеждений.

Уоррен Шуди

$x$

Уоррен Шуди
источник

s

$s$

t

$t$

x

$x$

x_{s} - x_{t}

$x_s-x_t$

x_{s} - x_{t}

$x_s-x_t$

x_{s} - x_{t} = c

$x_s - x_t = c$

Уоррен Шуди

Конечно, вычисление объема конкретного рассматриваемого многогранника может быть намного проще. Я должен был бы думать об этом.

Уоррен Шуди

У меня есть подозрение, что гауссиане ведут себя лучше, так как MLE совместного распределения также дает MLE каждой переменной. Но я должен был бы подумать больше и / или посмотреть, чтобы быть уверенным.

Уоррен Шуди

Ваш ряд / параллельный пример показывает, что минимизация суммы квадратов невязок может быть эффективной эвристикой для некоторых графиков, даже если ваши ошибки не являются гауссовыми.

Уоррен Шуди