In this chapter, we have briefly reviewed the existing relevance feedback techniques. Emphasis is put on the analysis of the unique characteristics of multimedia information retrieval problems and the corresponding on-line learning algorithms. We presented a variant of discriminant analysis that is suited for the asymmetric nature of this small sample learning problem. A kernel-based approach is used to derive its non linear counterpart. We also presented experimental results on synthetic and real world image and video datasets. The proposed algorithm demonstrated promising potential in facilitating complex retrieval tasks using both numerical and textual inputs.