报告题目：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.