МОБ 6. Расширенный алгоритм динамической интерактивной кластеризации
Критика алгоритма, предложенного ранее в гл. 4
Давайте теперь вернемся к нашему первоначальному алгоритму кластеризации (гл. 4) и хорошенько покритикуем его. Во-первых, этот алгоритм исходит из того, что сначала участники понабросали в общий котел аж несколько сотен предложений (все - на одну и ту же тему, по одной и той же обсуждаемой проблеме), затем по многим из них (по крайней мере по тем, что получили высокие оценки качества) выразили свое согласие (или несогласие), так что мы можем говорить о «группе поддержки» каждого предложения, - и вот теперь, наконец, система разобьет на кластеры все это пока еще не структурированное множество предложений, так что участники смогут увидеть, что они все сообща совершили. И при этом - во-вторых - есть риск, что картина окажется тут и там настолько неполной, что системе придется посылать участникам дополнительные запросы на оценку некоторых предложений.
В главе 5 мы, наоборот, попытались описать самое начало обсуждения, т.е. процесс подачи первых предложений и первых комментариев по ним. Понятно, что возможности участников на этом начальном этапе и на дальнейших этапах весьма различаются: пока предложений всего несколько (одно, два,... ну, скажем, до 10, максимум до 20), внимательный участник может просмотреть их все, может быть прокомментировать, и только потом подать свое собственное новое предложение, которое будет как-то опираться на предыдущие предложения других авторов. Когда же предложений станет намного больше этого максимума, почти никто из участников не будет иметь ни возможности, ни желания просматривать их все - вот тут-то и ему понадобится представление всех поданных предложений (и комментариев к ним) в виде совокупности «ранжированных кластеров». При этом нам представляется, что между начальной ситуацией, описанной в главе 5, и «сильно запущенной» ситуацией, представленной в главе 4, находится некоторая зона, скажем, от 15 до 100 предложений, когда кластеризация уже стала необходимой для продолжения осмысленного обсуждения, но количество предложений еще не настолько велико, чтобы можно было применить «грубый» метод главы 4.
Из сказанного вытекает, что, поскольку количество поданных предложений возрастает постепенно, столь же постепенно меняя «условия работы» участников, наш алгоритм кластеризации должен приспосабливаться к этим количественным изменениям: он должен быть эффективен и при совсем маленьком количестве предложений, и при очень большом. Более того, если на каждом этапе наш алгоритм будет достаточно осмысленно кластеризовать всю накопившуюся совокупность предложений, то эта совокупность будет расти медленнее, потому что многие участники будут совершенно оправданно отказываться от желания подать свое предложение, увидев нечто близкое, что уже было кем-то предложено.
Конечно, можно разработать два или три разных алгоритма для разных диапазонов количества предложений, и переключаться с одного алгоритма на другой при переходе из одного диапазона в следующий. Но гораздо лучше сгладить эти переходы, например включив в наш алгоритм действия «для малого количества предложений» и «для большого количества предложений», так что вообще говоря и те и другие могут выполняться при каждом конкретном количестве предложений, но, скажем, в разных пропорциях: с увеличением числа поданных предложений доля действий первого типа уменьшается, а второго - возрастает. А еще лучше будет, если мы сможем составить единый набор системных действий, для которых один и тот же универсальный алгоритм будет использоваться при самом разном количестве предложений. Именно этот последний вариант мы и попытаемся описать.
Что же это за «действия»? со стороны участников - это действия по оценке (индивидуальной или сравнительной) различных предложений. Эти действия могут производиться участниками как по собственной инициативе, так и в ответ на запросы со стороны системы. Со стороны системы - это действия по подаче таких запросов участникам; в свою очередь, запросы могут посылаться в большей или меньшей мере случайно, вплоть до вполне детерминированной ситуации, когда системе нужна оценка именно этого предложения именно этим участником.
Таким образом, «продвинутый» алгоритм кластеризации должен быть динамическим и в высшей степени интерактивным. Он должен уметь выполнять кластеризацию при любом числе поданных предложений, должен работать постоянно (или запускаться достаточно часто), и на каждом этапе должен тщательно выбирать, кому какие запросы посылать. При этом важно достичь оптимального соответствия между качеством кластеризации и количеством запросов, рассылаемых системой участникам, с целью минимизации совокупных усилий сообщества участников. Следует при этом учитывать, что разные виды запросов требуют разного уровня усилий от их исполнителей; например, выразить степень своего согласия с конкретным предложением - совсем не такая трудоемкая акция, как сравнить два предложения и выявить, в каком отношении они находятся друг к другу.
Из всего этого затянувшегося вводного рассуждения следует, что нам надо для начала составить список видов элементарных «оценочных действий» пользователей, плюс к тем, самым простым, о которых мы говорили в главе 3.
Расширенный набор оценочных действий участников
Попытаемся представить себе, какие оценочные действия могут быть запрошены системой - когда, у кого, в каких ситуациях; а также, в какой мере естественно и просто будет участнику, получившему от системы запрос, выполнить его в конкретной ситуации. Сначала рассортируем эти ситуации. Совокупность действий системы по контролю над действиями участников, а также по содействию участникам в выполнении требований системы будем называть системным контролем и содействием (сокращенно «СКС»). В какой-то мере мы воспользуемся здесь терминами и формализмом, введенными выше в главе 5.
1) Пусть участник X написал некий текст и хочет подать его как свой новый пост в данном обсуждении. Понятно, что без какого-либо контроля (и содействия) системы, это будет просто некий новый пост (выступление) участника X, лишенный структуры, а может быть даже и без указания конкретной категории постов - предложение, аргумент(ы) за или против... Поскольку наша система не занимается текстовым анализом постов, а только обрабатывает структурированную и формализованную информацию, вводимую участниками в связи с постами, такой «голый» пост представляет для нее весьма малую ценность.
Какая-то структурированная и формализованная информация может быть затребована у автора поста в момент его подачи или сразу после:
(А) Текст поста, составленный участником X1, не будет принят системой к рассмотрению, если не заполнены следующие рубрики, сопровождающие его и являющиеся частью поста:
(а1) Категория: предложение, аргументация за, аргументация против, (здесь также могут появиться такие категории, как «дополнительная информация к другому посту», «дополнительная информация по обсуждаемому вопросу», а также, возможно, еще какие-то другие).
(а2) Краткое резюме поста (не более чем столько-то знаков, допустим, две строчки установленной длины, чтобы можно было представить этот пост вместе с другими в табличном виде), в случае если сам пост достаточно длинный.
(а3) Если в тексте есть ссылки на другие посты - отношение автора к каждому из них (pro, contra и т.д., как обсуждалось в предыдущей главе.
Понятно, что если данный пост - первое поданное предложение, то в нем не может быть ссылок на другие посты, так что пункт (а3) не применим. Если же данный пост - не первый, то может быть две ситуации:
(Б) Пост не содержит явных ссылок на какие-то другие посты (например, на другие предложения), но неявно (описательно) они в нем упоминаются. Чтобы выявить такие неявные ссылки, система может задать автору вопрос:
(б1) «Все ли посты (Ваши или других авторов), которые Вы обсуждаете в данном посте, явно перечислены в заполненной Вами рубрике (а3)? Если нет, продолжите ее заполнение, вставив внутренние ссылки на эти обсуждаемые Вами посты»
Заметим, что пользовательский интерфейс системы должен предоставлять удобную возможность автоматически генерировать такие «внутренние ссылки» на посты (или их «дискурсивные элементы», об этом будет в одной из следующих глав) и вставлять их в новый пост в процессе его написания или редактирования. Например это может быть такая последовательность действий: открыть цитируемый или комментируемый пост, щелкнуть по нему правой кнопкой мыши и выбрать опцию «копировать ссылку» (или нажать определенную «горячую комбинацию клавиш»), затем вставить ссылку в редактируемый пост. Другой вариант - экран делится на два окна, в одном - то, что пишешь, в другом - то, что читаешь и комментируешь. Второй вариант представляется более оправданным, «интуитивным». Мы посвятим пользовательскому интерфейсу одну из следующих глав.
Вторая ситуация - автор нового поста отрицательно ответил на вопрос (б1), но тем не менее система (по некоторым заложенным в нее критериям, которые мы обсудим ниже) считает, что автору следовало бы сделать дополнительные усилия в помощь системе по «размещению» нового поста относительно каких-то предыдущих. Это касается в первую очередь (а может быть и исключительно) постов, содержащих предложения. Поскольку автор сам не охарактеризовал свое предложение в сравнении с другими поданными ранее, система может прислать ему, например, такой запрос:
(б2) «Можете ли Вы указать какие-то уже поданные предложения, к которым Ваше относится следующим образом:»
Дальше может следовать список опций вроде описанных в главе 5, куда автор может вставлять ссылки на конкретные посты; либо он вставляет в предложенную ему форму ссылку на некоторое предложение, и появляется список возможных вариантов взаимоотношений между этим предложением и новым предложением автора.
Другой вариант - система просит автора сравнить свое предложение с другими предложениями, но уже конкретно предлагаемыми системой:
(б3) «Пожалуйста, сравните Ваше предложение по отдельности с каждым из следующих:»
При этом предложения, предлагаемые для сравнения, могут быть как ранее оцененными автором, или просто прочитанные /просмотренные им (система может вести учет этим действиям), так и совершенно еще не знакомыми автору. Критерий выбора предложений для сравнения с данным должен быть отдельно разработан и запрограммирован (заложен в систему).
Заметим, что запросы типов (б2) и (б3) могут в принципе присылаться автору не только сразу после подачи его нового предложения, но и позднее, например когда системе требуются дополнительные сведения от участников, для более точной кластеризации.
2) Несколько иная ситуация - когда системе требуются дополнительные сравнительные оценки между некоторыми предложениями, не в связи с подачей какого-то нового предложения, а чтобы произвести более надежную кластеризацию. Тут могут быть полезны запросы, являющиеся обобщением запросов типа (б3):
(в1) «Пожалуйста, сравните между собой попарно следующие предложения:»
Для подачи такого запроса система должна не только выбрать те несколько предложений, сравнение которых ей сейчас нужнее всего, но и выбрать предположительно оптимальным образом того или тех участников, к которым должны быть обращены эти запросы.
Понятно, что попросить выполнить что-то, относящееся к данному посту, у автора этого поста - гораздо легче, чем просить выполнить то же сравнение у участника, не являющегося автором ни одного из сравниваемых постов. Здесь может быть две стратегии, у каждой из которых имеются свои преимущества:
- Послать запросы о сравнении данных предложений каждому из их авторов (это будут рассмотренные выше «отложенные» запросы типа (б3)), и затем каким-то образом агрегировать полученные от всех авторов результаты.
- Послать такие же запросы «посторонним» участникам (одному или более). Результаты будут, возможно, более объективными, но склонить «посторонних» участников к выполнению таких запросов будет, вообще говоря, труднее.
«Не вполне посторонние» участники - те, кто уже как-то оценил или прокомментировал одно (или оба, или более) сравниваемых предложений; возможно, они и будут первыми кандидатами на получение запросов на выполнение попарного (или тройственного, или множественного) сравнения.
Другой вопрос, ответ на который трудно дать в настоящее время - что предпочтительнее: посылать отдельные запросы на попарные сравнения (и, возможно, более широкому кругу участников), или просить сразу сравнить три или более предложений.
Использование оценок качества постов в процессе их кластеризации
В одной из предыдущих глав мы уже говорили, что оценки качества в основном должны использоваться не для кластеризации, а для относительного ранжирования постов, попавших в один и тот же кластер. Действительно, «самый лучший» пост в каком-нибудь кластере может быть существенно «ниже» по абсолютной оценке качества, чем «самые лучшие» посты в других кластерах; он, тем не менее, может выражать, хотя и не лучшим образом, совершенно обособленную идею, так что нет никаких оснований «вливать» его в какой-нибудь другой кластер.
Оставаясь верными этому принципу, давайте вспомним, однако, что при количестве постов-предложений, скажем, 500, число их попарных сравнений будет 500 в квадрате, т.е. 250 тысяч, т.е очевидным образом намного больше, чем допустимая нагрузка на сообщество участников обсуждения. Значит, наш алгоритм должен в каждый момент выбирать такие пары постов, сравнение которых даст ему наиболее полезную информацию.
Предлагается следующий метод. Пусть в некоторый момент все (или большинство) из n уже поданных и оцененных постов (более конкретно, предложений) разбиты на k кластеров. Например n=500, k=10. Системе надо поместить новый (или еще недостаточно оцененный) пост P в один из этих кластеров. Обозначим «лучшие» посты имеющихся кластеров как Q1, Q2,... Qk . В соответствии с предлагаемым методом, система должна в первую очередь запрашивать сравнения пар
1>,
2>,...
k> (в каком порядке - отдельный непростой вопрос).
Если эти сравнения выполняются не одновременно, то в какой-то момент кто-то из участников, получивших запрос на сравнение, скажем,
i>, может выдать ответ, означающий, что пост P следует включить в i-ый кластер, т.е. в кластер, представленный постом Qi. Получив такой ответ, система меняет тактику, и посылает другим участникам либо (а) тот же запрос на сравнение
i>, либо, что, может быть, будет разумнее, (б) запросы на сравнение P с другими постами того же i-ого кластера (желательно, расположенными в нем достаточно высоко или даже непосредственно под постом Qi). Запросы типа (б) могут, конечно, посылаться тому же участнику, от которого был получен первый ответ на запрос
i>; но следует, однако, помнить, что система не должна чересчур перегружать никого из участников.
Если ответы на несколько запросов типа (а) и/или типа (б) дают согласованную картину, то пост P помещается в i-ый кластер, даже без выполнения остальных еще не поданных системой «первоначальных» запросов
1>,...
k>. Если полученные ответы не дают согласованной картины, то придется не только продолжить серию «первоначальных» запросов, но и повторить некоторые из них, обратившись к другим участникам; в первую очередь это касается вызвавшего смущение запроса
i>.
Если система получила по-видимому противоречащие друг другу ответы, означающие, что P должно быть включено в два (или более) разных кластеров, скажем, в i-ый и в j-ый, то это можно интерпретировать по-разному: либо сейчас ошибся кто-то из этих двух оценщиков, либо i-ый и в j-ый кластеры следует объединить (т.е. на предыдущем этапе система выполнила разбиение на кластеры неоптимальным образом, например из-за недостатка оценок и сравнений), либо, наконец, предложение P по смыслу таково, что им может быть дополнено как предложение Qi, так и предложение Qj, но при этом само по себе P не является предложением решения поставленной проблемы (заметим, что последний случай, вообще говоря, должен был быть выявлен системой ранее, по результатам заполнения автором предложения P соответствующих системных запросов, как было описано выше.
Наконец, если ответы участников на все первоначальные запросы определенно говорят, что P отличается от всех Q, то система создает для P новый кластер (k+1-ый). Так как создание нового кластера - достаточно ответственное действие, то перед этим системе, наверное, следует опросить «по второму кругу» еще несколько участников, для сравнения P с теми же «лучшими» представителями Q1, Q2,... Qk всех существующих кластеров, либо с другими предложениями, достаточно высоко расположенными в этих кластерах.
Переупорядочение кластеров
Понятно, что в результате включения в какой-нибудь кластер нового предложения P с высокой оценкой качества сам этот кластер будет несколько перетасован; возможно, P теперь станет его «лучшим» предложением. Тут следует, однако, заметить, что абсолютные оценки качества постов, т.е. оценки качества, полученные отдельно для каждого поста сразу после его появления, представляют, вообще говоря, меньший интерес, чем сравнительные оценки качества внутри данного кластера. А если быть еще точнее, то внутри кластера наибольшую ценность представят ответы участников на вопросы системы, касающиеся (сравнительной оценки) представительности различных постов в этом кластере. В первую очередь или исключительно такие вопросы должны быть заданы тем, кто выразил согласие с идеей этого кластера, а значит, максимально заинтересован в его наиболее выигрышном показе другим участникам.
С учетом этого замечания, обсуждавшиеся выше «лучшие» посты Q1, Q2,... Qk существующих кластеров должны пониматься не как «лучшие по первоначальным «абсолютным» оценкам их качества, но как «самые представительные» предложения в своих кластерах. Действительно, предложение Q наивысшего в своем кластере качества может не быть наиболее представительным, потому что какой-то из его аспектов был мало кем поддержан, в то время как другое предложение Q’ в том же кластере получило более широкую поддержку.
Тут мы впервые сталкиваемся с еще одной метрикой - степенью поддержки каждого предложения. Степень поддержки может быть как абсолютной (иначе, глобальной), рассчитанной по всему сообществу участников данного обсуждения, так и относительной (внутри-кластерной); понятно, что только относительная степень поддержки представляет для нас интерес - иначе нарушается наш базовый принцип «защиты меньшинств» в процессе обсуждения данной проблемы.
Сложность алгоритма
Конечно, предложенное выше является лишь наброском полного описания нашего алгоритма «динамической интерактивной кластеризации» предложений; и даже в этом неполном изложении алгоритм представляется чрезвычайно сложным, а во многих местах явно видны лакуны в описании. Сказать по правде, некоторые из этих лакун я пока не заполнил - да и не хотел бы фиксировать все детали на данном этапе разработки.
Дело в том, что, как знают все разработчики софтвера, программирование взаимодействий системы с пользователями - самый громоздкий и трудоемкий аспект разработки системы. Если же номенклатура всех элементарных взаимодействий составлена, и каждое из них запрограммировано как на серверной стороне, так и на стороне пользователя, а «алгоритму» предоставлена возможность достаточно формальным образом комбинировать эти элементарные взаимодействия, запускать примитивы вычисления различных метрик по базе данных системы, а также поиска элементов с конкретными свойствами, и т.д., - то сам алгоритм, после создания его первоначальной версии, может быть достаточно быстро изменен, скажем, от версии N к версии N+1, или даже существовать в двух различных версиях для сравнения их эффективности.
Имея это в виду, мы на данном этапе в первую очередь должны составить разумный и достаточно полный список таких «примитивов» - типов запросов к участникам и их ответов, параметров, вычисляемых метрик и т.д. Вот этим я и занимаюсь в последних двух (и нескольких следующих) главах.