Каждый день люди решают множество проблем. Может быть, мы придумываем, что нам надеть на вечеринку, или, может быть, мы придумываем лучший способ поехать в какое-то место. Иногда мы даже пытаемся понять, за кого выйти замуж или в какой колледж поступить.
Когда человек решает сложную проблему, включающую множество различных факторов, он идет на компромисс, даже не осознавая этого. Если мы тратим слишком мало времени на решение проблемы, мы получаем решение, которого просто недостаточно. Однако если мы потратим слишком много времени на решение проблемы, мы получим отличное решение, но это займет слишком много времени. Другими словами, когда мы решаем сложные проблемы, мы неосознанно, но эффективно отвечаем на следующий вопрос:
Когда мы должны перестать думать о проблеме и просто начать действовать, исходя из лучшего решения, которое мы придумали на данный момент?
Рассмотрим пример. Предположим, Салли придумывает лучший способ добраться от дома до горнолыжного курорта. Взгляните на несколько вариантов. Что ей предпочесть?
- Стоит ли ей долго думать (30 минут), чтобы найти отличный маршрут, который займет 35 минут?
- Стоит ли ей вообще думать почти мгновенно (1 секунда), чтобы проложить ужасный маршрут, который займет 2 часа?
- Стоит ли ей подумать о приличном количестве времени (2 минуты), чтобы составить приличный маршрут, который займет 40 минут?
Хотя первый вариант приводит к самому быстрому пути, она слишком много думала. Точно так же, хотя второй вариант требует от нее очень мало думать, она слишком много проводила за рулем. Однако третий вариант предлагает хороший компромисс между временем обдумывания и временем вождения.
Моя первая работа в аспирантуре пыталась ответить на этот вопрос для робота: когда робот должен перестать думать о своей проблеме и начать действовать, исходя из лучшего решения, которое он придумал до сих пор? мы поговорим о сегодняшнем дне.
Что мы подразумеваем под мышлением?
Давайте сначала формализуем, что мы подразумеваем под роботом мышлением. Мы не говорим о трудной проблеме сознания или аргументе китайской комнаты для философов вроде меня в этой комнате. Вместо этого мы говорим о классе алгоритмов, который называется алгоритм в любое время. Проще говоря, алгоритм в любое время - это просто алгоритм, который постепенно улучшает решение с течением времени и может быть прерван в любое время для этого решения. Например, если мы пытаемся найти маршрут от продуктового магазина до больницы, алгоритм в любое время будет постоянно создавать маршруты, которые со временем становятся все лучше и лучше. По сути, когда мы говорим, что робот думает, мы на самом деле имеем в виду, что робот выполняет в любое время алгоритм, который создает решения, которые со временем улучшаются.
У алгоритма, работающего в любое время, обычно есть пара хороших свойств. Во-первых, постоянный алгоритм демонстрирует монотонность: он гарантирует, что качество решения увеличивается или остается неизменным, но никогда не ухудшается с течением времени. Далее, алгоритм в любое время демонстрирует убывающую отдачу: улучшение качества решения высокое на ранних этапах вычислений и низкое на более поздних этапах.
Чтобы проиллюстрировать поведение алгоритма в любое время, взгляните на эту фотографию. На этой фотографии по мере увеличения времени вычисления увеличивается и качество решения. Оказывается, такое поведение довольно типично для алгоритма, работающего в любое время.
Качество торгового решения по времени вычислений
Чтобы определить, когда робот должен перестать думать и начать действовать, нам нужно количественно оценить две вещи: насколько качество решения стоит для нас и сколько времени стоит для нас. Подсказка зависящая от времени утилита. Зависимая от времени полезность представляет собой полезность решения, вычисленного с помощью алгоритма в любое время. Интуитивно понятно, что в любых задачах принятия решений в реальном времени решение некоторого качества, вычисленное за секунду, имеет более высокую полезность, чем решение того же качества, вычисленное за час. Это означает, что полезность решения зависит как от качества, так и от времени вычислений. Вот формальный способ сказать это:
К счастью, обычно можно упростить зависящую от времени функцию полезности, выразив ее как разницу между двумя функциями, называемыми функцией внутренней ценности и стоимостью времени. Во-первых, функция внутренней ценности представляет полезность решения, если мы учитываем только качество этого решения, игнорируя стоимость времени вычислений. Во-вторых, затраты времени представляют полезность решения, если мы принимаем во внимание только время, необходимое для вычисления этого решения, не принимая во внимание значение качества решения. Давайте определим это упрощение более формально ниже:
В чем смысл всего этого? Отличный вопрос. Учитывая зависящую от времени функцию полезности, разделенную на функцию внутренней ценности и стоимость времени, проблема принятия решения о том, когда прервать алгоритм в любое время и действовать в соответствии с текущим решением, становится четко определенной. Например, взгляните на пример ниже. У нас есть три функции: функция внутренней ценности, затраты времени и функция полезности, зависящая от времени. Функция внутренней стоимости постепенно увеличивается с течением времени, затраты времени экспоненциально снижаются с течением времени, а функция полезности, зависящая от времени, создает для нас выпуклую функцию. Мы должны перестать думать и начать действовать в верхней части функции полезности, зависящей от времени.
Звучит просто, правда? Что ж, есть проблема. Хотя легко указать на оранжевый кружок и сказать, остановитесь здесь, на самом деле мы не знаем заранее о производительности алгоритма в любое время. Чтобы решить, когда прервать алгоритм в любое время и действовать в соответствии с текущим решением, необходимо спрогнозировать производительность алгоритма в любое время в будущем.
Прогнозирование производительности алгоритма в любое время
Прежде чем мы перейдем к тому, как мы можем предсказать производительность алгоритма в любое время, давайте определим еще несколько вещей. Мы собираемся определить пару векторов, которые вместе представляют производительность алгоритма в любое время. Первый вектор описывает прошлую производительность алгоритма в любое время, когда он решает экземпляр проблемы. Мы можем определить прошлую производительность как вектор качеств решения, наблюдаемых от начального решения до текущего решения. Другими словами, история производительности - это последовательность качеств решения, наблюдаемых от начального временного шага до текущего временного шага алгоритма в любое время, например:
Второй вектор представляет будущую производительность постоянного алгоритма, когда он решает конкретную проблему. Мы можем определить будущую производительность как вектор качеств решения, спроецированный на оставшееся время работы алгоритма после текущего решения до окончательного решения. То есть проекция производительности - это последовательность качеств решения, спроецированная после текущего временного шага до последнего временного шага алгоритма, подобного следующему:
Чтобы предсказать будущую производительность алгоритма в любое время, мы можем использовать его прошлую производительность в случае решаемой проблемы. Как правило, это просто функция, которая вычисляет прогноз производительности на основе истории производительности. Не связываясь с конкретной реализацией, давайте определим эту функцию примерно так:
Важно подчеркнуть, что эту функцию можно реализовать разными способами. В большинстве случаев простой метод, такой как нелинейная регрессия, позволяет рассчитать прогноз производительности на основе истории производительности. Собственно, это то, что я сделал в газете. Однако для всех тех экспертов по глубокому обучению это также может быть сделано с использованием сложной модели, такой как нейронная сеть, которая включает в себя функции алгоритма.
Вот интуитивно понятное изображение предсказателя производительности. В идеале он рассчитывает прогнозы производительности, которые приближаются к истинной производительности алгоритма в любое время по мере увеличения размера истории производительности. Например, на i -м временном шаге i -ый прогноз производительности не очень хорошо соответствует истинной производительности p *. На самом деле это слишком оптимистично. Однако на (i + 1) -м временном шаге следующий прогноз производительности (i + 1) -й прогноз производительности становится ближе к истинной производительности p * . Интуитивно понятно, что по мере того, как предсказатель производительности использует больше качеств решения в истории производительности, прогнозы производительности приближаются к истинной производительности алгоритма.
Когда робот должен перестать думать и начать действовать?
Теперь, когда мы определили множество вещей, мы, наконец, можем увидеть, как робот решает, когда перестать думать и начать действовать. По сути, робот будет отслеживать свой алгоритм в любое время через фиксированные интервалы. На каждом временном шаге робот будет генерировать прогноз производительности на основе истории производительности, используя предсказатель производительности. В зависимости от того, как выглядит этот прогноз производительности, робот либо прервет алгоритм в любое время, либо позволит ему продолжить работу. На более глубоком уровне основной алгоритм работает следующим образом:
- Инициализировать временной шаг и историю производительности.
- Запустите алгоритм в любое время.
- Пока постоянный алгоритм работает, выполните следующие операции:
- - Получить текущее решение алгоритма в любое время.
- - Рассчитайте качество текущего решения.
- - Добавить качество текущего решения в историю производительности.
- - Вычислить прогноз производительности на основе истории производительности с помощью предиктора производительности.
- - Если прогноз производительности соответствует условию остановки:
- - - Прервать алгоритм в любое время.
- - - Вернуть текущее решение.
- - В противном случае, увеличьте временной шаг и спите на некоторое время.
Но что такое условие остановки? Проще говоря, мы используем условие остановки, чтобы определить, следует ли прерывать любой алгоритм в любое время на заданном временном шаге. Если условие остановки верно, мы прерываем алгоритм. В противном случае мы позволяем алгоритму продолжать работу.
И какое условие остановки мы должны использовать? Мы используем условие остановки, которое позволяет алгоритму в любое время работать до тех пор, пока разница между полезностью прогнозируемого лучшего решения , а полезность текущего решения больше нуля . Более формально, мы позволяем алгоритму в любое время работать, когда следующее значение больше нуля:
Без лишних слов, для тех, кто хочет увидеть больше технических деталей, вот как выглядит метод принятия решения, когда интеллектуальная система должна перестать думать и начать действовать:
