[ml_ned] CWI Machine Learning seminar: Jaron Sanders, Thu 20th Sep, 10:00, L016

Wouter Koolen-Wijkstra W.M.Koolen-Wijkstra at cwi.nl
Wed Jul 4 18:24:58 CEST 2018

Dear all,

It is my pleasure to announce the following CWI Machine Learning 
seminar, which will take place after summer:

Speaker:  Jaron Sanders(Delft University)
Title:    Optimal Clustering Algorithms in Block Markov Chains
Date:     Thursday 20th September, 10:00
Location: CWI L016

Please find the abstract below.

Hope to see you then.

Best wishes,




Optimal Clustering Algorithms in Block Markov Chains

Jaron Sanders
Delft University

This paper considers cluster detection in Block Markov Chains (BMCs). 
These Markov chains are characterized by a block structure in their 
transition matrix. More precisely, the n possible states are divided 
into a finite number of K groups or clusters, such that states in the 
same cluster exhibit the same transition rates to other states. One 
observes a trajectory of the Markov chain, and the objective is to 
recover, from this observation only, the (initially unknown) clusters. 
In this paper we devise a clustering procedure that accurately, 
efficiently, and provably detects the clusters. We first derive a 
fundamental information-theoretical lower bound on the detection error 
rate satisfied under any clustering algorithm. This bound identifies the 
parameters of the BMC, and trajectory lengths, for which it is possible 
to accurately detect the clusters. We next develop two clustering 
algorithms that can together accurately recover the cluster structure 
from the shortest possible trajectories, whenever the parameters allow 
detection. These algorithms thus reach the fundamental detectability 
limit, and are optimal in that sense.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.leidenuniv.nl/pipermail/machine_learning_nederland/attachments/20180704/1e4ef8ed/attachment.html>

More information about the machine_learning_nederland mailing list