【2021.07.12】Active Monotone Classification

报告题目Active Monotone Classification    


报告时间2021年7月12日 10:00-11:00

报告地点腾讯会议号:873 504 189


报告摘要In d-dimensional space, a point p dominates another point q if the coordinate of p is at least that of q on every dimension. A monotone classifier is a function h mapping each point to {0, 1}, subject to the condition that h(p) >= h(q) holds whenever p dominates q. Now, fix a set P of points in d-dimensional space, where each point carries a label 0 or 1. A classifier h misclassifies a point p in P if h(p) is different from the label of p. The error of h is the number of points in P misclassified by h.In active monotone classification, we have an input set P, where the labels of all points are hidden in the beginning. An algorithm must pay a unit cost to reveal the label of a point in P. The challenge to find the best monotone classifier with the smallest cost. The problem is fundamental to numerous applications, e.g., entity matching, record linkage, duplicate detection, and so on.This talk will provide in-depth coverage of the latest results on the problem. Our discussion will involve both algorithms with non-trivial guarantees and lower bounds on the best performance achievable by any algorithms, deterministic or randomized.


关于嘉宾Yufei Tao is a Professor at the Department of Computer Science and Engineering, the Chinese University of Hong Kong (CUHK). He is an ACM Fellow and received the best paper award in SIGMOD'13, SIGMOD'15, and PODS'18. Besides CUHK, he has held professorial positions in the City University of Hong Kong, Korea Advanced Institute of Science and Technology, and the University of Queensland. Currently, he is an Adjunct Professor at Fudan University.

地址: 中国 上海市杨浦区淞沪路2005号复旦大学江湾校区2号交叉学科楼
邮编: 200438
电话: +86-21-31242153
传真: +86-21-31242153
E-mail: dataology@fudan.edu.cn