MEGA - The maximizing expected generalization algorithm for learning complex query concepts

Edward Yi Chang

doi:10.1145/944012.944014

Return

MEGA - The maximizing expected generalization algorithm for learning complex query concepts

2003-10-01

PRE

Edward Yi Chang

Beitao Li

DOI：10.1145/944012.944014

Original

Original request for help

Save

Abstract

En 中文

Specifying exact query concepts has become increasingly challenging to end-users. This is because many query concepts ( e. g., those for looking up a multimedia object) can be hard to articulate, and articulation can be subjective. In this study, we propose a query-concept learner that learns query criteria through an intelligent sampling process. Our concept learner aims to fulfill two primary design objectives: ( 1) it has to be expressive in order to model most practical query concepts and ( 2) it must learn a concept quickly and with a small number of labeled data since online users tend to be too impatient to provide much feedback. To fulfill the first goal, we model query concepts in k-CNF, which can express almost all practical query concepts. To fulfill the second design goal, we propose our maximizing expected generalization algorithm ( MEGA), which converges to target concepts quickly by its two complementary steps: sample selection and concept refinement. We also propose a divide-and-conquer method that divides the concept-learning task into G subtasks to achieve speedup. We notice that a task must be divided carefully, or search accuracy may suffer. Through analysis and mining results, we observe that organizing image features in a multiresolution manner, and minimizing intragroup feature correlation, can speed up query-concept learning substantially while maintaining high search accuracy. Through examples, analysis, experiments, and a prototype implementation, we show that MEGA converges to query concepts significantly faster than traditional methods.

Keywords:

algorithms

management

active learning

data mining

query concept

relevance feedback