Но некоторые типы данных собрать сложнее, чем истории посещений в Интернете — например, информацию о геологических формациях на глубине тысячи футов под землей. А в других приложениях — например, при попытке предсказать путь шторма — может просто не хватить времени, чтобы обработать все доступные данные.
Дэн Левин, аспирант Массачусетского технологического института по аэронавтике и космонавтике, и его советник Джонатан Хау, профессор аэронавтики и астронавтики Ричарда Кокберна Маклорена, разработали новую технику, которая может помочь в решении обеих проблем. Для ряда распространенных приложений, в которых данные либо трудно собрать, либо слишком много времени для обработки, этот метод может определить подмножество элементов данных, которые дадут наиболее надежные прогнозы. Таким образом, геологи, пытающиеся оценить масштабы подземных залежей нефти, или метеорологи, пытающиеся спрогнозировать погоду, могут обойтись всего несколькими целевыми измерениями, экономя время и деньги.
Левин и Хау, представившие свою работу на конференции «Неопределенность в искусственном интеллекте» на этой неделе, рассматривают особый случай, когда кое-что о взаимосвязях между элементами данных известно заранее. Прогнозирование погоды представляет собой интуитивно понятный пример: измерения температуры, давления и скорости ветра в одном месте, как правило, являются хорошими индикаторами измерений в соседних местах или измерений в том же месте через короткое время, но корреляция тем слабее, чем дальше. вы перемещаетесь либо географически, либо хронологически.
Графический контентТакие корреляции могут быть представлены так называемой вероятностной графической моделью.
В этом контексте граф представляет собой математическую абстракцию, состоящую из узлов, обычно изображаемых в виде кругов, и ребер, обычно изображаемых в виде отрезков линий, соединяющих узлы. Сетевая диаграмма — это один из примеров графа; генеалогическое древо — другое. В вероятностной графической модели узлы представляют переменные, а края представляют силу корреляций между ними.
Левин и Хау разработали алгоритм, который может эффективно вычислить, сколько информации любой узел графа дает вам о любом другом — то, что в теории информации называется «взаимной информацией». Как объясняет Левин, одним из препятствий на пути к эффективному выполнению этого вычисления является наличие «петель» в графе или узлов, соединенных более чем одним путем.
По словам Левина, вычисление взаимной информации между узлами похоже на введение синего красителя в один из них и последующее измерение концентрации синего в другом. «По мере того, как мы продвигаемся дальше по графику, он обычно будет падать», — говорит Левин. «Если между ними есть уникальный путь, то мы можем довольно легко вычислить его, потому что мы знаем, какой путь пойдет синий краситель. Но если на графике есть петли, то нам труднее вычислить, насколько синие другие узлы, потому что есть много разных путей ".
Итак, первым шагом в методике исследователей является вычисление «остовных деревьев» для графа. Дерево — это просто граф без петель: например, в семейном дереве петля может означать, что кто-то был родителем и братом одного и того же человека.
Остовное дерево — это дерево, которое касается всех узлов графа, но не имеет ребер, образующих петли.Ставки на спред
Однако большинство узлов, которые остаются в графе, являются «неприятными», то есть они не содержат много полезной информации об интересующем узле. Ключ к технике Левина и Хау — это способ использовать эти узлы для навигации по графу, не позволяя их ближнему влиянию искажать дальнодействующие вычисления взаимной информации.Это возможно, объясняет Левин, потому что вероятности, представленные на графике, являются гауссовскими, что означает, что они следуют колоколообразной кривой, известной как модель, например, дисперсии характеристик в популяции. Гауссово распределение исчерпывающе характеризуется всего двумя измерениями: средним значением — скажем, средним ростом в популяции — и дисперсией — скоростью, с которой распространяется колокол.
«Неопределенность проблемы на самом деле является функцией разброса распределения», — говорит Левин. «На самом деле это не зависит от того, где сосредоточено распределение в пространстве». Как следствие, часто можно рассчитать дисперсию по вероятностной графической модели, не полагаясь на конкретные значения узлов. «Полезность данных можно оценить до того, как они станут доступны», — говорит Левин.