A New Vision of Collaborative Active Learning
Tobias Reitmaier
Adrian Calma
Name\corauthref{cor1
%\lipsum[1-2] Active learning (AL) is a paradigm where an active learner has to train a model (e.g., a classifier) which is in principle trained in a supervised way. In contrast to supervised learning, AL has to be done by means of a data set where a low fraction of samples is labeled or even with an initially unlabeled set of samples. To obtain labels for the unlabeled samples, the active learner has to ask an oracle (e.g., a human expert) for labels. In most cases, the goal is to maximize some metric or task performance and to minimize the number of queries at the same time. In this article, we first briefly discuss the state-of-the-art and own, preliminary work in the field of AL. Then, we propose the concept of collaborative active learning (CAL). With CAL, we will overcome some of the harsh limitations of current AL. In particular, we envision scenarios where the expert or the gold standard may be wrong for various reasons. There also might be several or even many experts with different expertise, the experts may label not only samples but also supply knowledge at a higher level such as rules, and we consider that the labeling costs depend on many conditions. Moreover, in a CAL process human experts may even profit by improving their own knowledge, too.
CALConcept.tex
% Template article for preprint document class `elsart'
% SP 2006/04/26
%\documentclass[preprint,3p,times,onecolumn]{elsarticle}
\documentclass[3p,times,onecolumn]{elsarticle}





%\documentclass{llncs}

%% Use the option review to obtain double line spacing
%% \documentclass[authoryear,preprint,review,12pt]{elsarticle}

%% Use the options 1p,twocolumn; 3p; 3p,twocolumn; 5p; or 5p,twocolumn
%% for a journal layout:
%% \documentclass[final,1p,times]{elsarticle}
%% \documentclass[final,1p,times,twocolumn]{elsarticle}
%% \documentclass[final,3p,times]{elsarticle}
%% \documentclass[final,3p,times,twocolumn]{elsarticle}
%% \documentclass[final,5p,times]{elsarticle}
%% \documentclass[final,5p,times,twocolumn]{elsarticle}

%\documentclass[onecolumn]{elsart3p}
% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}

% if you use PostScript figures in your article
% use the graphics package for simple commands
% \usepackage{graphics}
% or use the graphicx package for more complicated commands
\usepackage{graphicx}
\usepackage{subfigure}
%\usepackage{caption}
% or use the epsfig package if you prefer to use the old commands
% \usepackage{epsfig}

% The amssymb package provides various useful mathematical symbols
\usepackage{amssymb}
\usepackage{amsmath}
%\usepackage{fleqn}
%\setlength{\mathindent}{0mm}

% The lineno packages adds line numbers. Start line numbering with
% \begin{linenumbers}, end it with \end{linenumbers}. Or switch it on
% for the whole article with \linenumbers.
% \usepackage{lineno}

% \linenumbers

\usepackage{url}
\usepackage[dvipsnames]{xcolor}

\makeatletter
\newif\if@restonecol
\makeatother

\usepackage{bm}
\usepackage{multirow}
\usepackage{mathrsfs}

\let\algorithm\relax
\let\endalgorithm\relax
\usepackage[ruled,linesnumbered,lined]{algorithm2e}

\usepackage{boolexpr,pdftexcmds,trace}
\usepackage{array} 

\usepackage{pdflscape}


% Select what to do with todonotes: 
\usepackage[disable]{todonotes} % notes not showed
%\usepackage[draft,textsize=tiny,backgroundcolor=white,linecolor=orange,bordercolor=orange]{todonotes}   % notes showed

\setlength{\marginparwidth}{0.95cm}
%\newcommand{\comment}[1]{\marginpar{\tiny #1}}
\newcommand{\comment}[1]
{{\bfseries  \marginpar{\tiny \color{blue} #1}}} %comment showed

\renewcommand{\topfraction}{1.0}
\renewcommand{\bottomfraction}{1.0}
\renewcommand{\textfraction}{0.0}

\newcommand{\abs}[1]{\left\vert#1\right\vert}
\newcommand{\Sst}{\scriptstyle}
\newcommand{\N}{\ensuremath{\mathbb{N}}}
\newcommand{\R}{\ensuremath{\mathbb{R}}}
\newcommand{\norm}[1]{\left\Vert#1\right\Vert}
\newcommand{\scalarproduct}[2]{\left<#1\vphantom{#2} \right| \! %
                                       \left.\vphantom{#1}#2\right>}
\newcommand{\scp}[2]{\scalarproduct{#1}{#2}}
\newcommand{\id}{\operatorname{id}}

\newcommand{\fs}[2]{\fontsize{#1 pt}{#2 pt}\selectfont}
\newcommand{\rd}[1]{\color{red} #1}

\allowdisplaybreaks

\newcommand{\up}{\vspace*{-1em}}
\newcommand{\dn}{\vspace*{1em}}

\makeatletter
\newcommand{\customlabel}[2]{%
\protected@write \@auxout {}{\string \newlabel {#1}{{#2}{}}}}
\makeatother

\def\clap#1{\hbox to 0pt{\hss#1\hss}}
\def\mathclap{\mathpalette\mathclapinternal}
\def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}}
\DeclareMathOperator*{\argmin}{argmin}
\DeclareMathOperator*{\argmax}{argmax}
\DeclareTextAccent{\myacc}{T1}{4}

\newenvironment{rcases}{%
  \left.\renewcommand*\lbrace.%
  \begin{cases}}%
{\end{cases}\right\rbrace}


\usepackage{fancyhdr}
\usepackage{multirow}
\usepackage{booktabs}


\usepackage{float}
\usepackage{pgffor}
\usepackage{morefloats}
\usepackage{xspace}

\usepackage{hyperref}

\setcounter{secnumdepth}{3}

\usetikzlibrary{matrix}

%%for charts with tikz
%\usepackage{bchart}
%\usepackage{pgfplots}
%\usepackage{pgfplotstable}
%\pgfplotsset{compat=newest}
%\usepackage{caption}
%\usetikzlibrary{patterns,backgrounds,shapes,arrows}

\newcolumntype{C}[1]{>{\centering\let\newline\\\arraybackslash\hspace{0pt}}m{#1}}
\newcolumntype{L}[1]{>{\raggedright\let\newline\\\arraybackslash\hspace{0pt}}m{#1}}

\hyphenation{res-pon-sa-bi-li-ty clas-si-fi-ca-tion e-la-bo-rately un-su-per-vised stra-te-gy re-posi-tory}

\begin{document}
% LNCS
%\title{Resp-$k$NN: A Semi-Supervised Classifier for Sparsely Labeled Data in the Field of Organic Computing}
%\author{Tobias Reitmaier, Adrian Calma}
%\institute{Intelligent Embedded Systems Lab, University of Kassel, Germany\\
%	\email{\{tobias.reitmaier,adrian.calma\}@uni-kassel.de}}

\begin{frontmatter}

% Title, authors and addresses

% use the thanksref command within \title, \author or \address for footnotes;
% use the corauthref command within \author for corresponding author footnotes;
% use the ead command for the email address,
% and the form \ead[url] for the home page:
% \title{Title\thanksref{label1}}
% \thanks[label1]{}
% \author{Name\corauthref{cor1}}
% \ead{email address}
% \ead[url]{home page}
% \thanks[label2]{}
% \corauth[cor1]{}
% \address{Address\thanksref{label3}}
% \thanks[label3]{}

\title{A New Vision of Collaborative Active Learning}
\author[IES]{Adrian Calma}
\author[IES]{Tobias Reitmaier}
\author[IES]{Bernhard Sick}
\author[DFKI]{Paul Lukowicz}
\author[RPI]{Mark Embrechts}

\address[IES]{Intelligent Embedded Systems Lab, University of Kassel, Kassel, Germany\\ 
(e-mail: $\{\text{adrian.calma,tobias.reitmaier,bsick}\}\text{@uni-kassel.de}$)}
\address[DFKI]{Embedded Intelligence, German Research Center for Artificial Intelligence, University of Kaiserslautern, Kaiserslautern, Germany\\ 
(e-mail: $\text{paul.lukowicz@dfki.de}$)}
\address[RPI]{Rensselaer Polytechnic Institute, Troy, New York, USA\\
(e-mail: $\text{embrem@rpi.edu}$)}

% use optional labels to link authors explicitly to addresses:
% \author[label1,label2]{}
% \address[label1]{}
% \address[label2]{}

\begin{abstract}
%\lipsum[1-2]
Active learning (AL) is a paradigm where an active learner has to train a model (e.g., a classifier) which is in principle trained in a supervised way. In contrast to supervised learning, AL has to be done by means of a data set where a low fraction of samples is labeled or even with an initially unlabeled set of samples. To obtain labels for the unlabeled samples, the active learner has to ask an oracle (e.g., a human expert) for labels. In most cases, the goal is to maximize some metric or task performance and to minimize the number of queries at the same time. In this article, we first briefly discuss the state-of-the-art and own, preliminary work in the field of AL. Then, we propose the concept of collaborative active learning (CAL). With CAL, we will overcome some of the harsh limitations of current AL. In particular, we envision scenarios where the expert or the gold standard may be wrong for various reasons. There also might be several or even many experts with different expertise, the experts may label not only samples but also supply knowledge at a higher level such as rules, and we consider that the labeling costs depend on many conditions. Moreover, in a CAL process human experts may even profit by improving their own knowledge, too.
\end{abstract}

%\begin{keyword} 
%pool-based active learning; noisy oracles; noisy labels; multi oracle; collaborative active learning;
%\end{keyword}

\end{frontmatter}

%\maketitle

%\todo[inline]{Inhalt muss besser (nicht vollständig) ohne Zusatzliteratur verstÃ¤ndlich sein}
\section{Introduction}\label{sec:Introduction}
%\begin{itemize}
%	\item \checkmark AL as subfield of machine learning 
%	\item \checkmark key idea: a machine can learn better if it is allowed to ask questions 
%	\item \checkmark pool-based AL: add figure 
%	\item \checkmark oracle: domain expert  
%\end{itemize}

%{Why is AL important}
%\begin{itemize}
%	\item \checkmark reduce costs
%	\item \checkmark reduce time
%\end{itemize}

%{What is active learning?}
\todo{TR@all: Was ist mit weak learner (mechanical turk)? BS@TR: im Prinzip interessant aber wie und wo dar\"uber schreiben?}
Machine learning is based on sample data. Sometimes, these data are labeled and, thus, models to solve a certain problem (e.g., a classification or regression problem) can be built using targets assigned to input data of the model. In other cases, data are unlabeled (e.g., for clustering problems) or only partially labeled. Correspondingly, we distinguish the areas of supervised, unsupervised, and semi-supervised learning. In many application areas (e.g., industrial quality monitoring processes \cite{Sic98}, intrusion detection in computer networks \cite{HSS03}, speech recognition \cite{FHYA12}, or drug discovery \cite{MME14}) it is rather easy to collect unlabeled data, but quite difficult, time-consuming, or expensive to gather the corresponding targets. That is, labeling is in principal possible, but the costs may be enormous.

This article focuses on \textit{active learning (AL)}, a machine learning area that is sometimes considered to be a special case of semi-supervised learning (SSL) \cite{CSZ06}, but it can also be regarded as being closely related to SSL. AL starts with an initially unlabeled or very sparsely labeled set of samples and iteratively increases the labeled fraction of the training data set by ``asking the right questions''. These questions are then answered by humans (e.g., experts in an application domain), by simulation systems, by means of real experiments, etc., often modeled by an abstract ``oracle''. Basically, the ``idealized'' goal of AL is to obtain a model with (almost) the performance of a model trained with a fully labeled data set at (almost) the cost of an unlabeled data set. Thus, we also can say that SSL has to \textit{exploit} the knowledge contained in the unlabeled data, while AL has to \textit{explore} the knowledge contained in the unlabeled data.
Typically, the following assumptions are made (amongst others) in AL:
\begin{enumerate}
	\item The oracle labels single samples or sets of samples (called queries depending on the AL type, see below) presented by an active learner.
	\item The oracle is omniscient and omnipresent, i.e., it always delivers the correct answers and it is always available).
	\item The labeling costs for all samples are identical.
\end{enumerate}
This article develops a vision to overcome these limitations that are definitely not realistic for many applications. In particular, we assume that
\begin{enumerate}
	\item an expert may be wrong for various reasons, e.g., depending on her/his experience in the application domain (we still assume we have no ``malicious or deceptive experts'' that cheat or attack the active learner),
	\item there might be several or even many experts with different expertise (e.g., degree or kind of experience),
	\item the experts may label not only samples but also infer knowledge at a higher level such as rules (e.g., by assigning a conclusion to a presented premise), and
	\item the labeling costs depend on many conditions, e.g., whether samples or rules are labeled, on the location of samples in the input space of a model (i.e., making labeling more or less difficult), the degree of expertise of a human, etc.
\end{enumerate}
%\todo{BS@all: K\"onnte man auch als Punkt 5 formulieren, ist aber vielleicht nicht CAL-spezifisch.}
Moreover, there may be several tasks that have to be fulfilled at the same time (e.g., movies that are assessed regarding several criteria) and different kinds of information sources (e.g., human experts and simulation systems).

We envision \textit{collaborative active learning (CAL)} approaches where the above limitations no longer hold. Moreover, the humans involved in such a CAL process shall be offered the opportunity to profit by improving their own knowledge.

The field of AL recently has awoken the interest of many companies, such as Microsoft, IBM, Siemens, AT$\&$T, Mitsubishi, or Yahoo. Existing publications of those companies show that AL can be successfully utilized to solve a wide range problems, such as:
\begin{itemize}
	\item \textit{Text Classification:} Microsoft Research describes in \cite{PVS+10} an AL approach for providing personalized news to Project Emporia \cite{PE11} users in real-time. The news on user selected topics are coming from RSS feeds and tweets. The main challenge consists in training the underlying classifier on-line, as the news' trends have to be promptly classified. This problem is solved in two steps: First, appropriate unlabeled tweets are selected by means of AL and forwarded to Amazon Mechanical Turk (AMT) \cite{AMT} for labeling. Second, a Bayesian corroboration model, that takes the reliabilities of AMT workers into account, is used to label the corresponding tweets.
	
	Microsoft and Yahoo Lab present a further application of AL for detecting and filtering abusive user-generated content (UGC) on the Web in \cite{CZL+11}. The huge number of posts and the user's ability to learn how to avoid static, hand-coded detection rules, motivates the need of fast, automatic detection systems, that periodically update based on newly labeled data, provided by paid annotators. Therefore, AL is used to reduce the labeling costs.
	
	IBM uses AL in \cite{MS09} to carry out a sentiment analysis of texts, i.e., an automatic analysis of emotions expressed in posts. The goal is to identify whether a post reveals positive or negative opinions, e.g., criticism or approval.
	
	\item \textit{Speech Recognition:} In \cite{HRT06,TSH03} AT\&T shows how AL techniques can be employed to reduce the effort of transcribing natural spoken language required to generate labeled instances for data-driven speech and language processing systems. The goal of such a system may be to automate the classification of customer calls according to their content (e.g, account balance or rates inquiries) and consequently work through the customer requests with the help of a dialog. The transcription of an utterance is usually performed by a human expert and is very expensive, so the costs for extension and improvement can be reduced by an AL approach. At first, the system is trained based on an initial set of transcriptions and, in the following steps, it iteratively selects from a large pool of utterances those with a low transcription confidence. These utterances are then transcribed by an expert and the system is updated.
	
	Another approach to minimizing the transcription effort is presented by Microsoft Research in \cite{YDA10}, which combines AL with semi-supervised learning to select most likely misclassified as well as frequently occurring, untranscribed utterances.  
	
	\item \textit{Image Classification:} Mitsubishi Electric Research Laboratories present in \cite{JPP12} an AL approach to minimize the image classification cost. The novelty of the presented approach consists in its possibility to start the training process without being aware of the total number of classes (categories). Initially, a classifier is trained based on a small amount of labeled images. Then, a pair of an unlabeled and a labeled image is selected and presented to the human expert for a ``match'' or ``no-match'' response. In case of a ``match'', the queried image is labeled accordingly (the same category as the labeled image), added to the labeled set and the classifier is updated. Otherwise, based on the selection algorithm another labeled sample is selected for comparison. The query step is repeated until the ``match'' response is obtained or the unlabeled sample does not match any of the labeled samples. In the latter case, the number of classes is increased and a new category (label) is assigned to the queried sample.
	
	\item \textit{Drug Design:} Quantitative Medicine\footnote{\url{http://qtmed.com/home-page/active-learning/} -- last access 02/24/2015} claims to offer the first AL software as a service (SaaS) solution for drug discovery and development. By using AL techniques the efficiency of identifying optimal drug candidates is substantially improved.
	
	\item \textit{Malware Detection:} In order to detect and remove malware (malicious software) most anti-virus vendors rely on signature-based detection of previously seen malwares. Therefore, they have to keep their signature repository up to date by collecting suspicious files, which are then manually analyzed by security experts. As the labeling process is a time-consuming task, AL techniques may help the security experts to reduce the number of manually inspected files.
	Telekom Innovation Laboratories present in \cite{NMR+14} an AL framework to select the most likely to be malware files for manual inspection. Support vector machines (SVM) with radial basis function (RBF) kernel are used as classification algorithm. The most informative samples are acquired in two phases: First, the files for which the classifier is most unconfident (low distance to the separating hyperplane) about the category (malware or benign) are selected for manual analysis. In the second phase, the files that reside deep inside the malicious side (high distance to the separating hyperplane) are	picked out for further investigation. The proposed AL techniques was tested in a 10 day experiment, showing an improvement in the daily number of new detected malwares.

	\item \textit{Recommender Systems:} The Android application Shopr \cite{Trottmann15} is a mobile recommender system that suggests clothing items from stores situated in user's vicinity. The system requires feedback from users in order to understand and fulfill his/her desires. At this point comes AL into play narrowing down the item space to those that match the user's interest, taking both similarity and dissimilarity between the items into account. For a detailed description of the AL-based recommender system see \cite{LTW14}.			
			
\end{itemize}

	In the past years there is a strong increase of devices connected to internet which generate a storm of raw data, making the term \textit{Big~Data} become popular. From a data analytics point of view, big data may be defined by the four~\textit{V}'s: \textit{V}olume, \textit{V}ariety, \textit{V}elocity and \textit{V}eracity. Volume describes the big size of data, Velocity indicates fast generating rates, Variety implies the heterogeneity of data, and Veracity refers to the uncertainty of data quality \cite{ZCJ+14, BigData15}. 
	Further, the \textit{Internet of Things} aims at connecting everything with everything, leading to a huge network of things that should possess a certain intelligence that may support and improve the daily life of people around the world. To extract high-quality information from big data it may necessary for the system to receive feedback, e.g, from domain experts. Moreover, the humans should benefit too, by exchanging and improving their knowledge. 
	With regard to the previously presented trends, CAL may contribute to addressing these new, future challenges.

%Microsoft takes an interest in the classification of voice-mail \cite{KHB07}, IBM in the emotion analysis of texts \cite{PV09}, Siemens in computer aided diagnosis \cite{VFKD06} and Google says: ``While I can confirm that we're using active learning in earnest on many problem areas\dots I really can't provide any more details than that. Sorry to be so opaque!'' -- \textit{David Cohn}\footnote{\url{http://www.cs.cmu.edu/~tom/10709_fall09/slides/settles.active.pdf} -- last access 02/24/2015}.  
Altogether, we can be sure that there will also be an increasing interest in AL and, as many limitations of AL are abolished, in CAL, too.

In the remainder of this article, we first present some foundations of AL in Section \ref{sec:Foundations} and summarize results of own, preliminary work in Section \ref{sec:PreliminaryWork}. Section \ref{sec:casestudy} presents some experimental results for our AL techniques. In Section~\ref{sec:Challenges} we investigate the above challenges of CAL in more detail and briefly discuss possible solutions. Finally, Section \ref{sec:SummaryOutlook} concludes the article by taking a look at possible application fields.

\section{Overview of Active Learning Foundations}\label{sec:Foundations}

The motivation of AL is that obtaining plenty of unlabeled data is often quite cheap, while acquiring labels is a task with high costs (monetary or temporal). AL is based on the hypothesis that a process of (iteratively) asking an \textit{oracle} for labels and refining the current model can be realized in a way such that
\begin{itemize}
	\item the performance of the resulting model is comparable to the performance of a model trained on a fully labeled data set and
	\item the overall labeling costs to obtain the final model are much lower (typically simply measured by the number of labels).
\end{itemize}
Actually, to address the previous requirements it is possible to build an \textit{active learner} that is based on a complementary pair of \textit{model} (e.g., a classifier) and \textit{selection strategy}. With a selection strategy, the active learner decides whether a sample is \textit{informative} and asks the oracle for labels. Here, informative means that the active learner expects a (high) performance gain if this sample is labeled (similarly, a set of samples can also be called informative). 

\todo{BS@BS: Neues Paper aus Google Scholar zur Klassifikation von Blattkrankheiten einbauen.}
Basically, various kinds of models can be used for AL, but the selection strategy should always be defined depending on the model type (e.g., whether SVMs, neural networks, probabilistic classifiers, or decision trees are chosen to solve a classification problem). In the remainder of this article we focus on AL for classification problems (see \cite{RS13,RCS14,CL06,ZYPPJC15}, for example), but AL can be applied to modify the results of clustering (see \cite{MCR12}, for example) or to regression problems, too (see \cite{CZZ13,PM11,DB14,DMB13}, for example).
%\todo{BS@AC: Handelt es sich um ueberwachtes Clsutering oder wieso braucht man Labels?}

%For many real-world classification problems, a large, non-changing set of unlabeled samples is available and acquiring labels generates costs. The labels for learning a non-active model are obtained without referring to the learning algorithm. But, to acquire label information for the most ``informative'' (i.e., likely to increase the learner's performance if it is labeled) samples the learner should be allowed to ask questions, e.g., to choose for itself from which data it learns. In AL paradigms, the learner interactively selects the data points for which label information should be inquired. The hypothesis is that by using AL techniques the same or better performance may be achieved with a substantially lower number of labeled instances. Reducing the number labeled samples will bring down the costs. In a nutshell, the motivation of AL is that obtaining plenty of unlabeled data is inexpensive, while acquiring labels is time-consuming or expensive effort.

In the field of AL, membership query learning (MQL) \cite{Angluin88}, stream-based active learning (SAL) \cite{ACLEM90}, and pool-based active learning (PAL) \cite{LG94} are the most important paradigms (see Figure \ref{fig:PAL}, left hand side).
 
In an (MQL) scenario, the active learner may query labels for any sample in the input space, including samples generated by the active learner itself. Lang and Baum \cite{LB92}, for example, describe an (MQL) scenario with human oracles for classifying written digits. The queries generated by the active learner turned out to be some mixtures of digits, therefore being too difficult for a person to provide reliable answers.

An alternative to (MQL) is (SAL), which assumes that obtaining unlabeled samples generates low or no costs. Therefore, a sample is drawn from the data source and the active learner decides whether or not to request label information. Practically, in an (SAL) setting the source data is scanned sequentially and a decision is made for each sample individually. The SAL scenario has been applied, for example, in \cite{Yu2005} to learn ranking functions for retrieving for-sale houses listed on realtor.com that meet the user's preferences.

%Similar to \ac{MQL}, SAL may generate artificial samples that cannot be understood or labeled by human experts and
Typically, SAL selects only one sample in each learning cycle. 
%To overcome these limitations we refer to the PAL scenario.

For many practical problems a large set of unlabeled samples may be gathered inexpensively and this set is available at the very beginning of the AL process. This motivates the PAL scenario. The learning cycle of PAL is depicted in Figure~\ref{fig:PAL} on the right hand side. Typically, PAL starts with a large pool of unlabeled and a small set of labeled samples. On the basis of the labeled samples the active learner is trained. Then, based on a selection strategy, which considers  the ``knowledge'' of the learner, a query set of unlabeled samples is determined and presented to the oracle (e.g., a human domain expert), who provides the label information. The set of labeled samples is updated with the newly labeled samples and the learner updates its knowledge. The learning cycle is repeated until a given stopping condition is met. 

In the remainder of this article we focus on PAL for the sake of simplicity. Many ideas, however, may be transferred to MQL or SAL.

\begin{figure}[htb]
	\centering
	\subfigure[Main AL pradigms.]{\scalebox{.7}{\input{images/al_scenarios.tex}}}
	\hspace*{10mm}
	\subfigure[Learning cycle of standard PAL.]{\scalebox{.7}{\input{images/pool_based_cycle.tex}}}
	\caption{Overview of main AL scenarios with focus on PAL.}
	\label{fig:PAL}
\end{figure}

A selection strategy for PAL has to fulfill several tasks, two of which shall be given as an example: At an early stage of the AL process, samples have to be chosen in all regions of the input space covered by data (\textit{exploration phase}). At a late stage of the AL process, a fine-tuning of the decision boundary of the classifier has to be realized by choosing samples close to the (current) decision boundary (\textit{exploitation phase}). Thus, ``asking he right question'' (i.e., choosing samples for a query) is a multi-faceted problem and various selection strategies have been proposed and investigated. We want to emphasize that a successful selection strategy has to consider structure in the (un-)labeled data. We come back to this point later.

Typically, the very limiting assumptions listed in Section \ref{sec:Introduction} are made concerning the oracle and the labeling costs (omniscient, omnipresent oracle that labels samples on a fixed cost basis). Moreover, some other aspects of real-world problems are often more or less neglected by current research, for example:
\begin{itemize}
	\item In real-world applications, AL has often to start ``from scratch'', i.e., with no labels at all. This requires sophisticated selection strategies with different behaviors at different phases of the AL process.
	\item Parameters of the active learner (including parameter of training algorithms of the classifier and the selection strategy) cannot be found by trial-and-error. AL only allows for ``one shot''.
\end{itemize}

There are several articles that assess the state of the art in AL. We do not want to replicate this work here but refer to the (in our opinion) most important articles:
\begin{itemize}
	\item A general introduction to AL, including a discussion of AL scenarios and an overview of query strategies is provided in \cite{Set09}.
	\item A detailed overview of relevant PAL techniques is part of \cite{RS13}. In addition to single-view/single-learner methods, alternative approaches are outlined: multi-view/single-learner, single-view/multi-learner, and multi-view/multi-learner.
	%concisely.
	\item For certain problem areas it makes sense to use AL in combination with semi-supervised learning (SSL). AL techniques that integrate SSL techniques are succinctly presented in \cite{RCS14}.
	\item AL in combinations with SVM for solving classification problems are summarized in \cite{JH09, KPI14}.
\end{itemize}

%\todo[inline,caption={}]{Paper's purpose
%	\begin{itemize}
%		\item present challenges / research topics in the field of AL in order to bring AL from theory to practice
%	\end{itemize}
%	}
%Most research in the field of AL assumes an omniscient oracle who is available on demand. But in practice these assumptions do not hold. The human domain experts have finite wisdom and are not available round the clock. Besides, more than one oracle (e.g., a group of experts) may be available for specific task. The purpose of this article is to present practical challenges and possible research topics in an real-world AL scenario in order to bring it from theory to practice. The focus lies on oracle relates issue, such as how to learn from one or multiple human domain experts with finite wisdom.

\section{Preliminary Work -- \textit{What are we able to do right now}?}\label{sec:PreliminaryWork}
%\todo[inline,caption={}]{
%\begin{itemize}
%	\item \checkmark Structure information: by means of a selection strategy $\rightarrow$ 4DS; by means of model: CMM, RWM kernel
%	\item \checkmark We can train generative classifiers actively. We can use a combination between generative and discriminative
%	\item \checkmark Self-adaption: selection strategy 4DS; shared by means of transductive step becomes separate
%	\item \checkmark Parameter-free active learning: 4DS + VI
%\end{itemize}								
%}

In our preliminary work we tried to overcome some of the mentioned limitations. In particular, we focused on
\begin{enumerate}
	\item capturing structure in (un-)labeled data to support the exploration/exploitation phases of new selection strategies for PAL,
	\item self-adapting weighting schemes for different criteria combined in a selection strategy, and
	\item parameter-free AL (apart from parameters that can be found offline using the unlabeled data before the AL process starts, for instance).
\end{enumerate}
We still make the (also very limiting) assumptions concerning oracles and labeling costs that will be addressed later (cf.\ Section \ref{sec:Challenges}). 
%
Solutions to the above challenges were not developed separately but with a holistic view on the problem field. Thus, the following subsections sketch closely related solutions and refer to the publications where these approaches are described in much more detail.

%Most research work done in the field of AL refers to classification problems and assumes an oracle which is well intentioned, available on demand, and has infinite wisdom. That is, the oracle always answers instantaneously and correctly. Based on these assumptions, we focused our preliminary research on 
%\begin{itemize}
%	\item capturing structure information in data,
%	\item self-adapting of active learning techniques concerning the weighting of different criteria in selection strategies,
%	\item parameter-free active learning methods.
%\end{itemize}

\subsection{Capturing Structure in Data}

%\todo[inline,caption={}]{Es muss klarer sein: \newline 
%	worum geht es?  
%	\begin{itemize}
%		\item \checkmark Similarity, so the structure information is important
%		\end{itemize}
%		
%		warum man sich mit dem Punkt beschÃ¤ftigt
%		\begin{itemize}
%			\item \checkmark reduce the number of queries, higher performance
%		\end{itemize}
%			}
%The correlation between the samples from the training set, given the value of one or more specific features, determines the way they are arranged in the input space. 

Machine learning becomes possible if certain ``regularities'' or ``patterns'' in data can be identified and exploited. For classification problems we may assume that the data form clusters of arbitrary shape. For AL, such structure in data has to be captured to improve selection strategies and/or to improve the training of the classifier. In our work, we made two important assumptions that will be outlined in the following. We want to emphasize first that we do not claim that these assumptions always hold. They hold often and to a certain degree and, thus, building solutions based on these assumptions leads to an average, but yet significant improvement of a classifier's performance (shown on average over a number of benchmark data sets, see Section \ref{sec:casestudy}).

First, we assume that there is a correspondence of processes in the real world that ``generate'' the samples that we 
observe and want to classify on the one hand, and clusters in the training data on the other hand. We may assume further that processes are uniquely assigned to classes and, thus, clusters can also be uniquely assigned to classes. Of course, this does not contradict the fact that clusters belonging to different classes might widely overlap, which means that they cannot be clearly identified if we have the unlabeled data only.

Second, in the real world, these data-generating processes (and the mechanisms necessary to observe these processes) are affected by a (superposition of) random influences (or influences that we have to regard as being random). Two examples are (1) stochasticity which is inherent to certain processes or (2) measurement effects such as sensor noise. Following the generalized central limit theorem \cite{DHS01} we may assume that structure in continuous (real-valued) input dimensions of a classifier may well be captured by means of (mixtures of) Gaussian (i.e., normal) distributions, called components of this mixture model. Apart from that reason, under some mild assumptions it is always possible to model continuous densities using mixtures of Gaussians with arbitrary precision. In practical applications, particular discrete dimensions (integer dimensions) can often be handled like real ones.

Based on these assumptions we developed solutions in an evolutionary approach.
%\todo{BS@AC: Waren bei 3DS schon kategorische dabei? AC@BS: ja}

%The training data is arranged in a particular form in the input space. The way the samples lie in the input space describes the interdependence between them, given the value of one or more specific features. Based on the interdependece between the samples, it is possible to detect structures in different regions of the input space, e.g., in the form of clusters. Furthermore, valuable information about the distribution of the samples may be inferred from these structures. Therefore, by capturing structure information we are able to improve the AL process.
\begin{enumerate}
\item \textit{Capture Data Structure in AL:} In a first step, we decided to use probabilistic generative models to capture structure in data and to build classifiers based upon these models. The probabilistic models are parametric density models, mixtures of Gaussians for continuous (or integer where appropriate) input dimensions and special cases of multinomial distributions for the categorical ones. These models can be parametrized (trained) from a set of unlabeled data either in an expectation maximization approach or in a Bayesian approach, called variational Bayesian inference (VI) \cite{Bis06}. The VI has the advantages that, in contrast to EM, effects caused by singularities can be avoided and the number of components in the mixture models can be determined automatically with a built-in pruning technique \cite{FS09}.
%\todo{AC@BS: richtiges Paper?}
%For most practical applications, it turns out that there is a relation between structure and decision regions associated to the classes that have to be detected. The observed processes (i.e., the processes responsible for generating data) can be assigned to a specific class. We are able to identify structure in data in an unsupervised way, e.g., by means of generative models (probabilistic mixture models, for example Gaussian mixtures) trained by using a technique based on \ac{VI} \cite{Bis06}. 
Having found the density model, a classifier (CMM: classifier based on mixture models) is constructed using any available labels. This classifier gradually (i.e., with a certain probability) assigns the model components to classes. The components are intended to model the data originating from the data-generating processes in the real world. Our approach for AL based on CMM now exploits the density information in various ways (see below). It was first proposed in \cite{RS11} and extended in \cite{RS13}.

\item \textit{Revise Captured Structure during AL:} The approach above has the property that the density models are found in an unsupervised way using the unlabeled data available at the very beginning of the AL process. Any label information becoming available throughout the AL process is not used so far to refine the model. With label information, for example, overlapping clusters assigned to different classes could be identified more easily. The approach above is called $\text{CMM}_{sha}$ (shared-components classifier) because in an unsupervised training approach all classes ``share'' the same density model. In a supervised approach, separate density models are trained for the different classes and then combined. This leads to the $\text{CMM}_{sep}$ (separate-components classifier) which may basically perform better in many applications regarding data modeling and classification accuracies. In an AL approach, we must start with a $\text{CMM}_{sha}$, but, when more and more labeled data become available, we may iteratively transform this $\text{CMM}_{sha}$ towards a $\text{CMM}_{sep}$. In a second step, we realized this idea by adopting techniques from non-parametric density estimation, nearest neighbor classification \cite{RC14}, and transductive learning. The latter is also a variant of semi-supervised learning where labels are found for unlabeled data using the labeled fraction of data. 
%%
%%Further, we introduced an AL setting that involves a transductive step \cite{RCS14}. 
%First, the components of the CMM$_{sha}$ are analyzed to
%%with respect to their uniqueness (a measure to evaluate if a component is responsible for generating samples that belong to only one class or for samples which belong to different classes) and during the AL process mutate to CMM$_{sep}$. By doing so, we are able to 
%identify the regions in the input space where the model should be improved. and locally update the classifier. Second, the current classifier is used for transductive learning: It labels the samples in the pool and a new CMM$_sep$ is build from scratch using these samples too. 
%\todo{BS@AC: Sollte man zu transductive mehr sagen? AC@BS: Nein}
More details about this AL technique can be found in \cite{RCS14}. 
Preliminary work has shown that the samples queried by means of this techniques are not completely biased to the actively trained CMM$_{sep}$ and can be (re-)used to train a different classifier paradigm as well, e.g., classifiers such as support vector machines (SVM).

%In \cite{RCS14} we have introduced two types of classifiers based on mixture models: $\text{CMM}_{sha}$ (shared-components classifier ) and $\text{CMM}_{sep}$ (separate-components classifier). $\text{CMM}_{sha}$ captures the structure information in an unsupervised way with a shared-components density model and is subsequently extended to a classifier. $\text{CMM}_{sep}$ utilizes the class information from the beginning of the training: first to build a separate-components density model by classes and then extended to a classifier. With the components we aim at modeling the underlying processes.

\item \textit{Exploit Structure for AL with SVM:} In principal, generative classifiers such as CMM often perform worse than discriminative classifiers such as SVM in many applications. But, on the other hand no density information (or, more general, information concerning structure of data in the input space of the classifier) can be extracted from standard SVM to use it in selection strategies (see below). Thus, a first idea would be to build a generative data model and a discriminative classifier in parallel in an AL process. Having investigated this idea first, we then decided to follow another idea in a third development step of our AL technique: 
We developed the responsibility weighted Mahalanobis (RWM) kernel \cite{RS15}, a new kernel for SVM that assesses the similarity of samples by means of a Mahalanobis distance in the case of Gaussian mixtures. Thereby, model components that are assumed to be ``responsible'' for the generation of a sample get a high weight. The RWM kernel can be used for AL with SVM in combination with various selection strategies. This third evolution step in our approach to capture structure in data is part of our ongoing research.
\end{enumerate}

%In \cite{RS11} and \cite{RS13} we have shown how structure in data can be captured by means of generative models (probabilistic hybrid mixture models) by using a PAL algorithm for classification problems. In \cite{RCS14} we have introduced two types of classifiers based on mixture models: $\text{CMM}_{sha}$ and $\text{CMM}_{sep}$. We have developed a new kernel function, the RWM kernel, which considers structure in data for similarity assessment by means of Gaussian mixture models. Thus, we are able to train both generative (CMM) and discriminative (SVM with RWM kernel) classifiers actively.


\subsection{Self-Adapting Selection Strategies}
%\todo[inline,caption={}]{Es muss klarer sein: \newline 
%	worum es geht \newline
%	\begin{itemize}
%		\item \checkmark es geht um die auswahlstrategie
%	\end{itemize}
%	warum man sich mit dem Punkt beschÃ¤ftigt
%	\begin{itemize}
%		\item \checkmark key component of AL
%		\item \checkmark query set should be diverse, therefore we are interested in capturing structure info
%		\item \checkmark the query set is not alway one
%	\end{itemize}}

A key component of an AL process is the selection strategy. Uncertainty sampling (US) strategies, for example, are frequently used in AL processes. The idea is to select the sample for which the classifier (or a committee of classifiers) is most uncertain concerning its class assignment. This approach has some drawbacks: As the queried samples are always close to the (current) decision boundary, the exploration of the input space may be suppressed, and if more than one sample is queried in each learning cycle, then the selected samples are similar to each other. A selection strategy should be able to detect all decision regions (exploration phase) and fine-tune the decision boundary (exploitation phase), which means that an efficient and effective selection strategy has to find a good trade-off between exploration and exploitation. Thus, our approaches for selection strategies are based on the following two hypotheses:
 \begin{enumerate}
	 \item A selection strategy has to consider various aspects and, thus, must combine several criteria.
	 \item In different phases of the AL process, these criteria must be weighed differently.
 \end{enumerate}

In a first step, we developed the selection strategy 3DS which combines three criteria \cite{RS11}:
\begin{enumerate}
	\item the \textit{density} of regions where samples are selected, 
	\item the \textit{distance} of samples to the decision boundary, and
	\item the \textit{diversity} of samples in the query set.
\end{enumerate}
The density is an exploration criterion, the distance is an exploitation criterion, and the diversity has to be considered for query sizes larger than one to avoid asking for redundant information (i.e., for efficiency reasons). These criteria can be weighed individually in a linear combination. Moreover, we developed a self-adaptation scheme for 3DS that 
%\todo{BS@AC: 2-3 Saetze ergaenzen, wie jeweils passende Werte fuer die Gewichte geschaetzt werden. AC@BS: ok?} 
weights the density criterion more strongly at the beginning of the AL process, in order to explore different regions. In later cycles it is necessary to exploit the gathered information, therefore the distance criterion is emphasized.  

In a second step, we extended the 3DS strategy by another criterion:
\begin{itemize}
	\item the class \textit{distribution} of samples is considered indirectly by evaluating responsibilities.
\end{itemize}
That is, this 4DS strategy (see \cite{RS13} for details) aims at labeling samples in a way such that the distribution of the samples approximates the unknown true class distribution. 
%\todo{BS@AC: Ein Satz dazu wieso das nuetzlich ist. AC@BS: ok?} 
This is especially beneficial for data sets with an unbalanced class distribution, as the generalization performance is improved. How can this be done as we do not know the labels in advance? This is possible (1) by assuming that processes in the ``true'' world can uniquely be assigned to classes (see above) and (2) by considering the responsibilities of model components (that model these processes) for the samples. Responsibilities are estimates of conditional probabilities, that indicate how likely specific processes modeled by corresponding components are ``responsible'' for ``the generation of a given sample'' (i.e., that the sample originates from the considered processes). 

The self-adaptation of weights in 3DS was extended in 4DS with the idea of focussing on the class distribution criterion in initial cycles of an AL process.

%The 4DS selection strategy \cite{RS13} combines the following four selection criteria: (1) distance of samples to the decision boundary, (2) density of regions where samples are selected, (3) diversity of samples in the query set, and (4) indirectly the unknown class distribution of samples. Therefore, 4DS tries to provide in each learning cycle a set of samples that are near the decision boundary, lie in high density regions, are not similar to each other, and the distribution of the samples approximates the unknown true class distribution. By doing so, the performance of AL is substantially increased.

\subsection{Parameter-free AL}
%\todo{BS@AC: Passt der Titel hier noch? AC@BS: Vorschlag: User-independent Parametrization}
%\todo[inline,caption={}]{Es muss klarer sein: \newline 
%	worum es geht \newline
%		\begin{itemize}
%			\item \checkmark we want to use methods that are parameter free
%		\end{itemize}
%	warum man sich mit dem Punkt beschÃ¤ftigt
%		\begin{itemize}
%			\item the more parameters there are, the harder is to use in real-world application
%		\end{itemize}
%		}

In an AL process, many parameters have to be set: parameters of learning algorithms for classifiers, parameters of selection strategies, etc. Typically, a real application of AL only allows for ``one shot'' for some of these parameters. The selection strategy, for example , should be parameter-free. Other parameters can be tuned, e.g., those of techniques that capture structure in unlabeled data before the AL process starts. 

In our work we addressed the following parameter types:
\begin{itemize}
	\item \textit{Parameters of techniques needed to capture structure in unlabeled data:} Appropriate parameters of the VI algorithm (see above) can in principal be found by repeated training and analysis of reached likelihood values, for instance. Another possibility is to analyze the representativity measure, as described in \cite{FKSO15}. 
	%\todo{There are a number of heuristics, cf.\ \cite{Bis94, Cho83} to estimate the only required parameter. Therefore, the parametrization can be done user-independently.}
	\item \textit{Parameters of the selection strategies:} Here, we realized the idea that the active learner should be free of such parameters. In 4DS (and 3DS) we start with appropriate initial weights of criteria in the linear combination and let the system self-adapt these weights (see above). A parameter that still remains as it has definitely to be set by a user is the query size. For a query size of one sample, 4DS already is parameter-free. For larger queries we still have to set the weight for the diversity criterion. Finding appropriate heuristics to set this parameter is part of our current research.
	\item \textit{Parameters of algorithms for classifier training:} Having found the density model, e.g., by means of VI, no further parametrization is required for constructing the CMM classifier, which can be trained using any available label information.
	%\todo{BS@AC: Hier auch was zur Parametrierung von CMM AC@BS: Satz hinzugefuegt. Fuer den Klassifikator ist keine Parametrisierung notwendig. Nur das Model (item 1) muss parametriert werden.} 
	The parametrization of SVM is part of our ongoing research. Here, we also aim at adapting the penalty factor $C$ (of $C$-SVM) and the kernel width $\gamma$ (of Gaussian kernels) considering the observations made while applying the parametrization heuristic for $C$ and $\gamma$ presented in \cite{KL03}.
\end{itemize}
%For some other parameter we have shown that the AL process is quite robust \todo{AC@BS: bzgl. $k$ ist der AL Prozess nicht sehr robust. } against modifications of values of these parameters. 
%\todo[inline]{BS@AC: Hier ergaenzen! Was war das? $k$ im transductive learning, ..., ..., vielleicht auch nicht alle angeben. AC@BS: Ausser $k$ gibt es den fusion threshold und einen treshold fÃ¼r die uniqueness measure. Bezueglich den letzten 2 ist der AL process nicht robust. Bzgl. $k$ -- Anzahl an Nachbarn -- haben wir nur die im Text stehende Aussage getroffen. Eine sehr genaue Untersuchung bzgl. Aenderungen von $k$ in einem AL Prozess haben wir noch nicht durchgefÃ¼hrt.}
%The number of nearest neighbors $k$ influences the transformation process of CMM$_{sha}$ towards CMM$_{sep}$ in an early stage of the AL process. Less transformation steps are required for a larger value of $k$, as ``general'' information is considered. Small values of $k$ lead to a exploitation of the local information, which may be desirable on data sets with strongly overlapping processes.

%AL settings that require the user to set a large number of parameters are hard to put to use in real-world applications.
%To avoid the difficulties associated with parametrization, we concentrate on using paradigms that have very few or no parameters to be set. An important advantage of using the \ac{VI} technique is that we can estimate the parameter (e.g., mixing coefficients, number of components, etc.) of the density model in an unsupervised manner. 4DS selection strategy requires the user to set only one parameter, the one that controls the influence of the diversity measure. Therefore, we are able to realize the PAL process largely (or fully) parameter-free.

\subsection{Summary of Preliminary Research}

We could show that our AL approach is able to boost the classification accuracy significantly. Here ``significantly'' actually means that we applied statistical tests to show the superiority of our techniques on certain significance levels. Apart from accuracy measures (to assess the effectiveness of our AL approach) such as the \textit{ranked performance} on a number of benchmark data sets, we also applied other measures to assess the efficiency of our AL approach (i.e., the learning speed) such as a \textit{data utilization rate} or the \textit{area under the learning curve} \cite{CKS06}. 
We also defined a new measure, the \textit{class distribution match} \cite{RS13}. 

Some (in our opinion) less important assumptions or achievements were not mentioned so far. Examples are the assumption that the computational costs of AL are negligible compared to labeling costs or the fact that our AL approach is in principal able to start the AL process with a completely unlabeled data set (in contrast to many other approaches).
%\todo{BS@AC: Hier ein Satz dazu? AC@BS: ich wuerde nein sagen, da wir jetzt ein case study section haben}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Preliminary Experimental Results}\label{sec:casestudy}

In this section we will compare our AL technique with RWM kernel and 4DS selection strategy to an AL technique with generative classifiers, $\text{CMM}_{sha}$ with 4DS strategy, and to an AL technique with discriminative classifiers, SVM with RBF (Gaussian) kernel and uncertainty sampling (US) strategy. First, we visualize the behavior of the two kernels on a two dimensional data set. Second, simulation experiments are conducted and evaluated for 20 benchmark data sets.

\subsection{Behavior of SVM with RBF and RWM Kernels}

We decided to visualize the behavior of SVM with RBF and RWM kernels on the Clouds data set from the UCI Machine Learning Repository \cite{AN07}. We performed a $z$-score normalization, conducted a stratified 5-fold cross-validation and choose the first fold for presentation here. Figures \ref{fig:USRBF} and \ref{fig:RWM4DS} show the state of SVM with RBF and RWM kernels at different cycles of the AL processes. The orange colored samples correspond to the 8 initially selected samples, whereas the actively selected samples are colored red if they are selected in the current query round otherwise purple. The support vectors are indicated by framing the specific samples with a black square. The decision boundary is depicted as a solid black line. In case of the RWM kernel, Figure \ref{fig:RWM4DS}, the gray colored ellipses correspond to level curves of the Gaussians the RWM kernel is based on (located at centers indicated by large $\times$s). Points on these level curves have a Mahalanobis distance of one to the center of the respective Gaussian.

We can see that the SVM with RBF kernel performs worse at the beginning of the AL process, as it does not exploit the unlabeled data. By using structure information derived from the unlabeled data, the RWM kernel achieves a noticeably higher classification accuracy, which is maintained until the end of the AL process. 

Furthermore, we can state that US selects samples near the decision boundary (e.g., Figure \ref{fig:RBFCycle112}), whereas the 4DS selection strategy by its explorative manner selects samples in other regions, too (e.g., Figure \ref{fig:RWM4DSCycle112}).

\input{figuresRBF.tex}

\input{figuresRWM.tex}

\subsection{Results for 20 Benchmark Data Sets}

To evaluate the performance of the active learner with RWM kernel and 4DS selection strategy numerically we conduct experiments on 20 publicly available data sets. For more information regarding general data set characteristics and experimental setup see \cite{RCS14}. The AL techniques are ranked based on a Friedman test \cite{Fri40} with a significance value $\alpha$ of $0.01$ followed by a Nemenyi test \cite{Nem63} as post hoc test. A detailed description of the evaluation method can be found in \cite{RS15}. 

The classification accuracies achieved by each of the AL paradigms are shown in Table \ref{tab:Accuracies}. The average ranks and the number of wins summarize the classification performance over all data sets. A good technique yields a low average rank and a large number of wins. The AL technique with RWM kernel and 4DS selection strategy performs best on 16 of the 20 data sets (highest number of wins) and achieves the smallest average rank. The critical difference (CD) plot of the Nemenyi test is shown in Figure~\ref{fig:CDplot}. As the differences of the average ranks between the active learner for SVM with RWM kernel and 4DS selection strategy and the other two paradigms are greater than the CD we can state that the former performs significantly better than the latter mentioned ones.
\input{tables.tex}

Furthermore, three additional evaluation measures are used to assess our results numerically: (1) the area under the learning curve (AULC)~\cite{CKS06}, (2) the data utilization rate (DUR)~\cite{CKS06}, and (3) the class distribution match (CDM)~\cite{RS13}. The evaluation results are summarized in Table \ref{tab:PerfromanceMeasures}. A good active learner achieves a large, positive AULC value, a DUR value less than one, a CDM value close to zero, and, of course, a large number of wins for each of the evaluation measures. Table \ref{tab:PerfromanceMeasures} shows that the AL technique with RWM kernel and 4DS selection strategy outperforms the other two paradigms regarding all evaluation criteria.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Challenges for Future Research on Collaborative Active Learning -- \textit{What are the unanswered questions that we will address?}}
\label{sec:Challenges}
%\todo[inline]{nicht zu technisch }

Up to now, we discussed the state of the art and, in particular, our own efforts to improve the state of the art. In the preceding section we have shown that significant achievements were made. Now, the curtain falls, and the stage is set for the next scene: \textit{collaborative active learning (CAL)}. In our future work we will answer many questions, most of which caused by the harsh limitations sketched in Section \ref{sec:Introduction}. To give some examples for questions:
%
%Most AL research concentrates on the question if a machine can learn with fewer samples if it is allowed to choose for itself from which data it learns, thus, focusing on developing high-performance selection strategies. The results of the research work have showed that this is possible, subject to some assumptions: There is only one oracle, the oracle has infinite wisdom, is available on demand and the cost for labeling is uniformly expensive. But in most of the real-world applications these assumptions do not hold. We can assume that the quality of labeling depends on the level of expertise and on the expert's form of the day. Thus, further questions arise: 
%
Is it possible to train a classifier actively with labels that are subject to uncertainty? Whom do we ask for labels, if there is a ``pool'' of experts available? Do we query label information from more than one expert? How do we exploit the various, possibly contradictory label information? Is it cheaper or faster, to query for label information for a process (e.g., modeled by a rule premise for which a conclusion has to be found) instead for a batch of samples? 
%Which is an adequate form for visualizing a modeled process? 
How can we give feedback to the experts and how can the experts in turn learn from the active learner? How do we determine if we reached a saturation point (e.g., more label information will not increase the performance)? 
%Considering  these realistic assumptions and questions, we should concentrate on investigating if a machine can learn more economically if it asks questions \cite{Set09}.

\subsection{Challenge 1: Uncertain Oracles}
%\todo[inline]{Klare Aufteilung in 
%		Problem statement: labels are subject to noise or uncertainty\\
%		Challenge: how to deal with it. How to model the noisy label, how to simulate a noisy oracle}
In a first step, we address the very obvious fact that oracles are not always right. In principal, labels are subject to uncertainty. Here, the meaning of the term uncertainty is adopted from \cite{MS97}. 
That is, ``uncertain'' is a generic term to address various aspects such as ``unlikely'', ``doubtful'', ``implausible'', ``unreliable'', ``imprecise'', ``inconsistent'', or ``vague''.

In real-world applications the labels may come from various sources, often but not always humans. Therefore, a new problem arises: The labels are subject to uncertainty for different reasons. For example, the performance of human annotators depends on many factors: e.g., expertise/experience, concentration/distraction, boredom/disinterest, fatigue level, etc. Furthermore, some samples are difficult for both experts and machines to label (e.g., samples near the decision boundary). Results of real experiments or simulations may be influenced, too: There may be stochasticity which is inherent to a certain process, sensor noise, transmission errors, etc., just to mention a few. Thus, we face many questions: How can we make use of uncertain oracles (annotators that can be erroneous)? How do we decide whether an already queried sample has to be labeled again? How do we deal with noisy experts whose quality varies over time (e.g., they gather experience with the task, they get fatigued)? How does remuneration influence the labeling quality of a noisy expert (e.g., if they are payed better, they are more accurate)? How can we decide whether the expert is erroneous or an observed process itself is nondeterministic? 

As a starting point, we may assume that the ``expertise of an expert'' (i.e., the degree of uncertainty of an oracle) is time-invariant and global in the sense that it does not depend on certain classes, certain regions of the input space of the model to be learned (e.g., a classifier), etc. Then, we may ask experts for either (1) one class label with a degree of confidence, (2) membership probabilities for each class (with or without confidence labels), (3) lower bounds for membership probabilities (cf.\ \cite{AS09}),
(4) a difficulty estimate for a data object that is labeled,
(5) relative difficulty estimates for two data objects (``easier'' or ``more difficult'' to label), etc. Then, we have to define appropriate ways to model that uncertainty (e.g., second-order distributions over parameters of class distributions in a probabilistic framework) and to consider it in selection strategies (e.g., with additional criteria) and for the training of a classifier (e.g., with gradual labels). 
%A possible solution for dealing with noisy labeling may be to ask the annotators to additionally provide for each class a confidence value associated to the label. Another possibility may be to require only one class and the associated level of confidence.

%Some related work that has to be considered for this challenge includes \cite{DL10}, which addresses binary classification problems in a PAL setting, assuming that the noise is non-uniformly distributed (sample-dependent). The goal is to construct a model that behaves similarly to the human oracle. Thus, it can be assumed that the initial model is not similar to the target model (the model to be learned), but as PAL advances the target model behaves similarly to the oracle. Two further assumption are made: First, the label is more likely to be correct if the oracle answers with high confidence. Second, the maximum posterior probability (the maximum probability for class membership given a certain sample) induced by the target model indicates the oracle's confidence, i.e., high posterior probability indicates high confidence, and vice versa. Based on these assumptions a two component selection strategy is developed, which \textit{explores} the pool of unlabeled samples and \textit{exploits} the set of labeled samples. The exploration component is favored in the early stages of the PAL as it examines the pool and selects the ``informative'' samples that are more likely to be labeled correctly. For that, US is used in combination with a regularization parameter to penalize the uncertainty as more and more labels become available. The exploitation component relabels (repeated-labeling) samples, by applying \textit{leave-one-out}~\cite{EncycML10} to estimate the posterior class probabilities of the labeled samples, comparing them with the current label of the ``left-out'' sample and selecting the one with the highest inconsistency for relabeling. In other words, the labeled samples are examined and the one that is more likely to have been labeled incorrectly is selected.
Different query strategies based on density power divergence~\cite{BSP11} (such as $\beta$-divergence and $\gamma$-divergence) for PAL are proposed in \cite{SUK+13}, under the assumption that there is a binary classification problem to solve and wrong labels are induced by careless mistakes or failures of experimental instruments. Thus, the noise is assumed to be uniformly-distributed over the samples space.


%\begin{itemize}
%\item \checkmark Active Learning with Human-Like Noisy Oracle, ICDM, 2010 \cite{DL10}
%\item \checkmark Active learning for noisy oracle via density power divergence, Neural Networks, 2013 \cite{SUK+13}
%\item An Analysis of Active Learning With Uniform Feature Noise, AISTATS , 2014 \cite{RPS+14}
%	\begin{itemize}
%		\item Setting: one-dimensional, binary classification; I don't we should mention it here.
%	\end{itemize}
%\end{itemize}


\subsection{Challenge 2: Multiple Uncertain Oracles}
In a second step, we address situations where several, individually uncertain oracles (e.g., several human experts with different degree of expertise) contribute their knowledge to an AL process. Thus, AL will now rely on the collective intelligence of a group of oracles. We see this step as a first important step towards collaborative active learning.

\begin{figure}[htb]
	\centering
	\input{images/cal_pool_based_cycle.tex}
	\caption{Learning cycle of PAL with multiple uncertain experts.}\label{fig:CALloop}
\end{figure}

In various applications, different, uncertain oracles may contribute labels to an AL process (cf.\ Figure \ref{fig:CALloop}). These experts may not only have different degrees of expertise. They also may have more or less expertise for different parts of the problem that has to be solved, e.g., for different classes that have to be recognized, for different regions of the input space, for different dimensions of the input space (attributes), etc. Also, experts may learn from others and improve over time, for instance. Now, we face many new questions: How can we recognize and model the expertise of humans? How can we decide whom to ask next and how can we merge the uncertain label information (cf.\ also challenge 1)? How can such exploration and exploitation phases be interwoven? Can we identify groups of experts that should cooperate in a labeling process?
%TODO
%\todo[inline]{BS@AC: Waere es vielleicht besser ueberall annotating statt labeling zu verwenden? AC@BS: ich wuerde nein sagen, da wir labeled/unlabeled samples haben. Ic wÃ¼rde label/annotate im Kombination mit samples als synonyme verwenden. Fuer das Labeln von Prozesse/Komponente wuerde ich annotate vorschlagen. BS@AC: Fuer Finetuning wÃ¤hrend wir das Paper intern weitergegeben haben.}
How to proceed if experts are only available on a part time basis?

As a starting point, we may initially assume that the ``expertise of an expert'' is known. In principal, we are convinced that generative, probabilistic models can be taken to model the individual knowledge of experts and not only the ``global'' knowledge of the active learner. Uncertainty may again be captured with second-order approaches. New selection strategies must then not only choose samples, but also oracles. If the expertise of an oracle is not known, it must be stated either by asking for difficulty or confidence estimates or by comparing it to the knowledge of others (e.g., by asking an expert who has to be assessed questions with already known answers). In order to explore solutions to challenge 2, we are also confronted with the problem of simulation: We have to simulate several uncertain oracles with the different characteristics mentioned above.

%In some context, several collaborating experts with different degrees of expertise or non-experts may be available. For very complex problems, there may be group of annotators, whose members have a high level of expertise on subproblems. 

%Furthermore, it is conceivable that oracles with a higher level of expertise are more expensive. Consequently, AL approaches should consider irregular costs wrt.~annotators (e.g., expensive vs.~ cheaper human domain experts).

%The challenge consists in deciding how to merge the information provided by the annotators and how to decide whom to ask next.
%We should be able to estimate the expertise of the experts and to merge the obtained label information. We may also investigate if the quality of an annotator improves over time or if it is possible that he learns from the others.
%If we assume that the annotators are not available on demand, a further challenge arise: Is it possible to obtain achieve estimates of the oracle annotation quality?

%Additionally we are confronted with the problem of simulation, as it we would like to compare the results obtained through an AL process to the performance of non-active paradigms. The challenge is to simulate a noisy oracle. A possible solution may be to represent the oracle as a Gaussian mixture model.

%Some related work that has to be considered for this challenge includes works that handle label noise and multiple (sometimes irresponsible) experts. Most approaches that deal with these problems use majority voting (a very simple but popular way) to reduce the influence of noisy labels \cite{VG14, SPI08, WSBT11, DC08, DCS09}. \cite{SPI08} for example makes use of repeated learning strategies to improve the labels quality inferred via majority voting. \cite{DC08, DCS09} uses higher costs for experts with higher expertise and solves a optimization problem to select in each active learning cycle the ``optimal'' combination of asked expert and queried sample. For this, budget constraints are considered, in which experts with higher expertise are assumed to provide labels with higher quality. This work is extended in \cite{WSBT11} by using sophisticated selection strategies for a better balancing between weaker and stronger experts. The main drawbacks of the previously mentioned works are: First, they assume that the expert's expertise are known (i.~e.~given by application knowledge), but to ensure that only the most reliable expert (the expert with the highest expertise) is ask (i.~e., the labeling costs are reduced the most), the reliability of the involved experts have to be explicitly estimated. Second, \cite{RYZ+09, WBBP10, YRF+10} suggest that majority voting is suboptimal. Works that address the challenge to estimate each expert's expertise are based on the idea either to build a classifier for each expert and approximate the expert's expertise using confidence values (cf.~\cite{CKW08, RYZ+09}) or to estimate the reliability of the experts based on a selected subset of samples, that is labeled by all involved experts. \cite{YRF+12} uses a probabilistic multi-labeler to model the expert's expertise. \cite{RYZ+09} proposes also a probabilistic model, which assumes that the answers of the expert are independent given the true labels. In addition, an EM algorithm is used to estimate the classification model and the performance of the multiple experts. \cite{DS09} adapted the approach for SVM to identify experts with low quality, so that they can be neglected. Under the assumption that strong experts behave similar \cite{CZC+10} develops an spectral clustering in the input space of the expert to identify strong experts. In \cite{FYZ13} transfer learning is used to select the most informative sample and its most reliable expert in each active learning cycle. Therefore also a probabilistic model is proposed that transfers knowledge from a rich set of labeled samples in some auxiliary domains to help model the experts' expertise. \cite{HLY+13} presents a distributed discriminative learning model that learns an ensemble of classifier from multiple noisy experts and allows to identify irresponsible experts online. 

%, or ``correct'' prelabeled data sets to measure the experts' expertises, i.~e.~their label qualities \cite{AVC10} for instance. Both methods require that the labeling process of the different experts is synchronized since the same samples have to be labeled from multiple experts in the same active learning cycle \cite{LSS11}. Two approaches that deal with (non-)stationary labeling qualities are proposed in \cite{DCS09}. Although reliable annotators can be selected, the labels for one sample still need to be synchronized over the selected annotators. An incremental labeling mechanism, which exploits AL to not only query unlabeled samples, but also select samples for relabeling until sufficient confidence is reached, is presented in \cite{ZSS11}. A probabilistic model, which assumes independence of the annotator judgment give the true label is showed in \cite{RYZ+09}. Am EM algorithm is developed to alternatively estimate the classifier and measure the performance of multiple annotators. In \cite{DS09}, it is showed how low quality (i.e., binary quality: either good or bad) and malicious annotators can be identified by adapting the formulation for SVM. Further, a method for pruning out low-quality annotators is proposed in \cite{DS092}. This is done by using the model trained from the entire labeled data set from all annotators as ground truth. Spectral clustering in the annotators space can be also used to identify good annotators, under the assumption that good annotators behave similarly, as shown in \cite{CZC+10}. A probabilistic multi-annotator model to learn from the crowds, which models the quality of each annotator by logistic regression is presented in \cite{YRF+12}. Furthermore, in \cite{HLY+13}, a collaborative computational model for AL with multiple human oracles is presented. The model captures the inherent correlations among annotators by sharing data among them. From the computational model a measure is derived to detect irresponsible annotators. A probabilistic model, that transfers knowledge from a rich set of labeled instances to help modeling the annotator's expertise, is introduced in \cite{FYZ13}.
	

%\todo[inline,caption= Challenge 2 -- Related papers]{
%\begin{itemize}
%\item Learning Active Fusion of Multiple Experts Decisions: An Attention-Based Approach, Neural Computation 23, 2011.
%\item \checkmark Active Learning from Multiple Knowledge Sources, AISTATS, 2012 
%\item Who Should Label What? Instance Allocation in Multiple Expert Active Learning, SIAM, 2011
%\item \checkmark Knowledge Transfer for Multi-Labeler Active Learning, ECML, 2013
%\item \checkmark Collaborative Active Learning of a Kernel Machine Ensemble for Recognition, 2013 IEEE International Conference on Computer Vision
%\item Proactive learning: cost-sensitive active learning
%with multiple imperfect oracles, CIKM, 2008: Proaktives Lernen unterl\"asst die zuvor erw\"ahnten restriktiven Annahmen (2)--(3) und nutzt dazu einen entscheidungstheoretischen Ansatz, um in jeder Anfragerunde sowohl das ``optimale'' Orakel als auch das informativste Muster aktiv zu wählen. Hierzu werden diese ``Auswahlm\"oglichkeiten'' in ein Optimierungsproblem überf\"uhrt, das einer festgelegten Budgetbeschr\"ankung unterliegt.
%\item From active to proactive learning methods, Domnez, 2010: Erweiterung von Proaktivem Lernen, wobei mehrere Orakel, die w\"ahrend des AL-Prozesses befragt
%werden k\"onnen, zus\"atzlich unterschiedliche Expertisen in verschiedenen Regionen des Eingaberaums besitzen. Zudem wird beruÌcksichtigt, dass Orakel ungleiche Bereitschaft zeigen k\"onnen, w\"ahrend des AL-Prozesses zu kooperieren.
%
%\end{itemize}
%}
\subsection{Challenge 3: Alternative Query Types}\label{subsec:AlternativeQueryTypes} 

By exploring and modeling the knowledge of oracles as sketched above, the costs of AL would increase substantially. In the other hand, we might ask oracles such as human experts for more abstract knowledge with the goal to reduce the number of queries this way.

In many applications, active learners could ask for more ``valuable'' knowledge. Examples are conclusions that a human expert gives for a presented rule premise, or correlations between different features or features and classes that an expert provides in order to identify important or redundant features. Questions that arise in this context are: Which questions can be asked? How can we provide (i.e., visualize, for instance) the required information to the expert? How can we combine different kinds of expert statements, e.g., about samples, rules, relations between features, etc? How can we use this information to initialize the models that are trained or to restrict the model capabilities in an appropriate way (e.g., if features are known not to be correlated?
                                                                                           
\begin{figure}[htb]
	\centering
	\includegraphics[scale=1.2]{RuleQuery}
	\caption{Asking for conclusions of rule premises.}\label{fig:RuleQuery}
\end{figure}

As a starting point, we could investigate the case of annotating rule premises with conclusions. To stay in a probabilistic framework we could obtain user-readable rule premises by marginalization of density functions from a generative process model. Figure \ref{fig:RuleQuery} gives an example for a density model consisting of three components in a three dimensional input space.
The first two dimensions $x_1$ and $x_2$ are continuous and, thus, modeled by bivariate Gaussians whose centers are described by larger crosses (+).
The ellipses are level curves (surfaces of constant density) with shapes defined by the covariance matrices of the Gaussians.
Here, due to the diagonality of the covariance matrices these ellipses are axes-oriented and their projection onto the axes is also shown.
The third dimension $x_3$ is categorical with categories A (red), B (green), and C (blue).
The distributions of $x_3$ are illustrated by the histograms next to every component.
Here, only categories with a probability strictly greater than the average are considered in rules in order to simplify the resulting rules. The components modeling sets of circles (green) and crosses (red) are already labeled, resulting in two rules for the components $i = 1$ and $i = 3$:
%Altogether, the following rule set can be extracted from the classifier in Fig.~\ref{fig:rules}:
\begin{quote}
  \begin{minipage}{\textwidth}
    if $x_1$ is \textit{low} and $x_2$ is \textit{high} and $x_3$ is A or $x_3$ is B
    \hspace*{0.0cm} then class = red,\\
    if $x_1$ is \textit{high} and $x_2$ is \textit{high} and $x_3$ is C
    \hspace*{0.0cm} then class = green.
		%\\
    %if $x_1$ is \textit{high} and $x_2$ is \textit{low}\\
    %\hspace*{0.35cm} then c = red
  \end{minipage}
\end{quote}
Now, the active learner presents the following rule premise and asks for a conclusion in form of a class assignment:
\begin{quote}
  \begin{minipage}{\textwidth}
    %if $x_1$ is \textit{low} and $x_2$ is \textit{high} and $x_3$ is A or $x_3$ is B\\
    %\hspace*{0.35cm} then c = red\\
    %if $x_1$ is \textit{high} and $x_2$ is \textit{high} and $x_3$ is C\\
    %\hspace*{0.35cm} then c = green\\
     $x_1$ is \textit{high} and $x_2$ is \textit{low} and $x_3$ is B.
		%\\
    %\hspace*{0.35cm} then class = red
  \end{minipage}
\end{quote}
This information could then be used to (re-)train a classifier, e.g., in a transductive learning step.
%%\todo[inline]{Klare Aufteilung in 
%%	Problem statement: acquire information not only for samples, but for processes\\
%%	Challenge: how to present a specific processes to the expert}
%Another unrealistic assumption of research work in AL is that only label information for samples should be queried. In some cases, it may possible for the annotator to provide additional information, too. The challenge consists in deciding which other forms a query may take, and how to extract the abstract knowledge from the annotators. For example, the learner may perform better and more economically if it queries labels for whole processes. Another possibility may be to query for constraints/relations between features and labels (e.g., ``70\% of the time, when \textit{age less than 20}, the class label is \textsc{tension-type headache}").

%In the following we discuss some work that can be seen to be related. A conventional AL-query consists in choosing an unlabeled sample (or a set of samples) and requesting a label (labels) from an expert. In \cite{CT12} AL is combined with Learning from Demonstration (LfD), that allows end-users to program new skills (e.g.~a special movement) on a robot with minimal effort. The aim of LfD is to learn a robot skills that can be generalized to unseen situations with a minimal number of demonstrations provided by humans. To combine AL and LfD \cite{CT12} presents three different query types (label, demonstration and feature queries). In a label query the robot executes a movement (specified by a trajectory) and asks whether the skill was preformed correctly. A demonstration query is used to learn a new skill for that a demonstration from the teacher is requested. A feature query is used for directly manipulating the representation of a skill by trying to identify a subspace or by assigning weights to features in such a way that a ``new'' skill is best represented. An other kind of AL techniques that uses two different query types has been successfully applied especially to solve documents or more generally text classification problems \cite{RMJ06, DSM09, GYM11}. Here, not only samples but also features are queried and presented to a domain expert for improving the learning process. It has been shown experimentally that labeling features is useful in the presence of few labeled samples (i.e., at the beginning of the AL process). In \cite{RMJ06, GYM11} the labeled features are used for feature selection or re-weighting while in \cite{DSM09} they are used as proxies for sample labels.

\subsection{Challenge 4: True Collaboration of Human Experts in AL}\label{subsec:TrueCAL} 

In a fourth step we could pave the way for a true collaboration of human experts in AL, which will essentially be based on the capability of humans to learn and the ability of the active learner to provide appropriate feedback to the humans to enable them to learn. Then, the new technique actually deserves to be called CAL.

In particular applications, experts would be interested in getting feedback from an active learner, in improving their own knowledge, and sharing their expertise with others. As an important requirement, the active learner must be able to give feedback to the humans and asking for comments on such feedback. Some possible kinds of interactions with humans are (cf.\ also \cite{HS07}):
\begin{quote}
  \begin{minipage}{\textwidth}
	  The following rule appears to be very certain because ... !\\
    The following rule is in conflict with your knowledge because ... !\\
		Other experts are much less uncertain concerning the following rule than you are ... !\\
		Can you confirm the following rule ... ?\\
		Can you confirm that the following two features are not correlated ... ?\\
		Can you confirm that the following feature is very important ... ?\\
		Can you provide additional samples for the following regions of the input space of the classifier ... ?
  \end{minipage}
\end{quote}
Solutions to this challenge (which is based on appropriate solutions for the preceding three challenges) will open the door for online AL (cf.\ SAL mentioned in Section \ref{sec:Foundations}). Some of the many new questions that have to be answered are: How can we deal with time-invariant knowledge of oracles? Which information should be provided and how (e.g., with/without certainty estimates, restriction to ``crisp'' rules or not)? How must we adapt the active learner and the selection strategies? In particular, a compromise has to be found between modeling capabilities on the one hand and the abilities of humans to actually understand readable rules on the other.

As a starting point, we may stay within our probabilistic framework, consider the individual knowledge of humans (challenge 2) and present samples and rules (obtained by marginalization from density models to make them human-readable as sketched above, challenge 3) with fused statements (labels or conclusions) and certainty estimates. Then, the time-variance of human knowledge must be considered by extending the solutions from challenge 2. Again, the evaluation of any proposed techniques will be a challenge by itself.

%To the best of our knowledge, there are no publications focusing on AL techniques that include feedback to human experts and expertise sharing.


\subsection{Challenge 5: Complex Cost Schemes} 
%\todo[inline]{Klare Aufteilung in 
%	Problem statement: variance in cost.~some classes are more expensive than other; misclassification cost \\
%	Challenge: develop a selection strategy that regards these assumptions}

In many real-world applications obtaining class information may be possible at different costs, e.g., some class information is more expensive than other or the labeling costs depend on the location of the sample in the input space. This already applies to a ``conventional'' AL setting without the many ideas discussed in challenges 1 -- 4. In a CAL setting, considering complex cost schemes is even more important.
%TODO mit Bernhard nochmal darueber sprechen
%\todo{BS@AC: Further, the misclassification cost may be non uniform. -- Was hat das mit labeling costs zu tun? AC@BS: ich dachte es gÃ¤be einen indirekten Zusammenhang, vielleicht bei der Musterauswahl. Wenn fÃ¼r eine Klasse die misclassification costs sehr hoch sind, sollte die Auswahlstrategie dies berÃ¼cksichtigen.}

For CAL applications, we must consider costs that depend on
\begin{enumerate}
	\item \textit{samples with their classes:} As mentioned above, labeling costs may depend on the class (e.g., some kinds of error classes in an industrial production process may be more difficult to detect than others) or on the location of the sample in the input space (e.g., samples close to the decision boundary require higher temporal effort), for instance.
	\item \textit{query types:} It is obvious that different labeling costs have to be foreseen for samples (with or without certainty estimates) or for more complex queries such as rule premises. The cost schemes have to be even more detailed in a CAL setting with feedback to the humans (e.g., with queries such as ``Can you confirm that ...?'').
	\item \textit{oracles (experts):} The costs of humans may depend on their expertise, their temporal effort, their availability (e.g., working hour may be modeled with finite costs, otherwise costs are infinite), etc.
\end{enumerate}
In principle, all these costs may change over time, too. The basic questions in this context are: How can a cost scheme be defined? How must the selection strategies be adapted?

As a starting point, we suggest to choose the first point from the list above and investigate solutions in a ``classical'' AL setting. Then, the most important case for CAL must be addressed, second point. After successfully extending the cost schemes to address the first two tasks we advance to apply CAL with human experts, third point.

%Thus, there is variance in the cost of obtaining label information. Further, the misclassification cost may be non uniform.  Consequently, AL approaches should consider irregular costs wrt.~samples (the labeling cost depends on the sample position in the input space) or the misclassification cost. Considering misclassification cost may be particularly relevant if solving problems with imbalanced data sets (skewed label distribution). The challenge consists in developing a selection strategies that regard the previous, more realistic assumptions. 
%Further challenges may be to detect rare classes or multi-label learning (i.e., a sample may be associated to more than one class).
%
%Furthermore, it is conceivable that oracles with a higher level of expertise are more expensive. Consequently, AL approaches should consider irregular costs wrt.~annotators (e.g., expensive vs.~ cheaper human domain experts).

% % First paper
%Some related work that has to be considered for this challenge includes~\cite{JF14}, which suggests a new AL-framework for computed-assisted translation systems that should support the translators in their work. The main idea is to find a trade-off between translation quality and productivity (i.e.,~translation effort), by allowing the translator to supervise only the translations of the most ``informative'' sentences. Three properties for determining the ``informativeness'' of the sentences, and the according selection strategies, are proposed: \textit{Uncertainty} describes how unsure the model is about the translation of a sentence. \textit{Representativeness} tells how representative a sentence for a block of sentences is and \textit{unreliability} expresses the number of words contained in a sentence that do not appear in the training set, but in a specific block of sentences. 
%Depending on the number of sentences to be supervised, a specific translation quality can be reached. For example, a translation agency may decide to reduce costs and increase the productivity of translating user manuals for electronic devices (i.e., small number of supervised sentences) by scarifying translation quality. 
%The results showed that AL-techniques can reduce the translator's effort, assessed by keystroke and mouse-action ratio (KSMR) \cite{BBC+09}, by one half. 
%Furthermore, if all sentences have to be supervised (e.g., legal document) the order in which they are considered affects the translator's effort. Thus, the costs may be reduced by applying AL with a suitable selection strategy. 
% % Second paper
%In \cite{SCF08} an empirical study of labeling costs in four text and image classification problems is presented. It is assumed that the time required for labeling is the actual cost, which is not known in advance. Therefore, questions like: ``Are annotation times variable for a given task or domain?'', ``Do times vary from one annotator to the next?'' or ``Can we improve active learning by utilizing cost information?'' are addressed and analyzed on the basis of four data sets and three human experts. The analysis in \cite{SCF08} concludes that: (a) the labeling costs may vary considerably across samples, (b) ignoring cost information does not lead to a better performance than random, (c) if the costs can be accurately predicted, than the AL process may be improved, (d) the cost may vary across experts and (e) for some problems, the labeling cost can be predicted accurately, even after querying labels a small number of samples.
% % Third paper
%Three approaches that regard the cost (i.e., labeling time), which is known in advance, in an AL selection strategy are investigated for natural language problems on one data set (\textmd{MUC}$7_{\tau}$) in \cite{TH10}. The first selection strategy, fixed maximal budget per sample, constrains querying samples that would generate costs larger than a given maximum cost. The second strategy, linear rank combination, ranks the samples according to a linear combination of utility (i.e., informativeness) and cost. The third selection strategy ranks the samples based on their benefit-cost ratio, which is the ratio between the utility and cost. The experimental results showed that the three cost-sensitive selection strategies outperformed the cost-insensitive ones in the early stage of the AL process. 
%Further, BCR has a slight advantage compared to the other two selection strategies. 
%Nevertheless, in real-world scenarios the cost is mostly not known in advance, thus it has to be predicted.

\subsection{Further Challenges}

Some other important challenges must be addressed as well or they will be subject to future research. Apart from these challenges we still face the already discussed requirements such as ``parameter-free'' AL or self-adaptation of selection strategies. 

%\todo[inline]{Klare Aufteilung in \\
%	Problem Statement: when do we terminate the AL process\\
%	Challenge: develop stopping criteria that is suitable for real-world application}
\begin{enumerate}
\item{\textit{Stopping Criterion:}} Currently, the stopping criterion in real-world applications is based on economic factors, e.g., the learner queries samples as long as the budget allows it. The challenge consists in knowing when to stop querying for labels. One possibility may be to determine the point at which the cost of querying more labels is higher than costs for misclassification. Another possibility is to determine when the learner is at least as good as the group of annotators. 
%In other words, when the classification performance reaches a plateau, the AL process should be stopped. 
For such a ``self-stopping criterion'', the active learner should be able to assess its own performance. 

\item{\textit{Performance Assessment:}} In AL, the performance of an active learner must be assessed by means of several criteria to capture effectiveness and efficiency of AL. For this purpose, we used a ranked performance measure, a data utilization measure, the area under the learning curve, and a class distribution measure in our preliminary work (see, e.g., \cite{RS13,RCS14}). CAL requires additional measures, e.g., to assess the various learning costs or to evaluate the learning progress of human experts.

%\todo[inline]{Klare Aufteilung in \\
%	Problem Statement: the processes change\\
%	Challenge: the models should react on changes; they should be updated; self-adapting models}
\item{\textit{Dynamic Environment:}} Above, we have sketched CAL which takes place in a time-variant environment in the sense that the knowledge of experts improves over time. But, the observed and modeled processes could be time-variant, too. That is, these processes may change slightly (e.g., due to increased wear), become obsolete or new processes corresponding to known or to new, previously unknown, classes may arise during the application of the model. Then, a major challenge consists in developing online AL / CAL techniques that cope with such effects. Mixtures of PAL and SAL techniques would be needed.
\end{enumerate}

%In relation to the stopping criterion some related work includes \cite{SC00}, which terminates the AL process with SVM if the next sample to be queried is further away from the decision hyperplane than any of the support vectors. The idea of stopping the AL process when the confidence of the classifier on an external test set remains at the same level or drops for a specified number of consecutive cycles is presented in \cite{Vlachos08}. An intrinsic stopping criterion for committee-based AL is proposed in \cite{FK09}. If the members of the committee are in complete agreement concerning the classification of a validation set, the AL process is stopped. Further stopping criteria that regard the maximum confidence, the minimum expected error, overall uncertainty, or classification change are presented in \cite{ZH07, ZWH08a, ZWH08b}.

\section{Summary and Outlook}\label{sec:SummaryOutlook}

In this article, we have sketched our vision of collaborative active learning which will certainly be discussed in more detail in the near future. In the novel field of CAL, we would like to concentrate on developing classifiers that take class information uncertainty into consideration, identifying the annotators' level of expertise,
%. We should be able to determine and model the level of expertise during the AL.
making use of different levels of expertise and fusing possibly contradicting knowledge,
%. Supposing that experts with a high level of expertise are more expensive than the experts with a lower level of expertise, we should optimize a cost function to train a classifier more economically.
labeling abstract knowledge, and
% Instead of querying labels for samples, we should query for class information for components or for constraints between features and labels (see Section \ref{subsec:AlternativeQueryTypes  }).
%	\item fusing the knowledge/expertise. As the class information provided by the noisy experts are subject to variance and may be contradictory, we should develop a mechanism to fuse the different, possibly contradictory, class information.
 improving the expertise of the experts. 
In the envisioned CAL system, human domain experts should benefit from sharing their knowledge in the group. They should receive feedback which will improve their own level of expertise.

In principal, many application areas could benefit from CAL techniques. We can distinguish two possible basic cooperation scenarios: First, scenarios involving specialists (e.g., industrial experts) and, second, scenarios involving non-experts (e.g., crowd-sourcing).

In the former scenario, the number of humans will be lower, the humans are motivated, their expertise will be easier to capture, they collaborate over longer time periods, etc. 
Typical industrial problems are, for example, product quality control (e.g., deflectometry, classification of errors on silicon wafers or mirrors, analysis of sewing or garments in clothing industry, etc.), fault detection in technical and other systems (e.g., analysis of fault memory entries in control units of cars, analysis of different kinds of errors in cyber-physical systems, etc.), planing of product development processes (e.g., in drug design), or fraud detection and surveillance (e.g., credit card fraud, detection of tax evasion, intrusion detection, or video surveillance). This scenario may be called \textit{Dedicated CAL}.

In the latter scenario, we face larger, open groups of people that will be available for shorter time spans. 
Typical crowd-sourcing applications will address problems where queries (samples or rules) can easily be understood and assessed by many people including ``non-experts'' and, thus, be based on video, audio, text or image data. CAL may even be a core component of recommender systems, e.g., to suggest television programs. This scenario may be called \textit{Opportunistic CAL}, as the active learner hay to make the most of the current situation.

%\subsubsection{Industrial problems}
%%\href{http://www.iosb.fraunhofer.de/servlet/is/16677/}{Fraunhofer}\footnote{Deflectometry for the inspection of specular surfaces: \url{http://www.iosb.fraunhofer.de/servlet/is/16677/}}, \href{http://www.isravision.com/likecms.php?nav=869&siteid=1258&entryid=}{ISRA Vision AG}\footnote{ISRA Vision: \url{http://www.isravision.com/likecms.php?nav=869&siteid=1258&entryid=}} and \href{http://www.micro-epsilon.de/measurement-systems/Paint-Inspection/karosserie/index.html}{Micro-Epsilon}\footnote{Paint inspection of car bodies: \url{http://www.micro-epsilon.de/measurement-systems/Paint-Inspection/karosserie/index.html}} 
%
%\paragraph{\textbf{Deflectometry}}  
%Industrial companies have developed systems to automatically detect defects on the paint coat. The next step may be, not only to detect the imperfection, but to classify them too. A possible scenario may look like this: The pool consists of the instances that proved to be defective. The most informative instances are selected, based on a specific selection strategy, and presented to the human domain experts. The experts annotate the instances and the classifier is updated. A further goal may be to react to different types of imperfections automatically and accordingly.
		 %
%\paragraph{\textbf{Silicon wafer / mirror quality}} The goal is to classify defects (e.g., scratches or cracks) of silicon wafers or mirrors. A possible scenario may be similar to the previous one, as the domain experts classify the different defects based on a images of the defective silicon wafers.
%
%\paragraph{\textbf{Quality control}} The previous two scenarios may be applied to different (automated) quality control tasks from various industries, such as: milling industry (e.g., check for irregularities), clothing industry (e.g., check the sewing of the garments) or pharmaceutical industry (e.g., check the purity of drugs).
%
%\paragraph{\textbf{Vehicle diagnosis}} The huge number of vehicle issues may be facilitated by the use of AL, especially for non-routine problems. The pool consists of instances describing the problems. The group of oracles is represented by the car mechanics. Through knowledge sharing they can improve their expertise and correct the problems faster.  %\href{http://www.bosch.us/content/language1/html/10615.htm}{Bosch}\footnote{Deflectometry for the inspection of specular surfaces: \url{Data Mining Research Engineer - Active Learning: http://www.bosch.us/content/language1/html/10615.htm}}\footnote{Data Mining Research Intern: Sequential Active Learning: \url{http://www.bosch.us/content/language1/html/11081.htm}} may interested in this research theme.
%
%\paragraph{\textbf{Fraud detection in utility networks}} After an anomaly has been detected in an electricity grid, the experts may be queried for the cause.
%
%\paragraph{\textbf{Surveillance}} (a) Identify a person in a video surveillance system. (b) Intrusion detection and classification in a network environment. (c) Actively classify threats in a video surveillance system.
%
%\paragraph{\textbf{Segmentation}} Actively choose which samples should be manually segmented by an oracle.
%
%\paragraph{\textbf{Calculatory system for granting credits / detecting possible tax evasion}} The goal is to decide if a person should get a loan or if a person should be suspected for tax fraud. In order to come to a conclusion, experts with different fields of expertise have to be consulted. Each expert has access only to features that are related to his field of expertise. 
%
%\paragraph{\textbf{Visualizing big data}} The goal is to get the data in the right shape in the visualization space, so that it can be visualized. In this case the oracles must posses solid domain expertise, as knowing what they are trying to visualize out of the data is crucial. For example, the oracles may have the possibility to drag samples or clusters to the desired position.
%
%\paragraph{\textbf{Biological experiments}} The goal may be to find a drug for a specific disease. For example, to speed up the high-throughput screening (HTS) an active learner has to generate a compound that is most probable to be a hit. This type of problems may be solved by using membership query synthesis AL. 
%
%\subsubsection{Crowd-sourcing} 
%Probably, classification problems that involve video, audio, text or image data are more suitable to be solved by  crowd-sourcing. In this cases, the queries should be easily interpretable, because non-experts are used as oracles.

%\section{Objectives -- What would we essentially like to do?}
%\label{sec:Objectives}
%We would like to concentrate on:
%\begin{itemize}
	%\item on developing classifiers that take the class information uncertainty into consideration.
	%\item identifying the annotator's level of expertise. We should be able to determine and model the level of expertise during the AL.
	%\item making use of different levels of expertise. Supposing that experts with a high level of expertise are more expensive than the experts with a lower level of expertise, we should optimize a cost function to train a classifier more economically.
	%\item labeling abstract knowledge. Instead of querying labels for samples, we should query for class information for components or for constraints between features and labels (see Section \ref{subsec:AlternativeQueryTypes  }).
	%\item fusing the knowledge/expertise. As the class information provided by the noisy experts are subject to variance and may be contradictory, we should develop a mechanism to fuse the different, possibly contradictory, class information.
	%\item improving the expertise of the experts. The human domain experts should benefit from sharing their knowledge in the group. They should receive feedback which will improve their level of expertise.
%\end{itemize}

\todo{BS@AC: Literaturstellen sehr uneinheitlich, fehlende Informationen, evtl teilw. falscher Bib-Typ.}

\biboptions{sort&compress}
\bibliographystyle{elsart-num-sort.bst}
\bibliography{bib/bibliography}

\listoftodos

\end{document}

figuresRBF.tex
\newcommand{\prefWidth}{0.24}
\begin{figure}[H]
	\begin{center}
		\subfigure[Cycle  0]{\label{fig:RBFCycle0}\includegraphics[width=\prefWidth\textwidth]{images/clouds_RBF_0.pdf}}
		\hfill
		\subfigure[Cycle  12]{\label{fig:RBFCycle12}\includegraphics[width=\prefWidth\textwidth]{images/clouds_RBF_12.pdf}}
		\hfill
		\subfigure[Cycle  112]{\label{fig:RBFCycle112}\includegraphics[width=\prefWidth\textwidth]{images/clouds_RBF_112.pdf}}
		\hfill
		\subfigure[Learning Curve]{\label{fig:RBFLearningCurve}\includegraphics[width=\prefWidth\textwidth]{images/clouds_RBF_112_graph.pdf}}
	\end{center}
	\vspace{-2.0em}
	\caption{Different stages of an AL process with SVM using RBF kernel and US selection strategy. The samples with known label are colored orange (initially selected) and red or purple (actively selected). The decision boundary is depicted as a solid black line.}
	\label{fig:USRBF}
\end{figure}
figuresRWM.tex
% \prefWidth is set in figuresRBF.tex
\begin{figure}[H]
	\begin{center}
		\subfigure[Cycle 0]{\label{fig:RWM4DSCycle0}\includegraphics[width=\prefWidth\textwidth]{images/clouds_RWM_4DS_0.pdf}}
		\hfill
		\subfigure[Cycle 12]{\label{fig:RWMvCycle12}\includegraphics[width=\prefWidth\textwidth]{images/clouds_RWM_4DS_12.pdf}}
		\hfill
		\subfigure[Cycle 112]{\label{fig:RWM4DSCycle112}\includegraphics[width=\prefWidth\textwidth]{images/clouds_RWM_4DS_112.pdf}}
		\hfill
		\subfigure[Learning Curve]{\label{fig:RWM4DSLearningCurve}\includegraphics[width=\prefWidth\textwidth]{images/clouds_RWM_4DS_112_graph.pdf}}
	\end{center}
	\vspace{-2.0em}
	\caption{Different stages of an AL process with SVM using RWM kernel and 4DS selection strategy. The samples with known label are colored orange (initially selected) and red or purple (actively selected). The decision boundary is depicted as a solid black line.}
	\label{fig:RWM4DS}
\end{figure} 


cal_pool_based_cycle.tex
\tikzstyle{background grid}=[draw, black!50,step=.5]
\begin{tikzpicture}[line width = 1pt]

	\node  at (0,0){
        \includegraphics[scale=.5]{images/cal_pool_based_cycle_stop_crit.png}};
        
	\node [align=left] at (-0.05,-.25) {Uncertain Oracles};    
	
	\node at (-1.85,-1.85) {\scriptsize{Pool}};        
	\node at (-2.1,-.85) {\textit{\scriptsize{Selection Strategy}}};
	\node at (1.8,-1.85) {\scriptsize{Labeled Set}};        
	\node at (-0.2,-2.85) {\scriptsize{Classifier}};
	\node at (-1.6,-2.6) {\scriptsize{break?}};
		

	\node  at  (-2.2,-3.15) {\footnotesize{Active Learner}}; 
   	
\end{tikzpicture}

al_scenarios.tex
\tikzstyle{background grid}=[draw, black!50,step=.5]
\begin{tikzpicture}[line width = 1pt]

	\node  at (0,0){
        \includegraphics[scale=.4]{images/al_scenarios.png}};

	\node [align=center] at (.72,2.5) {Learner generates\\a query};        
	\node [align=center] at (.72,0) {Learner decides\\to query or not};        
	\node [align=center] at (.72,-2.5) {Learner selects\\the best query};        
	
	\node [align=center] at (.72,3.5) {\textbf{Membership Query Learning}};        
	\node [align=center] at (.72,1) {\textbf{Stream-based Active Learning}};        
	\node [align=center] at (.72,-1.5) {\textbf{Pool-based Active Learning}};        


	
%	\node [align=center] at  (-0.1,-3.7) {Active Learner\\with Selection Strategy};        
	\node [align=center] at  (-2.3,-3.5) {Pool};        


	\node [align=center] at (-4.3,0.1) {Data\\Source};        
	\node[align=center] at (3.8,-1.) {Oracle};        
	

   	
\end{tikzpicture}
pool_based_cycle.tex
\tikzstyle{background grid}=[draw, black!50,step=.5]
\begin{tikzpicture}[line width = 1pt]

	\node  at (0,0){
        \includegraphics[scale=.4]{images/pool_based_cycle_stop_crit.png}};

	\node at (-3.8,-.8) {Pool};        
	\node [align=center] at (-3.6,2.4) {\textit{Selection}\\\textit{Strategy}};
	\node at (0,1.8) {Oracle};        
	\node[align=center] at (3.75,-1.) {Labeled\\Set};        
	\node  at  (0.,-3.1) {Classifier};
	\node at (-3.2,-2.2) {\small{break?}};
	
	\node  at  (-3.3,-3.6) {Active Learner};        

   	
\end{tikzpicture}

tables.tex
	
\begin{table*}[htb]
	\caption{Classification accuracy (in \%) on test data (5-fold cross validation results) for AL of SVM with RBF kernel and US selection strategy, $\text{CMM}_{sha}$ and 4DS selection strategy, and SVM with RWM kernel and 4DS selection strategy. The best results are printed in bold face. A good paradigm yields a small rank and a large number of wins.}
	\label{tab:Accuracies}
	\centering
	\vspace{0.5em}
	\scriptsize{
		\begin{tabular}{l c c c }
			\toprule
			Data Set & RBF kernel with US  & $\text{CMM}_{sha}$ with 4DS  & RWM kernel with 4DS  \\
\midrule
Australian & 84.06 & 81.01 & \textbf{85.65} \\
Clouds & 77.20 & \textbf{89.30} & 88.92 \\
Concentric & 99.52 & 97.32 & \textbf{99.64} \\
CreditA & 84.35 & 77.97 & \textbf{85.65} \\
CreditG & 71.20 & 69.60 & \textbf{72.40} \\
Ecoli & \textbf{85.73} & 80.30 & 85.15 \\
Glass & 65.89 & 56.08 & \textbf{71.01} \\
Heart & 82.96 & 81.11 & \textbf{84.81} \\
Iris & 96.67 & 84.00 & \textbf{98.00} \\
Page Blocks & 93.06 & 94.37 & \textbf{94.52} \\
Phoneme & 80.50 & 79.22 & \textbf{80.66} \\
Pima & \textbf{76.04} & 70.18 & 75.00 \\
Ripley & 88.96 & 90.24 & \textbf{90.40} \\
Satimage & 75.39 & 83.92 & \textbf{86.33} \\
Seeds & 91.43 & 92.86 & \textbf{97.62} \\
Two Moons & 95.50 & 99.99 & \textbf{100.00} \\
Vehicle & \textbf{80.02} & 61.11 & 76.84 \\
Vowel & 77.98 & 88.89 & \textbf{93.23} \\
Wine & 97.21 & 96.06 & \textbf{98.32} \\
Yeast & 56.94 & 44.47 & \textbf{58.08} \\[0.5em]
Mean & 83.03 & 80.90 & 86.11 \\[0.5em]
Rank & 2.200 & 2.600 & 1.200 \\
Wins & 3.0 & 1.0 & 16.0 \\
\bottomrule
		\end{tabular}
	}
\end{table*}


% % % % % % % % % % % % % % % % %
%REQUIRED FOR THE DESCRIPTION
%[40.641 s, ãmainã, ActiveFriedmanTest.main(139)] INFO: alpha: 0.01
%[40.646 s, ãmainã, FriedmanTest.doFriedmanTest(486)] INFO: Î§Â²F: 20.80
%
%[40.647 s, ãmainã, FriedmanTest.doFriedmanTest(498)] INFO: p-Value from Friedman table: 9.3
%[40.647 s, ãmainã, FriedmanTest.doFriedmanTest(501)] INFO: There is significantly difference between the ranks -> Proceeding with a post-hoc test
%[40.648 s, ãmainã, FriedmanTest.doNemenyiTest(529)] INFO: q_Î± = 3.0978348083782645
%[40.648 s, ãmainã, FriedmanTest.doNemenyiTest(566)] INFO: CD = 3.0978348083782645\sqrt\\{\frac{3 \cdot 4}{6 \cdot 20}\\}
%[40.648 s, ãmainã, FriedmanTest.doNemenyiTest(568)] INFO: CD: 0.9796213809426578
% % % % % % % % % % % % % % % % %

\begin{figure}[htb]
	\centering

		\begin{tikzpicture}[xscale=1]
		
		 \tikzstyle{every node}=[font=\scriptsize] % remove for PDF export
		
		\node[anchor=south] at (1 + 0.490, 0.8) {CD = 0.980};
		\draw [|-|] (1, 0.8) -- (1 + 0.980, 0.8);;
		\draw (1, 0) -- coordinate (x axis mid) (3, 0);
		\foreach \x in {1, ..., 3}  \draw (4-\x, 0pt) -- (4-\x, 6pt) node[anchor=south] {\x};
		\foreach \x in {1, 1.5, ..., 3}
		\draw (\x, 0pt) -- (\x, 3pt);
		\matrix [matrix of nodes,row sep=0.01cm,column sep=2.5cm,column 1/.style={anchor=east},column 2/.style={anchor=west}] at (2.0, -.6)
		{
			\node (4DS CMM) {$\text{CMM}_{sha}$ with 4DS};  &  \node (4DS RWM) {RWM kernel with 4DS};\\
			\node (US MRBF) {RBF kernel with US};  & \\
		};
		\draw (4DS RWM)[anchor=east] -| (4-1.200, -0.05);
		\draw (US MRBF)[anchor=east] -| (4-2.200, -0.05);
		\draw (4DS CMM)[anchor=east] -| (4-2.600, -0.05);
		\draw[black, very thick] (4-2.600,-0.2) -- (4-2.200,-0.2);
		\end{tikzpicture}

	\vspace{-0.3em}
	\caption{Friedman test with significance value $\alpha$ of 0.01 followed by a Nemenyi post hoc test. Active learners that are connected do not achieve classification accuracies that are significantly different.}
	\label{fig:CDplot}
\end{figure}

\begin{table*}[!ht]
	\caption{Summary of performance regarding additional evaluation criteria. Larger, positive mean AULC values, smaller mean DUR values and CDM values close to zero are indicators for a good AL approach. }
	\label{tab:PerfromanceMeasures}
	\centering
	\vspace{0.5em}
	\scriptsize{
		\begin{tabular}{l c c c  c  c  c }
			 \toprule 
			 \multirow{2}{*}{Active Learner}& \multicolumn{2}{c}{AULC} & \multicolumn{2}{c}{DUR} & \multicolumn{2}{c}{CDM} \\
			 \cmidrule(lr){2-3} \cmidrule(lr){4-5} \cmidrule(lr){6-7}
			 & Mean & Wins & Mean & Wins & Mean & Wins \\
			 \midrule
			 RBF kernel with US  & 0.000 & 7.0 & 1.000 & 6.0 & 0.080 & 4.0 \\[0.25em]
			 $\text{CMM}_{sha}$ with 4DS & -1.407 & 2.5 & 1.970 & 1.5 & 0.058 & 3.5 \\[0.25em]
			 RWM kernel with 4DS  & 2.978  & 10.5 & 0.947 & 12.5 & 0.048 & 12.5 \\
			 \bottomrule
		\end{tabular}
	}
\end{table*}

CALConcept.bbl
\begin{thebibliography}{10}
\expandafter\ifx\csname url\endcsname\relax
  \def\url#1{\texttt{#1}}\fi
\expandafter\ifx\csname urlprefix\endcsname\relax\def\urlprefix{URL }\fi

\bibitem{AMT}
Amazon, Mechanical {T}urk, \url{https://www.mturk.com/mturk/welcome} (letzter
  Zugriff 03/31/2015).

\bibitem{AS09}
D.~Andrade, B.~Sick, Lower bound bayesian networks -- an efficient inference of
  lower bounds on probability distributions in bayesian networks, in:
  Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial
  Intelligence, AUAI Press, 2009, pp. 10--18.

\bibitem{Angluin88}
D.~Angluin, Queries and concept learning, Machine Learning 2~(4) (1988)
  319--342.

\bibitem{AN07}
A.~Asuncion, D.~Newman, {UCI} {M}achine {L}earning {R}epository,
  \url{http://archive.ics.uci.edu/ml/} (03/02/2014).

\bibitem{ACLEM90}
L.~Atlas, D.~Cohn, R.~Ladner, M.~A. El-Sharkawi, R.~J. Marks, II, Training
  connectionist networks with queries and selective sampling, in: Advances in
  Neural Information Processing Systems 2, Morgan Kaufmann, Denver, CO, 1990,
  pp. 566--573.

\bibitem{BSP11}
A.~Basu, H.~Shioya, C.~Park, Statistical Inference: The Minimum Distance
  Approach, CRC Press, 2011.

\bibitem{Bis06}
C.~M. Bishop, Pattern Recognition and Machine Learning, Springer, New York, NY,
  USA, 2006.

\bibitem{CZZ13}
W.~Cai, Y.~Zhang, J.~Zhou, Maximizing expected model change for active learning
  in regression, in: International Conference on Data Mining, 2013, pp. 51--60.

\bibitem{CSZ06}
O.~Chapelle, B.~SchÃ¶lkopf, A.~Zien, Semi-Supervised Learning, MIT Press,
  Cambridge, MA, USA, 2006.

\bibitem{CZL+11}
W.~Chu, M.~Zinkevich, L.~Li, A.~Thomas, B.~L. Tseng, Unbiased online active
  learning in data streams, in: 17th International Conference on Knowledge
  Discovery and Data Mining (SIGKDD'11), San Diego, CA, 2011, pp. 195--203.

\bibitem{CL06}
C.~Constantinopoulos, A.~C. Likas, An incremental training method for the
  probabilistic {RBF} network, IEEE Transactions on Neural Networks 17~(4)
  (2006) 966--974.

\bibitem{CKS06}
M.~Culver, D.~Kun, S.~Scott, Active learning to maximize area under the {ROC}
  curve, in: Proceedings of the Sixth International Conference on Data Mining,
  IEEE, Hong Kong, China, 2006, pp. 149--158.

\bibitem{DB14}
B.~Demir, B.~L., A multiple criteria active learning method for support vector
  regression, Pattern Recognition 47~(7) (2014) 2558--2567.

\bibitem{DMB13}
F.~Douaka, F.~Melgania, N.~Benoudjitb, Kernel ridge regression with active
  learning for wind speed prediction, Applied Energy 103 (2013) 328--340.

\bibitem{DHS01}
R.~O. Duda, P.~E. Hart, D.~G. Stork, Pattern Classification, John Wiley \&
  Sons, Chichester, NY, USA, 2001.

\bibitem{FKSO15}
D.~Fisch, E.~Kalkowski, B.~Sick, S.~J. Ovaska, Towards automation of knowledge
  understanding: An approach for probabilistic generative classifiers, under
  review (2015).

\bibitem{FS09}
D.~Fisch, B.~Sick, Training of radial basis function classifiers with resilient
  propagation and variational bayesian inference, in: Proceedings of the
  International Joint Conference on Neural Networks, IEEE, Atlanta, GA, USA,,
  2009, pp. 838--847.

\bibitem{FHYA12}
C.~Fook, M.~Hariharan, S.~Yaacob, A.~Adom, A review: Malay speech recognition
  and audio visual speech recognition, in: International Conference on
  Biomedical Engineering, 2012, pp. 479--484.

\bibitem{Fri40}
M.~Friedman, A comparison of alternative tests of significance for the problem
  of $m$ rankings, The Annals of Mathematical Statistics 11~(1) (1940) 86--92.

\bibitem{HRT06}
D.~Hakkani-T\"ur, G.~Riccardi, G.~Tur, An active approach to spoken language
  processing, ACM Transactions on Speech and Language Processing 3~(3) (2006)
  1--31.

\bibitem{HSS03}
A.~Hofmann, C.~Schmitz, B.~Sick, Intrusion detection in computer networks with
  neural and fuzzy classifiers, in: O.~Kaynak, E.~Alpaydin, E.~Oja, L.~Xu
  (eds.), Artificial Neural Networks and Neural Information Processing
  (ICANN/ICONIP), vol. 2714 of LNCS, Springer-Verlag Berlin Heidelberg, 2003,
  pp. 316--324.

\bibitem{HS07}
T.~Horeis, B.~Sick, Collaborative knowledge discovery {\&} data mining: From
  knowledge to experience, in: Proceedings of the {IEEE} Symposium on
  Computational Intelligence and Data Mining, IEEE, Honolulu, Hawaii, USA,,
  2007, pp. 421 -- 428.

\bibitem{BigData15}
IBM, The four v's of big data,
  \url{http://www.ibmbigdatahub.com/infographic/four-vs-big-data} (letzter
  Zugriff 04/27/2015).

\bibitem{JPP12}
A.~J. Joshi, F.~Porikli, N.~P. Papanikolopoulos, Scalable active learning for
  multi-class image classification, IEEE Transactions on Pattern Analysis and
  Machine Intelligence 34~(11) (2012) 2259--2273.

\bibitem{JH09}
J.~Jun, I.~Horace, Active learning with {SVM}, in: J.~Ram\'{o}n, R.~Dopico,
  J.~Dorado, A.~Pazos (eds.), Encyclopedia of Artificial Intelligence, vol.~3,
  IGI Global, 2009, pp. 1--7.

\bibitem{KL03}
S.~S. Keerthi, C.-J. Lin, Asymptotic behaviors of support vector machines with
  {G}aussian kernel, Neural Computation 15~(7) (2003) 1667--1689.

\bibitem{KPI14}
J.~Kremer, K.~S. Pedersen, C.~Igel, Active learning with support vector
  machines, Wiley Interdisciplinary Reviews. Data Mining and Knowledge
  Discovery 4~(4) (2014) 313--326.

\bibitem{LTW14}
B.~Lamche, U.~Trottmann, W.~W\"{o}rndl, Active learning strategies for
  exploratory mobile recommender systems, in: Proceedings of the Fourth
  Workshop on Context-Awareness in Retrieval and Recommendation (CARR'14),
  Amsterdam, Niederlande, 2014, pp. 10--17.

\bibitem{LB92}
K.~Lang, E.~Baum, Query learning can work poorly when a human oracle is used,
  in: Proceedings of the IEEE International Joint Conference on Neural
  Networks, 1992, pp. 335--340.

\bibitem{LG94}
D.~D. Lewis, W.~A. Gale, A sequential algorithm for training text classifiers,
  in: Proceedings of the Seventeenth Annual International ACM SIGIR Conference
  on Research and Development in Information Retrieval, Springer-Verlag New
  York, Inc., Dublin, Ireland, 1994, pp. 3--12.

\bibitem{MME14}
M.~G. Malhat, H.~M. Mousa, A.~B. El-Sisi, Clustering of chemical data sets for
  drug discovery, in: International Conference on Informatics and Systems,
  2014, pp. DEKM--11 -- DEKM--18.

\bibitem{MCR12}
R.~Marcacini, G.~Correa, S.~Rezende, An active learning approach to frequent
  itemset-based text clustering, in: International Conference on Pattern
  Recognition, 2012, pp. 3529--3532.

\bibitem{MS09}
P.~Melville, V.~Sindhwani, Active dual supervision: Reducing the cost of
  annotating examples and features, in: Proceedings of the NAACL HLT 2009
  Workshop on Active Learning for Natural Language Processing, HLT '09,
  Boulder, CO, 2009, pp. 49--57.

\bibitem{PE11}
{Microsoft Research}, Project {E}mporia,
  \url{http://fuse.microsoft.com/projects/project-emporia} (last accessed
  04/22/2015).

\bibitem{MS97}
A.~Motro, P.~Smets (eds.), Uncertainty Management in Information Systems --
  From Needs to Solutions, Springer Verlag, London, UK, 1997.

\bibitem{Nem63}
P.~Nemenyi, Distribution-free multiple comparisons. phd thesis, princeton
  university, Ph.D. thesis, Princeton University (1963).

\bibitem{NMR+14}
N.~Nissim, R.~Moskovitch, L.~Rokach, Y.~Elovici, Novel active learning methods
  for enhanced {PC} malware detection in windows {OS}, Expert Systems with
  Applications 41~(13) (2014) 5843--5857.

\bibitem{PVS+10}
U.~Paquet, J.~V. Gael, D.~Stern, G.~Kasneci, R.~Herbrich, T.~Graepel, Vuvuzelas
  {\&} active learning for online classification (2010).

\bibitem{PM11}
E.~Pasolli, F.~Melgani, Gaussian process regression within an active learning
  scheme, in: International Geoscience and Remote Sensing Symposium, 2011, pp.
  3574--3577.

\bibitem{RC14}
T.~Reitmaier, A.~Calma, Resp-{\textit{k}}nn: A semi-supervised classifier for
  sparsely labeled data in the field of organic computing, in: Organic
  Computing Doctoral Dissertation Colloquium, vol.~4, kassel university press
  GmbH, 2014, pp. 85--97.

\bibitem{RCS14}
T.~Reitmaier, A.~Calma, B.~Sick, Transductive active learning -- a new
  semi-supervised learning approach based on iteratively refined generative
  models to capture structure in data, Information Sciences 239 (2014)
  275--298.

\bibitem{RS11}
T.~Reitmaier, B.~Sick, Active classifier training with the {3DS} strategy, in:
  Proceedings of the IEEE Symposium on Computational Intelligence and Data
  Mining, IEEE, Paris, France, 2011, pp. 88--95.

\bibitem{RS13}
T.~Reitmaier, B.~Sick, Let us know your decision: Pool-based active training of
  a generative classifier with the selection strategy {4DS}, Information
  Sciences 230 (2013) 106--131.

\bibitem{RS15}
T.~Reitmaier, B.~Sick, The responsibility weighted {M}ahalanobis kernel for
  semi-supervised training of support vector machines for classification,
  Information Sciences 323 (2015) 179--198.

\bibitem{Set09}
B.~Settles, Active learning literature survey, Computer {S}ciences {T}echnical
  {R}eport 1648, University of Wisconsin, Department of Computer Science
  (2009).

\bibitem{Sic98}
B.~Sick, Online tool wear monitoring in turning using time-delay neural
  networks, in: Proceedings of the 1998 IEEE International Conference on
  Acoustics, Speech and Signal Processing (ICASSP), vol.~1, 1998, pp. 445--448.

\bibitem{SUK+13}
Y.~Sogawa, T.~Ueno, Y.~Kawahara, T.~Washio, Active learning for noisy oracle
  via density power divergence, Neural Networks 46 (2013) 133--143.

\bibitem{Trottmann15}
U.~Trottmann, Shopr, \url{https://github.com/UweTrottmann/Shopr} (last accessed
  03/31/2015).

\bibitem{TSH03}
G.~Tur, R.~E. Schapire, D.~Hakkani-T\"ur, Active learning for spoken language
  understanding, in: Proceedings of the International Conference on Acoustics,
  Speech, and Signal Processing (ICASSP'03), Hong Kong, China, 2003, pp.
  276--279.

\bibitem{YDA10}
D.~Yu, B.~Varadarajan, L.~Deng, A.~Acero, Active learning and semi-supervised
  learning for speech recognition: A unified framework using the global entropy
  reduction maximization criterion, Computer Speech {\&} Language 24~(3) (2010)
  433--444.

\bibitem{Yu2005}
H.~Yu, {SVM} selective sampling for ranking with application to data retrieval,
  in: 11th International Conference on Knowledge Discovery and Data Mining
  (SIGKDD'05), New York, NY, USA, 2005, pp. 354--363.

\bibitem{ZYPPJC15}
Y.~Zhang, H.~Yang, S.~Prasad, E.~Pasolli, J.~Jung, M.~Crawford, Ensemble
  multiple kernel active learning for classification of multisource remote
  sensing data, Selected Topics in Applied Earth Observations and Remote
  Sensing 8~(2) (2015) 845--858.

\bibitem{ZCJ+14}
Z.-H. Zhou, N.~Chawla, Y.~Jin, G.~Williams, Big data opportunities and
  challenges: Discussions from data analytics perspectives, Computational
  Intelligence Magazine, IEEE 9 (2014) 62--74.

\end{thebibliography}
