Глава
Term Weighting in Expert Search Task: Analyzing Communication Patterns?
В книге
Let G = (V,E) be an undirected graph, T ⊆ V be a set of terminals. Then a natural combinatorial problem consists in finding the maximum number of vertex-disjoint paths connecting distinct terminals. For this problem, a clever construction suggested by Gallai reduces it to computing a maximum non-bipartite matching and thus gives an O ( m √n log n 2 /m log n ) -Time algorithm (hereinafter n := |V |, m := |E|). Now let us consider the fractional relaxation, i.e. allow T-path packings with arbitrary nonnegative real weights. It is known that there always exists a half-integral solution, that is, one only needs to assign weights 0, 1/2 , 1 to maximize the total weight of T-paths. It is also known that an optimum half-integral packing can be found in strongly-polynomial time but the actual time bounds are far from being satisfactory. In this paper we present a novel algorithm that solves the half-integral problem within O ( m √n log n 2 /m log n )time, thus matching the complexities of integral and half-integral versions.
Рассмотрим неориентированный граф $G = (VG, EG)$, в котором выделено множество терминалов $T \subseteq VG$, и заданы неотрицательные пропускные способности $c(v)$, а также стоимости $a(v)$ для всех вершин $v\in VG$. Путь в $G$ называется $T$-путем, если его концы представляют собой различные терминалы. Мультипотоком называется функция $F$, приписывающую каждому $T$-пути $P$ неотрицательный рациональный вес $F(P)$. Мультипоток называется допустимым, если сумма весов $T$-путей, проходящих через каждую вершину $v$, не превышает $c(v)$. Величиной $F$ называется сумма весов $F(P)$, а стоимостью $F$ называется сумма (по всем $T$-путям $P$) произведений $F(P)$ на стоимости путей $P$ относительно функции $a$. В данной работе мы обобщаем известные результаты, касающиеся мультипотоков с ограничениями пропускных способностей на ребрах, и доказываем, что задача нахождения мультипотока минимальной стоимости среди мультипотоков, имеющих максимальную величину всегда имеет полуцелое прямое и двойственное решения. Более того, мы описываем сильнополиномиальный алгоритм, строящий такие решения.
We present the results of our enterprise expert search system application to the tasks that were introduced at the Text Retrieval Conference (TREC) in 2005—2007. The expert search system is based on the analysis of content and communications topology in an enterprise information space. During the performed experiments an optimal set of weighting coefficients for three query-candidate associating algorithms is selected for achieving the best search efficiency on a specified corpus. The obtained performance proved to be better than at most TREC participants. The hypothesis of additional efficiency improvement by means of query classification is proposed.
Пусть задан орграф $G = (VG,AG)$. Четным фактором $M \subseteq AG$ называется множество ребер, образованное набором вершинно непересекающихся путей и четных циклов. Четные факторы были введены Гиленом и Каннингхемом, они обобщают т.н. path matchings в неориентированных графах. Задача нахождения четного фактора максимального размера в графе общего вида является NP-трудной, однако для класса нечетно циклически симметричных орграфов эта задача является полиномиальной. К настоящему моменту был известен лишь один комбинаторный способ ее решения, принадлежащий Папу. Этот алгоритм имеет сложность $O(n^4)$ (где $n$ обозначает число вершин в $G$, а $m$ обозначает число ребер). В данной работе мы развиваем новую технику разреженного восстановления и строим алгоритм со сложностью $O(n^3 \log n)$, находящий нечетный фактор максимального размера в нечетно циклически симметричном орграфе. Наш подход также применим к другим аналогичным задачам, например к задаче нахождения максимального простого $b$-паросочетания без квадратов.
Большинство техник машинного обучения ориентированы на обработку структурированных данных, в то время как большая часть доступных данных, как правило, представлена в неструктурированном, в том числе текстовом, виде. Обнаружение концептов - это область извлечения знаний, использующая антропоцентрические методы, ориентированные на выявление глубинной концептуальной структуры данных и активно вовлекающие эксперта в процесс исследований. Семинар был посвящен методам обработки неструктурированной информации и, в первую очередь, превращения ее в структурированную или полуструктурированную. Он затронул самые различные области, такие как извлечение данных из текстов, из сети (в том числе блогов, форумов и социальных сетей), способы обработки неполных данных и самые разнообразные методы - графы, в том числе концептуальные графы, кластеризацию, онтологии. Семинар проходил совместно с конференцией ICFCA 2012, посвященной практическому применению и дополнениям метода FCA (formal concept analysis, формальный анализ концептов) и помимо упомянутого включавшей в себя два семинара - CUBIST (Combining and Uniting Business Intelligence with Semantic Technologies, объединение бизнес-аналитики с семантическими технологиями) и EEML (Experimental Economics and Machine Learning, экспериментальная экономика и машинное обучение), затрагивающими темы использования методов data mining в экономике и бизнес-моделях. Основным направлением проекта БР5 является создание кросс-платформенных систем обработки неструктурированной информации для повышения эффективности управления инновационной деятельностью предприятия, что полностью совпадает с тематикой семинаров. Информация о сотрудниках и оргструктуре компании, коммуникации между сотрудниками компании часто представлена в неструктурированном виде, поэтому важно компенсировать это более совершенными методами обработки.