Nano Hash - криптовалюты, майнинг, программирование

Теория графов - изучите функцию стоимости, чтобы найти оптимальный путь

Это проблема контролируемого обучения.

У меня есть ориентированный ациклический граф (DAG). Каждое ребро имеет вектор признаков X, а каждый узел (вершина) имеет метку 0 или 1. Задача состоит в том, чтобы найти функцию стоимости w(X), такую, чтобы кратчайший путь между любой парой узлов имел наибольшее отношение От 1 до 0 (минимальная ошибка классификации).

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

Хотя моя постановка задачи не является типичной постановкой задачи бинарной классификации, вот хорошее введение в нее: http://en.wikipedia.org/wiki/Supervised_learning#How_supervised_learning_algorithms_work

Вот еще некоторые подробности:

  1. Каждый вектор признаков X представляет собой d-мерный список действительных чисел.
  2. Каждое ребро имеет вектор признаков. То есть, учитывая набор ребер E = {e1, e2, .. en} и набор векторов признаков F = {X1, X2 ... Xn}, тогда ребро ei связано с вектором Xi.
  3. Можно придумать функцию f (X), так что f (Xi) дает вероятность того, что ребро ei указывает на узел, помеченный 1. Примером такой функции является упомянутая выше, найденная с помощью логистического регресс. Однако, как я уже говорил выше, такая функция неоптимальна.

ТАК ВОПРОС: Учитывая граф, начальный узел и конечный узел, как мне узнать оптимальную функцию стоимости w (X), чтобы отношение узлов 1 к 0 было максимальным (минимальная ошибка классификации)?

machine-learning classification graph-theory
04.11.2012

  • Можете ли вы уточнить, что вы пытались и что вы подразумеваете под этим, не работает? 05.11.2012
  • Граф, кажется, имеет только два узла, то есть узел для метки 0 и узел для метки 1?! Однако эти узлы являются отдельными, а это означает, что фактического графа нет? Не могли бы вы подробнее рассказать о своей модели и выбранном графическом представлении? 05.11.2012
  • @карлосдк. Хорошо, я подробно остановился на своем подходе к логистической регрессии, который не работал с моими игрушечными данными. Спасибо. 14.11.2012
  • Это с конкурса kaggle, верно? 14.11.2012
  • не совсем понял ваш вопрос. 1. в вашем логистическом подходе, что, если узел имеет два входящих ребра, как будет выглядеть ваша входная функция? 2. вы сказали, что это DAG, поэтому, когда вы прокладываете кратчайший путь между любой парой узлов, путь должен следовать топологии DAG (направленной), верно? 3. Можете ли вы уточнить функцию затрат и ее цель? Текущее утверждение не имеет для меня смысла. Благодарю. 14.11.2012
  • @зелень. Я добавил некоторые подробности, надеюсь, они помогут. 15.11.2012
  • Рассмотрим, есть ли два пути между A и B. Первые узлы пути помечены 0-1-1-1 (соотношение 3:1). Узлы второго пути помечены 0-1-1-1-1 (соотношение 4:1). Хотя второй путь имеет более высокое отношение 1 к 0, но он на два ребра длиннее! Чтобы минимизация стоимости пути была эквивалентна максимизации отношения, весовая функция должна давать отрицательные значения на ребрах, соединяющих две единицы. Просто чтобы уточнить, разрешены ли отрицательные веса ребер? 21.11.2012
  • Проблема интересная. У меня есть некоторый разумный уровень знаний о контролируемом обучении, но я никогда не видел его в таком контексте. Самая близкая проблема, которую я видел, - это изучение модели тегов последовательности, такой как условное случайное поле, она выполняет минимизацию кратчайшего пути, чтобы найти правильные метки последовательности, и вы хотите выбрать веса функций, чтобы вывод кратчайшего пути восстанавливал правильный путь / метки последовательности. Если бы вы отбросили обучающую часть и могли бы напрямую выбирать веса ребер, смогли бы вы решить свою проблему? Я хотел бы увидеть больше информации о мотивации. 21.11.2012

Ответы:


1

Это похоже на проблему, в которой генетический алгоритм имеет отличный потенциал. Если вы определяете желаемую функцию, например. (но не ограничиваясь этим) линейная комбинация признаков (вы можете добавить квадратичные члены, затем кубические, до бесконечности), тогда ген является вектором коэффициентов. Мутатор может быть просто случайным смещением одного или нескольких коэффициентов в разумных пределах. Функция оценки — это просто среднее отношение единиц к нулям на кратчайших путях для всех пар в соответствии с текущей мутацией. В каждом поколении выберите несколько лучших генов в качестве предков и мутируйте, чтобы сформировать следующее поколение. Повторяйте, пока ген ueber не окажется под рукой.

21.11.2012
  • Это новая и хорошая идея. Но очевидно, что метки (1 и 0) должны использоваться, чтобы заставить функцию оценки работать. 27.11.2012

    • 2

    На самом деле это не ответ, но нам нужно уточнить вопрос. Я мог бы вернуться позже для возможного ответа, хотя.

    Ниже приведен пример DAG.

    введите здесь описание изображения

    Предположим, что красный узел является начальным узлом, а желтый — конечным узлом. Как вы определяете кратчайший путь с точки зрения

    наибольшее отношение 1 к 0 (минимальная ошибка классификации)?

    Редактировать: я добавляю имена для каждого узла и два примера имен для двух верхних ребер.

    Мне кажется, вы не можете выучить такую ​​функцию стоимости, которая принимает векторы признаков в качестве входных данных и чьи выходные данные (веса ребер? или что-то еще) могут указать вам кратчайший путь к любому узлу с учетом топологии графа. Причина указана ниже:

    • Предположим, у вас нет указанных вами векторов признаков. Учитывая приведенный выше график, если вы хотите найти кратчайший путь для всех пар с соответствующим отношением 1s к 0s, идеально использовать уравнение Беллмана или, точнее, Dijkastra плюс правильная эвристическая функция (например, процент 1s в пути). Другой возможный безмодельный подход — использовать q-learning, в котором мы получаем вознаграждение + 1 за посещение узла 1 и -1 за посещение узла 0. Мы изучаем q-таблицу поиска для каждого целевого узла по одному. Наконец, у нас есть кратчайший путь для всех пар, когда все узлы рассматриваются как целевые узлы.

    • Теперь предположим, что вы волшебным образом получили векторы признаков. Поскольку вы можете найти оптимальное решение и без этих векторов, почему они помогут, если они существуют?

    • Существует одно возможное условие, при котором вы можете использовать вектор признаков для изучения функции стоимости, которая оптимизирует веса ребер, то есть векторы признаков зависят от топологии графа (связей между узлами и положения 1s и 0s). Но я вообще не увидел этой зависимости в вашем описании. Так что я думаю, что его не существует.

    15.11.2012
  • Спасибо за пример. Кратчайший путь в любом графе часто определяется с помощью функции стоимости w(.), которая присваивает вес каждому ребру. Я спрашиваю, как найти функцию стоимости w(X), которая зависит от вектора функций X на каждом ребре, чтобы кратчайший путь, основанный на этой весовой функции, максимизировал отношение 1 к 0 (вы можете быстро увидеть, что есть два пути, где это соотношение максимально в приведенном выше примере). Обратите внимание, однако, что весовая функция, которую я хочу найти, зависит ТОЛЬКО от вектора признаков на каждом ребре и не знает, что такое метка в каждом узле. 20.11.2012
  • Мне кажется, вы не можете выучить такую ​​функцию стоимости, которая принимает веса ребер в качестве входных данных. Как я уже говорил несколько раз, функция стоимости принимает в качестве входных данных векторы признаков, а не веса. Теперь я знаю, что могу использовать Dijkstra, чтобы найти путь, который максимизирует отношение 1 к 0, но это не проблема. Проблема состоит в том, чтобы найти функцию, которая, не используя метки в каждом узле (0 или 1), а только векторы признаков, присваивает веса ребрам так, чтобы кратчайший путь имел максимальное отношение 1 к 0. Пожалуйста, прочитайте задачу и поймите ее, прежде чем говорить, что это не имеет смысла. 20.11.2012
  • интересный. Где вы указали, что without using the labels at each node,but only... в вашем описании проблемы??? Вы даже приводите пример обучения с учителем, чтобы показать, что вы пытались сделать, как вы могли это сделать без меток 1 и 0s ... Да, я не понимаю ваш вопрос, но я не думаю, что вы понимаете свой собственный вопрос, по крайней мере, вы не сформулировали проблему четко в первую очередь. 21.11.2012
  • Это правда, я только новичок в контролируемом обучении. Я совершенно неправ, что пришел сюда, чтобы помочь. Я замолчу. 21.11.2012

    • 3

    Я считаю, что ваш вопрос очень близок к области обратного обучения с подкреплением, где вы берете определенные «экспертные демонстрации» оптимальных путей и пытаетесь изучить функцию стоимости, чтобы ваш планировщик (A * или какой-либо агент обучения с подкреплением) выводит тот же путь в качестве экспертной демонстрации. Это обучение проводится итеративно. Я думаю, что в вашем случае экспертные демонстрации могут быть созданы вами как пути, которые проходят через максимальное количество 1 помеченных ребер. Вот ссылка на хорошую статью на эту тему: Learning to Search: Функциональные градиентные методы для имитационного обучения. Это из сообщества робототехники, где планирование движения обычно настраивается как задача поиска по графу, а функции затрат на обучение необходимы для демонстрации желаемого поведения.

    06.06.2017
    Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..