English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

This paper investigates the problem of active learning for binary labelprediction on a graph. We introduce a simple and label-efficient algorithmcalled S2 for this task. At each step, S2 selects the vertex to be labeledbased on the structure of the graph and all previously gathered labels.Specifically, S2 queries for the label of the vertex that bisects the *shortestshortest* path between any pair of oppositely labeled vertices. We present atheoretical estimate of the number of queries S2 needs in terms of a novelparametrization of the complexity of binary functions on graphs. We alsopresent experimental results demonstrating the performance of S2 on both realand synthetic data. While other graph-based active learning algorithms haveshown promise in practice, our algorithm is the first with both goodperformance and theoretical guarantees. Finally, we demonstrate theimplications of the S2 algorithm to the theory of nonparametric activelearning. In particular, we show that S2 achieves near minimax optimal excessrisk for an important class of nonparametric classification problems.

S2: An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification