Оценка коллег - выбор графика, чтобы получить точные рейтинги / рейтинги

Фон. Я пишу некоторый код для полуавтоматической оценки, используя оценку сверстников как часть процесса оценки. Студентам дают пары эссе за один раз, и у студентов есть ползунок, чтобы выбрать, который лучше и насколько он лучше. например, слайдер может выглядеть примерно так:

A---X-B

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

Мой вопрос. Как выбрать пары эссе для студентов?

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

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

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

Что бы вы порекомендовали?

Я думаю, что эту проблему можно смоделировать с помощью неориентированного графа, используя что-то вроде следующего:

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

Это хороший подход? Если нет, то что бы вы порекомендовали вместо этого?

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

Выбор графика

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

Предлагаемое решение. Для этой задачи я предлагаю вам сгенерировать случайный граф , выбранный случайным образом из множества всех 3-регулярных (простых) графов.$G$

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

Возникает вопрос: как выбрать 3-регулярный (простой) граф на вершинах равномерно случайным образом?$n$

К счастью, существуют известные алгоритмы для этого. По сути, вы делаете следующее:

1. Создайте очков. Вы можете думать об этом как 3 копии каждого из$3n$ вершин. Произведите равномерно наугад случайное идеальное совпадение по этим 3 n точкам. (Другими словами, повторяйте следующую процедуру, пока все 3 n точек не будут спарены: выберите любую непарную точку и соедините ее с другой точкой, выбранной случайным образом из множества непарных точек.)$n$$3n$$3n$

2. Для каждых двух точек, которые соответствуют сопоставлению, нарисуйте грань между соответствующими вершинами (копии которых они являются). Это дает вам график по вершинам.$n$

3. Затем проверьте, является ли полученный граф простым (т. Е. У него нет самоконтроля и повторяющихся ребер). Если это не просто, откажитесь от графика и вернитесь к шагу 1. Если это просто, все готово; вывести этот график.

Известно, что эта процедура генерирует равномерное распределение на множестве 3-регулярных (простых) графов. Также известно, что на шаге 3 у вас есть постоянная вероятность принятия результирующего графа, поэтому в среднем алгоритм выполнит испытаний - так что это довольно эффективно (например, время полиномиального прогона).$O(1)$

Я видел, как этот подход приписывают Боллобасу, Бендеру и Канфилду. Подход также кратко изложен в Википедии . Вы также можете найти обсуждение в этом блоге .

Технически говоря, для этого необходимо, чтобы число $n$ было четным (в противном случае не существует 3-регулярного графа на вершинах). Однако с этим легко разобраться. Например, если n нечетно, вы можете случайным образом выбрать одно эссе, отложить его в сторону, сгенерировать случайный 3-регулярный граф на оставшихся эссе, а затем добавить еще 3 ребра из эссе с отложенным просмотром к 3 случайно выбранным другим эссе. (Это означает, что будет 3 эссе, которые фактически оценены 4 раза, но это не должно приносить вреда.)$n$$n$

Ранжирование всех эссе

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

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

Это должно быть идеально для вас. Вы можете рассматривать каждое эссе как игрок. Каждое сравнение между двумя эссе (в процессе оценки сверстников) похоже на результат соответствия между ними. Модель Брэдли-Терри позволит вам взять все эти данные и определить силу для каждого эссе, где более высокие значения соответствуют лучшим эссе. Теперь вы можете использовать эти сильные стороны, чтобы упорядочить все эссе.

Подробности и обсуждение. На самом деле, модель Брэдли-Терри даже лучше, чем вы просили. Вы просили линейное ранжирование, но модель Брэдли-Терри на самом деле дает (реальное число) оценку каждому эссе. Это означает , что вы знаете , не только ли эссе сильнее , чем эссе $i$$j$ , но грубая оценка , как сильно она сильнее. Например, вы можете использовать это, чтобы сообщить свой выбор, какие эссе для оценки.

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

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

Эффективное использование учителя

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

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

• $n$$k$$k$$k$

• $k$$d(e_i,e_j)$$e_i$$e_j$$S$$d(e,S) = \min_{e' \in S} d(e,e')$$e$$S$$k$$e_1,e_2,\dots,e_k$$e_{i+1}$$d(e,\{e_1,e_2,\dots,e_i\})$(из всех эссе$e$$e \notin \{e_1,e_2,\dots,e_i\}$$k$$k$$k$

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

$d(e_1,e_2) = (s(e_1)-s(e_2))^2$$s(e)$$e$$e_1$$e_2$$k$

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

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

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

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

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

[1] зачем использовать ранжирование Elo для алгоритма facemash? переполнение стека

[2] Система рейтинга Эло , Википедия

[3] Pagerank , Википедия

[4] анализ цитирования , википедия