結局スライドを作る時間が取れなかったので、一睡もせずスライド作ったり……。車のエンジンがかかるかどうか不安だったが、なんとかエンジンかかってよかった。
昼前には研究室に行けるかなと思っていたのだが、いろいろと長引いて結局 NAIST に着いたのは1時くらい。東京に持って帰らないといけないものを捜索したり、保健室に行って薬を処方してもらったり(NAIST は無料で薬をくれるし看護師さんが声はしゃがれているがすごく親身なのでとてもいいと思う)していると、研究室に着いたのが2時半。市役所に寄って転出届をもらったりしてから東京に帰らないといけないので、30分くらいしか時間がなかったが、ベルギーから来ているリンク解析の研究者の Saerens さんと議論。いろいろアイデアもらえてすごく勉強になった！ これは1週間くらいいて毎日議論したかったくらいかも……。ちなみに京都・奈良周辺にいる人は3月27日に講演会があるので、興味ある人はどうぞ〜
講演 1
Description and analysis of several recent kernels on a graph, with application to collaborative recommendation and semisupervised classification
講演者
Francois Fouss (FuCAM/Univeriste Catholique de Louvain, Belgium)概要
We will first introduce seven graph kernels and two related graph matrices, namely the exponential diffusion kernel, the Laplacian exponential diffusion kernel, the von Neumann diffusion kernel, the regularized Laplacian kernel, the commute-time kernel, the random-walk-with-restart similarity matrix, the regularized commute-time kernel, the Markov diffusion kernel, and the cross-entropy diffusion matrix. Graph kernels compute proximity measures between nodes that help to study the structure of the graph. The power of the kernel-on-a-graph approach will then be illustrated by comparing the nine kernel-based algorithms on a collaborative-recommendation task as well as on a semisupervised classification task on several databases.講演 2
The randomized shortest-paths approach and its applications
講演者
Marco Saerens (Universite Catholique de Louvain, Belgium)概要
This presentation will introduce the concept of randomized shortest-paths (RSP) and some of its applications. Designing a RSP strategy aims to compute the transition probabilities of a finite Markov chain (the policy) in order to minimize the expected cost for reaching a destination node from a source node while maintaining a fixed level of entropy spread throughout the network (the exploration). The global level of randomness of the policy is quantified by the expected Shannon entropy spread throughout the network, and is provided a priori by the designer. By taking a sum-over-paths statistical physics framework, it is shown that the unique optimal policy (transition probabilities) can be obtained by solving a simple linear system of equations.
Applications of this technique are currently investigated; for instance
- Defining a RSP edit-distance taking all alignments into account and favoring good alignments;
- Defining a RSP dissimilarity between nodes of a graph intermediate between the shortest-path distance and the commute-time (or resistance) distance;
- Defining a RSP covariance between nodes of a graph where two nodes are correlated when they often co-occur on the same paths;
- Defining a re-estimation method for hidden Markov models intermediate between the Viterbi and the Baum-Welch algorithms.
