Advanced search
1 file | 3.08 MB

Exact and efficient top-K inference for multi-target prediction by querying separable linear relational models

Author
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
    • |
    • PDF
    • |
    • 3.08 MB

Citation

Please use this url to cite or link to this publication:

Chicago
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.
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. Presented at the European conference on Machine Learning and Principles and Practice of Knowledge Discovery.
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.
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 30.5 (2016): 1370–1394. Print.
@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},
  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://dx.doi.org/10.1007/s10618-016-0456-z},
  volume       = {30},
  year         = {2016},
}

Altmetric
View in Altmetric
Web of Science
Times cited: