Exact and efficient top-K inference for multi-target prediction by querying separable linear relational models
- Author
- Michiel Stock (UGent) , Krzysztof Dembczynski, Bernard De Baets (UGent) and Willem Waegeman (UGent)
- Organization
- Abstract
- Many complex multi-target prediction problems that concern large target spaces are characterised by a need for efficient prediction strategies that avoid the computation of predictions for all targets explicitly. Examples of such problems emerge in several subfields of machine learning, such as collaborative filtering, multi-label classification, dyadic prediction and biological network inference. In this article we analyse efficient and exact algorithms for computing the top-K predictions in the above problem settings, using a general class of models that we refer to as separable linear relational models. We show how to use those inference algorithms, which are modifications of well-known information retrieval methods, in a variety of machine learning settings. Furthermore, we study the possibility of scoring items incompletely, while still retaining an exact top-K retrieval. Experimental results in several application domains reveal that the so-called threshold algorithm is very scalable, performing often many orders of magnitude more efficiently than the naive approach.
- Keywords
- KERNEL METHODS, FRAMEWORK, SYSTEMS, Top-K retrieval, Exact inference, Precision at K, Multi-target prediction, MATRIX, NETWORK
Downloads
-
KERMIT-A1-397.pdf
- full text
- |
- open access
- |
- |
- 3.08 MB
Citation
Please use this url to cite or link to this publication: http://hdl.handle.net/1854/LU-8197306
- MLA
- Stock, Michiel, et al. “Exact and Efficient Top-K Inference for Multi-Target Prediction by Querying Separable Linear Relational Models.” DATA MINING AND KNOWLEDGE DISCOVERY, vol. 30, no. 5, 2016, pp. 1370–94, doi:10.1007/s10618-016-0456-z.
- APA
- Stock, M., Dembczynski, K., De Baets, B., & Waegeman, W. (2016). Exact and efficient top-K inference for multi-target prediction by querying separable linear relational models. DATA MINING AND KNOWLEDGE DISCOVERY, 30(5), 1370–1394. https://doi.org/10.1007/s10618-016-0456-z
- Chicago author-date
- Stock, Michiel, Krzysztof Dembczynski, Bernard De Baets, and Willem Waegeman. 2016. “Exact and Efficient Top-K Inference for Multi-Target Prediction by Querying Separable Linear Relational Models.” DATA MINING AND KNOWLEDGE DISCOVERY 30 (5): 1370–94. https://doi.org/10.1007/s10618-016-0456-z.
- Chicago author-date (all authors)
- Stock, Michiel, Krzysztof Dembczynski, Bernard De Baets, and Willem Waegeman. 2016. “Exact and Efficient Top-K Inference for Multi-Target Prediction by Querying Separable Linear Relational Models.” DATA MINING AND KNOWLEDGE DISCOVERY 30 (5): 1370–1394. doi:10.1007/s10618-016-0456-z.
- Vancouver
- 1.Stock M, Dembczynski K, De Baets B, Waegeman W. Exact and efficient top-K inference for multi-target prediction by querying separable linear relational models. DATA MINING AND KNOWLEDGE DISCOVERY. 2016;30(5):1370–94.
- IEEE
- [1]M. Stock, K. Dembczynski, B. De Baets, and W. Waegeman, “Exact and efficient top-K inference for multi-target prediction by querying separable linear relational models,” DATA MINING AND KNOWLEDGE DISCOVERY, vol. 30, no. 5, pp. 1370–1394, 2016.
@article{8197306,
abstract = {{Many complex multi-target prediction problems that concern large target spaces are characterised by a need for efficient prediction strategies that avoid the computation of predictions for all targets explicitly. Examples of such problems emerge in several subfields of machine learning, such as collaborative filtering, multi-label classification, dyadic prediction and biological network inference. In this article we analyse efficient and exact algorithms for computing the top-K predictions in the above problem settings, using a general class of models that we refer to as separable linear relational models. We show how to use those inference algorithms, which are modifications of well-known information retrieval methods, in a variety of machine learning settings. Furthermore, we study the possibility of scoring items incompletely, while still retaining an exact top-K retrieval. Experimental results in several application domains reveal that the so-called threshold algorithm is very scalable, performing often many orders of magnitude more efficiently than the naive approach.}},
author = {{Stock, Michiel and Dembczynski, Krzysztof and De Baets, Bernard and Waegeman, Willem}},
issn = {{1384-5810}},
journal = {{DATA MINING AND KNOWLEDGE DISCOVERY}},
keywords = {{KERNEL METHODS,FRAMEWORK,SYSTEMS,Top-K retrieval,Exact inference,Precision at K,Multi-target prediction,MATRIX,NETWORK}},
language = {{eng}},
location = {{Riva del Garda, Italy}},
number = {{5}},
pages = {{1370--1394}},
title = {{Exact and efficient top-K inference for multi-target prediction by querying separable linear relational models}},
url = {{http://doi.org/10.1007/s10618-016-0456-z}},
volume = {{30}},
year = {{2016}},
}
- Altmetric
- View in Altmetric
- Web of Science
- Times cited: