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