- Rating
- 1
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
In this paper, the authors consider a computational task, which is called the PAC teaching problem. In this setting, the learner does not learn a concept directly from the samples. Instead, there is an algorithm called a teacher, which picks the samples to train the learner to learn the concept and the set of samples picked by the teacher is called teaching set. The task this paper tries to handle is how to find an optimal teaching set. The main results is that finding such an opitmal teaching set is hard under ETH. There are some hardness results in the parameterized complexity class as well.
Critical strengths
This paper considers the computational hardness of the teaching problem, especially when the learner may not always be consistent with the learned function. It is an interesting theoretical framework.
Critical weaknesses
I do not see many interesting technical ingredients in this paper. I also do not see the importance of this problem. The presentation of this paper makes it very hard to follow. First, what is the main problem this paper is trying to address? This is very unclear until the very end of this paper. Second, it spends a lot of words distinguishing the notion of teaching for identification and teaching for employment. But this distinction does not show up in the final theorem. I think the author should focus on the main definitions that are closely relevant to the main results and put the less relevant notations after the main results.
Questions for authors
In short, what is the main motivation of this research? Is it the question of computational efficiency in finding an optimal teaching set when the learner has pointwise noise in its predictions?
How untraditional is the reduction in this paper? Is it an easy implication of some traditional reductions?
3 comments
I sincerely do not see a significant difference between the model proposed by the author in this paper and the existing active learning with label noise model. I really want to understand what the difference between those models and what part changed in the result. I would appreciate the author if they can state this and make a good comparison to all the existing models. I apologize if I do not make this point clear in my initial comments.
According to the main theorem of this paper, I think the authors consider the computational resources required by a specific type of learning algorithm, which is very different from a normal statistical learning theory paper. They call this learning algorithm the PAC teaching model. Thus, I wrote the following sentences in the paper summary.
In this setting, the learner does not learn a concept directly from the samples. Instead, there is an algorithm called a teacher, which picks the samples to train the learner to learn the concept and the set of samples picked by the teacher is called teaching set.
What the author wrote in their paper:
Informally, in PAC teaching, when using a good teaching set S for the target concept , it should be probable that the concept c chosen by the learner (e.g., the concept that is L-consistent with most labelled examples in ), is approximately equal to the target . Finally, we introduce the Prudent-optimal PAC teacher TP aiming to find an optimal teaching set .
And in the theorem
Theorem 1. The problem facing the Prudent-optimal PAC Teacher TP for probable-optimizing (id or em), given consistency matrix and , approx factor and max-size , for a given target, can be solved in time .
The problem facing the Prudent-optimal PAC teacher TP, (I think this should be "the problem faced by the teacher"?) is the problem to find the optimal teaching set , as in the part cited above. I am not sure what the problem is in my interpretation of this theorem. I am very happy to know if there are some.
In my opinion, this paper is about computational hardness of a learning problem with label noise, or maybe more specifically, the computation complexity of the following problem: An algorithm with instance space and target concept and concept class in hand, want to pick a set of unlabeled data, then use a coin to decide the label for each unlabeled datum (the label noise), then what is the computation complexity of this problem? The model in this work seems very similar to the active learning under label noise to me. The learning under noise model has been extensively investigated in the area of statistical learning theory, both passive and active and I believe it is also investigated in computational learning theory.
However, I feel that the author's response is offensive and inappropriate, especially the assertion on the research experience of the reviewer. It is unclear what supports the author's assertion that the reviewer has no direct research experience in learning theory. I am happy to know the reason why the authors make such an assertion. I would like to say that learning theory is a large research area, people has considered learning problem from very different perspectives and I would not exclude other subareas from learning theory only because they are using different language or caring about different aspects.
Thank you for the follow-up.
Active learning: We have a teacher-learner setting, and the teacher has an algorithm to choose the examples. This is standard in the field of machine teaching, from the early days of learning theory, where machine teaching and query learning (and active learning) diverged. Precisely, in machine teaching, the teacher knows the concept, and the algorithm works with that information. In active learning, it is the learner asking for the examples. The learner doesn't know the concept of course, so the algorithm uses the learner's uncertainty to pick the next examples but can't use any information about the target concept. So it's not only that the example-selection algorithms are on different sides of the teacher-learner setting, they must be fundamentally different.
Label noise: Even assuming that the teacher samples according to a distribution (and then machine learning becomes a special case of machine teaching), labelling errors are fundamentally different from learner errors. Using the same example we used with another reviewer, when we consider a non-deterministic target and a perfect learner, the noise is in the label of the example. The learner sees one label and checks all its hypotheses against that label. In our model, the label is always correct and the noise is in the learner’s checks. Each time the learner checks whether a hypothesis is consistent with an example, it can make a mistake. With two hypotheses, both models can give the same result, and that's maybe why it is difficult to see. However, in general, with three or more hypotheses, they can give different results. Two hypotheses. The target is “multiples of 3”. The positive examples are 15, 45, 105 and 219, and the negative examples are 8 and 10. Suppose the label of 219 is wrong 50% of the time. A learner that makes no mistakes will select “multiples of 15” 50% of the time and “multiples of 3” 50% of the time. Now suppose the labels are always correct, but the learner makes a mistake when checking 219 50% of the time. The result is again 50% for each hypothesis. Modelling this either way would give equivalent results. Three hypotheses. The target is again “multiples of 3”. The positive examples are 3, 9 and 15, and the negative examples are 4, 10 and 91 (which may look like a multiple of 3). The learner tries the hypotheses in the following order and selects the first consistent one: (1) odd numbers, (2) multiples of 3, (3) odd numbers below 30. With no errors, (1) is rejected because of 91, and (2) is selected. Noisy label: 91 is labelled positive 50% of the time. When this happens, (1) is consistent with all the examples. Result: (1) 50%, (2) 50%. Learner error: the labels are correct, but 50% of the time the learner thinks 91 is a multiple of 3. (1) is always rejected, since the label of 91 is correct and checking that 91 is odd is easy. (2) is rejected 50% of the time, and then (3) is selected. Result: (2) 50%, (3) 50%. The two ways of "modelling" this are not only conceptually different but they give different results. Modelling this as labelling errors cannot account for the situations we consider in this paper. We can add this example to an appendix.
Learning theory vs computational complexity: Our comment referred to the fact of seeing a strong reject with low confidence and a comment about ETH, leading us to believe the reviewer came mostly from computational complexity, when we selected "learning theory" as the topic of our paper. We apologise if this is not the case. We can understand a strong reject when the gist of the paper is understood and it contains major errors or doesn't add anything novel or useful. We honestly think this is not the case for this paper.
The reviewer writes: 'The main results is that finding such an opitmal teaching set is hard under ETH.'. This must be based on a very cursory reading of the paper. We are very clear that the main contribution is the 'introduction of the PAC teaching framework, that is useful whenever we have a learner who does not perform perfect deductive inference'. This is an important contribution to the field, but I guess we must take responsibility for not having shown why this is important. We will add examples in the revision. PS Very disappointing that ICLR assigns our paper to a reviewer with no direct research experience in learning theory.