永利总站

  • 讲座信息

永利总站:07.12 | Active Monotone Classification

2021.07.08

演讲者陶宇飞 教授
头衔职位香港中文大学计算机系
时间2021年7月12号上午10:00-11:00
地点腾讯会议号:873 504 189
承办单位上海市智能信息处理重点实验室
永利总站
联系人周水庚,sgzhou@fudan.edu.cn

永利总站:演讲简介

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.
永利总站_奥门永利总站5856