WWW2007/Tuesday

複雑系

WWW2007に来ています。本セッションが始まる前日は併設のワークショップとチュートリアルに割り当てられました。

I3: Identity, Identifiers, Identifications -- Entity-Centric Approaches to Information and Knowledge Management on the Web

午前中は I3 というワークショップに行ってきました。Semantic Web における名前づけについての哲学的な話題から Semantic Web の枠組みを緩めて如何に Semantic Web を普及させるかといった問題意識を持っているようです。そもそも Semantic Web をよく知らないので、よく分らないのですが、それなりに楽しみました。

  • Aidan Hogan, Andreas Harth, and Stefan Decker: Performing Object Consolidation on the Semantic Web Data Graph
  • Paolo Bouquet, Heiko Stoermer, and Daniel Giacomuzzi: OKKAM: Enabling a Web of Entities
  • Raphael Volz, Joachim Kleb, and Wolfgang Mueller: Towards Ontology-based Disambiguation of Geographical Identifiers

~ 地理情報で用いられる名前の曖昧性を三種(同名異地域: フランスの Parisとテキサス州のParis、同地域異名: 東工大と東京工業大学、地域名称と一般名称: 東京と日本の首都みたいな？)に分類し、自然言語処理を用いて文脈から曖昧性を排除しています。このときに、文脈に現れる地域間の距離を最小化することによって同地域異名問題を解決したという主張は面白かったです。地域間のランキングには、行政区域の広さ、人口の多さ、コーパスにおける言及の頻度などを利用しているそうです。ただ、例のなかで Lancaster@US > Lancaster@UK となっていたことに（本人はこれを正当と主張しているようでしたが）についてフロアーから批判があり、歴史の長さも評価基準に加えるべきだという意見でまとまりました。そうなのかなぁ。。。

  • Pierre Levy (招待講演): Elements of Semantic Engineering

~ Semantic Webで用いられる言語について機械処理可能なメタ言語を与えて理論的な基盤にしようという研究です。この研究は、すでにIEML (Information Economy Meta Language)として公開されています。まず、アリストテレスの哲学に基づいて、表現というものを Being, Thing, Signifier の三つから構成されるとし、それに Virtualization 操作、Actualization 操作を与えることで 3 * 2 = 6 の概念を構成すると主張しています。さらに、これらを用いた三つ組を基本的な語素とする枠組みの上で言語を構成しています。なんだかよく分らないのですが、IEML は多国語化されています。たとえば英単語の "money" を入力すると、IEML の "diki" という単語が返ってきます。これは source = di (measurement instrument), destination = ki (gift) となっていて、さらに di = 'd' + 'i' に分解され。。。みたいに、よく分らなくて面白いのです。要するに、概念を言語に依存しない形で機械処理可能な形に整理しているわけで、Levy博士によれば、中世から現代に至るまでに物理世界における座標系を作ったように、サイバー空間にも同様の座標系を構成することを目標としているようです。フロアーの人で理解した人はいなかったようですが、議論は盛り上がってました。

Learning to rank in vector spaces and social networks

面白そうだったので参加したのですが、最初の数枚のスライドで落ちこぼれました（トホホ）。チュートリアルとしては異常にレベルの高いものだったようで、その道の専門家でなければついていけなかったことでしょう。参考文献のリストだけ紹介します。チュートリアル資料をいただいたので、欲しい方は帰国後に個人的に差し上げます。

  • T. Joachims: Optimizing search engines using clickthrough data, SIGKDD 2002.
  • T. Joachims: Training linear SVMs in linear time, in SIGKDD 2006.
  • I. Tsochantaridis, T. Joachims, T. Hofmann, and Y. Altun: Large margin methods for structured and interdependent output variables, JMLR, vol. 6, no. Sep, pp. 1453-1484, 2005.
  • C. Burges, T. Shaked, E. Renshaw, A. Lazier, M. Deeds, N. Hamilton, and G. Hullender: Learning to rank using gradient descent, ICML, 2005.
  • W. Cohen, R. Shapire, and Y. Singer: Learning to order things, JAIR, vol. 10, pp. 243-270, 1999.
  • Y. Freund, R. Iyer, R. Schapire, and Y. Singer: An efficient boosting algorithm for combining preferences, Journal of Machine learning research, vol. 4, pp. 933-969, 2003.
  • S. Agarwal: Ranking on graph data, in ICML 2006, pp. 25-32.
  • F. Chung, Laplacians and the Cheeger inequality for directed graphs, Annals of combinatorics, vol. 9, pp. 1-19, 2005.
  • J. Tomlin: A new paradigm for ranking pages on the world wide web, WWW conference 2003, pp. 350-355.
  • A. Agarwal, S. Chakrabarti, and S. Aggarwal: Learning to rank networked entities, SIGKDD 2006, pp. 14-23.
  • S. Chakrabarti and A. Agarwal, "Learning parameters in entity relationship graphs from ranking preferences, ECML/PKDD, ser. LNCS, vol. 4213, pp. 91-102, 2006.
  • N. Nie, Y. Zhang, J.-R. Wen, and W.-Y. Ma: Object-level ranking: Bringing order to Web objects, WWW2005, pp. 567-574.
  • M. Diligenti, M. Gori, and M. Maggini: Learning Web page scores by error back-propagation, in IJCAI, 2005.
  • A. Ng, A. Zheng, and M. Jordan: Stable algorithms for link analysis, in SIGIR conference 2001.
  • R. Lempel and S. Moran: Rank-stability and rank-similarity of link-based web ranking algorithms in authority-connected graphs, Information Retrieval, vol. 8, no. 2, pp. 245-264, 2005.
  • S. Agarwal and P. Niyogi: Stability and generalization of bipartite ranking algorithms, in COLT, pp. 32-47, 2005.
  • A. Agarwal and S. Chakrabarti: Learning random walks to rank nodes in graphs, ICML 2007.