$HS^2$: Active learning over hypergraphs with pointwise and pairwise queries

I (Eli) Chien, Huozhi Zhou, Pan Li
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:2466-2475, 2019.

Abstract

We propose a hypergraph-based active learning scheme which we term $HS^2$; $HS^2$ generalizes the previously reported algorithm $S^2$ originally proposed for graph-based active learning with pointwise queries. Our $HS^2$ method can accommodate hypergraph structures and allows one to ask both pointwise queries and pairwise queries. Based on a novel parametric system particularly designed for hypergraphs, we derive theoretical results on the query complexity of $HS^2$ for the above described generalized settings. Both the theoretical and empirical results show that $HS^2$ requires a significantly fewer number of queries than $S^2$ when one uses $S^2$ over a graph obtained from the corresponding hypergraph via clique expansion.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-chien19a, title = {$HS^2$: Active learning over hypergraphs with pointwise and pairwise queries}, author = {Chien, I (Eli) and Zhou, Huozhi and Li, Pan}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {2466--2475}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/chien19a/chien19a.pdf}, url = {https://proceedings.mlr.press/v89/chien19a.html}, abstract = {We propose a hypergraph-based active learning scheme which we term $HS^2$; $HS^2$ generalizes the previously reported algorithm $S^2$ originally proposed for graph-based active learning with pointwise queries. Our $HS^2$ method can accommodate hypergraph structures and allows one to ask both pointwise queries and pairwise queries. Based on a novel parametric system particularly designed for hypergraphs, we derive theoretical results on the query complexity of $HS^2$ for the above described generalized settings. Both the theoretical and empirical results show that $HS^2$ requires a significantly fewer number of queries than $S^2$ when one uses $S^2$ over a graph obtained from the corresponding hypergraph via clique expansion.} }
Endnote
%0 Conference Paper %T $HS^2$: Active learning over hypergraphs with pointwise and pairwise queries %A I (Eli) Chien %A Huozhi Zhou %A Pan Li %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-chien19a %I PMLR %P 2466--2475 %U https://proceedings.mlr.press/v89/chien19a.html %V 89 %X We propose a hypergraph-based active learning scheme which we term $HS^2$; $HS^2$ generalizes the previously reported algorithm $S^2$ originally proposed for graph-based active learning with pointwise queries. Our $HS^2$ method can accommodate hypergraph structures and allows one to ask both pointwise queries and pairwise queries. Based on a novel parametric system particularly designed for hypergraphs, we derive theoretical results on the query complexity of $HS^2$ for the above described generalized settings. Both the theoretical and empirical results show that $HS^2$ requires a significantly fewer number of queries than $S^2$ when one uses $S^2$ over a graph obtained from the corresponding hypergraph via clique expansion.
APA
Chien, I.(., Zhou, H. & Li, P.. (2019). $HS^2$: Active learning over hypergraphs with pointwise and pairwise queries. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:2466-2475 Available from https://proceedings.mlr.press/v89/chien19a.html.

Related Material