0
$\begingroup$

"...for learning transition dynamics...in the KWIK framework."

The above is part of a paper's conclusion - and I don't really seem to understand what the KWIK framework is. In the details of the paper, is a brief highlight of the KWIK conditions for a learning algorithm, which go as follows (I paraphrase):

  1. All predictions must be accurate (assuming a valid hypotheses class)
  2. However the learning algorithm may also return $\perp$, which indicates that it cannot yet predict the output for this input.

A quick Google Search brought me to this paper from ICML 2008, but it is a little difficult to comprehend without a detailed read.

Could someone please help me understand what the KWIK framework is, and what implication does it have for a learning algorithm to satisfy KWIK conditions? An explanation that starts at simple and goes to fairly advanced discussions is appreciated.

Thanks a lot!

$\endgroup$
  • $\begingroup$ What about this presentation about the very same paper from ICML 2008? It has less pages and is more simply put than the paper. $\endgroup$ – mico May 3 at 9:03
1
+50
$\begingroup$

Based on the presentation by Praveen Venkateswaran on the same paper, KWIK framework is any learning algorithm that makes the following:

  1. if it knows (by its learning) the answer already, it does tell that
  2. if it is uncertain, it tells the "I don't know" mark
  3. "I don't know" marks should have an upper limit, which is the accuracy/error term of the algorithm.

The idea is that algorithm has a trainer who knows the correct answers, like in any machine learning case, but the difference is that the algorithm agent should know when it has enough knowledge to give the result right away, and when is time to ask and learn. In learning phase the trainer does not calculate errors, only he gives right answers if asked.

There I see two implications: algorithm should know when it has not all the necessary data to answer (when to use "I don't know" answer) and a mechanism to be sure you're correct when the answer is e.g. 1 or 0 in binary case.

How to put that in mathematics, it varies by your chosen algorithm. Also there is a formal equation set for this, but I leave here only this literal definition to give the basic idea.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.