[ml_ned] CWI Machine Learning seminar: Jaron Sanders, Thu 20th Sep, 10:00, L016
W.M.Koolen-Wijkstra at cwi.nl
Wed Jul 4 18:24:58 CEST 2018
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.
Optimal Clustering Algorithms in Block Markov Chains
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...
More information about the machine_learning_nederland