Abstract: Traditional web image annotation methods neglect the relevance of the assigned label set as a whole, resulting in the label relevance deficiency and redundancy. To solve the above problems, a novel web image annotation method by learning the label set relevance is proposed, which considers both the relevance of label set to image and the label set internal correlation. Measures that can estimate the above factors are designed, and both the constraints are formulated into a joint framework. Meanwhile, an effective greedy search algorithm is proposed for an approximate optimal label set, which reaches a reasonable trade-off between the relevance of label set to image and internal correlation, and makes the framework more applicable to the data set that contains the large scale concept and images. Experiments on real world web image data sets demonstrate the general applicability of our algorithm. In comparison to the state-of-the-art methods, the proposed approach yields better performance.