arXiv:2012.10793

On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise

Jie Shen

제출 2020-12-19

원문 초록

We study {\em online} active learning of homogeneous halfspaces in $\mathbb{R}^d$ with adversarial noise where the overall probability of a noisy label is constrained to be at most $\nu$. Our main contribution is a Perceptron-like online active learning algorithm that runs in polynomial time, and under the conditions that the marginal distribution is isotropic log-concave and $\nu = \Omega(\epsilon)$, where $\epsilon \in (0, 1)$ is the target error rate, our algorithm PAC learns the underlying halfspace with near-optimal label complexity of $\tilde{O}\big(d \cdot polylog(\frac{1}{\epsilon})\big)$ and sample complexity of $\tilde{O}\big(\frac{d}{\epsilon} \big)$. Prior to this work, existing online algorithms designed for tolerating the adversarial noise are subject to either label complexity polynomial in $\frac{1}{\epsilon}$, or suboptimal noise tolerance, or restrictive marginal distributions. With the additional prior knowledge that the underlying halfspace is $s$-sparse, we obtain attribute-efficient label complexity of $\tilde{O}\big( s \cdot polylog(d, \frac{1}{\epsilon}) \big)$ and sample complexity of $\tilde{O}\big(\frac{s}{\epsilon} \cdot polylog(d) \big)$. As an immediate corollary, we show that under the agnostic model where no assumption is made on the noise rate $\nu$, our active learner achieves an error rate of $O(OPT) + \epsilon$ with the same running time and label and sample complexity, where $OPT$ is the best possible error rate achievable by any homogeneous halfspace.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2506.23921v5cs.CL공통 태그 Attribute공식 코드 · Papers with Code

대규모 언어 모델에서 진실의 트릴레마

The Trilemma of Truth in Large Language Models

일반 대중은 대규모 언어 모델(LLM)에 인간과 유사한 특성을 부여하며, LLM이 특정 정보를 '알고' 있다고 가정하는 경우가 많다. 실제로 LLM은 학습 중 보존된 정보를 내부적 확률적 지식으로 인코딩한다. 본 연구는 해당 지식의 진위를 탐칭(probing)하는 기존 방법들을 검토하고, 세 가지 결함 있는 근본 가정을 밝힌다. 이러한 결함을 해결하기 위해, 다중 인스턴스 학습(MIL)과 conformal prediction을 결합한 다중 클래스 탐칭 프레임워크인 sAwMIL(Sparse-Aware Multiple-Instance Learning)을 제안한다. sAwMIL은 LLM의 내부 표현(representation)을 활용하여 진술을 참, 거짓, 또는 둘 다 아님으로 분류한다. 우리는 새롭게 구축한 세 개의 데이터셋을 사용하여, 기본형 및 채팅 기반 변형을 포함한 16개의 오픈소스 LLM에 대해 sAwMIL을 평가한다. 결과는 (1) 일반적인 탐칭 방법은 신뢰할 수 있고 전이 가능한(transferable) 진위 방향을 제공하지 못하며, 일부 설정에서는 제로샷(zero-shot) 프롬프팅(prompting)보다 성능이 낮음을, (2) 진실과 거짓은 대칭적으로 인코딩되지 않음을, (3) LLM이 참과 거짓 모두와 구별되는 제3의 유형의 신호를 인코딩함을 보여준다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.