Scholarlink

We consider two very basic problems – one in unsupervised and one in supervised learning. In the former, we are given a set of points and have to label half of the points red and half the points blue so as to maximize the red–blue separation, i.e., the length of a shortest bichromatic edge. In the latter, the data (points in the plane) are already labeled red and blue, and we seek a linear classifier (a separator of the two given point sets) that can be described using the smallest integers. We give algorithms for both problems. Our solutions are simple; the main contribution of the paper is highlighting the problems and their algorithmic solutions, which, to our knowledge, have not been presented previously, despite the problems being fundamental to the field. We also consider related problems.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

On Two Simple[st] Learning Tasks

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Omrit Filtser,
  • Kien Huynh,
  • Anastasia Lemetti,
  • Joseph Mitchell,
  • Tatiana Polishchuk,
  • Valentin Polishchuk

摘要

We consider two very basic problems – one in unsupervised and one in supervised learning. In the former, we are given a set of points and have to label half of the points red and half the points blue so as to maximize the red–blue separation, i.e., the length of a shortest bichromatic edge. In the latter, the data (points in the plane) are already labeled red and blue, and we seek a linear classifier (a separator of the two given point sets) that can be described using the smallest integers. We give algorithms for both problems. Our solutions are simple; the main contribution of the paper is highlighting the problems and their algorithmic solutions, which, to our knowledge, have not been presented previously, despite the problems being fundamental to the field. We also consider related problems.