Способ и система создания параметра качества прогноза для прогностической модели, выполняемой в алгоритме машинного обучения

Изобретение относится к области вычислительной техники. Техническим результатом является определение параметра качества прогноза для дерева решений в прогностической модели дерева решений. Раскрыт способ определения параметра качества прогноза для дерева решений в прогностической модели дерева решений, данный уровень дерева решений обладает по меньшей мере одним узлом, параметр качества прогноза используется для оценки качества прогноза прогностической модели дерева решений на данной итерации обучения дерева решений, способ выполняется системой машинного обучения, которая выполняет прогностическую модель дерева решений, способ включает в себя: получение доступа, с постоянного машиночитаемого носителя системы машинного обучения, к набору обучающих объектов, причем каждый обучающий объект из набора обучающих объектов включает в себя указание на документ и цель, связанную с документом; организацию набора обучающих объектов в упорядоченный список обучающих объектов, причем упорядоченный список обучающих объектов организован таким образом, что для каждого обучающего объекта в упорядоченном списке обучающих объектов существует по меньшей мере один из: (i) предыдущий обучающий объект, который находится до данного обучающего объекта, и (ii) последующий обучающий объект, который находится после данного обучающего объекта; спуск набора обучающих объектов по дереву решений таким образом, что каждый из набора обучающих объектов подвергается классификации моделью дерева решений на данной итерации обучения в данный дочерний узел из по меньшей мере одного узла данного уровня дерева решений; создание параметра качества прогноза для дерева решений путем создания для данного обучающего объекта, который был классифицирован в данный дочерний узел, параметра качества прогноза, создание выполняется на основе целей только тех обучающих объектов, которые находятся раньше обучающего объекта в упорядоченном списке обучающих объектов. 5 н. и 25 з.п. ф-лы, 13 ил.

 

ОБЛАСТЬ ТЕХНИКИ

[01] Настоящая технология относится к электронным устройствам и способам создания прогностической модели, используемой в алгоритме машинного обучения (MLA). Конкретнее, настоящая технология связана со способом и системой создания параметра качества прогноза для прогностической модели, используемой в MLA.

УРОВЕНЬ ТЕХНИКИ

[02] Алгоритмы машинного обучения (MLA) используются для различных задач в компьютерных технологиях. Обычно, MLA используются для создания прогнозов, связанных с пользовательским взаимодействием с компьютерным устройством. Примером сферы использования MLA является пользовательское взаимодействие с содержимым, доступным, например, в сети Интернет.

[03] Объем доступной информации на различных интернет-ресурсах экспоненциально вырос за последние несколько лет. Были разработаны различные решения, которые позволяют обычному пользователю находить информацию, которую он(а) ищет. Примером такого решения является поисковая система. Примеры поисковых систем включают в себя такие поисковые системы как GOOGLE™, YANDEX™, YAHOO!™ и другие. Пользователь может получить доступ к интерфейсу поисковой системы и подтвердить поисковый запрос, связанный с информацией, которую пользователь хочет найти в Интернете. В ответ на поисковый запрос поисковые системы предоставляют ранжированный список результатов поиска. Ранжированный список результатов поиска создается на основе различных алгоритмов ранжирования, которые реализованы в конкретной поисковой системе, и которые используются пользователем, производящим поиск. Общей целью таких алгоритмов ранжирования является представление наиболее релевантных результатов вверху ранжированного списка, а менее релевантных результатов - на менее высоких позициях ранжированного списка результатов поиска (а наименее релевантные результаты поиска будут расположены внизу ранжированного списка результатов поиска).

[04] Поисковые системы обычно являются хорошим поисковым инструментом в том случае, когда пользователю заранее известно, что именно он(а) хочет найти. Другими словами, если пользователь заинтересован в получении информации о наиболее популярных местах в Италии (т.е. поисковая тема известна), пользователь может ввести поисковый запрос: «Наиболее популярные места в Италии». Поисковая система предоставит ранжированный список интернет-ресурсов, которые потенциально являются релевантными по отношению к поисковому запросу. Пользователь далее может просматривать ранжированный список результатов поиска для того, чтобы получить информацию, в которой он заинтересован, в данном случае - о посещаемых местах в Италии. Если пользователь по какой-либо причине не удовлетворен представленными результатами, пользователь может произвести вторичный поиск, уточнив запрос, например «наиболее популярные места в Италии летом», «наиболее популярные места на юге Италии», «Наиболее популярные места в Италии для романтичного отдыха».

[05] В примере поисковой системы, алгоритм машинного обучения (MLA) используется для создания ранжированных поисковых результатов. Когда пользователь вводит поисковый запрос, поисковая система создает список релевантных веб-ресурсов (на основе анализа просмотренных веб-ресурсов, указание на которые хранится в базе данных поискового робота в форме списков словопозиций или тому подобного). Далее поисковая система выполняет ML А для ранжирования таким образом созданного списка поисковых результатов. MLA ранжирует список поисковых результатов на основе их релевантности для поискового запроса. Подобный MLA "обучается" для прогнозирования релевантности данного поискового результата для поискового запроса на основе множества "факторов", связанных с данным поисковым результатом, а также указаний на взаимодействия прошлых пользователей с поисковыми результатами, когда они вводили аналогичные поисковые запросы в прошлом.

[06] Как было упомянуто ранее, поисковые системы полезны в случаях когда пользователь знает, что именно он(а) ищет (т.е. обладает конкретным поисковым намерением). Существует и другой подход, в котором пользователю предоставляется возможность обнаруживать содержимое и, конкретнее, позволяется отображать и/или рекомендовать содержимое, в поиске которого пользователь не был явно заинтересован. В некоторым смысле, подобные системы рекомендуют пользователю содержимое без отдельного поискового запроса, на основе явных или неявных интересов пользователя.

[07] Примерами таких систем являются система рекомендаций FLIPBOARD™, которая агрегирует и рекомендует содержимое из различных социальных сетей. Система рекомендаций FLIPBOARD предоставляет содержимое в «журнальном формате», где пользователь может «пролистывать» страницы с рекомендуемым/агрегированным содержимым. Системы рекомендаций собирают содержимое из социальных медиа и других веб-сайтах, представляет его в журнальном формате, и позволяют пользователям «пролистывать» ленты социальных новостей и ленты веб-сайтов, которые поддерживают партнерские отношения с компанией, что позволяет эффективно «рекомендовать» содержимое пользователю, даже если пользователь явно не выражал свой интерес в конкретном содержимом. Другим примером системы рекомендаций является система рекомендаций YANDEX.ZEN™, которая создает и представляет персонализированный контент пользователю, когда пользователь запускает приложение, связанное с Yandex.Zen™, которым может быть специальное приложение или соответствующая страница браузерного приложения.

[08] Для создания ранжированных результатов поиска в поисковой системе или списка рекомендуемых ресурсов в обычной системе рекомендаций, соответствующие системы используют алгоритм машинного обучения рекомендуемый контент из различных источников, доступных в Интернете.

[09] Обзор алгоритмов машинного обучения

[10] Существует множество типов MLA, известных в данной области техники. В широком смысле, можно выделить три типа MLA: алгоритм машинного обучения на основе обучения с учителем, алгоритм машинного обучения на основе обучения без учителя и алгоритм машинного обучения на основе обучения с подкреплением.

[11] Процесс MLA с учителем основан на целевом значении - итоговой переменной (или зависимой переменной), которая будет прогнозироваться из заданного набора предикторов (независимых переменных). Используя набор переменных, MLA (во время обучения) создает функцию, которая сопоставляет исходные данные с желаемыми результатами. Процесс обучения продолжается до тех пор пока MLA не достигнет желаемого уровня точности проверки данных. Примеры MLA на основе обучения с учителем включают в себя: Регрессию, Дерево решений, Случайный Лес, Логистическую Регрессию и т.д.

[12] MLA без учителя не использует для прогнозирования целевое значение или итоговую переменную как таковые. Подобные MLA используются для кластеризации множества значений в различные группы, которые широко используются для сегментирования клиентов в различные группы для конкретных целей. Примеры MLA без учителя включают в себя: Алгоритм Apriori, метод K-средних.

[13] MLA с подкреплением обучается принятию конкретных решений. Во время обучения, MLA находится обучающей среде, где он обучает сам себя постоянно используя систему проб и ошибок. MLA обучается на основе предыдущего опыта и пытается усвоить максимально качественные знания для принятия точных решений. Примером MLA с подкреплением может быть Марковский процесс.

[14] MLA на основе деревьев решений является примером MLA с учителем. Этот тип MLA использует дерево решений (какпрогностическую модель) для перехода от наблюдений за элементом (представлены в виде ветвей) к выводам о целевом значении элемента (представлены в виде листьев). Древовидные модели, в которых итоговая переменная может принимать дискретный набор значений, называются деревьями классификации; в этих древовидных структурах, листья представляют собой отметки класса, а ветви представляют собойсочетание факторов, которое приводит к этим отметкам класса. Деревья решений, в которых итоговая переменная может принимать непрерывные значения (как правило, вещественные числа), называются регрессионными деревьями.

[15] Для того чтобы MLA на основе деревьев решений работали, необходимо "создать" или обучить их с помощью обучающего набора объектов, содержащего множество обучающих объектов (например, документы, события и тому подобное). Эти обучающие объекты были "размечены" людьми-асессорами. Например, человек-асессор может ранжировать данный обучающий объект как "неинтересный", "интересный" или "очень интересный".

[16] Градиентный бустинг

[17] Градиентный бустинг - один из подходов к созданию MLA на основе деревьев решений, в котором создается прогностическая модель в форме ансамбля деревьев. Ансамбль деревьев создается ступенчатым способом. Каждое последующее дерево решений в ансамбле деревьев решений сосредоточено на обучении на основе тех итераций в предыдущем дереве решений, которые были "слабыми моделями" в предыдущей(их) итерации(ях) в ансамбле деревьев решений (т.е. теми, которые связаны с маловероятным прогнозом / высокой вероятностью ошибки).

[18] В общем случае, бустинг представляет собой способ, нацеленный на улучшение качества прогнозирования MLA. В этом сценарии, вместо того, чтобы полагаться на прогноз одного обученного алгоритма (например, одного дерева решений) система использует несколько обученных алгоритмов (т.е. ансамбль деревьев решений) и принимает окончательное решение на основе множества прогнозируемых результатов этих алгоритмов.

[19] В бустинге деревьев решений, MLA сначала создает первое дерево, затем второе, что улучшает прогноз результата, полученного от первого дерева, а затем третье дерево, которое улучшает прогноз результата, полученного от первых двух деревьев, и так далее. Таким образом, MLA в некотором смысле создает ансамбль деревьев решений, где каждое последующее дерево становится лучше предыдущего, конкретно сосредотачиваясь на слабых моделях из предыдущих итераций деревьев решений. Другими словами, каждое дерево создается на одном и том же обучающем наборе обучающих объектов, и, тем не менее, обучающие объекты, в которых первое дерево совершает "ошибки" в прогнозировании, являются приоритетными для второго дерева и т.д. Эти "сильные" обучающие объекты (те, которые на предыдущих итерациях деревьев решений были спрогнозированы менее точно), получают более высокие весовые коэффициенты, чем те, для которых были получены удовлетворительные прогнозы.

[20] Жадные алгоритмы

[21] При создании деревьев решений (например, с помощью градиентного бустинга), широко используются жадные алгоритмы. Жадный алгоритм - это алгоритмическая парадигма, которая связана с решением задач эвристическим путем принятия локально оптимального решения на каждом этапе (например, на каждом уровне дерева решений) с предположением о том, что таким образом будет найдено глобальное оптимальное значение. При создании деревьев решений использование жадного алгоритма может быть сведено к следующему: для каждого уровня дерева решений, алгоритм машинного обучения пытается найти наиболее оптимальное значение (фактора и/или разделения) - оно будет являться локально оптимальным решением. Когда определено оптимальное значение для данного узла, MLA переходит к созданию более низкого уровня дерева решений, ранее определенные значения для более высоких узлов являются "зафиксированными" - т.е. учитываются "без изменений" для данной итерации дерева решений в ансамбле дерева решений.

[22] Как и в случае с одним деревом, каждое дерево в ансамбле деревьев создается с помощью жадного алгоритма, что означает то, что когда MLA выбирает фактор и разделяющее значение для каждого узла дерева, MLA осуществляет выбор, который является локально оптимальным, например, для конкретного узла, а не для всего дерева в целом.

[23] Забывчивые деревья решений

[24] После того как были выбраны лучшие фактор и разделение для данного узла, алгоритм переходит к дочернему узлу данного узла и выполняет жадный выбор фактора и разделения для этого дочернего узла. В некоторых вариантах осуществления технологии, при выборе фактора для данного узла, алгоритм машинного обучения не может использовать факторы, использованные в узлах на более глубинных уровнях дерева. В других вариантах осуществления технологии, каждый глубинный уровень MLA анализирует все возможные факторы, вне зависимости от того, были ли они использованы на предыдущих уровнях. Подобные деревья называются "забывчивыми" деревьями, поскольку на каждом уровне дерево "забывает" о том, что оно использовало конкретный фактор на предыдущем уровне и снова учитывает этот фактор. Для выбора наилучшего фактора и разделителя для узла, для каждого возможного варианта вычисляется функция усиления). Выбирается опция (фактор или разделяющее значение) с наибольшим усилением.

[25] Параметр Качества Прогноза

[26] Когда создается данное дерево, для определения качества прогноза данного дерева (или данного уровня данного дерева при создании данного дерева), MLA вычисляет метрику (т.е. "оценку"), которая означает, насколько близко текущая итерация модели, которая включает в себя данное дерево (или данный уровень данного дерева) и предыдущие деревья, подходит к прогнозу правильного ответа (целевого значения). Оценка модели вычисляется на основе сделанных прогнозов и фактических целевых значений (правильных значений) обучающих объектов, использованных для обучения.

[27] Когда создается первое дерево, MLA выбирает значения для первого фактора и первого разделения для корневого узла первого дерева и оценивает качество подобной модели. Для этого, MLA "скрамливает" обучающие объекты первому дереву в том смысле, что он спускает обучающие объекты по ветвям дерева решений, и эти "скормленные" обучающие объекты разделяются на два (или более) различных листа первого дерева на разделении первого узла (т.е. они "классифицируются" деревом решений или, конкретнее, модель дерева решений пытается спрогнозировать целевое значение обучающего объекта, который проходит через модель дерева решений). После того, как все обучающие объекты были классифицированы, вычисляется параметр качества прогноза - определяется то, насколько близка классификация объектов к фактическим значениям целевых объектов.

[28] Конкретнее, зная целевые значения обучающих объектов, MLA вычисляет параметр качества прогноза (например, усиление информации и тому подобное) для этого первого фактора - первого разделения узла, и далее выбирает второй фактор со вторым разделением для корневого узла. Для этого второго варианта фактора и разделения корневого узла, MLA осуществляет те же этапы, что и в первом варианте (MLA "скармливает" обучающие объекты дереву и вычисляет результирующую метрику с помощью второго варианта комбинации фактора и разделения для корневого узла).

[29] MLA далее повторяет тот же процесс с третьим, четвертым, пятым и т.д. вариантам фактора и разделениям для корневого узла до тех пор пока MLA не проверит все возможные варианты фактора и разделяющего значения, и далее MLA выбирает тот вариант фактора и разделяющего значения для корневого узла, который дает наилучший результат прогноза (т.е. обладает самой высокой метрикой).

[30] После того как были выбраны фактор и разделяющее значение для корневого узла, MLA переходит к дочерним узлам корневого узла и выбирает свойства и разделяющие значения для дочерних узлов тем же способом, что и для корневого узла. Этот процесс далее повторяется для дочерних узлов первого дерева до тех пор пока дерево решений не будет создано.

[31] Далее, в соответствии с методом применения бустинга, ML А переходит к созданию второго дерева. Второе дерево нацелено на улучшение результатов прогнозирования, созданных первым деревом. Оно должно "исправлять" ошибки в прогнозировании, которые допущены первым деревом. Для этого второе дерево создается на обучающем объекте, и примеры, в которых были допущены ошибки первым деревом, обладают более высоким весовым коэффициентом, чем примеры, для которых первое дерево выдало правильный прогноз. Второе дерево создается аналогично тому как создавалось первое дерево.

[32] Этот подход позволяет последовательно создавать, десятки, сотни и даже тысячи деревьев. Каждое последующее дереве в ансамбле деревьев улучшает качество прогноза предыдущего дерева.

[33] Американская патентная заявка 8,572,071 (Опубликованная 29 октября 2013 года, под авторством Поттера и др., и выданная Ратгерскому университету в Нью-Джерси) описывает способ и устройство преобразования данных в векторную форму. Каждый вектор состоит из набора свойств, которые либо являются логическими, либо представлены в логической (булевой) форме. Векторы могу попадать или не попадать в категории, размеченные предметными экспертами (SME). Если категории существуют, метки категорий разделяют вектора на подмножества. Первое преобразование вычисляет предварительную вероятность для каждого свойства на основе связей между свойствами в каждом подмножестве векторов. Второе преобразование вычисляет новое числовое значение для каждого свойства на основе связей между свойствами в каждом подмножестве векторов. Третье преобразование работает с классифицированными векторами. На основе автоматического выбора категорий из свойств, это преобразование вычисляет новое числовое значение для каждого свойства на основе связей между свойствами в каждом подмножестве векторов.

[34] Американская патентная заявка 9,639,807 (опубликована 2 мая 2017 года под авторством Беренжера и др. и переданная Беренжеру и др.) описывает способ, включающий в себя: предоставление обучающих данных для обучения по меньшей мере одной одной математической модели, причем обучающие данные основаны на информации о прошлых полетах от множества пассажиров, и обучающие данные содержат первый набор векторов и соответствующую целевую переменную для каждого пассажира из множества пассажиров; обучение по меньшей мере одной математической модели с помощью обучающих данных; и предоставление второго набора векторов, относящихся к информации о прошлых полетах пассажира, в качестве входных данных для обученной по меньшей мере одной математической модели и расчет выходных данных обученной по меньшей мере одной математической модели на основе входных данных, причем выходные данные предоставляют прогноз о будущей активности пассажира, связанной с полетами.

РАСКРЫТИЕ ТЕХНОЛОГИИ

[35] Варианты осуществления настоящей технологии были разработаны с учетом определения разработчиками по меньшей мере одной технической проблемы, связанной с известными подходами к построению деревьев решений.

Полнота модели машинного обучения

[36] Полнота модели машинного обучения относится к одной или нескольким комбинация факторов, выбранных из набора факторов для создания одной или нескольких древовидных моделей, формирующих модели машинного обучения. В общем случае, чем больше в одной или нескольких древовидных моделях комбинаций факторов, тем лучше качество модели машинного обучения и, в результате, тем больше полнота модели машинного обучения. Методологии и/или алгоритмы, используемые для выбора одной или нескольких комбинаций факторов, могут привести, по меньшей мере при некоторых условиях обработки, к полноте, которая не является оптимальной. В качестве примера, такие алгоритмы как, например, «жадный» алгоритм, могут привести к выбору «слишком схожих» между собой в множестве древовидных моделей, формирующих модели машинного обучения, подгрупп факторов из набора факторов.

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

[38] Одна из причин, связанная с этой ситуацией, может быть объяснена тем, что некоторые алгоритмы, например, «жадный» алгоритм, созданы для выбора «наилучшего» фактора для данного уровня древовидной модели на основе определения того, что «фактор» с большой вероятностью является «лучшим», хотя такое определение на пофакторной основе может привести к более низкому среднему качеству древовидной модели. Эта ситуация может быть даже более вероятной, когда факторы по своей природе являются «сильными» (т.е. обладающими большим положительным вкладом в качество древовидной модели), хотя и не выбираются как «сильные» с помощью существующих алгоритмов. Такие факторы могут включать в себя факторы целочисленного типа и/или категориального типа, которые обычно связаны более чем с двумя ветвями после того, как они были выбраны как узлы в одной из древовидных моделей (в отличие от факторов бинарного типа, которые обычно связаны не более чем с двумя ветвями после того, как они были выбраны как узлы в одной из древовидных моделей).

[39] Эта проблема может в общем случае упоминаться как "искажение модели".

Переобучение модели машинного обучения

[40] В некоторых случаях алгоритмы, используемые для создания модели машинного обучения, такие как «жадный» алгоритм, могут создавать так называемую проблему переобучения. Такая проблема может быть выявлена при появлении недостоверных паттернов между значениями, созданными функцией h(q,d) и факторами, связанными с функцией h(q,d). Проблема переобучения может возникнуть, когда алгоритм, создающий одну или несколько древовидных моделей, формирующих модель машинного обучения, начинает выбирать и упорядочивать факторы, с помощью «запоминания» набора обучающих объектов, релевантных только набору трендов, а не создает закономерность («тренд») на основе набора обучающих объектов, который будет релевантней неизвестным объектам (т.е. тем объектам, которые не являются частью модели машинного обучения), а не только обучающим объектам из набора обучающих объектов.

[41] Другими словами, MLA может выявлять и изучать шаблоны, относящиеся только к объектам из обучающего набора, и не развивает в достаточной степени способность обобщать и эффективно использовать эти знания на еще не изученном объекте, который не использовался для обучения MLA.

Реализация "динамического бустинга" - одно дерево решений

[42] Как уже упоминалось ранее, в традиционных подходах к построению деревьев решений, после построения данного уровня данного дерева решений (или данного дерева целиком), MLA необходимо оценить результаты прогнозирования, которые завершенное к этому моменту дерево отображает для обучающих объектов, и далее оценить результат модели в каждом листе.

[43] Для этого, в обычных MLA, для каждого листа MLA принимает целевые значения (правильные ответы) обучающих объектов, которые попали в этот лист, и вычисляет среднее значение правильных прогнозов для этих целевых значений. Это среднее значение считается результатом текущей итерации дерева для каждого обучающего объекта, попавшего в этот лист. Таким образом, результат является одинаковым для всех обучающих объектов в данном листе (т.е. качество прогноза считается одинаковым для каждого обучающего объекта, который классифицирован в данный лист).

[44] Разработчики настоящей технологии предположили, что такой подход к созданию оценки прогнозирования модели дерева решений обладает недостатком. Когда MLA вычисляет оценку прогнозирования для данных обучающих объектов в листе на основе целевых значений всех обучающих объектов в листе, MLA в некотором смысле "подсматривает" в целевое значение обучающих объектов и целевые значения соседних обучающих объектов в листе (что можно рассматривать как "смотреть вперед"). Это может привести к тому, что переобучение в процессе обучения проявится раньше. Эта проблема также упоминается специалистами в данной области как "утечка данных" или "утечка информации".

[45] Разработчики настоящей технологии считают, что неограничивающие варианты осуществления настоящей технологии позволяют снизить эффект переобучения и повысить общее качество прогноза обученного MLA. Варианты осуществления настоящей технологии, в широком смысле, направлены на конкретную реализацию обучения MLA с использованием парадигмы "динамического бустинга".

[46] В соответствии с неограничивающими вариантами осуществления настоящей технологии, MLA сначала создает упорядоченный список всех обучающих объектов, которые предназначены для обработки во время этапа обучения MLA. В случае, если обучающие объекты обладают присущими им временными отношениями, MLA организует обучающие объекты в соответствии с этими временными отношениями. В случае если обучающие объекты не обладают присущими им временными отношениями, алгоритм машинного обучения создает упорядоченный список обучающих объектов на основе правила. Например, MLA может создавать случайный порядок обучающих объектов. Случайный порядок становится основой для временного порядка обучающих объектов, которые, в ином случае, не обладают никакими присущими им временными отношениями.

[47] Вне зависимости от того, как создается порядок, MLA далее "замораживает" обучающие объекты в таким образом организованном порядке. Таким образом организованный порядок, в некотором роде, может указывать для каждого обучающего объекта на то, какие другие обучающие объекты находятся "до" и какие находятся "после" (даже если обучающие объекты не связаны с присущими временными отношениями).

[48] Затем, когда MLA необходимо оценить качество прогноза с помощью данного обучающего объекта в листе, параметр качества прогноза определяется на основе целевых значений только тех обучающих объектов, которые "произошли" (или "находятся") перед данным обучающим объектом в упорядоченном списке обучающих объектов. Для создания временной аналогии, MLA использует только те обучающие объекты, которые произошли "раньше" по отношению к данным обучающим объектам. Таким образом, при определении параметра качества прогноза для данного обучающего объекта, MLA не "заглядывает" в будущее данного обучающего объекта (т.е. целевые значения тех обучающих объектов, которые находятся "в будущем" по отношению к данному обучающему объекту).

[49] Другими словами, MLA итеративно вычисляет факторы качества прогнозирования по мере того, как каждый новый обучающий объект классифицируется в данный лист, используя только те обучающие объекты, которые уже были классифицированы в данный лист (и которые находятся выше в упорядоченном списке обучающих объектов). MLA далее добавляет или усредняет все рассчитанные таким образом оценки прогноза для листа и, в конечном счете, для данного уровня дерева решений, используя все листы данного уровня дерева решений.

[50] Реализация "динамического бустинга" - несколько деревьев решений / ансамбль деревьев

[51] В альтернативных вариантах осуществления настоящей технологии, парадигма "динамического бустинга" применяется к нескольким деревьям решений / ансамблю деревьев решений. В частности, при реализации градиентного бустинга деревьев и построении ансамбля деревьев решений (каждое из которых построено на основе, в частности, результатов предыдущих деревьев с целью повышения качества прогнозирования предыдущих деревьев решений). В соответствии с неограничивающими вариантами осуществления настоящей технологии, MLA применяет подход "не смотреть вперед", как было описано выше в контексте построения одного дерева, к процессу построения нескольких деревьев решений, как части ансамбля во время способа с использованием бустинга.

[52] В общем, функции f(x) MLA для данного обучающего объекта х зависит не только от целевых значений обучающих объектов, которые предшествуют данному обучающему объекту в "хронологии" (порядке) и попадают в тот же лист, что и данный обучающий объект в текущем дереве, а также от аппроксимации (т.е. прогнозов) для обучающего объекта х, сделанных предыдущими деревьями решений. Эти прогнозы предыдущих итераций деревьев решений упоминаются здесь как "аппроксимации" или "параметр аппроксимации прогноза". Другими словами, аппроксимация для данного обучающего объекта х является прогнозом, сделанным ранее построенными деревьями, а также текущей итерацией дерева решений для данного обучающего объекта х.

[53] Поскольку на любой итерации построения деревьев решений в ансамбле деревьев решений обучающие объекты могут быть классифицированы в разные листьев, для любой данной итерации построения деревьев решений, аппроксимация данного обучающего объекта х вычисляется на основе другого набора "предыдущих обучающих объектов" - т.е. тех обучающих объектов, которые находятся раньше данного обучающего объекта в "хронологии" (порядке) и попадают в тот же лист, что и обучающий объект в предыдущем(их) дереве(ьях). Следовательно, для создания аппроксимаций для данного обучающего объекта х, MLA необходимо хранить указания на все предыдущие прогнозы и аппроксимации всех обучающих объектов, используя любую возможную комбинацию "предыдущих обучающих объектов".

[54] На Фиг. 1 представлена таблица 100, которая хранит результаты прогноза для каждого из обучающих объектов X. Таблица 100 сопоставляет данный обучающий объект 102 с его целевым значением 104 (т.е. фактическим значением цели, который MLA пытается предсказать) и соответственной аппроксимацией 106 (т.е. совокупностью прогнозов для обучающего объекта 102, сделанных на предыдущих итерациях деревьев решений).

[55] Также схематично представлен вектор 103 аппроксимации. Вектор 103 аппроксимации является вектором правильных ответов для всех представленных примерных объектов (от одного до тысячи на схеме, изображенной на Фиг. 1).

[56] Можно также сказать, что вектор 103 аппроксимации является вектором результатов прогнозирования модели прогнозирования, полностью выполняемой в текущий момент с помощью MLA. Другими словами, вектор 103 аппроксимации представляет собой результаты прогноза для всех обучающих объектов 102, полученных комбинацией деревьев решений, которые построены на текущем этапе бустинга деревьев решений MLA. В простейшей реализации неограничивающих вариантов настоящей технологии каждая аппроксимация вектора 103 аппроксимации является суммой предыдущих прогнозов для данного обучающего объекта 102.

[57] Когда MLA инициирует бустинг деревьев решений, вектор 103 аппроксимации содержит только нули (поскольку предыдущие итерации деревьев решений не были построены и, таким образом, предыдущие результаты прогнозов еще не доступны). По мере того, как MLA продолжает реализовывать бустинг (и, таким образом, строить дополнительные деревья решений в ансамбле деревьев решений), фокусируя внимание на моделях дерева, которые были "самыми слабыми моделями" в предыдущих итерациях деревьев решений, вектор 103 аппроксимации все больше и больше приближается к вектору целевых значений (не показано). Другими словами, задача MLA заключается в том, чтобы при выполнении бустинга максимально аппроксимировать целевые значения к фактическим значениям целей.

[58] Возвращаясь к примеру с обучающим объектом х в данном листе на данном этапе бустинга n, в соответствии с неограничивающими вариантами осуществления настоящей технологии, прогноз для обучающего объекта х (т.е. новая аппроксимация для этапа бустинга n), в данном новом дереве является функцией целевых значений, и аппроксимации обучающего(их) объекта(ов), который(е) (i) был(и) классифицирован(ы) (помещены) в один и тот же лист, что и обучающий объект х в новом дереве и (n) находится (находятся) до обучающего объекта х в упорядоченном списке обучающих объектов.

[59] К расчету аппроксимации может быть применена формула:

[60] где i=1…k - обучающий(е) объект(ы), который(е) (i) был(и) классифицирован(ы) (помещены) в один и тот же лист, что и обучающий объект х в новом дереве и (ii) находится (находятся) до обучающего объекта х в упорядоченном списке обучающих объектов.

[61] Разработчики обращают внимание по меньшей мере на одной техническую проблему, связанную с применением парадигмы "динамического бустинга" к расчету аппроксимаций при выполнении градиентного бустинга деревьев решений, на основе чего разработаны неограничивающие варианты осуществления настоящей технологии.

[62] Рассмотрим сценарий, в котором MLA во время выполнения способов бустинга деревьев решений необходимо вычислить результат прогноза для 1000-го обучающего объекта в новом дереве, построенном во время текущей итерации процедуры бустинга. Когда ML А вычисляет приближение для 1000-го обучающего объекта, если 3-ий обучающий объект попал в тот же лист, что и 1000-ый обучающий объект, ML А вычисляет результат прогноза для 1000-ого обучающего объекта с использованием аппроксимаций для 3-го обучающего объекта, т.е. прогноз, сделанный для 3-его обучающего объекта, созданного предыдущими деревьями. Однако аппроксимация для 3-го обучающего объекта рассчитывается с использованием "прошлого "не только 3-го обучающего объекта (т.е. 1-го и 2-го обучающих объектов), но и "прошлого" 1000-го обучающего объекта (т.е. всех обучающих объектов 1-1000).

[63] Таким образом, разработчики данной технологии обратили внимание на следующую проблему, связанную с использованием аппроксимаций из прошлых итераций деревьев решений. Для данного обучающего объекта в обучающем наборе размера N, MLA необходимо хранить N аппроксимаций для каждого данного обучающего объекта. Другими словами, для данного обучающего объекта (например, 3-го обучающего объекта), MLA необходимы аппроксимации, вычисленные с использованием прошлого 3-го обучающего объекта, а также "прошлое" 1-го, 2-го, 4-го … 1000-го обучающих объектов.

[64] Это приводит к усложнению алгоритма MLA и необходимости квадратичного увеличения вычислительных ресурсов. Другими словами, для системы MLA, использующей обучающие объекты из обучающего набора размера N, сложность систем MLA становится равной N.

[65] На Фиг. 2 представлена принципиальная схема корня / основания такого "квадратичного взрыва". На позиции 202 изображен упорядоченный список обучающих объектов. На позиции 204 изображены вычисленные аппроксимации для каждого из обучающих объектов 202. На позиции 208 изображен пример вычисления аппроксимации для 1000-го обучающего объекта на основании 3-го обучающего объекта (3-ий обучающий объект находится выше, чем 1000-ый объект в упорядоченном списке обучающих объектов, представленных на позиции 202, и классифицирован в тот же лист, что и 1000-ый объект на данной итерации бустинга деревьев решений в ансамбле деревьев решений.

[66] Для того, чтобы рассчитать приближение 1000-го обучающего объекта на основе 3-го обучающего объекта, MLA необходимо знать "прошлое" 3-го обучающего объекта на основе прошлого 1000-го обучающего объекта (показано на позиции 212). Это, в свою очередь, приводит к необходимости вычислять и/или хранить аппроксимации для всех обучающих объектов на основе всех других обучающих объектов - представленных схематически в виде матрицы 214.

[67] Разработчиками настоящей технологии разработаны некоторые описанные здесь неограничивающие варианты осуществления технологии для решения этой проблемы за счет снижения сложности (от квадратной сложности до линейной сложности) при сохранении на приемлемом уровне качества прогноза, полученного с помощью алгоритма MLA, который обучен с использованием обучающего набора размером N. Более конкретно, варианты настоящей технологии были разработаны на основе предпосылки о том, что MLA не нужно вычислять и хранить все потенциальные аппроксимации для каждого данного обучающего объекта, а только подмножество всех возможных аппроксимаций.

[68] В соответствии с неограничивающими вариантами осуществления настоящей технологии, MLA сначала разделяет упорядоченный список обучающих объектов на блоки. На Фиг. 3, ML А разбивает упорядоченный список обучающих объектов на множество блоков 301.

[69] Множество блоков 301 состоит из блоков нескольких уровней - блоки 302 первого уровня, блоки 304 второго уровня, блока 306 третьего уровня, блоки 308 четвертого уровня и т.д. В представленном варианте осуществления каждый уровень блоков (т.е. блоки 302 первого уровня, блоки 304 второго уровня, блока 306 третьего уровня, блоки 308 четвертого уровня) содержит два блока - первый блок и второй блок данного уровня. Естественно, что в любом данном варианте осуществления технологии из неограничивающих вариантов осуществления настоящей технологии количество уровней во множестве блоков 301 может быть разным.

[70] Каждый блок данного уровня блоков содержит определенное заранее определенное количество обучающих объектов. Исключительно в качестве примера, данный блок 310 первого уровня из блоков 302 первого уровня содержит 100 упорядоченных обучающих объектов. В изображенном примере блоки 302 первого уровня содержат два данных блока 310 первого уровня (содержащих 100 обучающих объектов каждый или 200 обучающих объектов суммарно).

[71] Данный блок 312 второго уровня из блоков 304 второго уровня содержит больше обучающих объектов, чем число обучающих объектов, содержащихся в данном блоке 310 первого уровня. В представленном варианте осуществления технологии, число обучающих объектов, хранящихся в данном блоке 312 второго уровня, в два раза превышает число обучающих объектов, хранящихся в данном блоке 310 первого уровня.

[72] В частности, если данный блок 310 первого уровня содержит 100 упорядоченных обучающих объектов, то данный блок 312 второго уровня содержит 200 упорядоченных обучающих объектов. Это, в свою очередь, означает, что данный блок 312 второго уровня (например, первый данный блок 312 второго уровня) может содержать те же упорядоченные обучающие объекты, что и два данных блока 310 первого уровня. Однако некоторые из блоков 312 второго уровня (например, второй блок 312 второго уровня) обладают упорядоченными обучающими объектами, которые не принадлежат ни к одному из блоков 310 первого уровня.

[73] Таким образом, можно сказать, что данный обучающий объект может присутствовать в нескольких блоках из множества 301 блоков. Например, 105-й обучающий объект располагается во: втором данном блоке 302 первого уровня, содержащем 100 упорядоченных обучающих объектов, первом данном блоке 312 второго уровня, содержащем 200 упорядоченных обучающих объектов, первом данном блоке третьего уровня (не пронумерован), содержащем 700 обучающих объектов, первом данном блоке четвертого уровня (не пронумерован), содержащем 800 обучающих объектов, и т.д. В качестве другого примера: 205-й обучающий объект расположен в: никаком из блоков 302 первого уровня, содержащих 100 упорядоченных обучающих объектов, втором данном блоке 312 второго уровня, содержащем 200 упорядоченных обучающих объектов, первом данном блоке третьего уровня (не пронумерован), содержащем 700 обучающих объектов, первом данном блоке четвертого уровня (не пронумерован), содержащем 800 обучающих объектов, и т.д.

[74] Таким образом, можно сказать, что аппроксимации обучающих объектов, расположенных, например, в первом данном блоке 312 второго уровня, содержащем 200 обучающих объектов, рассчитаны на основе всех обучающих объектов, расположенных в нем, и ни на одном из обучающих объектов, расположенных во втором данном блоке второго уровня (не пронумерован). Поэтому для обучающих объектов, расположенных в первом данном блоке 312 второго уровня, содержащем 200 обучающих объектов, используется "прошлое" всех обучающих объектов, расположенных в нем.

[75] Для иллюстрации рассмотрим 205-ый обучающий объект.MLA рассчитывает аппроксимации для 205-го обучающего объекта на основе тех блоков, где 205-ый обучающий объект расположен (и всех расположенных там обучающих объектов) -т.е. второго данного блока 312 второго уровня, содержащего 200 упорядоченных обучающих объектов, первого данного блока третьего уровня (не пронумерован), содержащего 700 обучающих объектов, первого данного блока четвертого уровня (не пронумерован), содержащего 800 обучающих объектов, и т.д. Когда MLA необходимо рассчитать аппроксимации для 407-го обучающего объекта на основе 205-го обучающего объекта, расположенного в том же листе, что и 407-ой обучающий объект (т.е. на основе "прошлого" 407-го обучающего объекта), MLA использует аппроксимации 205-го обучающего объекта на основе исключительно первого блока третьего уровня (не пронумерован), т.е. наибольшего блока, который не содержит "будущее" 407-го обучающего объекта.

[76] Другими словами, для вычисления значения прогноза для данного обучающего объекта, расположенного в данном листе, MLA использует аппроксимации "соседних" обучающих объектов (т.е. тех обучающих объектов, которые расположены в том же листе и расположены "раньше" в упорядоченном списке обучающих объектов). Аппроксимации соседних обучающих объектов принимаются исходя из наибольшего блока, который не содержит данный обучающий объект, другими словами, исходя из наибольшего куска, не содержащего данные о "будущем" данного обучающего объекта.

[77] В некоторых вариантах осуществления настоящей технологии, MLA может заранее организовать множество упорядоченных списков обучающих объектов, т.е. создавать различные "линии времени". В некоторых вариантах осуществления настоящей технологии, MLA создает заранее определенное количество упорядоченных списков, например, три (исключительно в качестве примера). Другими словами, MLA может создавать первый упорядоченный список обучающих объектов, второй упорядоченный список обучающих объектов и третий упорядоченный список обучающих объектов. Каждый из первого упорядоченного списка обучающих объектов, второго упорядоченного списка обучающих объектов и третьего упорядоченного списка обучающих объектов может обладать по меньшей мере частично отличающимися порядками обучающих объектов, указанными в нем.

[78] Далее, в процессе работы, для каждого прогноза MLA может использовать случайно выбранный из первого упорядоченного списка обучающих объектов, второго упорядоченного списка обучающих объектов и третьего упорядоченного списка обучающих объектов. В альтернативных вариантах осуществления настоящей технологии, MLA может использовать случайно взятый из первого упорядоченного списка обучающих объектов, второго упорядоченного списка обучающих объектов и третьего упорядоченного списка обучающих объектов для каждого дерева решений из ансамбля деревьев решений.

[79] Одиночное дерево решений

[80] Первым предметом настоящей технологии является способ определения параметра качества прогноза для дерева решений в прогностической модели дерева решений, причем данный уровень дерева решений обладает по меньшей мере одним узлом, причем параметр качества прогноза предназначен для оценки качества прогноза прогностической модели дерева решений на данной итерации обучения дерева решений. Способ выполняется системой машинного обучения, которая выполняет прогностическую модель дерева решений. Способ включает в себя: получение доступа со стороны постоянного машиночитаемого носителя системы машинного обучения, к набору обучающих объектов, причем каждый обучающий объект из набора обучающих объектов содержит указание на документ и целевое значение, связанное с документом, организацию набора обучающих объектов в упорядоченный список обучающих объектов, причем соответствующий упорядоченный список обучающих объектов организован таким образом, что для каждого обучающего объекта в упорядоченном списке обучающих объектов существует по меньшей мере одно из: (i) предыдущий обучающий объект, который находится до данного обучающего объекта и (ii) последующий обучающий объект, который находится после данного обучающего объекта; спуск набора обучающих объектов по дереву решений таким образом, что каждый из набора обучающих объектов классифицируется моделью дерева решений на данной итерации обучения в данный дочерний узел из по меньшей мере одного узла данного уровня дерева решений; создание параметра качества прогноза для дерева решений путем: создания для данного обучающего объекта, который классифицирован в данный дочерний узел, параметра качества прогноза, причем создание выполняется на основе целевых значений только тех обучающих объектов, которые находятся раньше обучающего объекта в упорядоченном списке обучающих объектов.

[81] В некоторых вариантах осуществления способа, способ далее включает в себя, для данного узла, обладающего по меньшей мере одним обучающим объектом, классифицированным в дочерний узел данного узла: объединение в параметр качества прогноза на уровне узла параметров качества прогноза по меньшей мере одного обучающего объекта.

[82] В некоторых вариантах осуществления способа, объединение в параметр качества прогноза на уровне узла параметров качества прогноза по меньшей мере одного обучающего объекта включает в себя одно из: добавление всех параметров качества прогноза по меньшей мере одного обучающего объекта, создание среднего значения параметров качества прогноза по меньшей мере одного обучающего объекта и применение формулы к параметрам качества прогноза по меньшей мере одного обучающего объекта.

[83] В некоторых вариантах осуществления способа, способ далее включает в себя: для данного уровня дерева решений, данный уровень обладает по меньшей мере одним узлом, объединение в общеуровневый параметр качества прогноза параметра качества прогноза уровня узла, параметров качества прогноза по меньшей мере одного узла.

[84] В некоторых вариантах осуществления способа, спуск включает в себя: спуск набора обучающих объектов по дереву решений в порядке обучающего объекта в упорядоченном списке обучающих объектов.

[85] В некоторых вариантах осуществления способа, создание параметра качества прогноза для данного обучающего объекта, обладающего данной позицией в упорядоченном списке обучающих объектов включает в себя: создание параметра качества прогноза на основе целевых значений только тех обучающих объектов, которые (i) находятся на позиции до данного обучающего объекта в упорядоченном списке обучающих объектов и (ii) классифицированы в один и тот же лист.

[86] В некоторых вариантах осуществления способа, организация набора обучающих объектов в упорядоченный список обучающих объектов включает в себя: создание множества упорядоченных списков обучающих объектов, причем каждый из множества упорядоченных списков обучающих объектов организован таким образом, что для каждого обучающего объекта в упорядоченном списке обучающих объектов существует по меньшей мере один из: (i) предыдущий обучающий объект, который находится до данного обучающего объекта и (ii) последующий обучающий объект, который находится после данного обучающего объекта; данный упорядоченный список из множества упорядоченных списков обучающих объектов обладает, по меньшей мере частично, отличающимся порядком от других упорядоченных списков во множестве упорядоченных списков обучающих объектов.

[87] В некоторых вариантах осуществления способа, способ далее включает в себя выбор одного из множества упорядоченных списков обучающих объектов.

[88] В некоторых вариантах осуществления способа, выбор осуществляется для каждой итерации создания параметра качества прогноза.

[89] В некоторых вариантах осуществления способа, выбор осуществляется в процессе проверки качества прогноза для данного дерева решений.

[90] В некоторых вариантах осуществления способа, набор обучающих объектов связан с присущими им временными отношениями обучающих объектов, и причем организация набора обучающих объектов в упорядоченный список обучающих объектов включает в себя организацию набора обучающих объектов в соответствии с временными отношениями.

[91] В некоторых вариантах осуществления способа, набор обучающих объектов не связан с присущими им временными отношениями обучающих объектов, и причем организация набора обучающих объектов в упорядоченный список обучающих объектов включает в себя организацию набора обучающих объектов в соответствии с правилом.

[92] В некоторых вариантах осуществления способа, набор обучающих объектов не связан с присущими им временными отношениями обучающих объектов, и причем организация набора обучающих объектов в упорядоченный список обучающих объектов включает в себя организацию набора обучающих объектов в соответствии со случайно созданным порядком.

[93] Ансамбль деревьев решений

[94] Другим объектом настоящей технологии является способ определения параметра качества прогноза для дерева решений в прогностической модели дерева решений, причем данный уровень дерева решений обладает по меньшей мере одним узлом, параметр качества прогноза предназначен для оценки качества прогноза прогностической модели дерева решений на данной итерации обучения дерева решений, причем данная итерация обучения дерева решений обладает по меньшей мере одной предыдущей итерацией обучения предыдущего дерева решений, дерево решений и предыдущее дерево решений образуют ансамбль деревьев, созданный с помощью техники бустинга деревьев решений. Способ выполняется системой машинного обучения, которая выполняет прогностическую модель дерева решений. Способ включает в себя: получение доступа со стороны постоянного машиночитаемого носителя системы машинного обучения, к набору обучающих объектов, причем каждый обучающий объект из набора обучающих объектов содержит указание на документ и целевое значение, связанное с документом, организацию набора обучающих объектов в упорядоченный список обучающих объектов, причем соответствующий упорядоченный список обучающих объектов организован таким образом, что для каждого обучающего объекта в упорядоченном списке обучающих объектов существует по меньшей мере одно из: (i) предыдущий обучающий объект, который находится до данного обучающего объекта и (ii) последующий обучающий объект, который находится после данного обучающего объекта; спуск набора обучающих объектов по дереву решений таким образом, что каждый из набора обучающих объектов классифицируется моделью дерева решений на данной итерации обучения в данный дочерний узел из по меньшей мере одного узла данного уровня дерева решений; создание параметра качества прогноза для дерева решений путем: создания для данного обучающего объекта, который классифицирован в данный дочерний узел, параметра аппроксимации качества прогноза, причем создание выполняется на основе: целевых значений только тех обучающих объектов, которые находятся раньше обучающего объекта в упорядоченном списке обучающих объектов; и по меньшей мере одного параметра аппроксимации качества прогноза данного обучающего объекта, созданного во время предыдущей итерации обучения предыдущего дерева решений.

[95] В некоторых вариантах осуществления способа, способ дополнительно включает в себя вычисление указания на по меньшей мере один параметр аппроксимации качества данного обучающего объекта, созданного во время предыдущей итерации обучения предыдущего дерева решений.

[96] В некоторых вариантах осуществления способа, вычисление включает в себя: разделение упорядоченного списка обучающих объектов на множество блоков, причем множество блоков организовано по меньшей мере в два уровня блоков.

[97] В некоторых вариантах осуществления способа, блок данного уровня блоков содержит первое заранее определенное число обучающих объектов, и причем блок более низкого уровня блоков содержит другое заранее определенное число обучающих объектов, другое заранее определенное число обучающих объектов превышает первое заранее определенное число обучающих объектов.

[98] В некоторых вариантах осуществления способа, блок данного уровня блоков содержит первое заранее определенное число обучающих объектов, и причем блок более низкого уровня блоков содержит первое заранее определенное число обучающих объектов и второй набор обучающих объектов, расположенный сразу после первого заранее определенного числа обучающих объектов в упорядоченном списке, причем число обучающих объектов во втором наборе обучающих объектов такое же что, что и первое заранее определенное число обучающих объектов.

[99] В некоторых вариантах осуществления способа, вычисление указания на по меньшей мере один параметр аппроксимации качества данного обучающего объекта, созданного во время предыдущей итерации обучения предыдущего дерева решений, включает в себя: для данного обучающего объекта вычисление по меньшей мере одного параметра аппроксимации качества на основе обучающих объектов, расположенных в том же блоке, что и данный обучающий объект.

[100] В некоторых вариантах осуществления способа, создание параметра качества прогноза для данного уровня дерева решений включает в себя: использование параметров аппроксимации качества прошлых обучающих объектов, расположенных в наибольшем блоке, который не содержит данный обучающий объект.

[101] В некоторых вариантах осуществления способа, организация набора обучающих объектов в упорядоченный список обучающих объектов включает в себя: создание множества упорядоченных списков обучающих объектов, причем каждый из множества упорядоченных списков обучающих объектов организован таким образом, что для каждого обучающего объекта в упорядоченном списке обучающих объектов существует по меньшей мере один из: (i) предыдущий обучающий объект, который находится до данного обучающего объекта и (ii) последующий обучающий объект, который находится после данного обучающего объекта; данный упорядоченный список из множества упорядоченных списков обучающих объектов обладает, по меньшей мере частично, отличающимся порядком от других упорядоченных списков во множестве упорядоченных списков обучающих объектов.

[102] В некоторых вариантах осуществления способа, способ далее включает в себя выбор одного из множества упорядоченных списков обучающих объектов.

[103] В некоторых вариантах осуществления способа, выбор осуществляется для каждой итерации создания параметра качества прогноза.

[104] В некоторых вариантах осуществления способа, выбор осуществляется в процессе проверки качества прогноза для данного дерева решений.

[105] В некоторых вариантах осуществления способа, набор обучающих объектов связан с присущими им временными отношениями обучающих объектов, и причем организация набора обучающих объектов в упорядоченный список обучающих объектов включает в себя организацию набора обучающих объектов в соответствии с временными отношениями.

[106] В некоторых вариантах осуществления способа, набор обучающих объектов не связан с присущими им временными отношениями обучающих объектов, и причем организация набора обучающих объектов в упорядоченный список обучающих объектов включает в себя организацию набора обучающих объектов в соответствии с правилом.

[107] В некоторых вариантах осуществления способа, набор обучающих объектов не связан с присущими им временными отношениями обучающих объектов, и причем организация набора обучающих объектов в упорядоченный список обучающих объектов включает в себя организацию набора обучающих объектов в соответствии со случайно созданным порядком.

[108] Системные пункты

[109] Еще одним объектом настоящей технологии является сервер, который выполнен с возможностью реализовать алгоритм машинного обучения (MLA), MLA основан на прогностической модели дерева решений на основе дерева решений, причем данный уровень дерева решений обладает по меньшей мере одним узлом. Сервер также выполнен с возможностью осуществлять: получение доступа со стороны постоянного машиночитаемого носителя сервера, к набору обучающих объектов, причем каждый обучающий объект из набора обучающих объектов содержит указание на документ и целевое значение, связанное с документом, организацию набора обучающих объектов в упорядоченный список обучающих объектов, причем соответствующий упорядоченный список обучающих объектов организован таким образом, что для каждого обучающего объекта в упорядоченном списке обучающих объектов существует по меньшей мере одно из: (i) предыдущий обучающий объект, который находится до данного обучающего объекта и (ii) последующий обучающий объект, который находится после данного обучающего объекта; спуск набора обучающих объектов по дереву решений таким образом, что каждый из набора обучающих объектов классифицируется прогностической моделью дерева решений на данной итерации обучения в данный дочерний узел из по меньшей мере одного узла данного уровня дерева решений; создание параметра качества прогноза для данного уровня дерева решений, причем параметр качества прогноза предназначен для оценки качества прогноза прогностической модели дерева решений на данной итерации обучения дерева решений, путем: создания для данного обучающего объекта, который классифицирован в данный дочерний узел, параметра качества прогноза, причем создание выполняется на основе целевых значений только тех обучающих объектов, которые находятся раньше обучающего объекта в упорядоченном списке обучающих объектов.

[110] Еще одним объектом настоящей технологии является сервер, который выполнен с возможностью реализовать алгоритм машинного обучения (MLA), MLA основан на прогностической модели дерева решений на основе дерева решений, причем данный уровень дерева решений обладает по меньшей мере одним узлом. Сервер выполнен с возможностью осуществлять: получение доступа со стороны постоянного машиночитаемого носителя системы машинного обучения, к набору обучающих объектов, причем каждый обучающий объект из набора обучающих объектов содержит указание на документ и целевое значение, связанное с документом, организацию набора обучающих объектов в упорядоченный список обучающих объектов, причем соответствующий упорядоченный список обучающих объектов организован таким образом, что для каждого обучающего объекта в упорядоченном списке обучающих объектов существует по меньшей мере одно из: (i) предыдущий обучающий объект, который находится до данного обучающего объекта и (ii) последующий обучающий объект, который находится после данного обучающего объекта; спуск набора обучающих объектов по дереву решений таким образом, что каждый из набора обучающих объектов классифицируется моделью дерева решений на данной итерации обучения в данный дочерний узел из по меньшей мере одного узла данного уровня дерева решений; создание параметра качества прогноза для данного уровня дерева решений, причем параметр качества прогноза предназначен для оценки качества прогноза прогностической модели дерева решений на данной итерации обучения дерева решений, причем данная итерация обучения дерева решений обладает по меньшей мере одной предыдущей итерацией обучения предыдущего дерева решений, причем дерево решений и предыдущее дерево решений образуют ансамбль деревьев, созданных с помощью способа градиентного бустинга деревьев решений, путем: создания для данного обучающего объекта, который классифицирован в данный дочерний узел, параметра аппроксимации качества прогноза, причем создание выполняется на основе: целевых значений только тех обучающих объектов, которые находятся раньше обучающего объекта в упорядоченном списке обучающих объектов; и по меньшей мере одного параметра аппроксимации качества прогноза данного обучающего объекта, созданного во время предыдущей итерации обучения предыдущего дерева решений.

[111] Еще одним объектом настоящей технологии является способ определения параметра качества прогноза прогностической модели дерева решений, причем данный уровень дерева решений обладает по меньшей мере одним узлом, параметр качества прогноза предназначен для оценки качества прогноза прогностической модели дерева решений на данной итерации обучения дерева решений, причем данная итерация обучения дерева решений обладает по меньшей мере одной предыдущей итерацией обучения предыдущего дерева решений, дерево решений и предыдущее дерево решений образуют ансамбль деревьев, созданный с помощью техники бустинга деревьев решений. Способ выполняется системой машинного обучения, которая выполняет прогностическую модель дерева решений. Способ включает в себя: получение доступа со стороны постоянного машиночитаемого носителя системы машинного обучения, к набору обучающих объектов, причем каждый обучающий объект из набора обучающих объектов содержит указание на документ и целевое значение, связанное с документом, организацию набора обучающих объектов в упорядоченный список обучающих объектов, причем соответствующий упорядоченный список обучающих объектов организован таким образом, что для каждого обучающего объекта в упорядоченном списке обучающих объектов существует по меньшей мере одно из: (i) предыдущий обучающий объект, который находится до данного обучающего объекта и (ii) последующий обучающий объект, который находится после данного обучающего объекта; спуск набора обучающих объектов по дереву решений таким образом, что каждый из набора обучающих объектов классифицируется моделью дерева решений на данной итерации обучения в данный дочерний узел из по меньшей мере одного узла данного уровня дерева решений; создание параметра качества прогноза для дерева решений путем: создания для данного обучающего объекта, который классифицирован в данный дочерний узел, параметра аппроксимации качества прогноза, причем создание выполняется на основе: целевых значений только тех обучающих объектов, которые находятся раньше обучающего объекта в упорядоченном списке обучающих объектов; и по меньшей мере одного параметра аппроксимации качества прогноза данного обучающего объекта, созданного во время предыдущей итерации обучения предыдущего дерева решений; вычисление указания по меньшей мере на один параметр аппроксимации качества данного обучающего объекта, созданного во время предыдущей итерации обучения предыдущего дерева решений, путем разделения упорядоченного списка обучающих объектов на множества блоков, причем множества блоков организовано по меньшей мере в два уровня блоков.

[112] Настоящая технология, таким образом, приводит, среди прочих преимуществ, к более точному прогнозированию модели машинного обучения, позволяя компьютерной системе (1) более эффективно расходовать вычислительную мощность; и (2) предоставлять конечному пользователю более релевантные прогнозы.

[113] В контексте настоящего описания, если четко не указано иное, "электронное устройство", "пользовательское устройство", "сервер", "удаленный сервер" и "компьютерная система" подразумевают под собой аппаратное и/или системное обеспечение, подходящее к решению соответствующей задачи. Таким образом, некоторые неограничивающие примеры аппаратного и/или программного обеспечения включают в себя компьютеры (серверы, настольные компьютеры, ноутбуки, нетбуки и так далее), смартфоны, планшеты, сетевое оборудование (маршрутизаторы, коммутаторы, шлюзы и так далее) и/или их комбинацию.

[114] В контексте настоящего описания, если четко не указано иное, «машиночитаемый носитель» и «память» подразумевает под собой носитель абсолютно любого типа и характера, и примеры, не ограничивающие настоящую технологию, включают в себя ОЗУ, ПЗУ, диски (компакт диски, DVD-диски, дискеты, жесткие диски и т.д.), USB-ключи, флеш-карты, твердотельные накопители и накопители на магнитной ленте.

[115] В контексте настоящего описания, если четко не указано иное, «указание» информационного элемента может представлять собой сам информационный элемент или указатель, отсылку, ссылку или другой косвенный способ, позволяющий получателю указания найти сеть, память, базу данных или другой машиночитаемый носитель, из которого может быть извлечен информационный элемент. Например, указание на документ может включать в себя сам документ (т.е. его содержимое), или же оно может являться уникальным дескриптором документа, идентифицирующим файл по отношению к конкретной файловой системе, или каким-то другими средствами передавать получателю указание на сетевую папку, адрес памяти, таблицу в базе данных или другое место, в котором можно получить доступ к файлу. Как будет понятно специалистам в данной области техники, степень точности, необходимая для такого указания, зависит от степени первичного понимания того, как должна быть интерпретирована информация, которой обмениваются получатель и отправитель указателя. Например, если до установления связи между отправителем и получателем понятно, что признак информационного элемента принимает вид ключа базы данных для записи в конкретной таблице заранее установленной базы данных, содержащей информационный элемент, то передача ключа базы данных - это все, что необходимо для эффективной передачи информационного элемента получателю, несмотря на то, что сам по себе информационный элемент не передавался между отправителем и получателем указания.

[116] В контексте настоящего описания, если конкретно не указано иное, слова «первый», «второй», «третий» и и т.д. используются в виде прилагательных исключительно для того, чтобы отличать существительные, к которым они относятся, друг от друга, а не для целей описания какой-либо конкретной взаимосвязи между этими существительными. Так, например, следует иметь в виду, что использование терминов «первый сервер» и «третий сервер» не подразумевает какого-либо порядка, отнесения к определенному типу, хронологии, иерархии или ранжирования (например) серверов/между серверами, равно как и их использование (само по себе) не предполагает, что некий "второй сервер" обязательно должен существовать в той или иной ситуации. В дальнейшем, как указано здесь в других контекстах, упоминание «первого» элемента и «второго» элемента не исключает возможности того, что это один и тот же фактический реальный элемент. Так, например, в некоторых случаях, «первый» сервер и «второй» сервер могут являться одним и тем же программным и/или аппаратным обеспечением, а в других случаях они могут являться разным программным и/или аппаратным обеспечением.

[117] Каждый вариант осуществления настоящей технологии преследует по меньшей мере одну из вышеупомянутых целей и/или объектов, но наличие всех не является обязательным. Следует иметь в виду, что некоторые объекты данной технологии, полученные в результате попыток достичь вышеупомянутой цели, могут не удовлетворять этой цели и/или могут удовлетворять другим целям, отдельно не указанным здесь. Дополнительные и/или альтернативные характеристики, аспекты и преимущества вариантов осуществления настоящей технологии станут очевидными из последующего описания, прилагаемых чертежей и прилагаемой формулы изобретения.

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

[118] Для лучшего понимания настоящей технологии, а также других ее аспектов и характерных черт, сделана ссылка на следующее описание, которое должно использоваться в сочетании с прилагаемыми чертежами, где:

[119] На Фиг. 1 представлена таблица, в которой хранятся результаты прогноза для каждого из обучающих объектов х, используемых для создания и/или проверки деревьев решений модели дерева решений, используемой алгоритмом машинного обучения в соответствии с неограничивающими вариантами осуществления настоящей технологии.

[120] На Фиг. 2 представлена схема "квадратичного взрыва", который может возникнуть при вычислении аппроксимаций для деревьев решений во время бустинга деревьев решений.

[121] На Фиг. 3 представлен упорядоченный список обучающих объектов, созданный MLA в соответствии с неограничивающими вариантами осуществления настоящей технологии.

[122] На Фиг. 4 представлена диаграмма компьютерной системы, которая подходит для реализации настоящей технологии, и/или которая используется в сочетании с вариантами осуществления настоящей технологи.

[123] На Фиг. 5 представлена схема сетевой вычислительной среды в соответствии с вариантом осуществления настоящей технологии;

[124] На Фиг. 6 представлена схема, показывающая древовидную модель частично, и два примера векторов признаков в соответствии с вариантом осуществления настоящей технологии.

[125] На Фиг. 7 представлена схема полной древовидной модели в соответствии с вариантом осуществления настоящей технологии.

[126] На Фиг. 8 представлена схема, показывающая части предварительной древовидной модели и полную предварительную древовидную модель в соответствии с вариантом осуществления настоящей технологии.

[127] На Фиг. 9 представлена схема, показывающая части предварительной древовидной модели в соответствии с другим вариантом осуществления настоящей технологии.

[128] На Фиг. 10 представлена схема полной предварительной древовидной модели в соответствии с другим вариантом осуществления настоящей технологии.

[129] На Фиг. 11 представлена схема части прото-дерева с одним узлом первого уровня и двумя узлами второго уровня, а также упорядоченный список обучающих объектов, созданные в соответствии с другими вариантами осуществления настоящей технологии.

[130] На Фиг. 12 представлена схема, показывающая первый компьютерный способ, являющийся вариантом осуществления настоящей технологии;

[131] На Фиг. 13 представлена схема, показывающая второй компьютерный способ, являющийся вариантом осуществления настоящей технологии.

[132] Также следует отметить, что чертежи выполнены не в масштабе, если не специально указано иное.

[133] В конце настоящего описания предусмотрено приложение А. Приложение А включает в себя копию еще не опубликованной статьи под заголовком "CatBoost: градиентный бустинг с использованием категориальных факторов". Статья предоставляет дополнительную информацию об известном уровне техники, описание реализации неограничивающих вариантов осуществления настоящей технологии, а также некоторые дополнительные примеры. Эта статья включена здесь в полном объеме посредством ссылки для всех юрисдикции, допускающих включение в описание сведений посредством ссылки.

ОСУЩЕСТВЛЕНИЕ

[134] Все примеры и используемые здесь условные конструкции предназначены, главным образом, для того, чтобы помочь читателю понять принципы настоящей технологии, а не для установления границ ее объема. Следует также отметить, что специалисты в данной области техники могут разработать различные схемы, отдельно не описанные и не показанные здесь, но которые, тем не менее, воплощают собой принципы настоящей технологии и находятся в границах ее объема.

[135] Кроме того, для ясности в понимании, следующее описание касается достаточно упрощенных вариантов осуществления настоящей технологии. Как будет понятно специалисту в данной области техники, многие варианты осуществления настоящей технологии будут обладать гораздо большей сложностью.

[136] Некоторые полезные примеры модификаций настоящей технологии также могут быть охвачены нижеследующим описанием. Целью этого является также исключительно помощь в понимании, а не определение объема и границ настоящей технологии. Эти модификации не представляют собой исчерпывающего списка, и специалисты в данной области техники могут создавать другие модификации, остающиеся в границах объема настоящей технологии. Кроме того, те случаи, где не были представлены примеры модификаций, не должны интерпретироваться как то, что никакие модификации невозможны, и/или что то, что было описано, является единственным вариантом осуществления этого элемента настоящей технологии.

[137] Более того, все заявленные здесь принципы, аспекты и варианты осуществления настоящей технологии, равно как и конкретные их примеры, предназначены для обозначения их структурных и функциональных основ, вне зависимости от того, известны ли они на данный момент или будут разработаны в будущем. Таким образом, например, специалистами в данной области техники будет очевидно, что представленные здесь блок-схемы представляют собой концептуальные иллюстративные схемы, отражающие принципы настоящей технологии. Аналогично, любые блок-схемы, диаграммы, псевдокоды и т.п.представляют собой различные процессы, которые могут быть представлены на машиночитаемом носителе и, таким образом, использоваться компьютером или процессором, вне зависимости от того, показан явно подобный компьютер или процессор, или нет.

[138] Функции различных элементов, показанных на чертежах, включая функциональный блок, обозначенный как «процессор» или «графический процессор», могут быть обеспечены с помощью специализированного аппаратного обеспечения или же аппаратного обеспечения, способного использовать подходящее программное обеспечение. Когда речь идет о процессоре, функции могут обеспечиваться одним специализированным процессором, одним общим процессором или множеством индивидуальных процессоров, причем некоторые из них могут являться общими. В некоторых вариантах осуществления настоящей технологии, процессор может являться универсальным процессором, например, центральным процессором (CPU) или специализированным для конкретной цели процессором, например, графическим процессором (GPU). Более того, использование термина «процессор» или «контроллер» не должно подразумевать исключительно аппаратное обеспечение, способное поддерживать работу программного обеспечения, и может включать в себя, без установления ограничений, цифровой сигнальный процессор (DSP), сетевой процессор, интегральную схему специального назначения (ASIC), программируемую пользователем вентильную матрицу (FPGA), постоянное запоминающее устройство (ПЗУ) для хранения программного обеспечения, оперативное запоминающее устройство (ОЗУ) и энергонезависимое запоминающее устройство. Также в это может быть включено другое аппаратное обеспечение, обычное и/или специальное.

[139] Программные модули или простые модули, представляющие собой программное обеспечение, могут быть использованы здесь в комбинации с элементами блок-схемы или другими элементами, которые указывают на выполнение этапов процесса и/или текстовое описание. Подобные модели могут быть выполнены на аппаратном обеспечении, показанном напрямую или косвенно.

[140] С учетом этих примечаний, далее будут рассмотрены некоторые не ограничивающие варианты осуществления аспектов настоящей технологии.

[141] На Фиг. 4 представлена схема компьютерной системы 400, которая подходит для некоторых вариантов осуществления настоящей технологии, причем компьютерная система 400 включает в себя различные аппаратные компоненты, включая один или несколько одно- или многоядерных процессоров, которые представлены процессором 410, графическим процессором (GPU) 411, твердотельным накопителем 420, ОЗУ 430, интерфейсом 440 монитора, и интерфейсом 450 ввода/вывода.

[142] Связь между различными компонентами компьютерной системы 400 может осуществляться с помощью одной или нескольких внутренних и/или внешних шин 460 (например, шины PCI, универсальной последовательной шины, высокоскоростной шины IEEE 1394, шины SCSI, шины Serial ATA и так далее), с которыми электронными средствами соединены различные аппаратные компоненты. Интерфейс 440 монитора может быть соединен с монитором 442 (например, через HDMI-кабель 144), видимым пользователю 470, интерфейс 450 ввода/вывода может быть соединен с сенсорным экраном (не изображен), клавиатурой 451 (например, через USB-кабель 453) и мышью 452 (например, через USB-кабель 454), причем как клавиатура 451, так и мышь 452 используются пользователем 470.

[143] В соответствии с вариантами осуществления настоящей технологии твердотельный накопитель 420 хранит программные инструкции, подходящие для загрузки в ОЗУ 130, и использующиеся процессором 410 и/или графическим процессором GPU 411 для обработки показателей активности, связанных с пользователем. Например, программные команды могут представлять собой часть библиотеки или приложение.

[144] На Фиг. 5 показана сетевая компьютерная среда 500, подходящая для использования с некоторыми вариантами осуществления настоящей технологии, причем сетевая компьютерная среда 500 включает в себя ведущий сервер 510, обменивающийся данными с первым ведомым сервером 520, вторым ведомым сервером 522 и третьим ведомым сервером 524 (также здесь и далее упоминаемыми как ведомые серверы 520, 522, 524) по сети (не изображена), предоставляя этим системам возможность обмениваться данными. В некоторых вариантах осуществления настоящей технологии, не ограничивающих ее объем, сеть может представлять собой интернет. В других вариантах осуществления настоящей технологии сеть может быть реализована иначе - в виде глобальной сети передачи данных, локальной сети передачи данных, частной сети передачи данных и т.п.

[145] Сетевая компьютерная среда 500 может включать в себя большее или меньшее количество ведомых серверов, что не выходит за границы настоящей технологии. В некоторых вариантах осуществления настоящей технологии конфигурация "ведущий сервер - ведомый сервер" может не быть необходима, может быть достаточно одиночного сервера. Следовательно, число серверов и тип архитектуры не является ограничением объема настоящей технологии. Архитектура ведущий сервер - ведомый сервер, которая представлена на Фиг. 5, является частично полезной (но не ограничивающей) в тех случаях, когда желательна параллельная обработка всех или некоторых процедур, которые будут описаны далее.

[146] В одном варианте осуществления настоящей технологии между ведущим сервером 510 и ведомыми серверами 520, 522, 524 может быть установлен канал передачи данных (не показан), чтобы обеспечить возможность обмена данными. Такой обмен данными может происходить на постоянной основе или же, альтернативно, при наступлении конкретных событий. Например, в контексте сбора данных с веб-страниц и/или обработки поисковых запросов обмен данными может возникнуть в результате контроля ведущим сервером 510 обучения моделей машинного обучения, осуществляемого сетевой компьютерной средой.

[147] В некоторых вариантах осуществления настоящей технологии ведущий сервер 510 может получить набор обучающих объектов и/или набор тестирующих объектов и/или набор факторов от внешнего сервера поисковой системы (не изображен) и отправить набор обучающих объектов и/или набор тестирующих объектов и/или набор факторов одному или нескольким ведомым серверам 520, 522, 524. После получения от ведущего сервера 510, один или несколько ведомых серверов 520, 522, 524 могут обработать набор обучающих объектов и/или набор тестирующих объектов и/или набор факторов в соответствии с неограничивающими вариантами осуществления настоящей технологией для создания одной или нескольких моделей машинного обучения, причем каждая модель машинного обучения включает в себя в некоторых случаях одну или несколько древовидных моделей. В некоторых вариантах осуществления настоящей технологии одна или несколько древовидных моделей моделируют связь между документом и целевым значением (им может быть параметр интереса, оценка релевантности и т.д.).

[148] Созданная модель машинного обучения может быть передана ведущему серверу 510 и, таким образом, ведущий сервер 510 может создать прогноз, например, в контексте поискового запроса, полученного от внешнего сервера поисковой системы, на основе поискового запроса, полученного от электронного устройства, связанного с пользователем, который хочет использовать компьютерный поиск. После применения созданной модели машинного обучения к поисковому запросу, ведущий сервер 510 может передать один или несколько соответствующих результатов внешнему серверу поисковой системы. В некоторых альтернативных вариантах осуществления настоящей технологии один или несколько ведомых серверов 520, 522, 524 могут напрямую сохранять созданную модель машинного обучения и обрабатывать поисковый запрос, полученный от внешнего сервера поисковой системы через ведущий сервер 510 или напрямую от внешней поисковой системы.

[149] Ведущий сервер 510 может быть выполнен как обычный компьютерный сервер и может включать в себя некоторые или все характеристики компьютерной системы 400, изображенной на Фиг. 4. В примере варианта осуществления настоящей технологии ведущий сервер 510 может представлять собой сервер Dell™ PowerEdge™, на котором используется операционная система Microsoft™ Windows Server™. Излишне говорить, что ведущий сервер 510 может представлять собой любое другое подходящее аппаратное и/или прикладное программное, и/или системное программное обеспечение или их комбинацию. В представленном варианте осуществления настоящей технологии, не ограничивающем ее объем, ведущий сервер 510 является одиночным сервером. В других вариантах осуществления настоящей технологии, не ограничивающих ее объем, функциональность ведущего сервера 210 может быть разделена, и может выполняться с помощью нескольких серверов.

[150] Варианты осуществления ведущего сервера 510 широко известны среди специалистов в данной области техники. Тем не менее, для краткой справки: ведущий сервер 510 включает в себя интерфейс передачи данных (не показан), который настроен и выполнен с возможностью устанавливать соединение с различными элементами (например, с внешним сервером поисковой системы и/или ведомыми серверами 520, 522, 524 и другими устройствами, потенциально соединенными с сетью) по сети. Ведущий сервер 510 дополнительно включает в себя по меньшей мере один компьютерный процессор (например, процессор 410 ведущего сервера 510), функционально соединенный с интерфейсом передачи данных и настроенный и выполненный с возможностью выполнять различные процессы, описанные здесь.

[151] Основной задачей ведущего сервера 510 является координация создания моделей машинного обучения ведомыми серверами 520, 522, 524. Как было описано ранее, в одном варианте осуществления настоящей технологии набор обучающих объектов и/или набор тестирующих объектов и/или набор факторов может быть передан некоторым или всем ведомым серверам 520, 522, 524, и таким образом, ведомые серверы 520, 522, 524 могут создавать одну или несколько моделей машинного обучения на основе набора обучающих объектов и/или набора тестирующих объектов и/или набора факторов. В некоторых вариантах осуществления настоящей технологии, модель машинного обучения может включать в себя одну или несколько древовидных моделей. Каждая из древовидных моделей может быть сохранена на одном или нескольких ведомых серверах 520, 522, 524. В некоторых альтернативных вариантах осуществления настоящей технологии древовидные модели могут быть сохранены по меньшей мере на двух серверах из ведомых серверов 520, 522, 524. Как будет понятно специалистам в данной области техники, то, где сохраняются модель машинного обучения и/или древовидные модели, формирующие модель машинного обучения, не является важным для настоящей технологии, и может быть предусмотрено множество вариантов без отклонения от объема настоящей технологии.

[152] В некоторых вариантах осуществления настоящей технологии после того, как ведомые серверы 520, 522, 224 сохранили одну или несколько моделей машинного обучения, ведомые серверы 520, 522, 524 могут получить инструкции на проведение связей между документом и целевым значением, причем документ отличается от обучающих объектов из набора обучающих объектов и включает в себя набор факторов, соответствующих значениям, связанным с некоторыми факторами, выбранными из набора факторов, определяющих структуру по меньшей мере одной древовидной модели.

[153] Как только связывание между документом и целевым значением было завершено ведомыми серверами 520, 522, 524, ведущий сервер 510 может получить от ведомых серверов 520, 522, 524 целевое значение, которое должно быть связано с документом. В некоторых других вариантах осуществления настоящей технологии ведущий сервер 510 может отправлять документ и/или набор факторов, связанный с документом, не получая целевого значения в ответ. Этот сценарий может возникнуть после определения одним или несколькими ведомыми серверами 520, 522, 524 того, что документ и/или набор факторов, связанный с документом, приводят к модификации одной из древовидных моделей, хранящихся на ведомых серверах 520, 522, 524.

[154] В некоторых вариантах осуществления настоящей технологии ведущий сервер 510 может включать в себя алгоритм, который может создавать инструкции для модификации одной или нескольких моделей, хранящихся на ведомых серверах 520, 522, 524, с целевым значением для связи с документом. В таких примерах одна из древовидных моделей, хранящаяся на ведомых серверах 520, 522, 524, может быть модифицирована таким образом, что документ может быть связан с целевым значением в древовидной модели. В некоторых вариантах осуществления настоящей технологии после того, как одна из древовидных моделей, хранящаяся на ведомых серверах 520, 522, 524, была модифицирована, ведомые серверы 520, 522, 524 могут передать сообщение ведущему серверу 510, причем сообщение указывает на модификацию, осуществленную в одной из древовидных моделей. Могут быть предусмотрены другие варианты того, как ведущий сервер 510 взаимодействует с ведомыми серверами 520, 522, 524 что не выходит за границы настоящей технологии и может быть очевидным специалисту в данной области техники. Кроме того, важно иметь в виду, что для упрощения вышеприведенного описания конфигурация ведущего сервера 510 была сильно упрощена. Считается, что специалисты в данной области техники смогут понять подробности реализации ведущего сервера 510 и его компонентов, которые могли быть опущены в описании с целью упрощения.

[155] Ведомые серверы 520, 522, 524 могут быть выполнены как обычные компьютерные серверы и могут включать в себя некоторые или все характеристики компьютерной системы 400, изображенной на Фиг. 4. В примере варианта осуществления настоящей технологии ведомые серверы 520, 522, 524 могут представлять собой серверы Dell™ PowerEdge™, на которых используется операционная система Microsoft™ Windows Server™. Излишне говорить, что ведомые серверы 520, 522, 524 могут представлять собой любое другое подходящее аппаратное и/или прикладное программное, и/или системное программное обеспечение или их комбинацию. В представленном варианте осуществления настоящей технологии, не ограничивающем ее объем, ведомые серверы 520, 522, 524 функционируют на основе распределенной архитектуры. В альтернативных вариантах настоящей технологии, не ограничивающих ее объем, настоящую технологию может выполнять единственный ведомый сервер.

[156] Варианты осуществления ведомых серверов 520, 522, 524 широко известны среди специалистов в данной области техники. Тем не менее, для краткой справки: каждый из ведомых серверов 520, 522, 524 может включать в себя интерфейс передачи данных (не показан), который настроен и выполнен с возможностью устанавливать соединение с различными элементами (например, в внешним сервером поисковой системы и/или ведущим сервером 510 и другими устройствами, потенциально соединенные с сетью) по сети. Каждый из ведомых серверов 520, 522, 524 дополнительно включает в себя один или несколько пунктов из следующего: компьютерный процессор (например, аналогично процессору 410 на Фиг. 4), функционально соединенный с интерфейсом связи и настроенный и выполненный с возможностью выполнять различные процессы, описанные здесь. Каждый из ведомых серверов 520, 522, 524 дополнительно может включать в себя одно или несколько устройств памяти (например, аналогичных твердотельному накопителю 420, и/или ОЗУ 430, изображенным на Фиг. 4).

[157] Общей задачей ведомых серверов 520, 522, 524 является создание одной или нескольких моделей машинного обучения. Как было описано ранее, в одном варианте осуществления настоящей технологии, модель машинного обучения может включать в себя одну или несколько древовидных моделей. Каждая из древовидных моделей включает в себя набор факторов (которые также могут упоминаться как подгруппа факторов, если факторы, образующие подгруппу, были выбраны из набора факторов). Каждый фактор из набора факторов соответствует одному или нескольким узлам соответствующей древовидной модели.

[158] Во время создания одной или нескольких моделей машинного обучения для выбора и упорядочивания факторов таким образом, чтобы создать древовидную модель, ведомые серверы 520, 522, 524 могут исходить из набора обучающих объектов и/или набора тестирующих объектов. Этот процесс выбора и упорядочивания факторов может быть повторен с помощью многочисленных итераций таким образом, что ведомые серверы 520, 522, 524 создают множество древовидных моделей, причем каждая из древовидных моделей соответствует различным выборам и/или порядкам (после упорядочивания) факторов. В некоторых вариантах осуществления настоящей технологии набор обучающих объектов и/или набор тестирующих объектов и/или набор факторов может быть получен от ведущего сервера 510 и/или внешнего сервера. После создания моделей машинного обучения ведомые серверы 520, 522, 524 могут передать ведомому серверу 510 указание на то, что модели машинного обучения были созданы и могут использоваться для создания прогнозов, например (но не вводя ограничений) в контексте классификации документов во время процесса сбора данных в сети («веб-кроулинга») и/или после обработки поискового запроса, полученного от внешнего сервера поисковой системы и/или для создания персонализированных рекомендаций содержимого.

[159] В некоторых вариантах осуществления настоящей технологии ведомые серверы 520, 522, 524 могут также получать документ и набор факторов, связанных с документом, вместе с целевым значением, которое надлежит связать с документом. В некоторых других вариантах осуществления настоящей технологии ведомые серверы 520, 522, 524 могут не передавать никакого целевого значения ведущему серверу 510. Этот сценарий может возникнуть после определения ведомыми серверами 520, 522, 524 того, что целевое значение, которое надлежит связать с документом, что приводит к модификации одной из древовидных моделей, хранящихся на этих серверах.

[160] В некоторых вариантах осуществления настоящей технологии после того, как одна из древовидных моделей, хранящаяся на ведомых серверах 520, 522, 524, была модифицирована, ведомые серверы 520, 522, 524 могут передать сообщение ведущему серверу 510, причем сообщение указывает на модификацию, осуществленную в одной из древовидных моделей. Могут быть предусмотрены другие варианты того, как ведомые серверы 520, 522, 524 взаимодействует с ведущим сервером 510, что не выходит за границы настоящей технологии и может быть очевидным специалисту в данной области техники. Кроме того, важно иметь в виду, что для упрощения вышеприведенного описания конфигурация ведомых серверов 520, 522, 524 была сильно упрощена. Считается, что специалисты в данной области техники смогут понять подробности реализации ведомых серверов 520, 522, 524 и его компонентов, которые могли быть опущены в описании с целью упрощения.

[161] На Фиг. 5 показано, что ведомые серверы 520, 522, 524 могут быть функционально соединены соответственно с базой данных 530 «хэш-таблицы 1», базой данных 532 «хэш-таблицы 2» и базой данных 534 «хэш-таблицы n» (здесь и далее упоминаемых как «базы данных 530, 532, 534»). Базы данных 530, 532, 534 могут быть частью ведомых серверов 520, 522, 524 (например, они могут быть сохранены в устройствах памяти ведомых серверов 520, 522, 524, таких как твердотельный накопитель 420 и/или ОЗУ 430) или могут быть сохранены на отдельных серверах баз данных. В некоторых вариантах осуществления настоящей технологии может быть достаточно единственной базы данных, доступной ведомым серверам 520, 522, 524. Следовательно, число баз данных и организация баз данных 530, 532, 534 не является ограничением объема настоящей технологии. Базы данных 530, 532, 534 могут быть использованы для доступа и/или хранения данных, относящихся к одной или нескольким хэш-таблицам, представляющим модели машинного обучения, например (но без введения ограничений) древовидные модели, созданные в соответствии с настоящей технологией.

[162] В некоторых вариантах осуществления настоящей технологии, каждая из баз 530, 532, 534 данных хранит тот же набор информации (т.е. ту же информацию, которая хранится во всех базах 530, 532, 534 данных). Например, каждая из баз 530, 532, 534 данных может хранить один и тот же набор обучающих объектов. Это особенно полезно (без установления ограничений) в тех вариантах осуществления настоящей технологии, где структура ведущего сервера 510 и/или ведомых серверов 520, 522, 524 используется для параллельной обработки и создания деревьев решений. В данном случае, каждая из баз 520, 522, 524 данных обладает доступом к одному и тому же набору обучающих объектов.

[163] В некоторых вариантах осуществления настоящей технологии ведомые серверы 520, 522, 524 могут получить доступ к базам данных 530, 532, 534, чтобы идентифицировать целевое значение, которое надлежит связать с документом, и далее обработать набор факторов, связанный с документом, с помощью ведомых серверов 520, 522, 524 в соответствии с настоящей технологией. В некоторых других вариантах осуществления настоящей технологии ведомые серверы 520, 522, 524 могут получить доступ к базам данных 530, 532, 534, чтобы сохранить новую запись (здесь и далее также упоминаемую как «хэшированный комплексный вектор» и/или «ключ») в одной или нескольких хэш-таблицах, причем новая запись была создана после обработки набора факторов, связанных с документом; она представляет целевое значение, которое надлежит связать с документом. В таких вариантах осуществления настоящей технологии новая запись может представлять модификацию древовидных моделей, представленных хэш-таблицей. Несмотря на то, что на Фиг. 5 представлен варианта осуществления настоящей технологии, в котором базы данных 530, 532, 534 включают в себя хэш-таблицы, следует понимать, что могут быть предусмотрены альтернативные варианты сохранения моделей машинного обучения без отклонения от объема настоящей технологии.

[164] Подробности того, как обрабатываются древовидные модели, формирующие модель машинного обучения, будут предоставлены в описаниях к Фиг. 6-8.

[165] На Фиг. 6 изображены часть древовидной модели 600, первый набор 630 факторов и второй набор 640 факторов. Первый набор 630 факторов и второй набор 640 факторов могут также упоминаться как векторы признаков. Часть древовидной модели 600 могла быть создана в соответствии с настоящей технологией и может представлять связь между документом и целевым значением. Древовидная модель 600 может быть упомянута как модель машинного обучения или часть модели машинного обучения (например, для вариантов осуществления настоящей технологии, в которых модель машинного обучения опирается на множество древовидных моделей). В некоторых случаях древовидная модель 600 может быть упомянута как модель прогнозирования или часть модели прогнозирования (например, для вариантов осуществления настоящей технологии, в которых модель прогнозирования опирается на множество древовидных моделей).

[166] Документ может быть различных форм, форматов и может иметь разную природу, например, без введения ограничений, документ может быть текстовым файлом, текстовым документом, веб-страницей, аудио файлом, видео файлом и так далее. Документ может также упоминаться как файл, что не выходит за границы настоящей технологии. В одном варианте осуществления настоящей технологии файл может быть документом, который может быть найден поисковой системой. Однако, могут быть предусмотрены другие варианты осуществления технологии, что не выходит за границы настоящей технологии и может быть очевидным специалисту в данной области техники.

[167] Как было упомянуто ранее, целевое значение может быть разных форм и форматов, например (без введения ограничений), он представляет указание на порядок ранжирования документа, такое как отношение количества щелчков мышью к количеству показов ("click-through rate (CTR)"). В некоторых вариантах осуществления настоящей технологии целевое значение может упоминаться как метка и/или ранжирование, в частности, в контексте поисковых систем. В некоторых вариантах осуществления настоящей технологии, целевое значение может быть создано алгоритмом машинного обучения с использованием документа обучения. В некоторых альтернативных вариантах осуществления настоящей технологии могут быть использованы другие способы, например (без введения ограничений), определение целевого значения вручную. Следовательно, то, как создается целевое значение, никак не ограничивается, и могут быть предусмотрены другие варианты осуществления технологии, что не выходит за границы настоящей технологии и может быть очевидным специалисту в данной области техники.

[168] Путь в части древовидной модели 600 может быть определен первым набором 630 факторов и/или вторым набором 640 факторов. Первый набор 630 факторов и второй набор 640 факторов могут также быть связаны с тем же самым документом или с различными документами. Часть древовидной модели 600 включает в себя множество узлов, каждый из которых соединен с одной или несколькими ветвями. В варианте осуществления на Фиг. 6, присутствуют первый узел 602, второй узел 604, третий узел 606, четвертый узел 608 и пятый узел 610.

[169] Каждый узел (первый узел 602, второй узел 604, третий узел 606, четвертый узел 608 и пятый узел 610) связан с условием, таким образом определяя так называемое разделение.

[170] Первый узел 602 связан с условием "if Page_rank < 3" (значение ранжирования страницы), связанным с двумя ветками (т.е. значение «истина» представлено бинарным числом «0», а значение «ложь» представлено бинарным числом «1»); второй узел 604 связан с условием "Is main page?" («Главная страница?»), связанным с двумя ветками (т.е. Значение «истина» представлено бинарным числом «0», а значение «ложь» представлено бинарным числом «1»); третий узел 606 связан с условием "if Number_clicks < 5,000" (число щелчков), связанным с двумя ветками (т.е. значение «истина» представлено бинарным числом «0», а значение «ложь» представлено бинарным числом «1»); четвертый узел 608 связан с условием "which URL?" («Какой URL?»), которое связано более чем с двумя ветками (т.е. каждая ветка связана со своим URL, например, с URL "yandex.ru"); и пятый узел 610 связан с условием "which Search query?" («Какой поисковый запрос?»), которое связано более чем с двумя ветками (т.е. каждая ветка связана со своим поисковым запросом, например, поисковый запрос «посмотреть Эйфелеву башню»).

[171] В одном варианте осуществления технологии каждое из условий, установленной выше, может определять отдельный фактор (т.е. первый узел 602 определяется условием "if Page_rank < 3"(значение ранжирования страницы), второй узел 604 определяется условием "Is main page?" («Главная страница?»), третий узел 606 определяется условием "if Number_clicks < 5,000" (число щелчков), четвертый узел 608 определяется условием "which URL?" («Какой URL?»), пятый узел 610 определяется условием "which Search query?" («Какой поисковый запрос?»). Кроме того, пятый узел 610 по ветке «посмотреть Эйфелеву башню» связан с листом 612. В некоторых вариантах осуществления настоящей технологии лист 612 может указывать на целевое значение.

[172] Согласно описанной выше конфигурации, древовидная модель 600, определенная конкретным выбором и порядком первого узла 602, второго узла 604, третьего узла 606, четвертого узла 608 и пятого узла 610, может связывать документ (например, без введения ограничений, веб-страницу в формате html) с целевым значением, связанным с листом 612, причем связь определяется путем в части древовидной модели 300 на основе первого набора 630 факторов и/или второго набора 640 факторов.

[173] Следует учитывать, что с целью упрощения понимания приведена только часть древовидной модели 600. Специалисту в области настоящей технологии может быть очевидно, что число узлов, ветвей и листов фактически не ограничено и зависит исключительно от сложности построения древовидной модели. Кроме того в некоторых вариантах осуществления настоящей технологии древовидная модель может бинарной - включающей в себя набор узлов, каждый из которых содержит только две ветви (т.е. значение «истина» представлено бинарным числом «0», а значение «ложь» представлено бинарным числом «1»).

[174] Однако настоящая технология не ограничивается подобными древовидными моделями, и может быть предусмотрено множество вариаций, что может быть очевидно специалисту в области настоящей технологии: например, древовидная модель, состоящая из первой части, определяющей бинарную древовидную модель, и второй части, определяющей древовидную модель, которая определяет категориальную модель дерева, что проиллюстрировано на древовидной модели 600 (первая часть определяется первым узлом 602, вторым узлом 604, третьим узлом 606, а вторая часть определяется четвертым узлом 608 и пятым узлом 610).

[175] Первый набор 630 факторов является примером факторов, определяющих путь, проиллюстрированный на древовидной модели 600. Набор 630 факторов может быть связан с документом и может предоставить возможность определить путь в древовидной модели 600, описанной выше. По меньшей мере один факторов из набора факторов может быть бинарного типа и/или типа вещественных чисел (например, типа целых чисел, типа чисел с плавающей запятой).

[176] На Фиг. 6 представлен набор факторов включает в себя первый компонент 632, связанный со значением «01» и второй компонент 634, связанный со значением «3500». Хотя в настоящем описании используется термин «компонент», следует иметь в виду, что можно с равным успехом использовать термин «переменная», который можно рассматривать как эквивалент слова «компонент». Первый компонент 632 включает в себя бинарную последовательность «01», которая при переводе на древовидную модель 600 представляет первую часть пути. В примере, представленном на Фиг. 6, первая часть пути представлена с помощью применения первой двоичной цифры "0" из последовательности "01" к первому узлу 602, а затем второй цифры "1" последовательности "01" ко второму узлу 604. Второй компонент 634 при переводе на древовидную модель 600 представляет вторую часть пути. На Фиг. 6, вторая часть пути представлена с помощью применения числа "3500" к третьему узлу 606.

[177] Несмотря на то, что на Фиг. 6 приведена первая часть данных как включающая в себя первый компонент 632 и второй компонент 634, число компонентов и число цифр, включенное в один из компонентов, не ограничено и может быть предусмотрено множество вариантов, что не выходит за границы настоящей технологии.

[178] На Фиг. 6 представлен первый набор факторов, который также включает в себя третий компонент 636, связанный со значением "yandex.ru" и четвертый компонент 638, связанный со значением «посмотреть Эйфелеву башню». Третий компонент 636 и четвертый компонент 638 могут быть категориального типа. В некоторых вариантах осуществления настоящей технологии третий компонент 636 и четвертый компонент 638 также могут упоминаться как категориальные факторы и могут включать в себя, например (без введения ограничений), хост, URL, доменное имя, IP-адрес, поисковой запрос и/или ключевое слово.

[179] В некоторых вариантах осуществления настоящей технологии третий компонент 636 и четвертый компонент 638 могут быть в общем охарактеризованы как включающие в себя категории меток, которые предоставляют возможность категоризировать информацию. В некоторых вариантах осуществления настоящей технологии третий компонент 636 и четвертый компонент 638 могут принимать форму последовательности и/или строки символов и/или цифр. В других вариантах осуществления настоящей технологии, третий компонент 636 и четвертый компонент 638 могут содержать параметр, который принимает больше двух значений, как пример на Фиг. 6, что приводит к тому, что древовидная модель 600 обладает множеством ветвей, соединенных с данным узлом, как множеством возможных значений параметра.

[180] Может быть предусмотрено множество других вариантов того, что включают в себя третий компонент 636 и четвертый компонент 638, что не выходит за границы настоящей технологии. В некоторых вариантах осуществления настоящей технологии третий компонент 636 и четвертый компонент 638 могут представлять путь в части древовидной модели, причем эта часть является не-бинарной, как в случае, изображенном на Фиг. 6. В пределах объема настоящей технологии могут быть возможны другие варианты.

[181] Третий компонент 636 включает в себя строку символов "yandex.ru", которая, при переводе на древовидную модель 600 представляет четвертую часть пути. На Фиг. 6, четвертая часть пути представлена с помощью применения строки символов "yandex.ru" к четвертому узлу 608. Четвертый компонент 638 при переводе на древовидную модель 600 представляет пятую часть пути. На Фиг. 6, пятая часть пути представлена с помощью применения строки символов «посмотреть Эйфелеву башню» к пятому узлу 610, приводя к узлу 612 и целевому значению, связанному с ним. Несмотря на то, что на Фиг. 6 приведены третий компонент 636 и четвертый компонент 638, число компонентов и число цифр и/или символов, включенное в один из компонентов, не ограничено и может быть предусмотрено множество вариантов, что не выходит за границы настоящей технологии.

[182] Обратимся ко второму набору 640 факторов, который представляет собой другой пример факторов, определяющих путь, проиллюстрированный древовидной моделью 600. Как и в случае первого набора 630 факторов, второй набор 335 факторов может быть связан с документом и может предоставить возможность определить путь в древовидной модели 600, описанной выше. Второй набор 640 факторов аналогичен по всем аспектам первому набору 630 факторов за исключением того, что второй набор 640 факторов включает в себя первый компонент 642, а не первый компонент 632, и второй компонент 634 из первого набора 630 факторов.

[183] Первый компонент 642 включает в себя последовательность цифр «010», причем первый компонент 632 связан со значением «01» и второй компонент 634 связан со значением «3500». Как будет понятно специалисту в области настоящей технологии в первом компоненте 642 значение «3500» представлено бинарной цифрой «0», которая является результатом значения «3500», примененного к условию, связанному с третьим узлом 606 (т.е. "Number_licks < 5,000 ", число щелчков мышью). В итоге первый компонент 642 может быть рассмотрен как альтернативное представление первого компонента 632 и второго компонента 634 того же пути в древовидной модели 600.

[184] В итоге в некоторых вариантах осуществления настоящей технологи значение вещественного числа может быть переведено в бинарное значение, в частности, в случаях, в которых узел древовидной модели, к которому нужно применить целочисленное значение, соответствует бинарной части древовидной модели. Также возможны другие варианты; примеры второго набора 640 факторов не должны рассматриваться как ограничивающие объем настоящей технологии. Второй набор 640 факторов также включает в себя второй компонент 644 и третий компонент 646, которые идентичны третьему компоненту 636 и четвертому компоненту 638 первого набора 630 факторов.

[185] На Фиг. 7 приведен пример полной древовидной модели 700. Задачей древовидной модели 700 является иллюстрация типовой древовидной модели, которая может быть модифицирована таким образом, чтобы отвечать требованиям конкретной модели прогнозирования. Такие модификации могут включать в себя, например (но без введения ограничений), добавление или удаление одного или нескольких уровней дерева, добавление или удаление узлов (т.е. факторов и соответствующих разделений), добавление или удаление ветвей, соединяющих узлы, и/или листов дерева.

[186] Древовидная модель 700 может быть частью модели машинного обучения или моделью машинного обучения. Древовидная модель 700 может быть предварительной древовидной моделью или обученной древовидной моделью. В некоторых вариантах осуществления настоящей технологии, древовидная модель 700, после ее создания, может быть обновлена и/или модифицирована, например, для повышения уровня точности модели машинного обучения и/или расширения объема применения модели машинного обучения. В некоторых вариантах осуществления настоящей технологии древовидная модель 700 может исходить из обработки, например (но без установления ограничений), поисковых запросов или персонализированных рекомендаций содержимого. Без отклонения от объема настоящей технологии могут быть предусмотрены другие области, которые берет за основу древовидная модель 700.

[187] Древовидная модель 700 включает в себя первый узел 702, связанный с первым фактором "f1". Первый узел 702 определяет первый уровень древовидной модели 700. Первый узел 702 соединен ветвями со вторым узлом 704 и третьим узлом 706. Второй узел 704 и третий узел 706 связаны со вторым фактором "f2". Второй узел 704 и третий узел 706 определяют второй уровень древовидной модели 700. В одном варианте осуществления технологии, первый фактор "f1" и разделение для первого фактора "f1" были выбраны в наборе факторов для размещения на первом уровне древовидной модели 700 на основе набора обучающих объектов. Более подробное описание того, как осуществляется выбор факторов из набора факторов и соответствующих разделений, будет приведено ниже.

[188] Первый фактор "f1" определен таким образом, что, для данного объекта, значение параметра, связанного с первым фактором "f1" определяет то, связан ли объект со вторым узлом 704 или третьим узлом 706. В качестве примера, если значение меньше, чем значение "f1", то объект связан со вторым узлом 704. В другом примере, если значение больше, чем значение "f1", то объект связан с третьим узлом 706.

[189] В свою очередь, второй узел 704 связан с четвертым узлом 708, связанным с третьим фактором "f3", и четвертый узел 710 связан с третьим фактором "f3". Третий узел 706 связан с шестым узлом 712, связанным с третьим фактором "f3", и седьмой узел 714 связан с третьим фактором "f3". Четвертый узел 708, пятый узел 710, шестой узел 712 и седьмой узел 714 определяют третий уровень древовидной модели 700. Как было описано ранее по отношению к первому узлу 702, для данного объекта, значение параметра, связанного со вторым фактором "f2" определяет то, будет ли связан объект с четвертым узлом 708, или с пятым узлом 710 (если объект связан со вторым узлом 704), или с шестым узлом 712 или седьмым узлом 714 (если объект связан с третьим узлом 706).

[190] В свою очередь, каждый узел из узлов: четвертого узла 708, пятого узла 710, и шестого узла 712 и седьмого узла 714 связан с наборами прогнозированных параметров. На Фиг. 7 наборы прогнозированных параметров включают в себя первый набор 720, второй набор 722, третий набор 724 и четвертый набор 726. Каждый из наборов прогнозированных параметров включает в себя три целевых значения, а именно "C1", "С2" и"С3".

[191] Как будет понятно специалистам в данной области техники, древовидная модель 700 иллюстрирует вариант осуществления настоящей технологии, в котором конкретный уровень древовидной модели 700 связан с одним фактором. На Фиг. 7, первый уровень включает в себя первый узел 702 и связан с первым фактором "f1"; второй уровень включает в себя второй узел 704 и третий узел 706, и связан со вторым фактором "f2"; а третий уровень включает в себя четвертый узел 708, пятый узел 710, шестой узел 712 и седьмой узел 714, и связан с третьим фактором "f3".

[192] Другими словами, в представленном на Фиг. 7 варианте осуществления технологии, первый уровень связан с первым фактором "f1", второй уровень связан со вторым фактором "f2", и третий уровень связан с третьим фактором "f3". Могут быть, однако, предусмотрены другие варианты осуществления технологии. В частности, в альтернативном варианте осуществления технологии созданная древовидная модель может включать в себя различные факторы для данного уровня древовидной модели.

Например, первый уровень такой древовидной модели может включать в себя первый узел, связанный с первым фактором "f1", второй уровень может включать в себя второй узел, связанный со вторым фактором "f2" и третий узел, связанный с третьим фактором "f3". Как будет понятно специалистам в области настоящей технологии, можно предусмотреть множество вариантов того, какие факторы могут быть связаны с данным уровнем, не выходя за границы настоящей технологии.

[193] Релевантные этапы создания варианта модели прогнозирования в виде дерева решений (также упоминаемой как «обученное дерево решений», «древовидная модель», и/или «модель дерева решений») будут описаны с учетом Фиг. 8, 9 и 10.

[194] На Фиг. 8 представлены этапы создания варианты модели прогнозирования в виде дерева решений. На Фиг. 9 и 10 представлены наборы прото-деревьев (также упоминаемых как «предварительные древовидные модели» или «предварительные модели прогнозирования в виде деревьев решений», используемые для выбора первого фактора и второго факторов, которые используются в варианте осуществления прогностической модели обученного дерева решений.

[195] Следует отметить, что термин "прото-дерево" широко используется в настоящем описании. В некоторых вариантах осуществления настоящей технологии, термин "прото-дерево" используется для описания частично построенного / частично обученного дерева решений, например, когда дерево решений создается "уровень за уровнем". В других вариантах осуществления настоящей технологии, термин "прото-дерево" использован для описания обученного дерева решений в ансамбле деревьев решений, когда ансамбль деревьев решений создается в соответствии, например, с методами градиентного бустинга.

[196] На Фиг. 8 представлен процесс создания прогностической модели обученного дерева решений на основе набора объектов. Следует отметить, что нижеследующее описание прогностической модели обученного дерева решений, показанного на Фиг. 8, является только одним неограничивающим вариантом осуществления прогностической модели обученного дерева решений, и предусматривается, что другие неограничивающие варианты осуществления могут иметь больше или меньше узлов, факторов, уровней и листов.

[197] Как проиллюстрировано первым деревом 810 решений, создание прогностической модели обученного дерева решений начинается с выбора первого фактора, связанного здесь с первым узлом 811. Способ, с помощью которого выбираются факторы на каждом уровне, будет описан подробнее ниже.

[198] На окончании путей от первого узла 811 по ветви первого дерева решений 810 есть два листа 812 и 813. Каждый из листов 812 и 813 обладает "значением листа", которые связаны с заранее определенным целевым значением на данном уровне создания дерева решений. В некоторых вариантах осуществления технологии первый фактор "f1" был выбран для узла 811 первого уровня древовидной модели 810 на основе набора обучающих объектов и/или параметра точности дерева 810 решений. Параметр точности листа и/или параметр точности дерева 810 решений вычисляются посредством определения параметра качества прогнозирования, как будет более подробно описано далее.

[199] Конкретнее, первый фактор "f1" и соответствующее разделение были выбраны из всех возможных факторов и всех возможных разделений на основе таким образом созданного параметра качества прогнозирования.

[200] Второй фактор "f2" выбирается следующим и добавляется к дереву 810 решений, что создает дерево 820 решений. Второй узел 822 и третий узел 823, связанные со вторым фактором, добавляются к двум ветвям, исходящим из первого узла 811. В альтернативном варианте осуществления настоящей технологии второй узел 822 и третий узел 823 могут быть связаны с различными факторами.

[201] В вариантах осуществления, представленных на Фиг. 8, первый узел 811 дерева 820 решений остается таким же, как и в дереве 810 решений, потому что первый фактор был выбран и назначен на первый уровень, и связан с первым узлом 811 (на основе метода градиентного бустинга).

[202] Листы 824-828 теперь связаны с окончаниями путей в дереве 820 решений. Второй узел 822 имеет два листа, лист 824 и лист 825, исходящие из второго узла 822. Третий узел 823 имеет три листа, лист 826, лист 827 и лист 828, исходящие из третьего узла 823. Число листов, исходящих из любого данного узла, может зависеть, например, от факторов, выбранных в любом данном узле, и признаков обучающих объектов, с помощью которых была создана древовидная модель.

[203] Также как и в случае с первым фактором "f1", параметр качества прогнозирования используется для выбора второго фактора "f2" и соответствующих разделений для второго узла 822 и третьего узла 823.

[204] Также на Фиг. 8, показано, что затем выбирается фактор "f3" третьего уровня и добавляется к дереву 820 решений, что создает дерево 830 решений. Первый узел 811, второй узел 822 и третий узел 823 остаются теми же самыми, что и в дереве 810 решений и в дереве 820 решений. Первый фактор и второй фактор (и связанные с ними разделения) также остаются теми же самыми факторами (и узлами), выбранными и назначенными ранее.

[205] Новые узлы 834-838 добавляются к ветвям, исходящим из второго узла 822 и третьего узла 823. Новые листы 840-851, связанные с окончаниями путей дерева 830 принятия решения, исходят из новых узлов 834-838. Каждый лист из новых листов 840-851 имеет соответствующее значение листа, связанное с одним или несколькими прогнозированными значениями. В этом примере варианта осуществления настоящей технологии во время создания прогностической модели обученного дерева решений было выбрано три фактора. Предусматривается, что в различных вариантах осуществления прогностической модели обученного дерева решений может быть больше или меньше трех факторов. Следует отметить, что создаваемая древовидная модель может обладать числом уровней, созданных так, как описано выше, которое больше или меньше трех.

[206] То, как именно выбираются факторы для прогностической модели обученного дерева решений, как показано на Фиг. 7 и 8, будет описано в отношении Фиг. 9 и 10.

[207] Для выбора в качестве первого фактора «наилучшего» фактора создается набор «прото-деревьев» («прото-деревьев») с первым узлом. На Фиг. 9 показаны три прото-дерева 910, 920 и 930 как типичная выборка из набора прото-деревьев. В каждом отдельном прото-дереве 910, 920 и 930 первый узел связан с отдельным фактором из набора доступных факторов. Например, узел 911 прото-дерева 910 связан с одним из факторов, "fa", а узел 921 прото-дерева 920 связан с фактором "fb", а в прото-дереве 930 узел 931 связан с фактором "fh". В некоторых вариантах осуществления настоящей технологии для каждого из факторов, из которых должен быть выбран первый фактор, создается одно прото-дерево. Все прото-деревья отличаются друг от друга, и они могут не учитываться после выбора наилучшего фактора для использования в качестве узла первого уровня.

[208] В некоторых вариантах осуществления настоящей технологии такие факторы как, например, "fa", "fb" и "fn", будут связаны с признаками, которые являются численными или категориальными. Например, возможно не только наличие двух листов на узел (как в случае с использованием только бинарных данных), но и наличие большего количества листов (и ветвей, к которым могут быть добавлены дополнительные узлы). Как показано на Фиг. 9, прото-дерево 910, включающее в себя узел 911, имеет ветви, идущие в три листа 912 - 914, а прото-дерево 920 и прото-дерево 930 имеет два (922, 923) листа и четыре листа (932 - 935), соответственно.

[209] Этот набор прото-деревьев, показанный на Фиг. 9, далее используется для выбора «наилучшего» первого фактора для добавления к создаваемой прогностической модели обученного дерева решений. Для каждого дерева из прото-деревьев, параметр качества прогнозирования вычисляется по меньшей мере для некоторых листов, исходящих из одного или нескольких узлов.

[210] Например, параметр качества прогнозирования определяется для прото-деревьев 910, 920 и 930. В некоторых вариантах осуществления настоящей технологии факторы точности листа определяются по меньшей мере для некоторых листов, например, для листов 912, 913, и 914 прото-дерева 910. В некоторых вариантах осуществления настоящей технологии факторы точности листа могут быть комбинированы для определения параметра точности. То, как именно определяется параметр качества прогнозирования, будет определено далее более подробно.

[211] Первый фактор для использования при создании древовидной модели затем может быть выбран путем выбора прото-дерева «наилучшего качества» на основе параметра качества прогнозирования для каждого прото-дерева. Фактор, связанный с прото-деревом «наилучшего качества» затем выбирается как первый фактор для создания прогностической модели обученного дерева решений.

[212] С целью иллюстрации выберем прото-дерево 920 как «наилучшее» прото-дерево, например, на основе определения того, что прото-дерево 920 связано с наивысшим параметром точности. На Фиг. 10 показан созданный второй набор прото-деревьев для выбора «наилучшего» фактора второго фактора для добавления к создаваемой прогностической модели обученного дерева решений. Узел 921 и его соответствующие ветви сохраняются от прото-дерева 920. Остальное прото-дерево 920 и первый набор прото-деревьев может не учитываться.

[213] Те же самые обучающие объекты затем используются для тестирования второго набора прото-деревьев, включающих в себя узел 921, связанный с «наилучшим» первым фактором (назначенным с помощью описанного выше процесса) и двух узлов, связанных со вторым фактором, причем второй фактор из набора факторов для каждого прото-дерева свой.

[214] В этом примере присутствуют два узла второго уровня, потому что с узлом 921 связаны две ветви. Если бы «наилучшим» прото-деревом было прото-дерево 830, присутствовало бы четыре узла, связанных с четырьмя ветвями, исходящими из узла 831.

[215] Как показано на трех примерах прото-деревьев 940, 960 и 980 из второго набора прото-деревьев, который показан на Фиг. 10, первый узел каждого прото-дерева - это узел 921 от наилучшего первого прото-дерева, и в деревьях присутствуют, добавленные к двум ветвям, исходящим от узла 921, два узла 942, 943 (для прото-дерева 940), два узла 962, 963 (для прото-дерева 960) и два узла 982, 983 (для прото-дерева 980). Каждое из окончаний прото-деревьев 940, 960 и 980 связано с листами 944-647; 964-968 и 984-988, соответственно.

[216] «Наилучший» второй фактор теперь выбирается таким же образом, как описано выше для «наилучшего» первого фактора, причем прото-дерево, состоящее из первого фактора и второго фактора, будет обладать «более высоким качеством» (обладая более высоким параметром точности), чем другие прото-деревья, которые не были выбраны. Затем второй фактор, связанный со вторыми узлами прото-дерева, обладающими наиболее высоким параметром качества прогнозирования, выбирается как второй фактор для того, чтобы быть присвоенным создающейся прогностической модели обученного дерева решений. Например, если прото-дерево 960 определяется как прото-дерево с наивысшим параметром качества прогнозирования, узел 962 и узел 963 будут добавлены к создающейся прогностической модели обученного дерева решений.

[217] Аналогично, если добавляются последующие факторы и уровни, будет создаваться новый набор прото-деревьев с использованием узла 921, узла 962, и узла 963, с новыми узлами, добавленным к пяти ветвям, исходящим из узла 962 и узла 963. Способ будет проводиться для какого угодно количества уровней и связанных факторов при создании прогностической модели обученного дерева решений. Следует отметить, что прогностическая модель обученного дерева решений может обладать числом уровней, созданных так, как описано выше, которое больше или меньше трех.

[218] Когда создание прогностической модели обученного дерева решений завершено, для законченной модели прогнозирования может быть осуществлено определение параметра качества прогнозирования. В некоторых вариантах осуществления настоящей технологии определение модели прогнозирования может основываться на наборе прогностических моделей обученного дерева решений, а не на единственной прогностической модели обученного дерева решений, причем каждая прогностическая модель обученного дерева решений из набора может быть создана в соответствии со способом, описанным выше. В некоторых вариантах осуществления настоящей технологии факторы могут быть выбраны из того же самого набора факторов, и может быть использован тот же самый набор обучающих объектов.

[219] Далее следует описание того, как создается параметр качества прогноза. На Фиг. 11 представлена часть прото-дерева 1100 с одним узлом первого уровня (первым узлом 1102), который также может считаться "корневым узлом", и двумя узлами второго уровня (вторым узлом 1104 и третьим узлом 1106). Для целей иллюстрации предположим, что значение фактора и разделения для первого узла 1102 были выбраны (f1/s1).

[220] Как уже упоминалось ранее, в соответствии с неограничивающими вариантами осуществления настоящей технологии, предусмотрен упорядоченный список обучающих объектов 1120. В соответствии с неограничивающими вариантами осуществления настоящей технологии, ведущий сервер 510 и/или ведомые серверы 520, 522, 524 могут создавать упорядоченный список обучающих объектов 1120, как будет описано далее.

[221] Упорядоченный список обучающих объектов 1120 включает в себя шесть обучающих объектов - первый обучающий объект 1122, второй обучающий объект 114, третий обучающий объект 1126, четвертый обучающий объект 1128, пятый обучающий объект 1120 и шестой обучающий объект 1132. Следует отметить, что природа обучающих объектов (первого обучающего объекта 1122, второго обучающего объекта 114, третьего обучающего объекта 1126, четвертого обучающего объекта 1128, пятого обучающего объекта 1120 и шестого обучающего объекта 1132) практически не ограничена и будет зависеть от типа прогноза, для которого будет использована модель дерева решений.

[222] Исключительно в качестве примера, если прогноз, который ожидается от модели дерева решений, представляет собой ранг (или релевантность) конкретного документа по отношению к поисковому запросу, каждый из обучающих объектов (первый обучающий объект 1122, второй обучающий объект 114, третий обучающий объект 1126, четвертый обучающий объект 1128, пятый обучающий объект 1120 и шестой обучающий объект 1132) может включать в себя пару поисковый запрос и документ, а также соответствующую метку (метка указывает на то, насколько релевантен документ поисковому запросу). Метка, например, может предоставляться человеком-асессором.

[223] Порядок элементов в упорядоченном списке обучающих объектов 1120 показан на Фиг. 11 под номером 1134.

[224] Как уже было упомянуто выше, в тех вариантах осуществления технологии, где обучающие объекты (первый обучающий объект 1122, второй обучающий объект 114, третий обучающий объект 1126, четвертый обучающий объект 1128, пятый обучающий объект 1120 и шестой обучающий объект 1132) обладают присущими им временными отношениями, порядок элементов в упорядоченном списке обучающих объектов 1120 организован в соответствии с этими временными отношениями между обучающими объектами.

[225] В тех вариантах осуществления технологии, где обучающие объекты (первый обучающий объект 1122, второй обучающий объект 114, третий обучающий объект 1126, четвертый обучающий объект 1128, пятый обучающий объект 1120 и шестой обучающий объект 1132) не обладают присущими им временными отношениями, порядок элементов в упорядоченном списке обучающих объектов 1120 организован в соответствии с заранее определенным правилом (эвристикой). Например, порядок элементов в упорядоченном списке обучающих объектов 1120 может быть случайным (т.е. первый обучающий объект 1122, второй обучающий объект 114, третий обучающий объект 1126, четвертый обучающий объект 1128, пятый обучающий объект 1120 и шестой обучающий объект 1132 могут быть организованы в случайном порядке в пределах упорядоченного списка обучающих объектов 1120).

[226] В альтернативных неограничивающих вариантах осуществления настоящей технологии, порядок элементов в упорядоченном списке обучающих объектов 1120 может быть организован в соответствии с другим правилом.

[227] В тех вариантах осуществления настоящей технологии, где обучающие объекты (первый обучающий объект 1122, второй обучающий объект 114, третий обучающий объект 1126, четвертый обучающий объект 1128, пятый обучающий объект 1120 и шестой обучающий объект 1132) не обладают присущими им временными отношениями, порядок на основе правила становится основой для временного порядка обучающих объектов, которые, в ином случае, не обладают никакими присущими им временными отношениями.

[228] Независимо от того, как создается порядок 1134, порядок 1134 далее "замораживается" и обучающие объекты (первый обучающий объект 1122, второй обучающий объект 114, третий обучающий объект 1126, четвертый обучающий объект 1128, пятый обучающий объект 1120 и шестой обучающий объект 1132) обрабатываются в соответствии с этим "замороженным" порядком 1134.

[229] Таким образом организованный порядок, в некотором смысле, указывает для каждого обучающего объекта (т.е. одного из первого обучающего объекта 1122, второго обучающего объекта 114, третьего обучающего объекта 1126, четвертого обучающего объекта 1128, пятого обучающего объекта 1120 и шестого обучающего объекта 1132), какой другой обучающий объект находится "до" и какой находится "после".

[230] В качестве примера рассмотрим четвертый обучающий объект 1128. Про четвертый обучающий объект 1128 можно сказать, что:

- первый обучающий объект 1122, второй обучающий объект 114 и третий обучающий объект 1126 находятся до четвертого обучающего объекта 1128; и

- пятый обучающий объект 1120 и шестой обучающий объект 1132 находятся после четвертого обучающего объекта 1128.

[231] В соответствии с неограничивающими вариантами осуществления настоящей технологии, как часть оценки качества прогноза для данного листа или данной части дерева решений, ведущий сервер 510 и/или ведомые серверы 520, 522, 524 создают параметр качества прогноза: (i) для каждого обучающего объекта; и (ii) на основе целевых значений только тех обучающих объектов, которые "находятся" до данного обучающего объекта в упорядоченном списке обучающих объектов 1120.

[232] Если обратиться к временной аналогии, ведущий сервер 510 и/или ведомые серверы 520, 522, 524 вычисляют параметр оценки качества, используя только те обучающие объекты, которые находятся в "прошлом" по отношению к данному обучающему объекту. Другими словами, параметр качества прогноза вычисляется без "заглядывания" в целевое значение данного обучающего объекта и в целевые значения тех обучающих объектов, которые находятся "в будущем" по отношению к данному обучающему объекту.

[233] Таким образом, в соответствии с неограничивающими вариантами осуществления настоящей технологии, ведущий сервер 510 и/или ведомые серверы 520, 522, 524 итеративно вычисляют параметр качества прогноза по мере того как каждый новый обучающий объект классифицируется в данный лист, используя только те обучающие объекты, которые уже были классифицированы в данный лист. После расчета всех параметров качества прогноза, они агрегируются (например, путем добавления или вычисления среднего значения всех рассчитанных таким образом параметров качества прогноза для данного листа), а затем, в конечном итоге, для данного уровня дерева решений, используя все листы данного уровня дерева решений.

[234] Рассмотрим процесс расчета параметра качества прогноза на Фиг. 11. На текущем этапе построения дерева решений, основная задача - расчет параметра качества прогноза для второго уровня прото-дерева 1100. Конкретнее, ведущий сервер 510 и/или ведомые серверы 520, 522, 524 вычисляют параметр качества прогноза для данного значения фактора и разделение для второго узла 1104 и третьего узла 1106.

[235] Для целей иллюстрации, которые будут представлены далее, предположим, что значение фактора и разделение для второго узла 1104 было выбрано в виде fn/sn, и что значение фактора и разделение для третьего узла 1106 было выбран в виде fm/sm. Параметры качества прогноза нацелены именно на оценку значений факторов и разделений. Другими словами, ведущий сервер 510 и/или ведомые серверы 520, 522, 524 вычисляют параметр качества прогноза для данного уровня дерева решений и для выбранных в данный момент значений фактора и разделения.

[236] Сначала первый обучающий объект 1122 "спускается" по прото-дереву 1100 и первый обучающий объект 1122 классифицируется. Предположим, что первый обучающий объект 1122 классифицирован в третий узел 1106 (третий узел 1106 выступает качестве листа прото-дерева 1100). Поскольку первый обучающий объект 1122 является первым объектом порядка 1134, он не имеет "прошлых объектов" и значение качества прогноза не вычисляется. Альтернативно, значение параметра качества прогноза может быть вычислено как ноль.

[237] Далее второй обучающий объект 1124 "спускается" по прото-дереву 1100 и второй обучающий объект 1124 классифицируется. Предположим, что второй обучающий объект 1124 классифицирован во второй узел 1104 (второй узел 1104 выступает качестве листа прото-дерева 1100). Несмотря на то, что второй обучающий объект 1124 не является первым объектом порядка 1134, он является первым обученным объектом, классифицированным во второй узел 1104, и, следовательно, он не имеет "прошлых объектов" в том же "листе". В соответствии с неограничивающими вариантами осуществления настоящей технологии, значение качества прогноза не вычисляется. Альтернативно, значение параметра качества прогноза может быть вычислено как ноль.

[238] Далее третий обучающий объект 1126 "спускается" по прото-дереву 1100 и третий обучающий объект 1126 классифицируется. Предположим, что третий обучающий объект 1126 классифицирован во второй узел 1104 (второй узел 1104 выступает качестве листа прото-дерева 1100). Параметр качества прогноза для третьего обучающего объекта 1126 рассчитывается с использованием "прошлого" третьего обучающего объекта 1126, а именно - первого обучающего объекта 1122, который также классифицирован во второй узел 1104.

[239] Затем процесс повторяется с четвертым обучающим объектом 1128, пятым обучающим объектом 1120 и шестым обучающим объектом 1132. После того, как все обучающие объекты были классифицированы и были созданы все факторы качества прогноза, факторы качества прогноза всех обучающих объектов, классифицированных в данный узел (т.е. второй узел 1104 и третий узел 1106), агрегируются в параметр качества прогноза на уровне узла. Таким образом, можно сказать, что для данного узла (т.е. второго узла 1104 и третьего узла 1106) параметр качества прогноза на уровне узла создается на основе индивидуальных факторов качества прогноза обучающих объектов, которые были классифицированы в данный узел, причем индивидуальные факторы качества прогноза были созданы так, как описано выше.

[240] Как уже упоминалось ранее, то, как отдельные факторы качества прогноза агрегируются в параметр качества прогноза на уровне узла, никак конкретно не ограничено. Таким образом, параметр качества прогноза на уровне узла может быть создан на основе сложения индивидуальных факторов качества прогноза всех обучающих объектов, которые были классифицированы в данный узел. Альтернативно, параметр качества прогноза на уровне узла может быть создан на основе вычисления среднего (или усредненного) значения индивидуальных факторов качества прогноза всех обучающих объектов, которые были классифицированы в данный узел. Однако, в других альтернативных вариантах осуществления настоящей технологии, параметр качества прогноза на уровне узла может быть создан путем применения функции к индивидуальным факторам качества прогноза всех обучающих объектов, которые были классифицированы в данный узел.

[241] Продолжая приведенный выше пример, предположим, что на данной итерации обучения дерева решений, прото-дерево классифицировало обучающие объекты следующим образом:

[242] Для второго узла 1104, параметр качества прогнозирования уровня узла может быть вычислен следующим образом:

[243] Где NLPQP - параметр качества прогноза на уровне узла для второго узла, 1104, f(TO2) - параметр качества, связанный со вторым обучающим объектом 1124 и f(TO4) -параметр качества прогноза, связанный с четвертым обучающим объектом 1128.

[244] Для третьего узла 1106, параметр качества прогнозирования уровня узла может быть вычислен следующим образом:

[245] Где NLPQP - параметр качества прогноза на уровне узла для третьего узла 1106, f(TO22) - параметр качества, связанный с первым обучающим объектом 1122, f(TO3) - параметр качества прогноза, связанный с третьим обучающим объектом 1126, f(TO5) - параметр качества прогноза, связанный с пятым обучающим объектом 1130, и f(TO6) - параметр качества прогноза, связанный с шестым обучающим объектом 1132.

[246] Следует отметить, что также возможно агрегировать параметр качества прогноза на уровне узла в параметр качества прогноза всего уровня.

[247] С учетом вышеописанной архитектуры возможно реализовать способ определения параметра качества прогноза для дерева решений в прогностический модели дерева решений. Способ может выполняться системой машинного обучения, которая выполняет прогностическую модель дерева решений, Например, способ 1100 может выполняться ведущим сервером 510 и/или ведомыми серверами 520, 522, 524.

[248] На Фиг. 12 представлена блок-схема способа 1200, который выполняется в соответствии с не ограничивающими вариантами осуществления настоящей технологии.

[249] Этап 1202 - получение доступа с постоянного машиночитаемого носителя системы машинного обучения, к набору обучающих объектов, причем каждый обучающий объект из набора обучающих объектов включает в себя указание на документ и целевое значение

[250] Способ 1200 начинается на этапе 1202, где ведущий сервер 510 и/или ведомые сервера 520, 522, 524 получают доступ, с постоянного машиночитаемого носителя системы машинного обучения, к набору обучающих объектов, причем каждый обучающий объект из набора обучающих объектов включает в себя указание на документ и целевое значение.

[251] Этап 1204 - организация набора обучающих объектов в упорядоченный список обучающих объектов, причем упорядоченный список обучающих объектов организован таким образом, что для каждого обучающего объекта в упорядоченном списке обучающих объектов существует по меньшей мере один из: (i) предыдущий обучающий объект, который находится до данного обучающего объекта и (ii) последующий обучающий объект, который находится после данного обучающего объекта

[252] На этапе 1204 ведущий сервер 510 и/или ведомые серверы 520, 522, 524 организуют набор обучающих объектов в упорядоченный список обучающих объектов. В соответствии с вариантами осуществления настоящей технологии, упорядоченный список обучающих объектов организован таким образом, что для каждого обучающего объекта в упорядоченном списке обучающих объектов существует по меньшей мере один из: (i) предыдущий обучающий объект, который находится до данного обучающего объекта и (ii) последующий обучающий объект, который находится после данного обучающего объекта

[253] Как уже было упомянуто выше, в тех вариантах осуществления технологии, где обучающие объекты (первый обучающий объект 1122, второй обучающий объект 114, третий обучающий объект 1126, четвертый обучающий объект 1128, пятый обучающий объект 1120 и шестой обучающий объект 1132) обладают присущими им временными отношениями, порядок элементов в упорядоченном списке обучающих объектов 1120 организован в соответствии с этими временными отношениями между обучающими объектами.

[254] В тех вариантах осуществления технологии, где обучающие объекты (первый обучающий объект 1122, второй обучающий объект 114, третий обучающий объект 1126, четвертый обучающий объект 1128, пятый обучающий объект 1120 и шестой обучающий объект 1132) не обладают присущими им временными отношениями, порядок элементов в упорядоченном списке обучающих объектов 1120 организован в соответствии с заранее определенным правилом (эвристикой). Например, порядок элементов в упорядоченном списке обучающих объектов 1120 может быть случайным (т.е. первый обучающий объект 1122, второй обучающий объект 114, третий обучающий объект 1126, четвертый обучающий объект 1128, пятый обучающий объект 1120 и шестой обучающий объект 1132 могут быть организованы в случайном порядке в пределах упорядоченного списка обучающих объектов 1120).

[255] В альтернативных неограничивающих вариантах осуществления настоящей технологии, порядок элементов в упорядоченном списке обучающих объектов 1120 может быть организован в соответствии с другим правилом.

[256] В тех вариантах осуществления настоящей технологии, где обучающие объекты (первый обучающий объект 1122, второй обучающий объект 114, третий обучающий объект 1126, четвертый обучающий объект 1128, пятый обучающий объект 1120 и шестой обучающий объект 1132) не обладают присущими им временными отношениями, порядок на основе правила становится основой для временного порядка обучающих объектов, которые, в ином случае, не обладают никакими присущими им временными отношениями.

[257] Независимо от того, как создается порядок, порядок 1134 далее "замораживается" и обучающие объекты (первый обучающий объект 1122, второй обучающий объект 114, третий обучающий объект 1126, четвертый обучающий объект 1128, пятый обучающий объект 1120 и шестой обучающий объект 1132) обрабатываются в соответствии с этим "замороженным" порядком.

[258] Таким образом организованный порядок, в некотором смысле, указывает для каждого обучающего объекта (т.е. одного из первого обучающего объекта 1122, второго обучающего объекта 114, третьего обучающего объекта 1126, четвертого обучающего объекта 1128, пятого обучающего объекта 1120 и шестого обучающего объекта 1132), какой другой обучающий объект находится "до" и какой находится "после".

[259] Этап 1206 - спуск набора обучающих объектов по дереву решений таким образом, что каждый из набора обучающих объектов классифицируется в один из узлов данного уровня дерева решений

[260] На этапе 1206 ведущий сервер 510 и/или ведомые серверы 520, 522, 542 спускают набор обучающих объектов по дереву решений таким образом, что каждый из набора обучающих объектов классифицируется в один из узлов данного уровня дерева решений

[261] Этап 1208 - создание параметра качества прогноза для данного уровня дерева решений путем создания, для данного обучающего объекта, который классифицирован в данный узел дерева решений, параметра качества прогноза, причем создание выполняется на основании целевых значений только тех обучающих объектов, которые находятся до данного обучающего объекта в упорядоченном списке обучающих объектов

[262] На этапе 1208, ведущий сервер 510 и/или ведомые серверы 520, 522, 524 создают параметр качества прогноза для данного уровня дерева решений путем создания, для данного обучающего объекта, который классифицирован в данный узел дерева решений, параметра качества прогноза, причем создание выполняется на основании целевых значений только тех обучающих объектов, которые находятся до данного обучающего объекта в упорядоченном списке обучающих объектов

[263] Опциональные факторы способа 1200

[264] В некоторых вариантах осуществления способа 1200, способ 1200 далее включает для данного узла, обладающего по меньшей мере одним обучающим объектом, классифицированным в дочерний узел данного узла: объединение в параметр качества прогноза на уровне узла параметров качества прогноза по меньшей мере одного обучающего объекта.

[265] В некоторых вариантах осуществления способа 1200, объединение в параметр качества прогноза на уровне узла параметров качества прогноза по меньшей мере одного обучающего объекта включает в себя одно из: добавление всех параметров качества прогноза по меньшей мере одного обучающего объекта, создание среднего значения параметров качества прогноза по меньшей мере одного обучающего объекта и применение формулы к параметрам качества прогноза по меньшей мере одного обучающего объекта.

[266] В некоторых вариантах осуществления способа 1200, способ 1200 далее включает в себя: для данного уровня дерева решений, данный уровень обладает по меньшей мере одним узлом, объединение в общеуровневый параметр качества прогноза, параметр качества прогноза уровня узла, параметры качества прогноза по меньшей мере одного узла.

[267] В некоторых вариантах осуществления способа 1200, спуск включает в себя: спуск набора обучающих объектов по дереву решений в порядке обучающего объекта в упорядоченном списке обучающих объектов.

[268] В некоторых вариантах осуществления способа 1200, создание параметра качества прогноза для данного обучающего объекта, обладающего данной позицией в упорядоченном списке обучающих объектов включает в себя: создание параметра качества прогноза на основе целевых значений только тех обучающих объектов, которые (i) находятся на позиции до данного обучающего объекта в упорядоченном списке обучающих объектов и (ii) классифицированы в один и тот же лист.

[269] В некоторых вариантах осуществления способа 1200, организация набора обучающих объектов в упорядоченный список обучающих объектов включает в себя: создание множества упорядоченных списков обучающих объектов, причем каждый из множества упорядоченных списков обучающих объектов организован таким образом, что для каждого обучающего объекта в упорядоченном списке обучающих объектов существует по меньшей мере один из: (i) предыдущий обучающий объект, который находится до данного обучающего объекта и (ii) последующий обучающий объект, который находится после данного обучающего объекта; данный упорядоченный список из множества упорядоченных списков обучающих объектов обладает, по меньшей мере частично, отличающимся порядком от других упорядоченных списков во множестве упорядоченных списков обучающих объектов.

[270] В некоторых вариантах осуществления способа 1200, способ 1200 далее включает в себя выбор одного из множества упорядоченных списков обучающих объектов.

[271] В некоторых вариантах осуществления способа 1200, выбор осуществляется для каждой итерации создания параметра качества прогноза.

[272] В некоторых вариантах осуществления способа 1200, выбор осуществляется в процессе проверки качества прогноза для данного дерева решений.

[273] В некоторых вариантах осуществления способа 1200, набор обучающих объектов связан с присущими им временными отношениями обучающих объектов, и причем организация набора обучающих объектов в упорядоченный список обучающих объектов включает в себя организацию набора обучающих объектов в соответствии с временными отношениями.

[274] В некоторых вариантах осуществления способа 1200, набор обучающих объектов не связан с присущими им временными отношениями обучающих объектов, и причем организация набора обучающих объектов в упорядоченный список обучающих объектов включает в себя организацию набора обучающих объектов в соответствии с правилом.

[275] В некоторых вариантах осуществления способа 1200, набор обучающих объектов не связан с присущими им временными отношениями обучающих объектов, и причем организация набора обучающих объектов в упорядоченный список обучающих объектов включает в себя организацию набора обучающих объектов в соответствии со случайно созданным порядком.

[276] Реализация "динамического бустинга" - несколько деревьев решений / ансамбль деревьев

[277] Как было упомянуто ранее, в альтернативных вариантах осуществления настоящей технологии, парадигма "динамического бустинга" применяется к нескольким деревьям решений / ансамблю деревьев решений. В частности, при реализации градиентного бустинга деревьев и построении ансамбля деревьев решений (каждое из которых построено на основе, в частности, результатов предыдущих деревьев с целью повышения качества прогнозирования предыдущих деревьев решений). В соответствии с неограничивающими вариантами осуществления настоящей технологии, подход "не смотреть вперед", как было описано выше в контексте построения одного дерева, применяется к процессу построения нескольких деревьев решений, как части ансамбля во время способа с использованием бустинга.

[278] В общем, функции f(x) MLA для данного обучающего объекта х зависит не только от целевых значений обучающих объектов, которые предшествуют данному обучающему объекту в "хронологии" (порядке) и попадают в тот же лист, что и данный обучающий объект в текущем дереве, а также от аппроксимации (т.е. прогнозов) для обучающего объекта х, сделанных предыдущими деревьями решений. Эти прогнозы предыдущих итераций деревьев решений упоминаются здесь как "аппроксимации". Другими словами, аппроксимация для данного обучающего объекта х является прогнозом, сделанным ранее построенными деревьями, а также текущей итерацией дерева решений для данного обучающего объекта х.

[279] Ведущий сервер 510 и/или ведомые серверы 520, 522, 524 создают и поддерживают таблицу 100, представленную на Фиг. 1. В таблице 100 хранятся результаты прогноза для каждого из обучающих объектов х, которые были созданы во время предыдущей итерации обучения и проверки модели дерева решений.

[280] Таблица 100 сопоставляет данный обучающий объект 102 с его целевым значением 104 (т.е. фактическим значением цели, который MLA пытается предсказать) и соответственной аппроксимацией 106 (т.е. совокупностью прогнозов для обучающего объекта 102, сделанных на предыдущих итерациях деревьев решений).

[281] Также схематично представлен вектор 103 аппроксимации. Вектор 103 аппроксимации является вектором правильных ответов для всех представленных примерных объектов (от одного до тысячи на схеме, изображенной на Фиг. 1).

[282] Можно также сказать, что вектор 103 аппроксимации является вектором результатов прогнозирования модели прогнозирования, полностью выполняемой в текущий момент с помощью MLA. Другими словами, вектор 103 аппроксимации представляет собой результаты прогноза для всех обучающих объектов 102, полученных комбинацией деревьев решений, которые построены на текущем этапе бустинга деревьев решений MLA. В простейшей реализации неограничивающих вариантов настоящей технологии каждая аппроксимация вектора 103 аппроксимации является суммой предыдущих прогнозов для данного обучающего объекта 102.

[283] Когда ведущий сервер 510 и/или ведомые серверы 520, 522, 524 инициируют бустинг деревьев решений, вектор 103 аппроксимации содержит только нули (поскольку предыдущие итерации деревьев решений не были построены и, таким образом, предыдущие результаты прогнозов еще не доступны). По мере того, как ведущий сервер 510 и/или ведомые серверы 520, 522, 524 продолжают реализовывать бустинг (и, таким образом, строить дополнительные деревья решений в ансамбле деревьев решений), фокусируя внимание на "самых слабых моделях" в предыдущих итерациях деревьев решений, вектор 103 аппроксимации все больше и больше приближается к вектору целевых значений (не показано). Другими словами, задача ведущего сервера 510 и/или ведомых серверов 520, 522, 524 заключается в том, чтобы при выполнении бустинга максимально аппроксимировать целевые значения к фактическим значениям целей.

[284] Возвращаясь к примеру с обучающим объектом х в данном листе на данном этапе бустинга n, в соответствии с неограничивающими вариантами осуществления настоящей технологии, прогноз для обучающего объекта х (т.е. новая аппроксимация для этапа бустинга n), в данном новом дереве является функцией целевых значений, и аппроксимации обучающего(их) объекта(ов), который(е) (i) был(и) классифицирован(ы) (помещены) в один и тот же лист, что и обучающий объект х в новом дереве и (ii) находится (находятся) в упорядоченном списке обучающих объектов до обучающего объекта х.

[285] Ведущий сервер 510 и/или ведомые серверы 520, 522, 524 могут применять Формулу 1 для расчета аппроксимации.

[286] В соответствии с неограничивающими вариантами осуществления настоящей технологии, ведущий сервер 510 и/или ведомые серверы 520, 522, 524 сначала разделяют упорядоченный список обучающих объектов на блоки. На Фиг. 3 ведущий сервер 510 и/или ведомые серверы 520, 522, 524 разделяют упорядоченный список обучающих объектов на множество блоков 301.

[287] Множество блоков 301 состоит из блоков нескольких уровней - блоки 302 первого уровня, блоки 304 второго уровня, блока 306 третьего уровня, блоки 308 четвертого уровня и т.д. В представленном варианте осуществления каждый уровень блоков (т.е. блоки 302 первого уровня, блоки 304 второго уровня, блока 306 третьего уровня, блоки 308 четвертого уровня) содержит два блока - первый блок и второй блок данного уровня.

[288] Каждый блок данного уровня блоков содержит определенное заранее определенное количество примеров обучающих объектов. Исключительно в качестве примера, данный блок 310 первого уровня из блоков 302 первого уровня содержит 100 упорядоченных обучающих объектов. В изображенном примере блоки 302 первого уровня содержат два данных блока 310 первого уровня (содержащих 100 обучающих объектов каждый или 200 обучающих объектов суммарно).

[289] Данный блок 312 второго уровня из блоков 304 второго уровня содержит больше обучающих объектов, чем число обучающих объектов, содержащихся в данном блоке 310 первого уровня. В представленном варианте осуществления технологии, число обучающих объектов, хранящихся в данном блоке 312 второго уровня, в два раза превышает число обучающих объектов, хранящихся в данном блоке 310 первого уровня.

[290] В частности, если данный блок 310 первого уровня содержит 100 упорядоченных обучающих объектов, то данный блок 312 второго уровня содержит 200 упорядоченных обучающих объектов. Это, в свою очередь, означает, что данный блок 312 второго уровня (например, первый данный блок 312 второго уровня) может содержать те же упорядоченные обучающие объекты, что и два данных блока 310 первого уровня. Однако некоторые из блоков 312 второго уровня (например, второй блок 312 второго уровня) обладают упорядоченными обучающими объектами, которые не принадлежат ни к одному из блоков 310 первого уровня.

[291] Таким образом, можно сказать, что данный обучающий объект может выделяться в несколько блоков из множества 301 блоков. Например, 105-й обучающий объект расположен во: втором данном блоке 302 первого уровня, содержащего 100 упорядоченных обучающих объектов, первом данном блоке 312 второго уровня, содержащем 200 упорядоченных обучающих объектов, первом данном блоке третьего уровня (не пронумерован), содержащем 700 обучающих объектов, первом блоке четвертого уровня (не пронумерован), содержащем 800 обучающих объектов, и т.д.

[292] В качестве другого примера, 105-й обучающий объект расположен в: ни одном из блоков 302 первого уровня, содержащего 100 упорядоченных обучающих объектов, втором данном блоке 312 второго уровня, содержащем 200 упорядоченных обучающих объектов, первом данном блоке третьего уровня (не пронумерован), содержащем 700 обучающих объектов, первом блоке четвертого уровня (не пронумерован), содержащем 800 обучающих объектов, и т.д.

[293] В широком смысле, ведущий сервер 510 и/или ведомые серверы 520, 522, 524 вычисляют аппроксимации обучающих объектов, расположенных, например, в первом данном блоке 312 второго уровня, содержащем 200 обучающих объектов, рассчитаны на основе всех обучающих объектов, расположенных в нем, и ни на одном из обучающих объектов, расположенных во втором данном блоке второго уровня (не пронумерован). Поэтому для обучающих объектов, расположенных в первом данном блоке 312 второго уровня, содержащем 200 обучающих объектов, используется "прошлое" всех обучающих объектов, расположенных в нем.

[294] Для иллюстрации рассмотрим 205-ый обучающий объект. Ведущий сервер 510 и/или ведомые серверы 520, 522, 524 рассчитывают аппроксимации для 205-го обучающего объекта на основе тех блоков, где 205-ый обучающий объект расположен (и всех расположенных там обучающих объектов) - т.е. второго данного блока 312 второго уровня, содержащего 200 упорядоченных обучающих объектов, первого данного блока третьего уровня (не пронумерован), содержащего 700 обучающих объектов, первого данного блока четвертого уровня (не пронумерован), содержащего 800 обучающих объектов, и т.д. Когда ведущему серверу 510 и/или ведомым серверам 520, 522, 524 необходимо рассчитать аппроксимации для 407-го обучающего объекта на основе 205-го обучающего объекта, расположенного в том же листе, что и 407-ой обучающий объект (т.е. на основе "прошлого" 407-го обучающего объекта), ведущий сервер 510 и/или ведомые серверы 520, 522, 524 используют аппроксимации 205-го обучающего объекта на основе исключительно первого блока третьего уровня (не пронумерован), т.е. наибольшего блока, который не содержит "будущее" 407-го обучающего объекта.

[295] Другими словами, для вычисления значения прогноза для данного обучающего объекта, расположенного в данном листе, ведущий сервер 510 и/или ведомые серверы 520, 522, 524 используют аппроксимации "соседних" обучающих объектов (т.е. тех обучающих объектов, которые расположены в том же листе и расположены "раньше" в упорядоченном списке обучающих объектов). Аппроксимации соседних обучающих объектов принимаются исходя из наибольшего блока, который не содержит данный обучающий объект, другими словами, исходя из наибольшего куска, не содержащего данные о "будущем" данного обучающего объекта.

[296] В некоторых вариантах осуществления настоящей технологии, ведущий сервер 510 и/или ведомые серверы 520, 522, 524 могут заранее организовать множество упорядоченных списков обучающих объектов, т.е. создавать различные "линии времени". В некоторых вариантах осуществления настоящей технологии, ведущий сервер 510 и/или ведомые серверы 520, 522, 524 создают заранее определенное число упорядоченных списков, например, три (исключительно в качестве примера). Другими словами, ведущий сервер 510 и/или ведомые серверы 520, 522, 524 создают первый упорядоченный список обучающих объектов, второй упорядоченный список обучающих объектов и третий упорядоченный список обучающих объектов. Далее, в процессе работы, для каждого прогноза ведущий сервер 510 и/или ведомые серверы 520, 522, 524 могут использовать случайно выбранный из первого упорядоченного списка обучающих объектов, второго упорядоченного списка обучающих объектов и третьего упорядоченного списка обучающих объектов. В альтернативных вариантах осуществления настоящей технологии, ведущий сервер 510 и/или ведомые серверы 520, 522, 524 могут использовать случайно взятый из первого упорядоченного списка обучающих объектов, второго упорядоченного списка обучающих объектов и третьего упорядоченного списка обучающих объектов для каждого дерева решений из ансамбля деревьев решений.

[297] С учетом вышеописанной архитектуры возможно реализовать способ определения параметра качества прогноза для дерева решений в прогностический модели дерева решений. Данный уровень дерева решений обладает по меньшей мере одним узлом, параметр качества прогноза предназначен для оценки качества прогноза прогностической модели дерева решений на данной итерации обучения дерева решений, причем данная итерация обучения дерева решений обладает по меньшей мере одной предыдущей итерацией обучения предыдущего дерева решений, дерево решений и предыдущее дерево решений образуют ансамбль деревьев, созданный с помощью техники бустинга деревьев решений.

[298] Способ может выполняться системой машинного обучения, которая выполняет прогностическую модель дерева решений, Например, способ 1100 может выполняться ведущим сервером 510 и/или ведомыми серверами 520, 522, 524. На Фиг. 13 представлена блок-схема способа 1300, который выполняется в соответствии с неограничивающими вариантами осуществления настоящей технологии.

[299] 1302 - получение доступа, с постоянного машиночитаемого носителя системы машинного обучения, к набору обучающих объектов, причем каждый обучающий объект из набора обучающих объектов включает в себя указание на документ и целевое значение, связанное с документом

[300] Способ 1300 начинается на этапе 1302, где ведущий сервер 510 и/или ведомые сервера 520, 522, 524 получают доступ, с постоянного машиночитаемого носителя системы машинного обучения, к набору обучающих объектов, причем каждый обучающий объект из набора обучающих объектов включает в себя указание на документ и целевое значение, связанное с документом.

[301] 1304 - организация набора обучающих объектов в упорядоченный список обучающих объектов, причем упорядоченный список обучающих объектов организован таким образом, что для каждого обучающего объекта в упорядоченном списке обучающих объектов существует по меньшей мере один из: (i) предыдущий обучающий объект, который находится до данного обучающего объекта и (ii) последующий обучающий объект, который находится после данного обучающего объекта

[302] На этапе 1304 ведущий сервер 510 и/или ведомые серверы 520, 522, 524 осуществляют организацию набора обучающих объектов в упорядоченный список обучающих объектов, причем упорядоченный список обучающих объектов организован таким образом, что для каждого обучающего объекта в упорядоченном списке обучающих объектов существует по меньшей мере один из: (i) предыдущий обучающий объект, который находится до данного обучающего объекта и (ii) последующий обучающий объект, который находится после данного обучающего объекта

[303] 1306 - спуск набора обучающих объектов по дереву решений таким образом, что каждый из набора обучающих объектов классифицируется моделью дерева решений на данной итерации обучения в данный дочерний узел из по меньшей мере одного узла данного уровня дерева решений

[304] На этапе 1306, ведущий сервер 510 и/или ведомые серверы 520, 522, 524 спускают набор обучающих объектов по дереву решений таким образом, что каждый из набора обучающих объектов классифицируется моделью дерева решений на данной итерации обучения в данный дочерний узел из по меньшей мере одного узла данного уровня дерева решений

[305] 1308 - создание параметра качества прогноза для данного уровня дерева решений путем: создания для данного обучающего объекта, который классифицирован в данный дочерний узел, параметра аппроксимации качества прогноза, причем создание выполняется на основе: целевых значений только тех обучающих объектов, которые находятся раньше обучающего объекта в упорядоченном списке обучающих объектов; и по меньшей мере одного параметра аппроксимации качества прогноза данного обучающего объекта, созданного во время предыдущей итерации обучения предыдущего дерева решений

[306] На этапе 1308, ведущий 510 и/или ведомые сервера 520, 522, 524 1308 создают параметр качества прогноза для данного уровня дерева решений путем: создания для данного обучающего объекта, который классифицирован в данный дочерний узел, параметра аппроксимации качества прогноза, причем создание выполняется на основе: целевых значений только тех обучающих объектов, которые находятся раньше обучающего объекта в упорядоченном списке обучающих объектов; и по меньшей мере одного параметра аппроксимации качества прогноза данного обучающего объекта, созданного во время предыдущей итерации обучения предыдущего дерева решений.

[307] Опциональные усовершенствования способа 1300

[308] В некоторых вариантах осуществления способа 1300, способ 1300 дополнительно включает в себя вычисление указания на по меньшей мере один параметр аппроксимации качества данного обучающего объекта, созданного во время предыдущей итерации обучения предыдущего дерева решений.

[309] В некоторых вариантах осуществления способа 1300, вычисление включает в себя: разделение упорядоченного списка обучающих объектов на множество блоков, причем множество блоков организовано по меньшей мере в два уровня блоков.

[310] В некоторых вариантах осуществления способа 1300, блок данного уровня блоков содержит первое заранее определенное число обучающих объектов, и причем блок более низкого уровня блоков содержит другое заранее определенное число обучающих объектов, другое заранее определенное число обучающих объектов превышает первое заранее определенное число обучающих объектов.

[311] В некоторых вариантах осуществления способа 1300, блок данного уровня блоков содержит первое заранее определенное число обучающих объектов, и причем блок более низкого уровня блоков содержит первое заранее определенное число обучающих объектов и второй набор обучающих объектов, расположенный сразу после первого заранее определенного числа обучающих объектов в упорядоченном списке, причем число обучающих объектов во втором наборе обучающих объектов также что, что и заранее определенное число обучающих объектов.

[312] В некоторых вариантах осуществления способа 1300, вычисление указания на по меньшей мере один параметр аппроксимации качества данного обучающего объекта, созданного во время предыдущей итерации обучения предыдущего дерева решений, включает в себя: для данного обучающего объекта вычисление по меньшей мере одного параметра аппроксимации качества на основе обучающих объектов, расположенных в том же блоке, что и данный обучающий объект.

[313] В некоторых вариантах осуществления способа 1300, создание параметра качества прогноза для данного уровня дерева решений включает в себя: использование параметров аппроксимации качества прошлых обучающих объектов, расположенных в наибольшем блоке, который не содержит данный обучающий объект.

[314] В некоторых вариантах осуществления способа 1300, организация набора обучающих объектов в упорядоченный список обучающих объектов включает в себя: создание множества упорядоченных списков обучающих объектов, причем каждый из множества упорядоченных списков обучающих объектов организован таким образом, что для каждого обучающего объекта в упорядоченном списке обучающих объектов существует по меньшей мере один из: (i) предыдущий обучающий объект, который находится до данного обучающего объекта и (ii) последующий обучающий объект, который находится после данного обучающего объекта; данный упорядоченный список из множества упорядоченных списков обучающих объектов обладает, по меньшей мере частично, отличающимся порядком от других упорядоченных списков во множестве упорядоченных списков обучающих объектов.

[315] В некоторых вариантах осуществления способа 1300, способ 1300 далее включает в себя выбор одного из множества упорядоченных списков обучающих объектов.

[316] В некоторых вариантах осуществления способа 1300, выбор осуществляется для каждой итерации создания параметра качества прогноза.

[317] В некоторых вариантах осуществления способа 1300, выбор осуществляется в процессе проверки качества прогноза для данного дерева решений.

[318] В некоторых вариантах осуществления способа 1300, набор обучающих объектов связан с присущими им временными отношениями обучающих объектов, и причем организация набора обучающих объектов в упорядоченный список обучающих объектов включает в себя организацию набора обучающих объектов в соответствии с временными отношениями.

[319] В некоторых вариантах осуществления способа 1300, набор обучающих объектов не связан с присущими им временными отношениями обучающих объектов, и причем организация набора обучающих объектов в упорядоченный список обучающих объектов включает в себя организацию набора обучающих объектов в соответствии с правилом.

[320] В некоторых вариантах осуществления способа 1300, набор обучающих объектов не связан с присущими им временными отношениями обучающих объектов, и причем организация набора обучающих объектов в упорядоченный список обучающих объектов включает в себя организацию набора обучающих объектов в соответствии со случайно созданным порядком.

[321] Конкретные варианты осуществления настоящей технологии могут быть реализованы с помощью различных математических принципов, закодированных в соответствующие исполняемые на компьютере инструкции для выполнения различных описанных здесь способов и процедур. Примером подобных принципов может быть статья, озаглавленная "Борьба искажениями при динамическом бустинге" под авторством Дорогуш и др., поданная в Библиотеку Корнеллского Университета 28 января 2017 года, и доступная по следующей ссылке: https://arxiv.org/abs/1706.09516; содержимое этой статьи в полном объеме включено в настоящее описание).

[322] Важно иметь в виду, что не все упомянутые здесь технические результаты могут проявляться в каждом варианте осуществления настоящей технологии. Например, варианты осуществления настоящей технологии могут быть выполнены без проявления некоторых технических результатов, другие могут быть выполнены с проявлением других технических результатов или вовсе без них.

[323] Некоторые из этих этапов, а также процессы передачи-получения сигнала являются хорошо известными в данной области техники и поэтому для упрощения были опущены в некоторых частях данного описания. Сигналы могут быть переданы-получены с помощью оптических средств (например, опто-волоконного соединения), электронных средств (например, проводного или беспроводного соединения) и механических средств (например, на основе давления, температуры или другого подходящего параметра).

[324] Модификации и улучшения вышеописанных вариантов осуществления настоящей технологии будут ясны специалистам в данной области техники. Предшествующее описание представлено только в качестве примера и не устанавливает никаких ограничений. Таким образом, объем настоящей технологии ограничен только объемом прилагаемой формулы изобретения.

1. Способ определения параметра качества прогноза для дерева решений в прогностической модели дерева решений,

данный уровень дерева решений обладает по меньшей мере одним узлом,

параметр качества прогноза используется для оценки качества прогноза прогностической модели дерева решений на данной итерации обучения дерева решений,

способ выполняется системой машинного обучения, которая выполняет прогностическую модель дерева решений,

способ включает в себя:

получение доступа, с постоянного машиночитаемого носителя системы машинного обучения, к набору обучающих объектов, причем каждый обучающий объект из набора обучающих объектов включает в себя указание на документ и цель, связанную с документом;

организацию набора обучающих объектов в упорядоченный список обучающих объектов, причем упорядоченный список обучающих объектов организован таким образом, что для каждого обучающего объекта в упорядоченном списке обучающих объектов существует по меньшей мере один из:

(i) предыдущий обучающий объект, который находится до данного обучающего объекта, и

(ii) последующий обучающий объект, который находится после данного обучающего объекта;

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

создание параметра качества прогноза для дерева решений путем:

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

2. Способ по п. 1, дополнительно включающий в себя:

для данного узла, обладающего по меньшей мере одним обучающим объектом, классифицированным в дочерний узел данного узла:

объединение в один прогностический параметр качества прогноза уровня узла параметров качества прогноза по меньшей мере одного обучающего объекта.

3. Способ по п. 2, в котором объединение в один прогностический параметр качества прогноза уровня узла параметров качества прогноза по меньшей мере одного обучающего объекта включает в себя одно из:

добавление всех параметров качества прогноза по меньшей мере одного обучающего объекта, создание среднего из параметров качества прогноза по меньшей мере одного обучающего объекта и применение формулы к параметрам качества прогноза по меньшей мере одного обучающего объекта.

4. Способ по п. 1, дополнительно включающий в себя:

для данного уровня дерева решений, данный уровень обладает по меньшей мере одним узлом, объединение в общеуровневый параметр качества прогноза, параметр качества прогноза уровня узла, параметры качества прогноза по меньшей мере одного узла.

5. Способ по п. 1, в котором спуск включает в себя:

спуск набора обучающих объектов по дереву решений в порядке обучающего объекта в упорядоченном списке обучающих объектов.

6. Способ по п. 5, в котором создание параметра качества прогноза для данного обучающего объекта, обладающего данной позицией в упорядоченном списке обучающих объектов, включает в себя:

создание параметра качества прогноза на основе целей только тех обучающих объектов, которые (i) находятся до данной позиции данного обучающего объекта в упорядоченном списке обучающих объектов и (ii) категоризованы в один и тот же лист.

7. Способ по п. 1, в котором организация набора обучающих объектов в упорядоченный список обучающих объектов включает в себя:

создание множества упорядоченных списков обучающих объектов, каждый из множества упорядоченных списков обучающих объектов, причем упорядоченный список обучающих объектов организован таким образом, что для каждого обучающего объекта в упорядоченном списке обучающих объектов существует по меньшей мере один из:

(i) предыдущий обучающий объект, который находится до данного обучающего объекта, и

(ii) последующий обучающий объект, который находится после данного обучающего объекта;

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

8. Способ по п. 7, который далее включает в себя выбор одного из множества упорядоченных списков обучающих объектов.

9. Способ по п. 8, в котором выбор осуществляется для каждой итерации создания параметра качества прогноза.

10. Способ по п. 8, в котором выбор осуществляется в процессе проверки качества прогноза для данного дерева решений.

11. Способ по п. 1, в котором набор обучающих объектов связан с присущими им временными отношениями обучающих объектов, и причем организация набора обучающих объектов в упорядоченный список обучающих объектов включает в себя организацию набора обучающих объектов в соответствии с их временными отношениями.

12. Способ по п. 1, в котором набор обучающих объектов не связан с присущими им временными отношениями обучающих объектов, и причем организация набора обучающих объектов в упорядоченный список обучающих объектов включает в себя организацию набора обучающих объектов в соответствии с правилом.

13. Способ по п. 1, в котором набор обучающих объектов не связан с присущими им временными отношениями обучающих объектов, и причем организация набора обучающих объектов в упорядоченный список обучающих объектов включает в себя организацию набора обучающих объектов в случайно созданном порядке.

14. Способ определения параметра качества прогноза в прогностической модели дерева решений,

данный уровень дерева решений обладает по меньшей мере одним узлом,

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

способ выполняется системой машинного обучения, которая выполняет прогностическую модель дерева решений,

способ включает в себя:

получение доступа, с постоянного машиночитаемого носителя системы машинного обучения, к набору обучающих объектов, причем каждый обучающий объект из набора обучающих объектов включает в себя указание на документ и цель, связанную с документом;

организацию набора обучающих объектов в упорядоченный список обучающих объектов, причем упорядоченный список обучающих объектов организован таким образом, что для каждого обучающего объекта в упорядоченном списке обучающих объектов существует по меньшей мере один из:

(i) предыдущий обучающий объект, который находится до данного обучающего объекта, и

(ii) последующий обучающий объект, который находится после данного обучающего объекта;

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

создание параметра качества прогноза для данного уровня дерева решений путем:

создания для данного обучающего объекта, который был классифицирован в данный дочерний узел, параметра аппроксимации качества прогноза, создание выполняется на основе:

целевых значений только тех обучающих объектов, которые находятся до данного обучающего объекта в упорядоченном списке обучающих объектов тренировки; и

по меньшей мере одного параметра аппроксимации качества прогноза данного обучающего объекта, созданного во время предыдущей итерации обучения предыдущего дерева решений.

15. Способ по п. 14, в котором способ дополнительно включает в себя вычисление указания на по меньшей мере один параметр аппроксимации качества данного обучающего объекта, созданного во время предыдущей итерации обучения предыдущего дерева решений.

16. Способ по п. 15, в котором вычисление включает в себя:

разделение упорядоченного списка обучающих объектов на множество блоков, причем множество блоков организовано по меньшей мере в два уровня блоков.

17. Способ по п. 16, в котором блок данного уровня блоков содержит первое заранее определенное число обучающих объектов, и причем блок более низкого уровня блоков содержит другое заранее определенное число обучающих объектов, другое заранее определенное число обучающих объектов превышает первое заранее определенное число обучающих объектов.

18. Способ по п. 16, в котором блок данного уровня блоков содержит первое заранее определенное число обучающих объектов, и причем блок более низкого уровня блоков содержит первое заранее определенное число обучающих объектов и второй набор обучающих объектов, расположенный сразу после первого заранее определенного числа обучающих объектов в упорядоченном списке, причем число обучающих объектов во втором наборе обучающих объектов такое же , что и первое заранее определенное число обучающих объектов.

19. Способ по п. 16, в котором вычисление указания на по меньшей мере один параметр аппроксимации качества данного обучающего объекта, созданного во время предыдущей итерации обучения предыдущего дерева решений, включает в себя:

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

20. Способ по п. 19, в котором создание параметра качества прогноза для данного уровня дерева решений включает в себя:

использование параметров аппроксимации качества предыдущих обучающих объектов, расположенных в наибольшем блоке, не содержащем данный обучающий объект.

21. Способ по п. 14, в котором организация набора обучающих объектов в упорядоченный список обучающих объектов включает в себя:

создание множества упорядоченных списков обучающих объектов, каждый из множества упорядоченных списков обучающих объектов, причем упорядоченный список обучающих объектов организован таким образом, что для каждого обучающего объекта в упорядоченном списке обучающих объектов существует по меньшей мере один из:

(i) предыдущий обучающий объект, который находится до данного обучающего объекта, и

(ii) последующий обучающий объект, который находится после данного обучающего объекта;

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

22. Способ по п. 21, который далее включает в себя выбор одного из множества упорядоченных списков обучающих объектов.

23. Способ по п. 22, в котором выбор осуществляется для каждой итерации создания параметра качества прогноза.

24. Способ по п. 22, в котором выбор осуществляется в процессе проверки качества прогноза для данного дерева решений.

25. Способ по п. 14, в котором набор обучающих объектов связан с присущими им временными отношениями обучающих объектов, и причем организация набора обучающих объектов в упорядоченный список обучающих объектов включает в себя организацию набора обучающих объектов в соответствии с временными отношениями.

26. Способ по п. 14, в котором набор обучающих объектов не связан с присущими им временными отношениями обучающих объектов, и причем организация набора обучающих объектов в упорядоченный список обучающих объектов включает в себя организацию набора обучающих объектов в соответствии с правилом.

27. Способ по п. 14, в котором набор обучающих объектов не связан с присущими им временными отношениями обучающих объектов, и причем организация набора обучающих объектов в упорядоченный список обучающих объектов включает в себя организацию набора обучающих объектов в случайно созданном порядке.

28. Сервер, выполненный с возможностью реализовать алгоритм машинного обучения (MLA), MLA основан на прогностической модели дерева решений на основе дерева решений, причем данный уровень дерева решений обладает по меньшей мере одним узлом, сервер далее выполнен с возможностью осуществлять:

получение доступа, с постоянного машиночитаемого носителя сервера, к набору обучающих объектов, причем каждый обучающий объект из набора обучающих объектов включает в себя указание на документ и цель, связанную с документом;

организацию набора обучающих объектов в упорядоченный список обучающих объектов, причем упорядоченный список обучающих объектов организован таким образом, что для каждого обучающего объекта в упорядоченном списке обучающих объектов существует по меньшей мере один из:

(i) предыдущий обучающий объект, который находится до данного обучающего объекта, и

(ii) последующий обучающий объект, который находится после данного обучающего объекта;

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

создание параметра качества прогноза для данного уровня дерева решений, параметр качества прогноза используется для оценки качества прогноза прогностической модели дерева решений на данной итерации обучения дерева решений, путем:

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

29. Сервер, выполненный с возможностью реализовать алгоритм машинного обучения (MLA), MLA основан на прогностической модели дерева решений на основе дерева решений, причем данный уровень дерева решений обладает по меньшей мере одним узлом, сервер далее выполнен с возможностью осуществлять:

получение доступа, с постоянного машиночитаемого носителя системы машинного обучения, к набору обучающих объектов, причем каждый обучающий объект из набора обучающих объектов включает в себя указание на документ и целевое значение, связанное с документом;

организацию набора обучающих объектов в упорядоченный список обучающих объектов, причем упорядоченный список обучающих объектов организован таким образом, что для каждого обучающего объекта в упорядоченном списке обучающих объектов существует по меньшей мере один из:

(i) предыдущий обучающий объект, который находится до данного обучающего объекта, и

(ii) последующий обучающий объект, который находится после данного обучающего объекта;

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

создание параметра качества прогноза для данного уровня дерева решений, параметр качества прогноза предназначен для оценки качества прогноза прогностической модели дерева решений на данной итерации обучения дерева решений, причем данная итерация обучения дерева решений обладает по меньшей мере одной предыдущей итерацией обучения предыдущего дерева решений, дерево решений и предыдущее дерево решений образуют ансамбль деревьев, созданный с помощью техники бустинга деревьев решений, путем:

создания для данного обучающего объекта, который был классифицирован в данный дочерний узел, параметра аппроксимации качества прогноза, создание выполняется на основе:

целевых значений только тех обучающих объектов, которые находятся до данного обучающего объекта в упорядоченном списке обучающих объектов тренировки; и

по меньшей мере одного параметра аппроксимации качества прогноза данного обучающего объекта, созданного во время предыдущей итерации обучения предыдущего дерева решений.

30. Способ определения параметра качества прогноза в прогностический модели дерева решений,

данный уровень дерева решений обладает по меньшей мере одним узлом,

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

способ выполняется системой машинного обучения, которая выполняет прогностическую модель дерева решений,

способ включает в себя:

получение доступа, с постоянного машиночитаемого носителя системы машинного обучения, к набору обучающих объектов, причем каждый обучающий объект из набора обучающих объектов включает в себя указание на документ и цель, связанную с документом;

организацию набора обучающих объектов в упорядоченный список обучающих объектов, причем упорядоченный список обучающих объектов организован таким образом, что для каждого обучающего объекта в упорядоченном списке обучающих объектов существует по меньшей мере один из:

(i) предыдущий обучающий объект, который находится до данного обучающего объекта, и

(ii) последующий обучающий объект, который находится после данного обучающего объекта;

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

создание параметра качества прогноза для данного уровня дерева решений путем:

создания для данного обучающего объекта, который был классифицирован в данный дочерний узел, параметра аппроксимации качества прогноза, создание выполняется на основе:

целевых значений только тех обучающих объектов, которые находятся до данного обучающего объекта в упорядоченном списке обучающих объектов тренировки; и

не менее одного параметра аппроксимации качества прогноза данного обучающего объекта, сформированного в ходе предыдущей итерации обучения предыдущего дерева решений;

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



 

Похожие патенты:

Изобретение относится к вычислительной технике. Технический результат – повышение точности определения наличия у пользователя интереса к словам, отсутствующим в диалоговой информации пользователя.

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

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

Изобретение относится к способу моделирования оптимального варианта топологического размещения множества информационно взаимосвязанных абонентов на заданном фрагменте сети связи общего пользования.

Изобретение относится к области вычислительной техники и может быть использовано для интерпретации работы моделей искусственных нейронных сетей. Техническим результатом является повышение качества и точности интерпретации работы искусственной нейронной сети.

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

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

Изобретение относится к области прогнозирования преступлений. Технический результат заключается в повышении точности прогноза.

Изобретение относится к области вычислительной техники. Технический результат заключается в сокращении времени создания адекватной модели.

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

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

Изобретение относится к вычислительной технике. Технический результат – предоставление логических ответов, которые подражают стилю речи пользователя.

Группа изобретений относится к вычислительной технике и может быть использована для создания прогностической модели. Техническим результатом является обеспечение преобразования значения категориального фактора в его числовое представление.

Изобретение относится к вычислительной технике. Технический результат – обеспечение перевода исходного предложения целевым предложением.

Изобретение относится к области вычислительной техники. Техническим результатом является формирование алгоритма машинного обучения, использующего модель дерева решений и предназначенного для классификации объектов, обладающих значением категориального фактора, которое преобразуется в его числовое представление.

Изобретение относится к области вычислительной техники и может быть использовано для интерпретации работы моделей искусственных нейронных сетей. Техническим результатом является повышение качества и точности интерпретации работы искусственной нейронной сети.

Группа изобретений относится к ранжированию элементов, а именно к способам и системам определения ранжированных позиций ненативных элементов с помощью системы ранжирования.

Изобретение относится к способу и системе информационного моделирования бизнес-процессов жизненного цикла производственного объекта. Технический результат заключается в автоматизации информационного моделирования.

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

Изобретение относится к области техники и информатики, а более конкретно - к способу автоматизированного сбора и подготовки данных для мониторинга и моделирования сложной технической системы.
Наверх