l****i
发帖数: 230 | 1 one step in classification using decision tree: find an optimal split for a
set of one-dimensional example-label pairs such that the misclassifications
are minimized
findOptimalSplit(double* example, bool *label, int num)
I answered with a linear search solution, but the interviewer was not happy
with it. Should it be DP? |
l*********8
发帖数: 4642 | 2 不是每个人都熟悉decision tree classification, 给个例子吧。
a
misclassifications
happy
【在 l****i 的大作中提到】
: one step in classification using decision tree: find an optimal split for a
: set of one-dimensional example-label pairs such that the misclassifications
: are minimized
: findOptimalSplit(double* example, bool *label, int num)
: I answered with a linear search solution, but the interviewer was not happy
: with it. Should it be DP?
|
l*********8
发帖数: 4642 | 3 What is your linear algorithm?
If example is already sorted, I think we still need O(N) time to find
optimal split, which is linear. |
g*********e
发帖数: 14401 | |
l*********8
发帖数: 4642 | 5 what is the time complexity?
【在 g*********e 的大作中提到】
: llyod max algo
|
g*********e
发帖数: 14401 | 6
polynomial， should be fine.
【在 l*********8 的大作中提到】
: what is the time complexity?
|
l****i
发帖数: 230 | 7 Yes, assume the examples are already sorted. We can search through the set
to find the optimal split point t:
rmin = INFINITY
for z = x_i
calculate r = misclassification rate
if (r < rmin) rmin = r, z = x_i
return x_i
【在 l*********8 的大作中提到】
: What is your linear algorithm?
: If example is already sorted, I think we still need O(N) time to find
: optimal split, which is linear.
|
l*********8
发帖数: 4642 | 8 How do you calculate r = misclassification rate ?
If it's O(n), then the overall time complexity is o(n^2)
【在 l****i 的大作中提到】
: Yes, assume the examples are already sorted. We can search through the set
: to find the optimal split point t:
: rmin = INFINITY
: for z = x_i
: calculate r = misclassification rate
: if (r < rmin) rmin = r, z = x_i
: return x_i
:
|
l*********8
发帖数: 4642 | 9 I think llyod max algo is a more general algorithm. For this question, we
can have linear algorithm if "examples" are already sorted.
【在 g*********e 的大作中提到】
:
: polynomial， should be fine.
|
k***g
发帖数: 58 | 10 Maximum entropy
★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite |
l****i
发帖数: 230 | 11 more details please.
The interview also require coding for this question, any one tried coding
this?
【在 k***g 的大作中提到】
: Maximum entropy
: ★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite
|
