Evaluating Hierarchies through A Partially Observable Markov Decision Processes Methodology
Preprint
Abstract
Hierarchical clustering has been shown to be valuable in many scenarios, e.g. catalogues, biology research, image processing, and so on. Despite its usefulness to many situations, there is no agreed methodology on how to properly evaluate the hierarchies produced from different techniques, particularly in the case where ground-truth labels are unavailable. This motivates us to propose a framework for assessing the quality of hierarchical clustering allocations which covers the case of no ground-truth information. Such a quality measurement is useful, for example, to assess the hierarchical structures used by online retailer websites to display their product catalogues. Differently to all the previous measures and metrics, our framework tackles the evaluation from a decision theoretic perspective. We model the process as a bot searching stochastically for items in the hierarchy and establish a measure representing the degree to which the hierarchy supports this search. We employ the concept of Partially Observable Markov Decision Processes (POMDP) to model the uncertainty, the decision making, and the cognitive return for searchers in such a scenario. In this paper, we fully discuss the modeling details and demonstrate its application on some datasets.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Experimental IR Meets Multilinguality, Multimodality, and Interaction2017
- Understanding and Enhancement of Internal Clustering Validation MeasuresIEEE Transactions on Cybernetics, 2013
- Bayes-Adaptive Interactive POMDPsProceedings of the AAAI Conference on Artificial Intelligence, 2012
- Bayesian update of dialogue state: A POMDP framework for spoken dialogue systemsComputer Speech & Language, 2010
- Online Planning Algorithms for POMDPsJournal of Artificial Intelligence Research, 2008
- Near-Optimal Reinforcement Learning in Polynomial TimeMachine Learning, 2002
- A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision ProcessesMachine Learning, 2002
- Planning and acting in partially observable stochastic domainsArtificial Intelligence, 1998
- Efficient algorithms for agglomerative hierarchical clustering methodsJournal of Classification, 1984
- Dynamic programming of some sequential sampling designJournal of Mathematical Analysis and Applications, 1961