Library Header Image
LSE Theses Online London School of Economics web site

Relational learning for set value functions

Wang, Yiliu (2022) Relational learning for set value functions. PhD thesis, London School of Economics and Political Science.

[img] Text
Download (1MB)
Identification Number: 10.21953/lse.00004464


Relational learning is learning in a context where we have a set of items with relationships. For example, in a recommender system or advertising platform, items are grouped into lists to attract user attention, and some items may be more popular than others. We are often interested in learning individual abilities, approximating group performances and making best set selection. However, it could be challenging as we have limited feedback and various uncertainties. We might only observe noisy aggregate feedback at the set level (set level randomness), and each item could be a random variable following some distributions (item level randomness). To tackle the problem, we model the group performance using a set value function, defined as a function of item values within the group of interest. We first study the beta model for hypergraphs. The model treats relational data as hypergraphs where nodes represent items and hyper-edges group items into sets. The goal is to estimate individual beta values from the group outcomes. We study the inference problem under different settings using maximum likelihood estimation (MLE). We move on to consider more general set value functions and the second source of randomness at the item level. The goal is to find good item representations (sketches) for approximation of stochastic valuation functions, defined as the expectation of set value functions of independent random variables. We present an approximation everywhere guarantee for a wide range of stochastic valuation functions. Finally, we study an online variant where an agent can draw samples sequentially. At each time step, the agent chooses a group of items subject to constraints and receives some form of feedbacks. The goal is to select a set of items with maximum performances according to some stochastic valuation functions. We consider the regret minimization setting and address the problem under value-index feedback.

Item Type: Thesis (PhD)
Additional Information: © 2022 Yiliu Wang
Library of Congress subject classification: Q Science > QA Mathematics
Sets: Departments > Statistics
Supervisor: Vojnovic, Milan

Actions (login required)

Record administration - authorised staff only Record administration - authorised staff only


Downloads per month over past year

View more statistics