Расчет взаимной информации для выбора обучающего набора в Java

Question

Сценарий

---

Я пытаюсь реализовать контролируемое обучение для набора данных в приложении Java GUI. Пользователю будет предоставлен список предметов или «отчетов» для проверки, и он будет помечать их на основе набора доступных ярлыков. Как только контролируемое обучение будет завершено, помеченные экземпляры будут переданы в алгоритм обучения. Это попытается упорядочить остальные элементы по вероятности того, что пользователь захочет их просмотреть.

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

Пример

---

Здесь искусственный пример может помочь объяснить и может устранить путаницу, когда я, несомненно, использовал неправильную терминологию :-) Рассмотрим пример, в котором приложение отображает новости для пользователя. Он выбирает, какие новости показывать в первую очередь, исходя из показанных предпочтений пользователя. Особенности новостей, которые имеют корреляцию: country of origin, category или date. Таким образом, если пользователь помечает отдельную новость как интересную, когда она пришла из Шотландии, он сообщает обучающемуся машине, что существует повышенная вероятность того, что другие новостные истории из Шотландии будут интересны пользователю. Аналогично для такой категории, как Спорт, или для даты, такой как 12 декабря 2004 года.

Это предпочтение можно рассчитать, выбрав любой порядок для всех новостных сообщений (например, по категории, по дате) или случайным образом упорядочив их, а затем рассчитав предпочтение по мере продвижения пользователя. То, что я хотел бы сделать, это получить своего рода «стартовую позицию» по этому заказу, попросив пользователя просмотреть небольшое количество конкретных новостей и сказать, если они им интересуются (контролируемая часть обучения). Чтобы выбрать, какие истории показывать пользователю, я должен рассмотреть всю коллекцию историй. Вот тут и появляется взаимная информация. Для каждой истории я хочу знать, сколько она может рассказать мне обо всех других историях, когда она классифицируется пользователем. Например, если есть большое количество историй, происходящих из Шотландии, я хочу, чтобы пользователь классифицировал (по крайней мере) одну из них. Аналогично для других коррелирующих функций, таких как категория или дата. Цель состоит в том, чтобы найти примеры отчетов, которые, будучи классифицированными, предоставляют наибольшую информацию о других отчетах.

Задача

---

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

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

Как в моем примере, скажем, у меня было большое количество новых, немаркированных экземпляров этого класса:

public class NewsStory {
    private String countryOfOrigin;
    private String category;
    private Date date;
    // constructor, etc.
}

В моем конкретном сценарии корреляция между полями / объектами основана на точном совпадении , так что, например, разность в дате и 10 лет эквивалентна по своему неравенству.

Коэффициенты для корреляции (например, является ли дата более коррелирующей, чем категория?) Не обязательно равны, но они могут быть предопределены и постоянны. Означает ли это, что результат функции p(x,y) равен предопределенному значению, или я путаю термины?

Вопрос (наконец)

---

Как я могу осуществить взаимный расчет информации, учитывая этот (фальшивый) пример новостных рассказов? Библиотеки, javadoc, примеры кода и т. Д. - все это полезная информация. Кроме того, если этот подход в корне ошибочен, объяснение, почему это так, будет столь же ценным ответом.

---

PS. Мне известны такие библиотеки, как Weka и Apache Mahout, поэтому упоминание о них не очень полезно для меня. Я все еще ищу документацию и примеры для обеих этих библиотек, ища материал по Взаимной информации конкретно. Что мне действительно поможет, так это ссылки на ресурсы (примеры кода, javadoc), где эти библиотеки помогают с взаимной информацией.

Answer 1

Я предполагаю, что ваша проблема что-то вроде ...

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

Если это так, я не думаю, что взаимная информация - это правильная вещь, потому что вы не можете рассчитать MI между двумя экземплярами. Определение MI в терминах случайных величин, а отдельный экземпляр - это не случайная переменная, это просто значение.

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

Я думаю, что предложение Фердистщенко, что вы смотрите на активные методы обучения, является хорошим.

---

В ответ на комментарий Грундлефлека я углублюсь в терминологию, используя его идею аналогии с Java-объектом ...

В совокупности мы использовали термины «экземпляр», «вещь», «отчет» и «пример» для ссылки на классифицируемый объект. Давайте подумаем об этих вещах как об экземплярах класса Java (я оставил шаблонный конструктор):

class Example
{ String f1;
  String f2;
}

Example e1 = new Example("foo", "bar");
Example e2 = new Example("foo", "baz");

Обычная терминология в машинном обучении заключается в том, что e1 является примером , что во всех примерах есть две функции f1 и f2 и что для e1 f1 принимает значение 'foo' и f2 принимает значение «бар». Набор примеров называется набор данных .

Возьмите все значения f1 для всех примеров в наборе данных, это список строк, его также можно рассматривать как распределение. Мы можем думать о функции как о случайной переменной , и что каждое значение в списке является выборкой, взятой из этой случайной переменной. Таким образом, мы можем, например, рассчитать MI между f1 и f2. Псевдокод будет что-то вроде: <pre> mi = 0 for each value x taken by f1: { sum = 0 for each value y taken by f2: { p_xy = number of examples where f1=x and f2=y p_x = number of examples where f1=x p_y = number of examples where f2=y sum += p_xy * log(p_xy/(p_x*p_y)) } mi += sum }

Однако вы не можете рассчитать MI между e1 и e2, просто так не определено.

Answer 2

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

Кроме того, если я вас правильно понимаю, я думаю, что то, что вы пытаетесь сделать, обычно называется активное обучение . Там вам сначала понадобятся исходные помеченные тренировочные данные, которые подаются в ваш алгоритм машинного обучения. Затем ваш классификатор помечает набор немаркированных экземпляров и возвращает значения достоверности для каждого из них. Экземпляры с самыми низкими значениями достоверности, как правило, являются наиболее информативными, поэтому вы показываете их человеку-аннотатору и заставляете его / ее пометить их вручную, добавляете их в свой тренировочный набор, переобучаете свой классификатор и выполняете все заново снова, пока ваш классификатор не будет иметь достаточно высокую точность или пока не будет соблюден какой-либо другой критерий остановки. Поэтому, если это работает для вас, вы можете в принципе использовать любой ML-алгоритм, реализованный в Weka, или любую другую ML-инфраструктуру, если выбранный вами алгоритм способен возвращать доверительные значения (в случае байесовских подходов это будут просто вероятности) .

---

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

Подведем итоги: вы бы хотели обучить классификатор, который может обновляться пользователем. Это классический случай для активного обучения. Но для этого вам нужен начальный классификатор (вы могли бы просто дать пользователю произвольные данные для метки, но я так понимаю, что это не вариант), а для обучения вашего первоначального классификатора вам нужно, по крайней мере, небольшое количество помеченного обучения данные для контролируемого обучения. Тем не менее, все, что у вас есть, это немаркированные данные. Что вы можете сделать с этим?

Ну, вы могли бы кластеризовать их в группы связанных экземпляров, используя один из стандартных алгоритмов кластеризации, предоставляемых Weka, или какой-то конкретный инструмент кластеризации, такой как Cluto . Если вы сейчас возьмете x самых центральных экземпляров каждого кластера (x в зависимости от количества кластеров и терпения пользователя) и попросите пользователя пометить его как интересный или не интересный, вы можете принять этот ярлык для других экземпляров этот кластер также (или, по крайней мере, для центральных). Вуаля, теперь у вас есть обучающие данные, которые вы можете использовать для обучения вашего первоначального классификатора и запуска активного процесса обучения, обновляя классификатор каждый раз, когда пользователь отмечает новый экземпляр как интересный или нет. Я думаю, что то, что вы пытаетесь достичь, вычисляя MI, по сути схоже, но может быть неправильной кареткой для вашего заряда.

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