Active Learning is a machine learning framework that tries to solves the issue of having huge amount of unlabeled data compared to the labeled data. Most studies in Active Learning focus on how to select the unlabeled data to be labeled by a human oracle in order to maximize the performance gain of the model with as little labeling effort as possible. In this thesis, however, we focus not only in how to select the data instances but also how to select which features to be labeled by the oracle in a unified manner. By unified, it means that we tried to select the best possible combination of features and instances on each iteration. Labeling the features is especially helpful for high dimensional data, since it allows the model to discover the important features earlier.

The method that we propose is by synthesizing new instances that represent a set of features. By utilizing synthesized instances, we can treat this set of features as if they are regular instances. Therefore they could be compared on an equal ground when the model tries to select which instances to be labeled by the oracle. The features used to build the synthesized instances need to be carefully selected so the resulting synthesized instances could improve the model and not introducing any contradicting information. We utilize hierarchical clustering in order to group features that have similar context. This is done first by picking clusters whose purity are estimated to be high. Then we score the features based on how common the feature is in the cluster and how related the feature is to the estimated majority label. The top scoring features then will be used to synthesize instances. Since we are picking clusters that are estimated to has high purity, there is a good chance that the top scoring features will not contradicting each other.

Active Learning is a machine learning framework that tries to solves the issue of having huge amount of unlabeled data compared to the labeled data. Most studies in Active Learning focus on how to select the unlabeled data to be labeled by a human oracle in order to maximize the performance gain of the model with as little labeling effort as possible. In this thesis, however, we focus not only in how to select the data instances but also how to select which features to be labeled by the oracle in a unified manner. By unified, it means that we tried to select the best possible combination of features and instances on each iteration. Labeling the features is especially helpful for high dimensional data, since it allows the model to discover the important features earlier.

The method that we propose is by synthesizing new instances that represent a set of features. By utilizing synthesized instances, we can treat this set of features as if they are regular instances. Therefore they could be compared on an equal ground when the model tries to select which instances to be labeled by the oracle. The features used to build the synthesized instances need to be carefully selected so the resulting synthesized instances could improve the model and not introducing any contradicting information. We utilize hierarchical clustering in order to group features that have similar context. This is done first by picking clusters whose purity are estimated to be high. Then we score the features based on how common the feature is in the cluster and how related the feature is to the estimated majority label. The top scoring features then will be used to synthesize instances. Since we are picking clusters that are estimated to has high purity, there is a good chance that the top scoring features will not contradicting each other.

[1] H. Raghavan, O. Madani, and R. Jones, “Active learning with feedback on
features and instances,” Journal of Machine Learning Research, vol. 7, no. Aug,
pp. 1655–1686, 2006.
[2] H. Raghavan and J. Allan, “An interactive algorithm for asking and incorporat-
ing feature feedback into support vector machines,” in Proceedings of the 30th
annual international ACM SIGIR conference on Research and development in
information retrieval, pp. 79–86, ACM, 2007.
[3] J. Attenberg, P. Melville, and F. Provost, “A unified approach to active dual su-
pervision for labeling features and examples,” in Joint European Conference on
Machine Learning and Knowledge Discovery in Databases, pp. 40–55, Springer,
2010.
[4] B. Settles, “Closing the loop: Fast, interactive semi-supervised annotation with
queries on features and instances,” in Proceedings of the conference on empirical
methods in natural language processing, pp. 1467–1478, Association for Com-
putational Linguistics, 2011.
[5] B. Settles, “Active learning literature survey,” University of Wisconsin, Madi-
son, vol. 52, no. 55-66, p. 11, 2010.
[6] G. Druck, B. Settles, and A. McCallum, “Active learning by labeling features,”
in Proceedings of the 2009 Conference on Empirical Methods in Natural Lan-
guage Processing: Volume 1-Volume 1, pp. 81–90, Association for Computa-
tional Linguistics, 2009.
[7] W.-K. Wong, I. Oberst, S. Das, T. Moore, S. Stumpf, K. McIntosh, and M. Bur-
nett, “End-user feature labeling: A locally-weighted regression approach,” in
Proceedings of the 16th international conference on Intelligent user interfaces,
pp. 115–124, ACM, 2011
[8] D. D. Lewis and W. A. Gale, “A sequential algorithm for training text clas-
sifiers,” in Proceedings of the 17th annual international ACM SIGIR confer-
ence on Research and development in information retrieval, pp. 3–12, Springer-
Verlag New York, Inc., 1994.
[9] T. Scheffer, C. Decomain, and S. Wrobel, “Active hidden markov models for
information extraction,” in International Symposium on Intelligent Data Anal-
ysis, pp. 309–318, Springer, 2001.
[10] C. E. Shannon, “A mathematical theory of communication,” ACM SIGMO-
BILE Mobile Computing and Communications Review, vol. 5, no. 1, pp. 3–55,
2001.
[11] B. Settles and M. Craven, “An analysis of active learning strategies for sequence
labeling tasks,” in Proceedings of the conference on empirical methods in natural
language processing, pp. 1070–1079, Association for Computational Linguistics,
2008.
[12] N. Roy and A. McCallum, “Toward optimal active learning through monte carlo
estimation of error reduction,” ICML, Williamstown, pp. 441–448, 2001.
[13] B. Demir, C. Persello, and L. Bruzzone, “Batch-mode active-learning methods
for the interactive classification of remote sensing images,” IEEE Transactions
on Geoscience and Remote Sensing, vol. 49, no. 3, pp. 1014–1031, 2011.
[14] D. Müllner, “Modern hierarchical, agglomerative clustering algorithms,” arXiv
preprint arXiv:1109.2378, 2011.
[15] S. Dasgupta and D. Hsu, “Hierarchical sampling for active learning,” in Pro-
ceedings of the 25th international conference on Machine learning, pp. 208–215,
ACM, 2008.
[16] M. Lichman, “UCI machine learning repository,” 2013.
[17] D. Lewis, “Naive (bayes) at forty: The independence assumption in information
retrieval,” Machine learning: ECML-98, pp. 4–15, 1998.
[18] T. Joachims, “Text categorization with support vector machines: Learning with
many relevant features,” Machine learning: ECML-98, pp. 137–142, 1998.
[19] D. Cournapeau, “scikit-learn,” 2007.