The task of multimedia document classification is challenging due to a diverse set of problems like a high dimensional, sparse and noisy features space, the unknown relevance of the features towards the classification target and the semantic gap between non-informative, low-level features and high-level semantic meanings. As a solution we propose a classification approach combined with feature selection and construction based on feature information interactions. This information-theoretic dependence measure can detect complex feature de pendencies in multi-variate settings. They help to find relevant and non-redundant features and hence allow efficient classification. Experiments on artificial and real world data show the superiority of feature selection based on N-way interactions over greedy, pair-wise dependence measures like correlation and mutual information.