jmlr jmlr2007 jmlr2007-83 knowledge-graph by maker-knowledge-mining

83 jmlr-2007-The On-Line Shortest Path Problem Under Partial Monitoring

Source: pdf

Author: András György, Tamás Linder, Gábor Lugosi, György Ottucsák

Abstract: The on-line shortest path problem is considered under various models of partial monitoring. Given a weighted directed acyclic graph whose edge weights can change in an arbitrary (adversarial) way, a decision maker has to choose in each round of a game a path between two distinguished vertices such that the loss of the chosen path (deﬁned as the sum of the weights of its composing edges) be as small as possible. In a setting generalizing the multi-armed bandit problem, after choosing a path, the decision maker learns only the weights of those edges that belong to the chosen path. For this problem, an algorithm is given whose average cumulative loss in n rounds exceeds that of the best path, matched off-line to the entire sequence of the edge weights, by a quantity that is √ proportional to 1/ n and depends only polynomially on the number of edges of the graph. The algorithm can be implemented with complexity that is linear in the number of rounds n (i.e., the average complexity per round is constant) and in the number of edges. An extension to the so-called label efﬁcient setting is also given, in which the decision maker is informed about the weights of the edges corresponding to the chosen path at a total of m n time instances. Another extension is shown where the decision maker competes against a time-varying path, a generalization of the problem of tracking the best expert. A version of the multi-armed bandit setting for shortest path is also discussed where the decision maker learns only the total weight of the chosen path but not the weights of the individual edges on the path. Applications to routing in packet switched networks along with simulation results are also presented. Keywords: on-line learning, shortest path problem, multi-armed bandit problem c 2007 Andr´ s Gy¨ rgy, Tam´ s Linder, G´ bor Lugosi and Gy¨ rgy Ottucs´ k. a o a a o a ¨ ´ G Y ORGY, L INDER , L UGOSI AND OTTUCS AK

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 In a setting generalizing the multi-armed bandit problem, after choosing a path, the decision maker learns only the weights of those edges that belong to the chosen path. [sent-13, score-0.736]

2 An extension to the so-called label efﬁcient setting is also given, in which the decision maker is informed about the weights of the edges corresponding to the chosen path at a total of m n time instances. [sent-18, score-0.682]

3 A version of the multi-armed bandit setting for shortest path is also discussed where the decision maker learns only the total weight of the chosen path but not the weights of the individual edges on the path. [sent-20, score-1.367]

4 Keywords: on-line learning, shortest path problem, multi-armed bandit problem c 2007 Andr´ s Gy¨ rgy, Tam´ s Linder, G´ bor Lugosi and Gy¨ rgy Ottucs´ k. [sent-22, score-0.807]

5 More precisely, the per round cumulative loss of these algorithms is at most as large as that of the best expert plus a quantity proportional to ln N/n for any bounded loss function, where n is the number of rounds in the decision game. [sent-32, score-0.771]

6 (2002) who gave an algorithm whose normalized regret (the difference of the algorithm’s average loss and that of the best expert) is upper bounded by a quantity which is proportional to N ln N/n. [sent-37, score-0.703]

7 A recent result of Cesa-Bianchi, Lugosi, and Stoltz (2005) shows that in this case, if the decision maker can query the losses m times during a period of length n, then it can achieve O( ln N/m) normalized regret relative to the best expert. [sent-40, score-1.075]

8 o In the bandit setting only the weights of the edges or just the sum of the weights of the edges composing the chosen path are revealed to the decision maker. [sent-52, score-0.993]

9 They achieved this by extending the exponentially weighted average predictor and the follow-theperturbed-leader algorithm of Hannan (1957) to the generalization of the multi-armed bandit setting for shortest paths, when only the sum of the weights of the edges is available for the algorithm. [sent-56, score-0.659]

10 We achieve this bound in a model which assumes that the losses of all edges on the path chosen by the forecaster are available separately after making the decision. [sent-65, score-0.655]

11 In Section 2 we formally deﬁne the on-line shortest path problem, which is extended to the multi-armed bandit setting in Section 3. [sent-72, score-0.685]

12 Our new algorithm for the shortest path problem in the bandit setting is given in Section 4 together with its performance analysis. [sent-73, score-0.685]

13 The algorithm is extended to solve the shortest path problem in a combined label efﬁcient multi-armed bandit setting in Section 5. [sent-74, score-0.685]

14 An algorithm for the “restricted” multi-armed bandit setting (when only the sums 2371 ¨ ´ G Y ORGY, L INDER , L UGOSI AND OTTUCS AK of the losses of the edges are available) is given in Section 7. [sent-76, score-0.6]

15 , n of the decision game, the decision maker chooses a path I t among all paths from u to v. [sent-113, score-0.702]

16 We write e ∈ i if the edge e ∈ E belongs to the path i ∈ P , and with a slight abuse of notation the loss of a path i at time slot t is also represented by i,t . [sent-115, score-0.637]

17 , 1997), calculated over all possible paths, has regret 1 Ln − min Li,n i∈P n ≤K ln N + 2n ln(1/δ) 2n with probability at least 1 − δ, where N is the total number of paths from u to v in the graph and K is the length of the longest path. [sent-124, score-0.913]

18 In this setup, which is more realistic in many applications, the decision maker has only access to the losses corresponding to the paths it has chosen. [sent-127, score-0.565]

19 We distinguish between two types of bandit problems, both of which are natural generalizations of the simple bandit problem to the shortest path problem. [sent-129, score-0.986]

20 In the ﬁrst variant, the decision maker has access to the losses of those edges that are on the path it has chosen. [sent-130, score-0.797]

21 That is, after choosing a path I t at time t, the value of the loss e,t is revealed to the decision maker if and only if e ∈ I t . [sent-131, score-0.564]

22 2373 ¨ ´ G Y ORGY, L INDER , L UGOSI AND OTTUCS AK The second variant is a more restricted version in which the loss of the chosen path is observed, but no information is available on the individual losses of the edges belonging to the path. [sent-133, score-0.595]

23 That is, after choosing a path I t at time t, only the value of the loss of the path It ,t is revealed to the decision maker. [sent-134, score-0.598]

24 Formally, the on-line shortest path problem in the multi-armed bandit setting is described as follows: at each time instance t = 1, . [sent-137, score-0.685]

25 , n, the decision maker picks a path I t ∈ P from u to v. [sent-140, score-0.498]

26 Applying their algorithm to the on-line shortest path problem in the bandit setting results in a performance that can be bounded, for any 0 < δ < 1 and ﬁxed time horizon n, with probability at least 1 − δ, by 1 Ln − min Li,n i∈P n ≤ 11K 2 N ln(N/δ) K ln N + . [sent-149, score-1.236]

27 The new algorithm uses the fact that when the losses of the edges of the chosen path are revealed, then this also provides some information about the losses of each path sharing common edges with the chosen path. [sent-161, score-1.092]

28 To this end, we introduce a set C of covering paths with the property that for each edge e ∈ E there is a path i ∈ C such that e ∈ i. [sent-180, score-0.495]

29 (2002) is a special case of the algorithm below: For any multi-armed bandit problem with N experts, one can deﬁne a graph with two vertices u and v, and N directed edges from u to v with weights corresponding to the losses of the experts. [sent-183, score-0.777]

30 The solution of the shortest path problem in this case is equivalent to that of the original bandit problem with choosing expert i if the corresponding edge is chosen. [sent-184, score-0.807]

31 It states that the normalized regret of the algorithm, after n rounds of play, is, roughly, of the order of K |E| ln N/n where |E| is the number of edges of the graph, K is the length of the paths, and N is the total number of paths. [sent-190, score-0.869]

32 nβ δ nη ln |E| , γ = 2ηK|C |, and η = δ ≤2 K n 4K|C | ln N + 2375 |E| ln ln N 4nK 2 |C | |E| δ . [sent-192, score-2.12]

33 i∈P Figure 2: A bandit algorithm for shortest path problems The proof of the theorem is based on the analysis of the original algorithm of Auer et al. [sent-202, score-0.708]

34 Lemma 2 For any δ ∈ (0, 1), 0 ≤ β < 1 and e ∈ E we have P Ge,n > Ge,n + 1 |E| δ ≤ ln . [sent-209, score-0.53]

35 As usual in the analysis of exponentially weighted average forecasters, we start with bounding the quantity ln W n . [sent-226, score-0.567]

36 On the one hand, we have the lower bound W 0 ln Wn = ln ∑ eηGi,n − ln N ≥ η max Gi,n − ln N . [sent-227, score-2.156]

37 Therefore, ln η2 K(1 + β) η Wt (gIt ,t + |E|β) + ≤ ∑ ge,t . [sent-236, score-0.53]

38 , n, we obtain ln Wn W0 ≤ ≤ η η2 K(1 + β) Gn + n|E|β + ∑ Ge,n 1−γ 1−γ e∈E η2 K(1 + β) η |C | max Gi,n Gn + n|E|β + 1−γ 1−γ i∈P where the second inequality follows since ∑e∈E Ge,n ≤ ∑i∈C Gi,n . [sent-240, score-0.556]

39 Combining the upper bound with the lower bound (5), we obtain Gn ≥ (1 − γ − ηK(1 + β)|C |) max Gi,n − i∈P 1−γ ln N − n|E|β. [sent-241, score-0.602]

40 η Now using Lemma 2 and applying the union bound, for any δ ∈ (0, 1) we have that, with probability at least 1 − δ, Gn ≥ (1 − γ − ηK(1 + β)|C |) max Gi,n − i∈P K |E| 1−γ ln ln N − n|E|β , − β δ η where we used 1 − γ − ηK(1 + β)|C | ≥ 0 which follows from the assumptions of the theorem. [sent-242, score-1.06]

41 Since Gn = Kn − Ln and Gi,n = Kn − Li,n for all i ∈ P , we have Ln ≤ Kn (γ + η(1 + β)K|C |) + (1 − γ − η(1 + β)K|C |) min Li,n i∈P K |E| 1 − γ + (1 − γ − η(1 + β)K|C |) ln + ln N + n|E|β β δ η 2379 ¨ ´ G Y ORGY, L INDER , L UGOSI AND OTTUCS AK with probability at least 1 − δ. [sent-243, score-1.081]

42 This implies K |E| 1 − γ ln + ln N + n|E|β β δ η K |E| ln N ≤ Knγ + 2ηnK 2 |C | + ln + + n|E|β β δ η Ln − min Li,n ≤ Knγ + η(1 + β)nK 2 |C | + i∈P with probability at least 1 − δ, which is the ﬁrst statement of the theorem. [sent-244, score-2.163]

43 Setting β= K |E| ln n|E| δ and γ = 2ηK|C | results in the inequality Ln − min Li,n ≤ 4ηnK 2 |C | + i∈P ln N +2 η nK|E| ln |E| δ which holds with probability at least 1−δ if n ≥ (K/|E|) ln(|E|/δ) (to ensure β ≤ 1). [sent-245, score-1.637]

44 Finally, setting η= ln N 4nK 2 |C | yields the last statement of the theorem (n ≥ 4 ln N|C | is required to ensure γ ≤ 1/2). [sent-246, score-1.105]

45 This means that the decision maker only has access to the losses of all the edges on the chosen path upon request and the total number of requests must be bounded by a constant m. [sent-269, score-0.797]

46 Our model of the label-efﬁcient bandit problem for shortest paths is motivated by an application to a particular packet switched network model. [sent-274, score-0.659]

47 The task of the decision maker is to send packets from the source to the destination over routes with minimum average transmission delay (or packet loss). [sent-282, score-0.501]

48 Lemma 5 For any 0 < δ < 1, 0 < ε ≤ 1, for any n≥ 1 K 2 ln2 (2|E|/δ) K ln(2|E|/δ) max , ε |E| ln N |E| , parameters 2ηK|C | ≤ γ, ε η= ε ln N 4nK 2 |C | and β= K 2|E| ln ≤1, n|E|ε δ and e ∈ E, we have P Ge,n > Ge,n + 4 2|E| δ ln ≤ . [sent-300, score-2.12]

49 Using (1) with u = 4 βε ln 2|E| and c = δ βε 4, it sufﬁces to prove for all n that E ec(Ge,n −Ge,n ) ≤ 1 . [sent-302, score-0.53]

50 ε|E| ln N Combining (9) and (11) we get that Et [Zt ] ≤ Zt−1 . [sent-313, score-0.53]

51 , n, we obtain ln Wn W0 ≤ η n St η2 K(1 + β) (gIt ,t + |E|β ) + |C | max Gi,n . [sent-323, score-0.53]

52 ∑ 1 − γ t=1 ε (1 − γ)ε i∈P Combining the upper bound with the lower bound (5), we obtain n St (gIt ,t + |E|β ) ≥ t=1 ε ∑ 1−γ− ηK(1 + β)|C | ln N . [sent-324, score-0.602]

53 Now apply Bernstein’s inequality for martingale differences (see Lemma 14 in the Appendix) to obtain n δ P ∑ Xt > u ≤ , (14) 2 t=1 where u= 2n 2 2 4K 2 4K ln ln + . [sent-340, score-1.143]

54 2 t=1 ε n P ∑ (15) Now Lemma 5, the union bound, and (15) combined with (12) yield, with probability at least 1 − δ, Gn ≥ 1−γ− − ηK(1 + β)|C | ε max Gi,n − i∈P 4K 2|E| ln βε δ ln N − βn|E| − u η since the coefﬁcient of Gi,n is greater than zero by the assumptions of the theorem. [sent-342, score-1.06]

55 Since Gn = Kn − Ln and Gi,n = Kn − Li,n , we have K(1 + β)η|C | K(1 + β)η|C | min Li,n + Kn γ + i∈P ε ε K(1 + β)η|C | 4K 2|E| ln N + 1−γ− ln + βn|E| + +u ε βε δ η ln N K(1 + β)η|C | + 5βn|E| + +u , ≤ min Li,n + Kn γ + i∈P ε η Ln ≤ 1−γ− K where we used the fact that βε ln 2|E| = βn|E|. [sent-343, score-2.162]

56 δ Substituting the value of β, η and γ, we have Ln − min Li,n ≤Kn i∈P ≤4K ≤ 2Kη|C | ln N 2Kη|C | + Kn + + 5βn|E| + u ε ε η n|C | ln N +5 ε n|E|K ln(2|E|/δ) +u ε nK 4 K|C | ln N + 5 ε 4K ln (2/δ) + 3ε as desired. [sent-344, score-2.141]

57 2 2385 |E| ln(2|E|/δ) + 8K ln (2/δ) ¨ ´ G Y ORGY, L INDER , L UGOSI AND OTTUCS AK 6. [sent-345, score-0.53]

58 j=0 t=t j e∈i j The goal of the decision maker is to perform as well as the best time-varying path (partition), that is, to keep the normalized regret 1 Ln − min L(Part(n, m, t, i)) t,i n as small as possible (with high probability) for all possible outcome sequences. [sent-358, score-0.665]

59 (2005a) develop efﬁcient algorithms for tracking the best expert for certain large and structured classes of base experts, including the shortest path problem. [sent-364, score-0.502]

60 (2005a) to the bandit setting when the forecaster only observes the losses of the edges on the chosen path. [sent-366, score-0.673]

61 The following performance bounds shows that the normalized regret with respect to the best time-varying path which is allowed to switch paths m times is roughly of the order of K (m/n)|C | ln N. [sent-367, score-1.089]

62 Lemma 9 For any δ ∈ (0, 1), 0 ≤ β ≤ 1, t ≥ 1 and e ∈ E we have P Ge,t > Ge,t + δ 1 |E|(m + 1) ln ≤ . [sent-392, score-0.53]

63 Then we get ln Wn W0 η2 K(1 + β) η Gn + n|E|β + |C | max Gi,n . [sent-395, score-0.53]

64 Then the lower bound is obtained as ln w j,n v j,n vi ,n Wn = ln ∑ ≥ ln m = ln ∑ N W0 j∈P N j∈P N (recall that im denotes the path used in the last segment of the partition). [sent-397, score-2.425]

65 Combining the lower bound with the upper bound (16), we have αm (1 − α)n−m−1 N m+1 ln ≤ η 1−γ + max ηG (Part(n, m, t, i)) t,i Gn + n|E|β + η2 K(1+β) 1−γ |C | maxi∈P Gi,n , where we used the fact that Part(n, m, t, i) is an arbitrary partition. [sent-400, score-0.602]

66 After rearranging and using maxi∈P Gi,n ≤ maxt,i G (Part(n, m, t, i)) we get Gn ≥ (1 − γ − ηK(1 + β)|C |) max G (Part(n, m, t, i)) t,i −n|E|β − 1−γ N m+1 ln . [sent-401, score-0.53]

67 m (1 − α)n−m−1 η α Now since 1 − γ − ηK(1 + β)|C | ≥ 0, by the assumptions of the theorem and from Lemma 9 with an application of the union bound we obtain that, with probability at least 1 − δ, Gn ≥ (1 − γ − ηK(1 + β)|C |) max G(Part(n, m, t, i)) − t,i − n|E|β − N m+1 1−γ ln . [sent-402, score-0.589]

68 η αm (1 − α)n−m−1 This implies that, with probability at least 1 − δ, Ln − min L(Part(n, m, t, i)) t,i ≤ Kn (γ + η(1 + β)K|C |) + + n|E|β + K(m + 1) |E|(m + 1) ln β δ N m+1 1 ln η αm (1 − α)n−m−1 . [sent-404, score-1.081]

69 (17) p To prove the second statement, let H(p) = −p ln p − (1 − p) ln(1 − p) and D(p q) = p ln q + (1 − p) ln 1−p . [sent-405, score-1.59]

70 Optimizing the value of α in the last term of (17) gives 1−q 1 N m+1 ln η αm (1 − α)n−m−1 1 1 1 = (m + 1) ln (N) + m ln + (n − m − 1) ln η α 1−α 1 (m + 1) ln (N) + (n − 1)(Db (α∗ α) + Hb (α∗ )) = η where α∗ = m n−1 . [sent-406, score-2.65]

71 Therefore Ln − min L(Part(n, m, t, i)) t,i ≤ Kn (γ + η(1 + β)K|C |) + K(m + 1) |E|(m + 1) 1 ln + n|E|β + D . [sent-408, score-0.551]

72 Setting K(m + 1) |E|(m + 1) ln , γ = 2ηK|C |, and η = n|E| δ β= D 4nK 2 |C | results in the second statement of the theorem, that is, Ln − min L(Part(n, m, t, i)) t,i √ ≤ 2 nK 4K|C |D + |E|(m + 1) ln |E|(m + 1) δ . [sent-410, score-1.103]

73 N Figure 5: An alternative bandit algorithm for tracking shortest paths Similarly to Gy¨ rgy et al. [sent-424, score-0.804]

74 (2005a), in this alternative formulation of the algorithm one can compute the probabilities the normalization factors Zt ,t−1 efﬁciently, as the baseline bandit algorithm for shortest paths has an O(n|E|) time complexity by Theorem 3. [sent-429, score-0.604]

75 (2005a) that the o time complexity of the alternative bandit algorithm for tracking the shortest path is O(n 2 |E|). [sent-433, score-0.763]

76 That is, the forecaster has access to the sum It ,t of losses over the chosen path I t but not to the losses { e,t }e∈It of the edges belonging to I t . [sent-436, score-0.767]

77 The algorithm alternates between choosing a path from a “basis” B to obtain unbiased estimates of the loss (exploration step), and choosing a path according to exponential weighting based on these estimates. [sent-442, score-0.521]

78 In the previous sections, where the loss of each edge along the chosen path is available to the decision maker, the complexity stemming from the large number of paths was reduced by representing all information in terms of the edges, as the set of edges spans the set of paths. [sent-445, score-0.711]

79 i∈P Figure 6: A bandit algorithm for the restricted shortest path problem The theorem is proved using the following two lemmas. [sent-554, score-0.73]

80 The ﬁrst one is an easy consequence of Bernstein’s inequality: Lemma 12 Under the assumptions of Theorem 11, the probability that the algorithm queries the basis more than nε + 2nε ln 4 times is at most δ/4. [sent-555, score-0.53]

81 2395 ¨ ´ G Y ORGY, L INDER , L UGOSI AND OTTUCS AK Lemma 13 Let 0 < δ < 1 and assume n ≥ n ∑ ∑ pi,t n bK 2 4b 8 ln . [sent-558, score-0.53]

82 − ∑ ∑ pi,t ˜i,t ≤ b 2n 3 ε δ t=1 i∈P i,t t=1 i∈P ln 4bN . [sent-559, score-0.53]

83 For any i ∈ P , with probability at least 1−δ/4, δ 8b ε Furthermore, with probability at least 1 − δ/(4N), 8 bK 2 4bN ˜ Li,n − Li,n ≤ b 2n ln . [sent-560, score-0.53]

84 Then, using Bernstein’s inequality for martingale differences (Lemma 14), we have, for any ﬁxed b j , n P ∑ Xb j ,t ≥ t=1 8 3 2n δ bK 2 4b ≤ ln ε δ 4b where we used (23), (24) and the assumption of the lemma on n. [sent-570, score-0.651]

85 Similarly to earlier proofs, we follow the evolution of the term ln W n . [sent-576, score-0.53]

86 In the W0 same way as we obtained (5) and (7), we have ln Wn ≥ −η min Li,n − ln N i∈P W0 and ln n Wn W0 ≤ −η ∑ pi,t ˜i,t + ∑ i∈P t=1 η2 ∑ pi,t ˜2 i,t 2 i∈P . [sent-577, score-1.611]

87 Combining these bounds, we obtain − min Li,n − i∈P n ln N η − ∑ pi,t ˜i,t + ∑ ≤ i∈P t=1 ≤ −1 + ηKb ε η ∑ pi,t ˜2 i,t 2 i∈P n ∑ ∑ pi,t ˜i,t , t=1 i∈P because 0 ≤ ˜i,t ≤ 2Kb . [sent-578, score-0.551]

88 Applying the results of Lemma 13 and the union bound, we have, with ε probability 1 − δ/2, K 2 b 4bN 8 ln − min Li,n − b 2n i∈P 3 ε δ ≤ −1 + ηKb ε t=1 i∈P ≤ −1 + ηKb ε ∑ ∑ pi,t n ∑ ∑ pi,t i,t n t=1 i∈P i,t K 2 b 4b 8 ln − b 2n 3 ε δ + ln N η 8 K 2 b 4b ln N + b 2n ln + . [sent-579, score-2.671]

89 Then, by the Hoeffding-Azuma inequality (Hoeffding, 1963) we obtain that, with probability at least 1 − δ/4, ∑ ∑ pi,t t∈Tn i∈P i,t ≥ ∑ t∈Tn I t ,t 2397 − |Tn |K 2 4 ln . [sent-581, score-0.556]

90 The last two inequalities imply n ∑ ∑ pi,t t=1 i∈P i,t ≥ Ln − |Tn |K 2 4 ln − K|T n | . [sent-583, score-0.53]

91 2 δ (28) Then, by (27), (28) and Lemma 12 we obtain, with probability at least 1 − δ, Ln − min Li,n i∈P  ηb ≤ K  Kn + ε 2nε ln 4 δ n 4 ln + nε + 2 δ K +  b 4bN  ln N 16 + b 2n ln 3 ε δ η where we used Ln ≤ Kn and |Tn | ≤ n. [sent-584, score-2.141]

92 1K 2 bnε where we used n ln 4 ≤ 1 nε, 2 4 δ tions of the theorem). [sent-586, score-0.53]

93 2 1 2nε ln 4 ≤ 2 nε, δ n bK ln 4N = nε, and ε δ ln N η ≤ nε (from the assump- 8. [sent-587, score-1.59]

94 For the version of our bandit algorithm that is informed of the individual edge losses (edge-bandit), we used the simple 2-element cover set of the paths consisting of the upper and lower edges, respectively (other 2-element cover sets give similar performance). [sent-596, score-0.697]

95 5 0 0 2000 4000 6000 Number of packets 8000 10000 Figure 7: Normalized regret of several algorithms for the shortest path problem. [sent-607, score-0.593]

96 Efﬁcient algorithms have been provided for the multi-armed bandit setting and in a combined label efﬁcient multi-armed bandit setting, provided the individual edge losses along the chosen path are revealed to the algorithms. [sent-617, score-1.118]

97 Earlier methods for the multi-armed bandit problem either do not have the right O(1/ n) convergence rate, or their regret increase exponentially in the number of edges for typical graphs. [sent-619, score-0.609]

98 In the restricted version of the shortest path problem, where only the losses of the whole paths are revealed, an algorithm with a worse O(n−1/3 ) normalized regret was provided. [sent-621, score-0.866]

99 ) It is easy to see that each path from source to destination is of length K in the new graph and the weights of the new paths are the same as those of the corresponding originals. [sent-649, score-0.525]

100 Then, for all ε > 0, n P ∑ Xt > ε t=1 −ε2 ≤ e 2nσ2 +2ε(b−a)/3 and therefore n P ∑ Xt > t=1 √ 2nσ2 ln δ−1 + 2 ln δ−1 (b − a)/3 ≤ δ. [sent-663, score-1.06]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('ln', 0.53), ('bandit', 0.301), ('path', 0.247), ('maker', 0.213), ('ottucs', 0.195), ('orgy', 0.171), ('paths', 0.166), ('edges', 0.151), ('losses', 0.148), ('awerbuch', 0.146), ('hortest', 0.138), ('inder', 0.138), ('ugosi', 0.138), ('shortest', 0.137), ('zt', 0.129), ('rgy', 0.122), ('regret', 0.12), ('st', 0.11), ('roblem', 0.105), ('kleinberg', 0.092), ('packets', 0.089), ('ine', 0.083), ('det', 0.083), ('edge', 0.082), ('kn', 0.08), ('bb', 0.08), ('tracking', 0.078), ('vertices', 0.077), ('gy', 0.076), ('routing', 0.076), ('forecaster', 0.073), ('git', 0.073), ('mcmahan', 0.073), ('warmuth', 0.072), ('auer', 0.071), ('takimoto', 0.062), ('ak', 0.06), ('bbt', 0.057), ('linder', 0.057), ('martingale', 0.057), ('spanner', 0.057), ('packet', 0.055), ('gn', 0.053), ('ht', 0.052), ('awkl', 0.049), ('delay', 0.048), ('experts', 0.044), ('graph', 0.042), ('rounds', 0.042), ('herbster', 0.041), ('expert', 0.04), ('vk', 0.04), ('revealed', 0.039), ('kb', 0.039), ('gains', 0.038), ('decision', 0.038), ('lemma', 0.038), ('exponentially', 0.037), ('route', 0.037), ('destination', 0.037), ('wn', 0.037), ('lugosi', 0.037), ('bound', 0.036), ('round', 0.035), ('slot', 0.034), ('longest', 0.034), ('weights', 0.033), ('vovk', 0.033), ('cumulative', 0.032), ('kalai', 0.031), ('xb', 0.031), ('blum', 0.03), ('bt', 0.03), ('acyclic', 0.029), ('vertex', 0.029), ('smart', 0.028), ('tn', 0.028), ('hannan', 0.028), ('loss', 0.027), ('gi', 0.026), ('def', 0.026), ('inequality', 0.026), ('normalized', 0.026), ('directed', 0.025), ('actions', 0.025), ('adversarial', 0.025), ('delays', 0.025), ('gelenbe', 0.024), ('nk', 0.024), ('theorem', 0.023), ('vempala', 0.023), ('statement', 0.022), ('vi', 0.022), ('restricted', 0.022), ('xt', 0.022), ('min', 0.021), ('budapest', 0.021), ('routes', 0.021), ('hungarian', 0.021), ('oracle', 0.02)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999982 83 jmlr-2007-The On-Line Shortest Path Problem Under Partial Monitoring

Author: András György, Tamás Linder, Gábor Lugosi, György Ottucsák

2 0.17451113 9 jmlr-2007-AdaBoost is Consistent

Author: Peter L. Bartlett, Mikhail Traskin

Abstract: The risk, or probability of error, of the classiﬁer produced by the AdaBoost algorithm is investigated. In particular, we consider the stopping strategy to be used in AdaBoost to achieve universal consistency. We show that provided AdaBoost is stopped after n1−ε iterations—for sample size n and ε ∈ (0, 1)—the sequence of risks of the classiﬁers it produces approaches the Bayes risk. Keywords: boosting, adaboost, consistency

3 0.15716054 14 jmlr-2007-Behavioral Shaping for Geometric Concepts

Author: Manu Chhabra, Robert A. Jacobs, Daniel Štefankovič

Abstract: In a search problem, an agent uses the membership oracle of a target concept to ﬁnd a positive example of the concept. In a shaped search problem the agent is aided by a sequence of increasingly restrictive concepts leading to the target concept (analogous to behavioral shaping). The concepts are given by membership oracles, and the agent has to ﬁnd a positive example of the target concept while minimizing the total number of oracle queries. We show that for the concept class of intervals on the real line an agent using a bounded number of queries per oracle exists. In contrast, for the concept class of unions of two intervals on the real line no agent with a bounded number of queries per oracle exists. We then investigate the (amortized) number of queries per oracle needed for the shaped search problem over other concept classes. We explore the following methods to obtain efﬁcient agents. For axis-parallel rectangles we use a bootstrapping technique to obtain gradually better approximations of the target concept. We show that given rectangles R ⊆ A ⊆ R d one can obtain a rectangle A ⊇ R with vol(A )/vol(R) ≤ 2, using only O(d · vol(A)/vol(R)) random samples from A. For ellipsoids of bounded eccentricity in Rd we analyze a deterministic ray-shooting process which uses a sequence of rays to get close to the centroid. Finally, we use algorithms for generating random points in convex bodies (Dyer et al., 1991; Kannan et al., 1997) to give a randomized agent for the concept class of convex bodies. In the ﬁnal section, we explore connections between our bootstrapping method and active learning. Speciﬁcally, we use the bootstrapping technique for axis-parallel rectangles to active learn axis-parallel rectangles under the uniform distribution in O(d ln(1/ε)) labeled samples. Keywords: computational learning theory, behavioral shaping, active learning

4 0.14421822 34 jmlr-2007-From External to Internal Regret (Special Topic on the Conference on Learning Theory 2005)

Author: Avrim Blum, Yishay Mansour

Abstract: External regret compares the performance of an online algorithm, selecting among N actions, to the performance of the best of those actions in hindsight. Internal regret compares the loss of an online algorithm to the loss of a modiﬁed online algorithm, which consistently replaces one action by another. In this paper we give a simple generic reduction that, given an algorithm for the external regret problem, converts it to an efﬁcient online algorithm for the internal regret problem. We provide methods that work both in the full information model, in which the loss of every action is observed at each time step, and the partial information (bandit) model, where at each time step only the loss of the selected action is observed. The importance of internal regret in game theory is due to the fact that in a general game, if each player has sublinear internal regret, then the empirical frequencies converge to a correlated equilibrium. For external regret we also derive a quantitative regret bound for a very general setting of regret, which includes an arbitrary set of modiﬁcation rules (that possibly modify the online algorithm) and an arbitrary set of time selection functions (each giving different weight to each time step). The regret for a given time selection and modiﬁcation rule is the difference between the cost of the online algorithm and the cost of the modiﬁed online algorithm, where the costs are weighted by the time selection function. This can be viewed as a generalization of the previously-studied sleeping experts setting. Keywords: online learning, internal regret, external regret, multi-arm bandit, sleeping experts, reductions

5 0.12452777 53 jmlr-2007-Maximum Entropy Density Estimation with Generalized Regularization and an Application to Species Distribution Modeling

Author: Miroslav Dudík, Steven J. Phillips, Robert E. Schapire

Abstract: We present a uniﬁed and complete account of maximum entropy density estimation subject to constraints represented by convex potential functions or, alternatively, by convex regularization. We provide fully general performance guarantees and an algorithm with a complete convergence proof. As special cases, we easily derive performance guarantees for many known regularization types, including 1 , 2 , 2 , and 1 + 2 style regularization. We propose an algorithm solving a large and 2 2 general subclass of generalized maximum entropy problems, including all discussed in the paper, and prove its convergence. Our approach generalizes and uniﬁes techniques based on information geometry and Bregman divergences as well as those based more directly on compactness. Our work is motivated by a novel application of maximum entropy to species distribution modeling, an important problem in conservation biology and ecology. In a set of experiments on real-world data, we demonstrate the utility of maximum entropy in this setting. We explore effects of different feature types, sample sizes, and regularization levels on the performance of maxent, and discuss interpretability of the resulting models. Keywords: maximum entropy, density estimation, regularization, iterative scaling, species distribution modeling

6 0.093494125 73 jmlr-2007-Revised Loss Bounds for the Set Covering Machine and Sample-Compression Loss Bounds for Imbalanced Data

7 0.081143647 70 jmlr-2007-Ranking the Best Instances

8 0.078890704 6 jmlr-2007-A Probabilistic Analysis of EM for Mixtures of Separated, Spherical Gaussians

9 0.074914292 65 jmlr-2007-PAC-Bayes Risk Bounds for Stochastic Averages and Majority Votes of Sample-Compressed Classifiers

10 0.046976984 64 jmlr-2007-Online Learning of Multiple Tasks with a Shared Loss

11 0.046461619 89 jmlr-2007-VC Theory of Large Margin Multi-Category Classifiers (Special Topic on Model Selection)

12 0.040730081 20 jmlr-2007-Combining PAC-Bayesian and Generic Chaining Bounds

13 0.040131681 10 jmlr-2007-An Interior-Point Method for Large-Scalel1-Regularized Logistic Regression

14 0.038314983 17 jmlr-2007-Building Blocks for Variational Bayesian Learning of Latent Variable Models

15 0.037743777 88 jmlr-2007-Unlabeled Compression Schemes for Maximum Classes

16 0.035132863 2 jmlr-2007-A Complete Characterization of a Family of Solutions to a Generalized Fisher Criterion

17 0.034821019 55 jmlr-2007-Minimax Regret Classifier for Imprecise Class Distributions

18 0.034748465 38 jmlr-2007-Graph Laplacians and their Convergence on Random Neighborhood Graphs (Special Topic on the Conference on Learning Theory 2005)

19 0.034488656 19 jmlr-2007-Classification in Networked Data: A Toolkit and a Univariate Case Study

20 0.033872772 62 jmlr-2007-On the Effectiveness of Laplacian Normalization for Graph Semi-supervised Learning

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.233), (1, -0.167), (2, -0.304), (3, -0.322), (4, -0.046), (5, 0.067), (6, 0.007), (7, 0.099), (8, -0.055), (9, -0.036), (10, 0.11), (11, -0.072), (12, 0.016), (13, -0.061), (14, -0.219), (15, -0.107), (16, 0.11), (17, -0.077), (18, -0.103), (19, -0.199), (20, -0.074), (21, 0.132), (22, -0.144), (23, -0.065), (24, 0.105), (25, -0.038), (26, 0.129), (27, -0.023), (28, -0.034), (29, 0.066), (30, -0.126), (31, 0.056), (32, -0.003), (33, 0.018), (34, 0.025), (35, -0.02), (36, -0.113), (37, -0.058), (38, -0.021), (39, 0.05), (40, 0.021), (41, -0.012), (42, 0.029), (43, -0.028), (44, 0.062), (45, 0.091), (46, 0.178), (47, 0.057), (48, -0.063), (49, -0.015)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.98437917 83 jmlr-2007-The On-Line Shortest Path Problem Under Partial Monitoring

Author: András György, Tamás Linder, Gábor Lugosi, György Ottucsák

2 0.63325143 14 jmlr-2007-Behavioral Shaping for Geometric Concepts

Author: Manu Chhabra, Robert A. Jacobs, Daniel Štefankovič

3 0.5367133 53 jmlr-2007-Maximum Entropy Density Estimation with Generalized Regularization and an Application to Species Distribution Modeling

Author: Miroslav Dudík, Steven J. Phillips, Robert E. Schapire

4 0.48966691 34 jmlr-2007-From External to Internal Regret (Special Topic on the Conference on Learning Theory 2005)

Author: Avrim Blum, Yishay Mansour

5 0.47723845 9 jmlr-2007-AdaBoost is Consistent

Author: Peter L. Bartlett, Mikhail Traskin

6 0.30525383 70 jmlr-2007-Ranking the Best Instances

7 0.28977707 73 jmlr-2007-Revised Loss Bounds for the Set Covering Machine and Sample-Compression Loss Bounds for Imbalanced Data

8 0.21790726 6 jmlr-2007-A Probabilistic Analysis of EM for Mixtures of Separated, Spherical Gaussians

9 0.19857135 89 jmlr-2007-VC Theory of Large Margin Multi-Category Classifiers (Special Topic on Model Selection)

10 0.19195765 65 jmlr-2007-PAC-Bayes Risk Bounds for Stochastic Averages and Majority Votes of Sample-Compressed Classifiers

11 0.15881866 62 jmlr-2007-On the Effectiveness of Laplacian Normalization for Graph Semi-supervised Learning

12 0.15454428 20 jmlr-2007-Combining PAC-Bayesian and Generic Chaining Bounds

13 0.147036 77 jmlr-2007-Stagewise Lasso

14 0.14512992 17 jmlr-2007-Building Blocks for Variational Bayesian Learning of Latent Variable Models

15 0.13402627 33 jmlr-2007-Fast Iterative Kernel Principal Component Analysis

16 0.1311087 38 jmlr-2007-Graph Laplacians and their Convergence on Random Neighborhood Graphs (Special Topic on the Conference on Learning Theory 2005)

17 0.12877232 64 jmlr-2007-Online Learning of Multiple Tasks with a Shared Loss

18 0.12807621 27 jmlr-2007-Distances between Data Sets Based on Summary Statistics

19 0.124205 31 jmlr-2007-Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm

20 0.12305036 2 jmlr-2007-A Complete Characterization of a Family of Solutions to a Generalized Fisher Criterion

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(4, 0.012), (8, 0.014), (10, 0.012), (12, 0.027), (28, 0.029), (40, 0.016), (48, 0.019), (60, 0.039), (80, 0.011), (85, 0.635), (98, 0.08)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.95133609 91 jmlr-2007-Very Fast Online Learning of Highly Non Linear Problems

Author: Aggelos Chariatis

Abstract: The experimental investigation on the efﬁcient learning of highly non-linear problems by online training, using ordinary feed forward neural networks and stochastic gradient descent on the errors computed by back-propagation, gives evidence that the most crucial factors for efﬁcient training are the hidden units’ differentiation, the attenuation of the hidden units’ interference and the selective attention on the parts of the problems where the approximation error remains high. In this report, we present global and local selective attention techniques and a new hybrid activation function that enables the hidden units to acquire individual receptive ﬁelds which may be global or local depending on the problem’s local complexities. The presented techniques enable very efﬁcient training on complex classiﬁcation problems with embedded subproblems. Keywords: neural networks, online training, selective attention, activation functions, receptive ﬁelds 1. Framework Online supervised learning is in many cases the only practical way of learning. This includes situations where the problem size is very big, or situations where we have a non-recurring stream of input vectors that are unavailable before training begins. We examine online supervised learning using a particular class of adaptive models, the very popular feed forward neural networks, trained with stochastic gradient descent on the errors computed by back-propagation. In order to easily visualize the online training dynamics of highly complex non linear problems, we are experimenting on 2:η:1 networks where the input is a point in a two dimensional image and the output is the value of the pixel at the corresponding input position. This framework allows the creation of very complex non-linear problems, just by hand-drawing the problem on a bitmap and presenting it to the network. Most problems’ images in this report are 256 × 256 pixels in size, producing in total 65536 different samples each one. Classiﬁcation and regression problems can be modeled as black & white and gray scale images respectively. In this report we only examine training on classiﬁcation problems. However, since mixed problems are possible, we are only interested on techniques that can be applied to both classiﬁcation and regression. The target of this investigation is online training where the input is not known in advance, so the input samples are treated as random and non-recurring vectors from the input space and are discarded after being used. We select and train on random samples until the average classiﬁcation or RMS error is acceptable. Since both the number of training exemplars and the complexity of the underlying function are assumed unknown, we require from our training mechanism to have “initial state invariance” as a fundamental property. Thus we deliberately exclude from our arsenal any c 2007 Aggelos Chariatis. C HARIATIS training techniques that require a schedule to be decided ahead of training. Ideally we would like from the training mechanism to be totally invariant to the initial training parameters and network state. This report is organized as follows: Sections 2 and 3 describe techniques for global and local selective attention. Section 4 is devoted to acceleration of training. In Section 5 we present experimental results and in Section 6 we discuss the presented techniques and give some directions for future research. Finally, Appendix A contains a description of the notations that have been used. In Figure 1 you can see some examples of problems that can be learned very efﬁciently using the techniques that are presented in the following sections. (a) (b) (c) (d) (e) Figure 1: Examples of complex non-linear problems that can be learned efﬁciently. 2. Global Selective Attention - Dynamic Training Set Evolution Consider the two problems depicted in Figure 2. Clearly, both problems are of approximately equal complexity, since they encapsulate the same image in a different scale and position within the input space. We would like to have a mechanism that will make the network capable of learning both problems at about the same speed. (a) (b) Figure 2: Approximately equal complexity problems. Intuitively, the samples on the boundaries, which are the samples on positions with the highest contrast, are those that determine the complexity of each problem. During training, these samples have the property that they produce the highest errors. We thus need a method that will focus attention on samples with high error relatively to the rest. Previous work on such global selective attention has been published by many authors (Munro, 1987; Yu and Simmons, 1990; Bakker, 1992, 1993; Schapire, 1999; Zhong and Ghosh, 2000). 2018 V ERY FAST O NLINE L EARNING OF H IGHLY N ON L INEAR P ROBLEMS Of particular interest are the various boosting algorithms, such as AdaBoost (Schapire, 1999), which work by placing more emphasis on training samples that the system is currently getting wrong. Unfortunately, the most successful of these algorithms require a predeﬁned set of samples on which training will be performed, something that is excluded from our scenario. Nevertheless, in a less constrained scenario, boosting can be applied on top of our techniques as a meta-learning algorithm, using our techniques as the base-learning algorithm. A simple method that can provide such an adaptive selective attention mechanism, by keeping an exponential trace of the average error in the training set, is described in Algorithm 1. e←0 ¯ Repeat Pick a random sample Evaluate the error e for the sample If e > 0.5 e ¯ e ← e α + e (1 − α) ¯ ¯ Train End Until a stopping criterion is satisﬁed In this report’s context, error evaluation and train are deﬁned as: Error Evaluation: Computation of the output values by forward propagating the activations from the input to the output layer for a single sample, plus computation of the output errors. The sample’s error e is set to the quadratic mean (RMS) of the output units’ errors. Train: Back-propagation of the output errors to the hidden layer and immediate weights’ adjustment. Algorithm 1: The dynamic training set evolution algorithm. The algorithm evaluates the errors of all samples, but trains only for samples with error greater than half the average error of the current training set. Training is initially performed for all samples, but gradually, it is concentrated on the samples at the problem’s boundaries. When the error for these samples is reduced, other previously excluded samples enter the training set. Thus, samples enter and leave the training set automatically, with a tendency to train on samples with high error. The magnitude of the constant α that determines the time scale of the exponential trace is problem speciﬁc, but in all experiments in this report it was kept ﬁxed to 10 −4 . The fraction of 0.5 was determined experimentally to give a good balance between sample selectivity and training set size. If it is close to 0 then we train for almost all samples. If it is close to 1 then we are at risk of making the training set starve from samples. Of course, one can choose to vary it dynamically in order to have a ﬁxed percentage of samples in the training set, or, to not allow the training percentage to fall below a pre-speciﬁed limit. Figure 3 shows the training set evolution for the two-spirals problem (in Figure 1a) in various training stages. The network topology was 2:64:1. You can see the training set forming gradually and tracing the problem boundaries where the error is the highest. One could argue that such a process may be very sensitive to outliers. Experiments have shown that this does not happen. The algorithm does not try to recognize the outliers, but at least, adjusts naturally by not allowing the training set size to shrink. So, at the presence of heavy noise, the algorithm becomes ineffective, but does not introduce any additional harm. Figure 4 shows the two2019 C HARIATIS 10000-11840-93% 20000-25755-76% 40000-66656-41% 60000-142789-22% 90000-296659-18% Figure 3: Training set evolution for the two-spirals problem. Under each image you can see the stage of training in trains, error-evaluations and the percentage of samples for which training is performed at the corresponding stage. spirals problem distorted by dynamic noise and the corresponding training set after 90000 trains with 64 hidden units. You can see that the algorithm tolerates noise by not allowing the training set size to shrink. It is also interesting that at noise levels as high as 30% the algorithm can still exclude large areas of the input space from training. 10%-42% 20%-62% 30%-75% 50%-93% 70%-99% Figure 4: Top row shows the model with a visualization of the applied dynamic noise. Bottom row shows the corresponding training sets after 90000 trains. Under each pair of images you can see the percentage of noise distortion applied to the original input and the percentage of samples for which training is performed. 3. Local Selective Attention - Receptive Fields Having established a global method to focus attention on the important parts of a problem, we now come to address the main issue, which is the network training. Let ﬁrst discuss the roles of the hidden and output layers in a feed forward neural network with a single hidden layer and without shortcut input-to-output connections. 2020 V ERY FAST O NLINE L EARNING OF H IGHLY N ON L INEAR P ROBLEMS The hidden layer is responsible for transforming a non linear input-to-output mapping, into a non linear input-to-hidden layer mapping, that can be mapped linearly to the output. The output layer is responsible for learning a linear hidden-to-output mapping (which is an easy job), but most importantly, it must provide to the hidden layer error gradient information that will be used for the error credit assignment problem. In this respect, it becomes apparent that all hidden units should receive the most possibly accurate error information. That is why, we must train all hidden to output connections and back propagate the error through all these connections. This is not the case for the hidden layer. Consider, for a classiﬁcation problem, how the hidden units with sigmoidal activations partition the input space into sub areas. By adjusting the input-tohidden weights and biases, each hidden unit develops a hyperplane that bi-partitions the input space in the most useful sense. We would like to limit the number of hyperplanes in order to reduce the system’s available degrees of freedom and obtain better generalization capabilities. At the same time, we would like to thoroughly use them in order to optimize the input output approximation. This can be done by arranging the hyperplanes to touch the problem’s boundaries at regular intervals dictated by the boundary curvature, as it is shown in Figure 5a. Figure 5b, shows a suboptimal placement of the hyperplanes which causes a waste of resources. Each hidden unit must be differentiated from the others and ideally not interfere with the subproblems that the other units are trying to solve. Suppose that two hidden units are governed by the same, or nearly the same, parameters. How can we differentiate them? There are many possibilities. (a) (b) Figure 5: Optimal vs. suboptimal hyperplanes. One could be, to just throw one unit away and make the output weight of the other equal to the sum of the two original output weights. That would leave the function unchanged. However, identifying these similar units during training is not easy computationally. In addition, we would have to ﬁgure out a method that would compute the best initial placement for the hyperplane of the new unit that would substitute the one that was thrown away. Another possibility would be to add noise in the weight updates, gradually reduced with a simulated annealing schedule which should be decided before training begins. Unfortunately, the loss of initial state invariance would complicate training for unknown complex non linear problems. To our thinking, it is much better to embed constraints into the system, so that it will not be possible for two hidden units to develop the same hyperplane. Two computationally efﬁcient techniques to embed such constraints are described in sections 3.1 and 3.2. Many other authors have also examined methods for local selective attention. For the related discussions see Huang and Huang (1990), Ahmad and Omohundro (1990), Baluja and Pomerleau (1995), Flake (1998), Duch et al. (1998), and Phillips and Noelle (2004). 2021 C HARIATIS 3.1 Fixed Cascaded Inhibitory Connections A problem with the hidden units of conventional feed forward networks is that they are all fed with the same inputs and back propagated errors and that they operate without knowing each other’s existence. So, nothing prevents them from behaving identically. This lack of communication between hidden units has been addressed by researchers through hidden unit lateral connections. Agyepong and Kothari (1997) use unidirectional lateral interconnections between adjacent hidden layer units, claiming that these connections facilitate the controlled assignment of role and specialization of the hidden units. Kothari and Ensley (1998) use Gaussian lateral connections which enable the hidden decision boundaries to be global in nature but also be able to represent local structure. Numerous neural network algorithms employ bidirectional lateral inhibitory connections in order to generate competition between the hidden units. In an interesting variation described by Spratling and Johnson (2004), competition is provided by each hidden unit blocking its preferred inputs from activating other units. We use a single hidden layer where the hidden units are considered sequenced. Each hidden unit is connected to all succeeding hidden units with a ﬁxed connection with weight set to minus one. The hidden units get differentiated, because they receive different inputs, they produce different activations and they get back different error information. Another beneﬁt is that they can generate higher order feature detectors, that is, the resulting hidden hyperplanes are no longer strictly linear, but they may also be curved. Considering the ﬁxed value, -1 is used just to avoid a multiplication. Values from -0.5 to -2 give good results as well. As it is shown in Section 5.1.1, the ﬁxed cascaded inhibitory connections are very effective at reducing a problem’s asymptotic residual error. This should be attributed to both of their abilities, to generate higher order feature detectors and to hasten the hidden units’ symmetry breaking. These connections can be implemented very efﬁciently with just one subtraction per hidden unit for both hidden activation and hidden error computation. In addition, the disturbance to the parallelism of the backpropagation algorithm is minimal. Most operations on the hidden units can still be done in parallel and only the ﬁnal computations must be performed sequentially. We include the algorithms for the hidden activation and error computations as examples of sequential implementations. These changes can be very easily incorporated into conventional neural network code. Hidden Activations δ←0 For j ← 1 . . . η nj ← δ+x·wj h j ← f (n j ) δ ← δ−hj End Hidden Error Signals δ←0 For j ← η . . . 1 ej ← δ+r ·uj g j ← e j f (n j ) δ ← δ−gj End Algorithm 2: Hidden unit activation and error computation with Fixed Cascaded -1 Connections. 2022 V ERY FAST O NLINE L EARNING OF H IGHLY N ON L INEAR P ROBLEMS 3.2 Selective Training of the Hidden Units The hidden units’ differentiation can be farther magniﬁed if each unit is not trained on all samples, but only on the samples for which it receives a high error. We train all output units, but only the hidden units for which the error signal is higher than the RMS of the error signals of all hidden units. Typically about 10% of the hidden units are trained on each sample during early training and the percentage falls up to 2% when the network is close to the solution. This is intuitively justiﬁed by the observation that at the beginning of training the hidden units are largely undifferentiated and receive high error signals from the whole input space. At the ﬁnal stage of training, the hidden hyperplanes’ linear soft decision boundaries are combined by the output layer to deﬁne arbitrarily shaped decision boundaries. For µ input dimensions, from 1 up to µ units can deﬁne an open sub-region and µ + 1 units are enough to deﬁne a closed convex region. With such high level constructs, each sample may be discriminated from the rest with very few hidden units. These, are the units that receive the highest error signal for the sample. Experiments on various problems have shown that training on a fraction of the hidden units is always better (in respect to number of trains to convergence), than training all or just one hidden unit. It seems that training only one hidden unit on each sample is not sufﬁcient for some problems (Thornton, 1992). Measurements for one of these experiments are reported in Section 5.1.1. In addition to the convergence acceleration, the combined effect of training a fraction of the hidden units on a fraction of the samples, gives big savings in CPU usage per sample as well. This sparseness of training in respect to evaluation provides further opportunities for speedup as it is discussed in Section 4. 3.3 Centering On The Input Space It is a well known recommendation (Schraudolph, 1998a,b; LeCun et al., 1998) that the input values should be normalized to have zero mean and unit standard deviation over each input dimension. This is achieved by subtracting from each input value the mean and dividing by the standard deviation. For some problems, like the one in Figure 2b, the center of the input space is not equal to the center of the problem. When the input is not known in advance, the later must be computed adaptively. Moreover, since the hidden units are trained on different input samples, we should compute for each hidden unit its own mean and standard deviation over each input dimension. For the connection between hidden unit j and input unit i we can adaptively compute the approximate mean m ji and standard deviation s ji over the inputs that train the hidden unit, using either exponential traces: m ji (t) ← β xi + (1 − β) m ji (t−1) , q ji (t) ← β xi2 + (1 − β) q ji (t−1) , s ji (t) ← (q ji (t) − m ji 2 )1/2 , (t) or perturbated calculations: m ji (t) ← m ji (t−1) + β (xi − m ji (t−1) ), v ji (t) ← v ji (t−1) + β (xi − m ji (t) ) (xi − m ji (t−1) ) − v ji (t−1) , 2023 C HARIATIS 1/2 s ji (t) ← v ji (t) , where β is a constant that determines the time scale of exponential averaging, vector x holds the input values, matrix Q holds the means of the squared input values and matrix V holds the variances. The means and standard deviations of a hidden unit’s input connections are updated only when the hidden unit is trained. The result of this treatment is that each hidden unit is centered on a different part of the input space. This center is indirectly affected by the error that the inputs produce on the hidden unit. The magnitude of the constant β is problem speciﬁc, but in all experiments in this report it was kept ﬁxed to 10−3 . This constant must be selected large enough, so that the centers will rapidly move to their optimum locations, and small enough, so that the hidden units will see a relatively static view of the input space and the gradient descent algorithm will not be confused. As the hidden units jitter around their centers, we effectively train them on slightly shifted views of the input space, something that can assist generalization. We get something analogous to training with jitter (Reed et al., 1995), at no extra cost. In Figure 6, the squares show where each hidden unit is centered. You can see that most are centered on the problem boundaries at regular intervals. The crosses show the standard deviations. On some directions the standard deviations are very small, which results in very high normalized input values, causing the hidden units to act as threshold units at those directions. The sloped lines show the hyperplane distance from center and the slope. These are computed for display purposes, from their theoretical formulas for a conventional network, without considering the effect of the cascaded connections. For some units the hyperplanes shown are not exactly on the boundaries. This is because of the ﬁxed cascaded connections that cause the hidden units to be not exactly linear discriminants. In the last picture you can see the decision surface of a hidden unit which is a bit curved and coincides with the class boundary although its calculated hyperplane is not on the boundary. An observant reader may also notice that the hyperplane distances from the centers are very small, which implies that the corresponding biases are small as well. On the contrary, if all hidden units were centered on the center of the image, we would have the following problem. The hyperplanes of some hidden units must be positioned on the outer parts of the image. For this to happen, these units should develop large biases in respect to the weights. This would make their activations to have small variances. These small variances might need to be compensated by large output weights and biases, which would saturate the output units and in addition ill-condition the problems. One may wonder if the hidden biases are still necessary. Since the centers are individually set, it may seem at ﬁrst that they are not. However, the centers are not trained through error backpropagation, and the hyperplanes do not necessarily pass over them. The biases role is to drive the hyperplanes to the correct location and thus pull the centers in the corresponding direction. The individual centering of the hidden units based on the samples’ positions is feasible, because we train only on samples with high errors and only the hidden units with high errors. By ignoring the small errors, we effectively position the center of each hidden unit near the center of mass of the high errors that it receives. However, this centering technique can still be used even if one chooses to train on all samples and all hidden units. Then, the statistics interval should be differentiated for each hidden unit and be recomputed for each sample relatively to the normalized absolute error that each hidden unit receives. A way to do it is to set the effective statistics interval for hidden unit j 2024 V ERY FAST O NLINE L EARNING OF H IGHLY N ON L INEAR P ROBLEMS Figure 6: Hidden unit centers, standard deviations, hyperplanes, global and local training sets and a hidden unit’s output. The images were captured at the ﬁnal stage of training, of the problem in Figure 1a with 64 hidden units. and sample s to: β |e j,s | |e j | where β is the global statistics interval, e j,s is the hidden unit’s backpropagated error for the sample and |e j | is the mean of the absolute backpropagated errors that the hidden unit receives, measured via an exponential trace. The denominator acts as a normalizer, which makes the hidden unit’s mobility to be independent of the average magnitude of the errors. Centering on other factors has been extensively investigated by Schraudolph (1998a,b). These techniques can provide further convergence acceleration, but we chose not to use them because of the additional computational overhead that they require. 3.4 A Hybrid Activation Function As it is shown in Section 5, the aforementioned techniques enable successful training on some difﬁcult problems like those in Figures 1a and 1b. However, if the problem contains subproblems, or put in another way, if the problem generates more than one cluster of high error density, the centering mechanism does not manage to drive the hidden unit centers to the most suitable locations. The centers are attracted by the larger subproblem or get stuck in areas between the subproblems, as shown in Figure 7. 2025 C HARIATIS Figure 7: Model, training set, and inadequate centering We need a mechanism that can force a hidden unit to get out of balanced but suboptimal positions. It would be nice if this mechanism could also allow the centers to migrate to various points in the input space as the need arises. It has been found that both of these requirements are fulﬁlled by a new hybrid activation function. Sigmoid activations have the property that they produce hyperplanes that separate the input space globally. Our intention is to use a sigmoid like hidden activation function, because it can provide global separability, and at the same time, reduce the activation value towards zero on inputs which are not important to a hidden unit. The Gaussian function is commonly used within radial basis function (RBF) neural networks (Broomhead and Lowe, 1988). When this function is applied to the distance of a sample to the unit’s center, it produces a local response which is stronger near the center. We can then enclose the sigmoidal activation within a Gaussian envelope, by multiplying the activation with a value between 0 and 1, which is provided by applying the Gaussian function to the distance that is measured in the normalized input space. When the number of input dimensions is large, the distance metric that must be used is not an obvious choice. Table 1 contains the distance metrics that we have considered. The most suitable distance metric seems to depend on the distribution of the samples that train the hidden units. µ ∑ xi2 i=1 Euclidean 1 µ µ ∑ xi2 i=1 Euclidean Scaled µ ∑ |xi | i=1 Manhattan 1 µ µ ∑ |xi | i=1 Manhattan Scaled max |xi | Chebyshev Table 1: Various distance metrics that have been considered for the hybrid activation function. In particular, if the samples follow a uniform distribution over a hypercube, then the Euclidean distance has the disturbing property that the average distance grows larger as the number of input dimensions increases and consequently the corresponding average Gaussian response decreases towards zero. As suggested by Hegland and Pestov (1999), we can make the average distance to center independent of the input dimensions, by measuring it in the normalized input space and then dividing it by the square root of the input’s dimensionality. The same problem occurs for the Manhattan distance which has been claimed to be a better metric in high dimensions (Aggarwal et al., 2001). We can normalize this distance by dividing it by the input’s dimensionality. A problem that 2026 V ERY FAST O NLINE L EARNING OF H IGHLY N ON L INEAR P ROBLEMS appears for both of the above rescaled distance metrics, is that for the samples that are near the axes the distances will be very much attenuated and the corresponding Gaussian responses will be close to one, something that will make the Gaussian envelopes ineffective. A more suitable metric for this type of distributions is the Chebyshev metric whose average magnitude is independent of the dimensions. However, for reasons analogous to those mentioned above, this metric is not the most suitable if the distribution of the samples is spherical. In that case, the Euclidean distance does not need any rescaling and is the most natural distance measure. We can obtain spherical distributions by adaptively whitening them. As Plumbley (1993) and Laheld and Cardoso (1994) independently proposed, the whitening matrix Z can be adaptively computed as: Zt+1 = Zt − λ zt zt T − I Zt where λ is the learning rate parameter, zt = Zt xt is the whitened vector and xt is the input vector. However, we would need too many additional parameters to do it individually for each subset of samples on which each hidden unit is trained. For the above reasons (and because of lack of a justiﬁed alternative), in the implementation of these techniques we typically use the Euclidean metric when the number of input dimensions is up to three and the Chebyshev metric in all other cases. We have also replaced the usual tanh (sigmoidal) and Gaussian (bell-like) functions, by similar functions which do not involve exponentials (Elliott, 1993). For each hidden unit j we ﬁrst compute the net-input n j to the hidden unit (that is, the weighted distance of the sample to the hyperplane), as the inner product of normalized inputs and weights plus the bias: xi − m ji , s ji = z j · w j. z ji = nj We then compute the sample’s distance d j to the center of the unit which is measured in the normalized input space: dj = zj . Finally, we compute the activation h j as: nj , (1 + n j ) 1 , = bell(d j ) = (1 + d 2 ) j = a j b j. a j = Elliott(n j ) = bj hj Since d j is not a function of w j , we treat b j as a constant for the calculation of the activation derivative with respect to n j , which becomes: ∂h j = b j (1 − a j )2 . ∂n j 2027 C HARIATIS The hybrid activation function, which by deﬁnition may only be used for hidden units connected to the input layer, enables these units to acquire selective attention capabilities on the input space. Each hidden unit may have a global or local receptive ﬁeld on each input dimension. The size of this dimensional receptive ﬁeld depends on the standard deviation which is computed for the corresponding dimension. This activation makes balanced positions between subproblems to be unstable. As soon as the center is changed by a small amount, it will be attracted by the nearest subproblem. This is because the unit’s activation and the corresponding error will be increased for samples towards the nearest subproblem and decreased at the other direction. Hidden units can still be centered between subproblems but only if their movement at either direction causes a large error for samples at the opposite direction, that is, if they are absolutely necessary at their current position. Additionally, if a unit is centered near a subproblem that produces low errors and the unit is not necessary in that area, then it may migrate to other areas that still have high errors. This unit center migration has been observed in all experiments on complex problems. This may be due to the non-linear response of the bell function, and its long tails which keep the activation above zero for all input samples. Figure 8: Model, evaluation, training set, hidden unit centers and two hidden unit outputs showing the effect of the hybrid activation function. The images were captured at the ﬁnal stage of training, of the problem in Figure 1d with 700 hidden units. In Figure 8 you can see a complex problem with 9 clusters of high errors. The hidden units place their centers on all clusters and are able to solve the problem. In the last two images, you can see the 2028 V ERY FAST O NLINE L EARNING OF H IGHLY N ON L INEAR P ROBLEMS effect of the hybrid activation function which attenuates the activation at points far from the center in respect to the standard deviation on each dimension. One unit develops a near circular local receptive ﬁeld and one other develops an elongated ellipsoidal receptive ﬁeld. The later provides almost global separation in the vertical direction and becomes a useful discriminant for two of the subproblems. One may ﬁnd similarities between this hybrid activation function and the Square-MLP architecture described by Flake (1998). The later, partially implements higher order neurons by duplicating the number of input units and setting the new input values equal to the squares of the original inputs. This architecture enables the hidden units to form local features of various shapes, but not the locally constrained sigmoid formed by our proposal. In contrast, the hybrid activation function does not need any additional parameters beyond those that are already used for centering and it has the additional beneﬁt, which is realized by the local receptive ﬁelds in conjunction with the small biases and the symmetric sigmoid, that the hidden activations will have a mean close to zero. As discussed by Schraudolph (1998a,b) and LeCun et al. (1998), this is very beneﬁcial for the output layer training. However, there is still room for improvement. As it was also observed by Flake (1998), the orientations of the receptive ﬁeld ellipses are always at the direction of one of the input axes. This limitation is expected to hinder performance when training hidden units which have sloped hyperplanes. Figure 9 shows a complex problem at the middle of training. Units with sloped hyperplanes are trained on samples whose input values are highly correlated. This can slowdown learning by itself, but in addition, the standard deviations cannot get sufﬁciently small and as a result the receptive ﬁeld cannot be sufﬁciently shrunk at the direction perpendicular to the hyperplane. As a result the hidden unit’s activation unnecessarily interferes with the activations of nearby units. Although it may be possible to address the correlation problem with a more sophisticated training method that uses second order gradient information, like Stochastic Meta Descent (Schraudolph, 1999, 2002), the orientations of the receptive ﬁelds will still be limited. In Section 6.2 we discuss possible directions for further research that may circumvent this limitation. Figure 9: Evaluation and global and local training sets during middle training for the problem in Figure 1b. It can be seen that a hidden unit with a sloped hyperplane is trained on samples with highly correlated input values. Samples that are separated by horizontal or vertical hyperplanes are easier to be learned. 2029 C HARIATIS 4. Further Speedups In this section we ﬁrst describe an implementation technique that reduces the computational requirements of the error evaluation phase and then we give references to methods that have been proposed by other authors for the acceleration of the training phase. 4.1 Evaluation Speedup Two of the discussed techniques, training only for samples with high errors, and then, training only the hidden units with high error, make the error-evaluation phase to be the most processing demanding phase for the solution of a given problem. In addition, some other techniques, like board game learning through temporal difference methods, require many evaluations to be performed before each train. We can speedup evaluation by the following observation: For many problems, only part of the input is changed on successive samples. For example, for a backgammon program with 200 input units (with raw board data and not any additional features encoded), very few inputs will change on successive positions. Even on two dimensional problems such as images, we can arrange to train on samples selected by random changes on the X and Y dimensions alternatively. This process of only resampling one coordinate at a time is also known as “Gibbs sampling” and it nicely generalises to more than two coordinates (Geman and Geman, 1984). Thus, we can keep in memory all intermediate results from the evaluation, and recalculate only for the inputs that have changed. This implementation technique requires more storage, especially for high dimensional inputs. Fortunately, storage is not an issue on modern hardware. 4.2 Training Speedup Many authors have proposed methods for speeding-up online training by using second order gradient information in order to dynamically vary either the learning rate or the momentum (see LeCun et al., 1993; Leen and Orr, 1993; Murata et al., 1996; Harmon and Baird, 1996; Orr and Leen, 1996; Almeida et al., 1997; Amari, 1998; Schraudolph, 1998c, 1999, 2002; Graepel and Schraudolph, 2002). As it is shown in the next section, our techniques enable standard stochastic gradient descent with momentum to efﬁciently solve all the highly non-linear problems that have been investigated. However, the additional speed up that an accelerating algorithm can give is a nice thing to have. Moreover, these accelerating algorithms automatically reduce the learning rate when we are close to a solution (by sensing the oscillations in the error gradient) something that we should do through annealing if we wanted the best possible solution. We use the Incremental Delta-Delta (IDD) accelerating algorithm (Harmon and Baird, 1996), an incremental nonlinear extension to Jacobs’ (1988) Delta-Delta algorithm, because of its simplicity and relatively small processing requirements. IDD computes an individual learning rate λ for each weight w as: λ(t) = eξ(t) , ξ(t + 1) = ξ(t) + θ ∆w(t + 1) ∆w(t), λ(t) where θ is the meta-learning rate which we typically set to 0.1. 2030 V ERY FAST O NLINE L EARNING OF H IGHLY N ON L INEAR P ROBLEMS 5. Experimental Results In order to measure the effectiveness of the described techniques on various classes of problems, we performed several experiments. Each experiment was replicated 10 times with different random initial weights using matched random seeds and the means and standard deviations of the results were plotted in the corresponding ﬁgures. For the experiments we used a single hidden layer, the cross entropy error function, the logistic or softmax activation function for the output units and the Elliott or hybrid activation function for the hidden units. Output to hidden layer weights and biases were initialized to zero. Hidden to input layer weights were initialized to random numbers from a normal distribution and then rescaled so that the incoming weights to each hidden unit had norm unity. Hidden unit biases were initialized to a uniform random number between zero and one. The curves in the ﬁgures are labelled with a combination of the following letters which indicate the techniques that were applied: B – Adjust weights using stochastic gradient descent with momentum 0.9 and ﬁxed learning rate √ 0.1/ c where c is the number of incoming connections to the unit. A – Adjust weights using IDD with meta-learning rate 0.1 and initial learning rate √ 1/ c where c is as above. L – Use ﬁxed cascaded inhibitory connections as described in Section 3.1. S – Skip weights adjustment for samples with low error as described in Section 2. U – Skip weights adjustment for hidden units with low error as described in Section 3.2. C – Use individual means and stdevs for each hidden to input connection as described in Section 3.3. H – Use the hybrid activation function as described in Section 3.4. For the ‘B’ training method we deliberately avoided an annealing schedule for the learning rate, since this would destroy the initial state invariance of our techniques. Instead, we used a ﬁxed small learning rate which we compensated with a large momentum. For the ‘A’ method, we used a small meta-learning rate, to avoid instabilities due to the high non-linearities of the examined problems. It is important to note that for both training methods the learning parameters were ﬁxed to the above values and not optimized to each individual problem. For the ‘C’ technique, the centers of the hidden units where initially set to the center of the input space and the standard deviations were set to one third of the distance between the extreme values of each dimension. When the technique was not used, a global preprocessing was applied which normalized the input samples to have zero mean and unit standard deviation. 5.1 Two Input Dimensions In this section we give experimental results for the class of problems that we have mainly examined, that is, problems in two input and one output dimensions, for which we have dense and noiseless training samples from the whole input space. In the ﬁgures, we measure the average classiﬁcation error in respect to the stage of training. The classiﬁcation error was averaged via an exponential trace with time scale 10−4 . 2031 C HARIATIS 5.1.1 C OMPARISON OF T ECHNIQUE C OMBINATIONS For these experiments we used the two-spirals problem shown in Figures 1a, 3, 4 and 6. We chose this problem as a non trivial representative of the class of problems that during early training generate a single cluster of high error density. The goal of this experiment is to measure the effectiveness of various technique combinations and then to measure how well the best technique combination scales with the size of the hidden layer. Figures 10 and 11 show the average classiﬁcation error in respect to the number of evaluated samples and processing cycles respectively for 13 technique combinations. For these experiments we used 64 hidden units. The standard deviations were not plotted in order to keep the ﬁgures uncluttered. Figure 10 has also been split to Figures 12 and 13 in order to show the related error bars. Comparing the curves B vs. BL and BS vs. BLS on Figures 10 and 11, we can see that the ﬁxed cascaded inhibitory connections reduce the asymptotic residual error by more than half. This also applies, but to a lesser degree, when we skip weight updates for hidden units with low errors (B vs. BU, BS vs. BSU). When used in combination, we can see a speed-up of convergence but the asymptotic error is only marginally further improved (BLU and BLSU). In Figure 11, it can be seen that skipping samples with low errors can speed-up convergence and reduce the asymptotic error as well (BLU vs. BLSU). This is a very intriguing result, in the sense that it implies that the system can learn faster and better by throwing away information. Both Figures 10 and 11 show the BLUCH curve to diverge. Considering the success of the BLSUCH curve, we can imply that skipping samples is necessary for the hybrid activation. However, the real problem, which was found out by viewing the dynamics of training, is that the centering mechanism does not work correctly when we train on all samples. A possible remedy may be to modify the statistics interval which is used for centering, as it is described at the end of Section 3.3. BLSUC vs. BLSU shows that centering further reduces the remaining asymptotic error to half and converges much faster as well. Comparing curve BLSUCH vs. BLSUC, we see that the hybrid activation function does better, but only marginally. This was expected since this problem has a single region of interest, so the ability of H to focus on multiple regions simultaneously is not exercised. This is the reason for the additional experiments in Section 5.1.2. BLSUCH and ALSUCH were the most successful technique combinations, with the later being a little faster. Nevertheless, it is very impressive that standard stochastic gradient descent with momentum can approach the best asymptotic error in less than a second, when using a modern 3.2 GHz processor. Figure 14 shows the average classiﬁcation error in respect to the number of evaluated samples, for the ALSUCH technique combination and various hidden layer sizes. It can be seen that the asymptotic error is almost inversely proportional to the number of hidden units. This is a good indication that our techniques use the available resources efﬁciently. It is also interesting, that the convergence rates to the corresponding asymptotic errors are quite fast and about the same for all hidden layer sizes. 5.1.2 H YBRID VS . C ONVENTIONAL ACTIVATION For these experiments we used the two dimensional problem depicted in Figures 1c and 7. We chose this problem as a representative of the class of problems that during early training generate 2032 V ERY FAST O NLINE L EARNING OF H IGHLY N ON L INEAR P ROBLEMS B BU BL BLU BLUC BLUCH ALSUCH 0,35 0,30 BS BSU BLS BLSU BLSUC BLSUCH 0,25 0,20 0,15 0,10 0,05 0,00 0 100000 200000 300000 400000 500000 600000 700000 800000 900000 1000000 Figure 10: Average classiﬁcation error vs. number of evaluated samples for various technique combinations, while training the problem in Figure 1a with 64 hidden units. The standard deviations have been omitted for clarity. B BU BL BLU BLUC BLUCH ALSUCH 0,35 0,30 BS BSU BLS BLSU BLSUC BLSUCH 0,25 0,20 0,15 0,10 0,05 0,00 0 1 2 3 4 5 6 7 8 9 10 Figure 11: Average classiﬁcation error vs. Intel IA32 CPU cycles in billions, for various technique combinations, while training the problem in Figure 1a with 64 hidden units. The horizontal scale also corresponds to seconds when run on a 1 GHz processor. The standard deviations have been omitted for clarity. 2033 C HARIATIS BS BLS BLSUC ALSUCH 0,35 BSU BLSU BLSUCH 0,30 0,25 0,20 0,15 0,10 0,05 0,00 0 100000 200000 300000 400000 500000 600000 700000 800000 900000 1000000 Figure 12: Part of Figure 10 showing error bars for technique combinations which employ S. B BL BLUC 0,35 BU BLU BLUCH 0,30 0,25 0,20 0,15 0,10 0,05 0,00 0 100000 200000 300000 400000 500000 600000 700000 800000 900000 1000000 Figure 13: Part of Figure 10 showing error bars for technique combinations which do not employ S. 2034 V ERY FAST O NLINE L EARNING OF H IGHLY N ON L INEAR P ROBLEMS 32 48 64 96 128 256 0,20 0,15 0,10 0,05 0,00 0 100000 200000 300000 400000 500000 600000 700000 800000 900000 1000000 Figure 14: Average classiﬁcation error vs. number of evaluated samples for various hidden layer sizes, while training the problem in Figure 1a with the ALSUCH technique combination. ALSUCH 0,04 ALSUC 0,03 0,02 0,01 0,00 0 300000 600000 900000 1200000 1500000 1800000 2100000 2400000 2700000 3000000 Figure 15: Average classiﬁcation error vs. number of evaluated samples for the ALSUCH and ALSUC technique combinations, while training the problem in Figure 1c with 100 hidden units. The dashed lines show the minimum and maximum observed values. 2035 C HARIATIS small clusters of high error density of various sizes. For this kind of problems we typically obtain very small residuals for the classiﬁcation error, although the problem may not have been learned. This is because we measure the error on the whole input space and for these problems most of the input space is trivial to be learned. The problem’s complexities are conﬁned in very small areas. The dynamic training set evolution algorithm is able to locate these areas, but we need much more sample presentations, since most of the samples are not used for training. The goal of this experiment is to measure the effectiveness of the hybrid activation function at coping with the varying sizes of the subproblems. For these experiments we used 100 hidden units. Figure 15 shows that the ALSUCH technique, which employs the hybrid activation function, reduced the asymptotic error to half in respect to the ALSUC technique. As all of the visual inspections revealed, one of which is reproduced in Figure 16, the difference in the residual errors of the two curves is due to the insufﬁcient approximation of the smaller subproblem by the ALSUC technique. Model ALSUCH ALSUC Figure 16: ALSUCH vs. ALSUC approximations for a problem with two sub-problems. 5.2 Higher Input and Output Dimensions In order to evaluate our techniques on a problem with higher input and output dimensions, we selected a standard benchmark, the Letter recognition database from the UCI Machine Learning Repository (Newman et al., 1998). This database consists of 20000 samples that use 16 integer attributes to classify the 26 letters of the English alphabet. This problem is characterized by a medium input dimensionality and a large output dimensionality. The later, makes it a very challenging problem for any classiﬁer. This problem differs from those on which we have experimented so far, in that we do not have the whole input space at our disposal for training. We must train on a limited number of samples and then test the system’s generalization abilities on a separate test set. Although we have not taken any special measures to assist generalization, the experimental results indicate that our techniques have the inherent ability to generalize well, when given noiseless exemplars. An observation that applies to this problem is that the IDD accelerated training method could not do better than standard stochastic gradient descent with momentum. Thus, we report results using 2036 V ERY FAST O NLINE L EARNING OF H IGHLY N ON L INEAR P ROBLEMS the BLSUCH technique combination which is computationally more efﬁcient than the ALSUCH technique. For this experiment, which involves more than two output classes, we used the softmax activation function at the output layer. Table 2 contains previously published results showing the classiﬁcation accuracy of various classiﬁers. The most successful of them were the AdaBoosted versions of the C4.5 decision-tree algorithm and of a feed forward neural network with two hidden layers. Both classiﬁer ensembles required quite a lot of machines in order to achieve that high accuracy. Classiﬁer Naive Bayesian classiﬁer AdaBoost on Naive Bayesian classiﬁer Holland-style adaptive classiﬁer C4.5 AdaBoost on C4.5 (100 machines) AdaBoost on C4.5 (1000 machines) CART AdaBoost on CART (50 machines) 16-70-50-26 MLP (500 online epochs) AdaBoost on 16-70-50-26 MLP (20 machines) AdaBoost on 16-70-50-26 MLP (100 machines) Nearest Neighbor Test Error % 25,3 24,1 17,3 13,8 3,3 3,1 12,4 3,4 6,2 2,0 1,5 4,3 Reference Ting and Zheng (1999) Ting and Zheng (1999) Frey and Slate (1991) Freund and Schapire (1996) Freund and Schapire (1996) Schapire et al. (1997) Breiman (1996) Breiman (1996) Schwenk and Bengio (1998) Schwenk and Bengio (1998) Schwenk and Bengio (2000) Fogarty (1992) Table 2: A compilation of previously reported best error rates on the test set for the UCI Letters Recognition Database. Figure 17 shows the average error reduction in respect to the number of online epochs, for the BLSUCH technique combination and various hidden layer sizes. As suggested in the database’s documentation, we used the ﬁrst 16000 samples for training and for measuring the training accuracy and the rest 4000 samples to measure the predictive accuracy. The solid and dashed curves show the test and training set errors respectively. Similarly to ensemble methods, we can observe two interesting phenomena which both seem to contradict the Occam’s razor principle. The ﬁrst observation is that the test error stabilizes or continues to slightly decrease even after the training error has been zeroed. What is really happening is that the RMS error for the training set (which is related to the conﬁdence of classiﬁcation) continues to decrease even after the classiﬁcation error has been zeroed, something that is also beneﬁciary for the test set’s classiﬁcation error. The second observation is that increasing the network’s capacity does not lead to over ﬁtting. Although the training set error can be zeroed with just 125 hidden units, increasing the number of hidden units reduces the residual test error as well. We attribute this phenomenon to the conjecture that the hidden units’ differentiation results in a smoother approximation (as suggested by Figure 5 and the related discussion). Comparing our results with those in Table 2, we can also observe the following: The 16-125-26 MLP (5401 weights) reached a 4.6% misclassiﬁcation error on average, which is 26% better than the 6.2% of the 16-70-50-26 MLP (6066 weights), despite the fact that it had fewer weights, a simpler 2037 C HARIATIS 125 T RAIN 125 T EST 250 T RAIN 250 T EST 500 T RAIN 500 T EST 1000 T RAIN TEST ERROR % UNITS MIN AVG at end 125 4.0 4.6 250 2.8 3.2 500 2.3 2.6 1000 2.1 2.4 0,10 1000 T EST 0,05 0,00 0 10 20 30 40 50 60 70 80 90 100 Figure 17: Average error reduction vs. number of online epochs for various hidden layer sizes, while training on the UCI Letters Recognition Database with the BLSUCH technique combination. The solid and dashed curves show the test and training set errors respectively. The standard deviations for the training set errors have been omitted for clarity. The embedded table contains the minimum observed errors across all trials and epochs, and the average errors across all trials at epoch 100. architecture with one hidden layer only and it was trained for a far less number of online epochs. It is indicative that the asymptotic residual classiﬁcation error on the test set was reached in about 30 online epochs. The 16-1000-26 MLP (43026 weights) reached a 2.4% misclassiﬁcation error on average, which is the third best published result following the AdaBoosted 16-70-50-26 MLPs with 20 and 100 machines (121320 and 606600 weights respectively). The lowest observed classiﬁcation error was 2.1% and was reached in one of the 10 runs at the 80th epoch. It must be stressed that the above results were obtained without any optimization of the learning rate, without a learning rate annealing schedule and within a by far shorter training time. All MLPs with 250 hidden units and above, gave results which put them at the top of the list of non-ensemble techniques and they even outperformed Adaboost on C4.5 with 100 machines. Similarly to Figure 14, we also see that the convergence rates to the corresponding asymptotic errors on the test set are quite fast and about the same for all hidden layer sizes. 6. Discussion and Future Research We have presented global and local selective attention techniques that can help neural network training to concentrate on the difﬁcult parts of complex non-linear problems. A new hybrid activation function has also been presented that enables the hidden units to acquire individual receptive ﬁelds 2038 V ERY FAST O NLINE L EARNING OF H IGHLY N ON L INEAR P ROBLEMS in the input space. These individual receptive ﬁelds may be global or local depending on the problem’s local complexities. The success of the new activation function is due to the fact that it depends on two distances. The ﬁrst is the weighted distance of a sample to the hidden unit’s hyperplane. The second is the distance to the hidden unit’s center. We need both distances and neither of them is sufﬁcient. The ﬁrst helps us discriminate and the second helps us localize. The dynamic training set evolution algorithm locates the sub-areas of the input space where the problem resides. The ﬁxed cascaded inhibitory connections and the selective training of a subset of the hidden units on each sample, force the hidden units to get differentiated and attack different subproblems. The individual centering of the hidden units at different points in the input space, adaptively conditions the network to the problem’s local structures and enables each hidden unit to solve a well-conditioned subproblem. In coordination with the above, the hidden units’ limited receptive ﬁelds allow training to follow a divide and conquer paradigm where each hidden unit only solves a local subproblem. The solutions to the subproblems are then combined by the output layer to give a solution to the original problem. In the reported experiments we initialized the hidden weights and biases so that the hidden hyperplanes would cover the whole input space at random positions and orientations. The initial norm of the weights was also adjusted so that the net-input to each hidden unit would fall in the transition between the linear and non-linear range of the activation function. These speciﬁc initializations were necessary for standard backpropagation. On the contrary, we have found that the combined techniques are insensitive to the initial weights and biases, as long as their values are small. We have repeated the experiments with hidden biases set to zero and hidden weight norms set to 10 −3 and the results where equivalent to those reported in Section 5. However, the choice of the best initial learning rate is still problem speciﬁc. An additional and important characteristic of these techniques is that training of the hidden layer does not depend solely on gradient information. Gradient based techniques can only perform local optimization by locating a local minimum of the error function when the system is already at the basin of attraction of that minimum. Stochastic training has a potential of escaping from a shallow basin, but only when the basin is not very wide. Once there, the system cannot escape towards a different basin with a lower minimum. On the contrary, in our model some of the hidden layer’s free parameters (the weights) are trained through gradient descent on the error, whereas some other (the means and standard deviations) are “trained” from the statistical properties of the back-propagated errors. Each hidden unit places its center near the center of mass of the error that it receives and limits its visibility only to the area of the input space where it produces a signiﬁcant error. This model makes the hidden error landscape to constantly change. We conjecture that during training, paths connecting the various error basins are continuously emerging and vanishing. As a result the system can explore much more of the solution space. It is indicative that in all the reported experiments, all trials converged to a solution with more or less the same residual error irrespectively of the initial network state. The combination of the presented techniques enables very fast training on complex classiﬁcation problems with embedded subproblems. By focusing on the problem’s details and efﬁciently utilizing the available resources, they make feasible the solution of very difﬁcult problems (like the one in Figure 1e), provided that the adequate number of hidden units has been used. Although other machine learning techniques can do the same, to our knowledge this is the ﬁrst report that this can be done using ordinary feed forward neural networks and backpropagation, in an online, adaptive 2039 C HARIATIS and memory-less scenario, where the input exemplars are unknown before training and discarded after being used. In the following we discuss some areas that deserve further investigation. 6.1 Generalization and Regression For the classes of problems that were investigated, we had noiseless exemplars and the whole input space at our disposal for training, so there was no danger of overﬁtting. Thus, we did not use any mechanism to assist generalization. This does not mean of course that the network just stored the input output mapping, as a lookup table would do. By putting constraints on the positions and orientations of the hidden unit hyperplanes and by limiting their receptive ﬁelds, we reduced the system’s available degrees of freedom, and the network arranged its resources in a way to achieve the best possible input-output mapping approximation. The experiments on the Letter Recognition Database showed remarkable generalization capabilities. However, when we train on noisy samples or when the number of training samples is small in respect to the size and complexity of the input space, we have the danger of overﬁtting. It remains to be examined how the described techniques are affected by methods that avoid overﬁtting, such as, training with jitter, error regularization, target smoothing and sigmoid gain attenuation (Reed et al., 1995). This consideration also applies to regression problems which usually require smoother approximations. Although early experiments give evidence that the presented techniques can be applied to regression problems as well, we feel that some smoothing technique must be included in the training framework. 6.2 Receptive Fields Limited Orientations As it was noted in Section 3.4, the orientations of the receptive ﬁeld ellipses are limited to have the direction of one of the input axes. This hinders training performance by not allowing the receptive ﬁelds to be adequately shrunk at the direction perpendicular to the hyperplane. In addition, hidden units with sloped hyperplanes are trained on highly correlated input values. These problems are expected to be exaggerated in high dimensional input spaces. We would cure both of these problems simultaneously, if we could individually transform the input for each hidden unit through adaptive whitening, or, if we could present to each hidden unit a rotated view of the input space, such that, one of the axes to be perpendicular to the hyperplane and the rest to be parallel to the hyperplane. Unfortunately, both of the above transformations would require too many additional parameters. An approximation (for 2 dimensional problems) that we are currently investigating upon is the following: For each input vector we compute K vectors rotated around the center of the input space with successive angle increments equal to π/(2K). Our purpose is to obtain uniform rotations between 0 and π/4. Every a few hundred training steps, we reassign to each hidden unit the most appropriate input representation and adjust the affected parameters (weights, means and stdevs). The results are promising. 6.3 Dynamic Cascaded Inhibitory Connections Regarding the ﬁxed cascaded inhibitory connections, it must be examined whether it is better to make the strength of the connections, dynamic. Minus one is OK when the weights are small. How2040 V ERY FAST O NLINE L EARNING OF H IGHLY N ON L INEAR P ROBLEMS ever as the weights get larger, the inhibitory connections get less and less effective to differentiate the hidden units. We can try to make them relative to each hidden unit’s average absolute net-input or alternatively to make them trainable. It has been observed that increasing the strength of these connections enables the hidden units to generate more curved discriminant functions, which is very beneﬁciary for some problems. 6.4 Miscellaneous More experiments need to be done, in order to evaluate the effectiveness of the hybrid activation function on highly non-linear problems in many dimensions. High dimensional input spaces have a multitude of disturbing properties in regard to distance and density metrics, which may affect the hybrid activation in yet unknown ways. Last, we must devise a training mechanism, that will be invariant to the initial learning rate and that will vary automatically the number of hidden units as each problem requires. Acknowledgments I would like to thank all participants in my threads in usenet comp.ai.neural-nets, for their fruitful comments on early presentations of the subjects in this report. Special thanks to Aleks Jakulin for his support and ideas on further research that can make these results even better and to Greg Heath for bringing to my attention the perturbated forms for the calculation of sliding window statistics. I also thank the area editor L´ on Bottou and the anonymous reviewers for their valuable comments e and for helping me to bring this report in shape for publication. Appendix A. Notational Conventions The following list contains the meanings of the symbols that have been used in this report. Symbols with subscripts are used either as scalars or as vectors and matrices when the subscripts are omitted. For example, w ji is a single weight, w j is a weight vector and W is a weight matrix. α – A constant that determines the time scale of the exponential trace of the average training-set error within the dynamic training set evolution algorithm. β – A constant that determines the time scale of the exponential trace of the input means and standard deviations. δ – An accumulator for the efﬁcient implementation of the ﬁxed cascaded inhibitory connections. η – The number of hidden units. µ – The number of input units. f – The hidden units’ squashing function. i – Index enumerating the input units. j – Index enumerating the hidden units. k – Index enumerating the output units. 2041 C HARIATIS a j – The hidden unit’s activation computed from the sample’s weighted distance to the hidden unit’s hyperplane. b j – The hidden unit’s activation attenuation computed from the sample’s distance to the hidden unit’s center. d j – The sample’s distance to the hidden unit’s center. e j – The hidden unit’s accumulated back propagated errors. g j – The hidden unit’s error signal f (n j ) e j . h j – The hidden unit’s activation. m ji – The mean of the values received by hidden unit j from input unit i. n j – The net-input to the hidden unit. q ji – The mean of the squared values received by hidden unit j from input unit i. rk – The error of output unit k. s ji – The standard deviation of the values received by hidden unit j from input unit i. u jk – The weight of the connection from hidden unit j to output unit k. v ji – The variance of the values received by hidden unit j from input unit i. w ji – The weight of the connection from hidden unit j to input unit i. xi – The value of input unit i. z ji – The normalized input value received by hidden unit j from input unit i. It is currently computed as the z-score of the input value. A better alternative would be to compute the vector z j by multiplying the input vector x with a whitening matrix Z j . References C. C. Aggarwal, A. Hinneburg, and D. A. Keim. On the surprising behavior of distance metrics in high dimensional spaces. In J. Van den Bussche and V. Vianu, editors, Proceedings of the 8th International Conference on Database Theory (ICDT), volume 1973 of Lecture Notes in Computer Science, pages 420–434. Springer, 2001. K. Agyepong and R. Kothari. Controlling hidden layer capacity through lateral connections. Neural Computation, 9(6):1381–1402, 1997. S. Ahmad and S. Omohundro. A network for extracting the locations of point clusters using selective attention. In Proceedings of the 12th Annual Conference of the Cognitive Science Society, MIT, 1990. L. B. Almeida, T. Langlois, and J. D. Amaral. On-line step size adaptation. Technical Report INESC RT07/97, INESC/IST, Rua Alves Redol 1000 Lisbon, Portugal, 1997. 2042 V ERY FAST O NLINE L EARNING OF H IGHLY N ON L INEAR P ROBLEMS S. Amari. Natural gradient works efﬁciently in learning. Neural Computation, 10(2):251–276, 1998. P. Bakker. Don’t care margins help backpropagation learn exceptions. In A. Adams and L. Sterling, editors, Proceedings of the 5th Australian Joint Conference on Artiﬁcial Intelligence, pages 139– 144, 1992. P. Bakker. Exception learning by backpropagation: A new error function. In P. Leong and M. Jabri, editors, Proceedings of the 4th Australian Conference on Neural Networks, pages 118–121, 1993. S. Baluja and D. Pomerleau. Using the representation in a neural network’s hidden layer for taskspeciﬁc focus of attention. In IJCAI, pages 133–141, 1995. L. Breiman. Bias, variance, and arcing classiﬁers. Technical Report 460, Statistics Department, University of California, 1996. D. S. Broomhead and D. Lowe. Multivariate functional interpolation and adaptive networks. Complex Systems, 2(3):321–355, 1988. W. Duch, K. Grudzinski, and G. H. F. Diercksen. Minimal distance neural methods. In World Congress of Computational Intelligence, pages 1299–1304, 1998. D. L. Elliott. A better activation function for artiﬁcial neural networks. Technical Report TR 93-8, The Institute for Systems Research, University of Maryland, College Park, MD, 1993. G. W. Flake. Square unit augmented, radially extended, multilayer perceptrons. In G. B. Orr and K. R. M¨ ller, editors, Neural Networks: Tricks of the Trade, volume 1524 of Lecture Notes in u Computer Science, pages 145–163. Springer, 1998. T. C. Fogarty. Technical note: First nearest neighbor classiﬁcation on frey and slate’s letter recognition problem. Machine Learning, 9(4):387–388, 1992. Y. Freund and R. E. Schapire. Experiments with a new boosting algorithm. In ICML, pages 148– 156, 1996. P. W. Frey and D. J. Slate. Letter recognition using holland-style adaptive classiﬁers. Machine Learning, 6:161–182, 1991. S. Geman and D. Geman. Stochastic relaxation, gibbs distributions, and the bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6(6):721–741, 1984. T. Graepel and N. N. Schraudolph. Stable adaptive momentum for rapid online learning in nonlinear systems. In J. R. Dorronsoro, editor, Proceedings of the International Conference on Artiﬁcial Neural Networks (ICANN), volume 2415 of Lecture Notes in Computer Science, pages 450–455. Springer, 2002. M. Harmon and L. Baird. Multi-player residual advantage learning with general function approximation. Technical Report WL-TR-1065, Wright Laboratory, Wright-Patterson Air Force Base, OH 45433-6543, 1996. 2043 C HARIATIS M. Hegland and V. Pestov. Additive models in high dimensions. Computing Research Repository (CoRR), cs/9912020, 1999. S. C. Huang and Y. F. Huang. Learning algorithms for perceptrons using back propagation with selective updates. IEEE Control Systems Magazine, pages 56–61, April 1990. R.A. Jacobs. Increased rates of convergence through learning rate adaptation. Neural Networks, 1: 295–307, 1988. R. Kothari and D. Ensley. Decision boundary and generalization performance of feed-forward networks with gaussian lateral connections. In S. K. Rogers, D. B. Fogel, J. C. Bezdek, and B. Bosacchi, editors, Applications and Science of Computational Intelligence, SPIE Proceedings, volume 3390, pages 314–321, 1998. B. Laheld and J. F. Cardoso. Adaptive source separation with uniform performance. In Proc. EUSIPCO, pages 183–186, September 1994. Y. LeCun, P. Simard, and B. Pearlmutter. Automatic learning rate maximization by on-line estimation of the hessian’s eigenvectors. In S. Hanson, J. Cowan, and L. Giles, editors, Advances in Neural Information Processing Systems, volume 5, pages 156–163. Morgan Kaufmann Publishers, San Mateo, CA, 1993. Y. LeCun, L. Bottou, G. B. Orr, and K.-R. Mueller. Efﬁcient backprop. In G. B. Orr and K.-R. M¨ ller, editors, Neural Networks: Tricks of the Trade, volume 1524 of Lecture Notes in Computer u Science, pages 9–50. Springer, 1998. T. K. Leen and G. B. Orr. Optimal stochastic search and adaptive momentum. In J. D. Cowan, G. Tesauro, and J. Alspector, editors, Proceedings of the 7th NIPS Conference (NIPS), Advances in Neural Information Processing Systems 6, pages 477–484. Morgan Kaufmann, 1993. P. W. Munro. A dual back-propagation scheme for scalar reinforcement learning. In Proceedings of the 9th Annual Conference of the Cognitive Science Society, Seattle, WA, pages 165–176, 1987. N. Murata, K. M¨ ller, A. Ziehe, and S. Amari. Adaptive on-line learning in changing environments. u In M. Mozer, M. I. Jordan, and T. Petsche, editors, Advances in Neural Information Processing Systems 9 (NIPS), pages 599–605. MIT Press, 1996. D. J. Newman, S. Hettich, C.L. Blake, and C.J. Merz. UCI repository of machine learning databases, 1998. G. B. Orr and T. K. Leen. Using curvature information for fast stochastic search. In M. Mozer, M. I. Jordan, and T. Petsche, editors, Advances in Neural Information Processing Systems 9 (NIPS), pages 606–612. MIT Press, 1996. J. L. Phillips and D. C. Noelle. Reinforcement learning of dimensional attention for categorization. In Proceedings of the 26th Annual Meeting of the Cognitive Science Society, 2004. M. Plumbley. A hebbian/anti-hebbian network which optimizes information capacity by orthonormalizing the principal subspace. In Proc. IEE Conf. on Artiﬁcial Neural Networks, Brighton, UK, pages 86–90, 1993. 2044 V ERY FAST O NLINE L EARNING OF H IGHLY N ON L INEAR P ROBLEMS R. Reed, R.J. Marks, and S. Oh. Similarities of error regularization, sigmoid gain scaling, target smoothing, and training with jitter. IEEE Transactions on Neural Networks, 6(3):529–538, 1995. R. E. Schapire. A brief introduction to boosting. In T. Dean, editor, Proceedings of the 16th International Joint Conference on Artiﬁcial Intelligence (IJCAI), pages 1401–1406. Morgan Kaufmann, 1999. R. E. Schapire, Y. Freund, P. Barlett, and W. S. Lee. Boosting the margin: A new explanation for the effectiveness of voting methods. In D. H. Fisher, editor, Proceedings of the 14th International Conference on Machine Learning (ICML), pages 322–330. Morgan Kaufmann, 1997. N. N. Schraudolph. Fast curvature matrix-vector products for second-order gradient descent. Neural Computation, 14(7):1723–1738, 2002. ¨ N. N. Schraudolph. Centering neural network gradient factors. In G. B. Orr and K. R. M uller, editors, Neural Networks: Tricks of the Trade, volume 1524 of Lecture Notes in Computer Science, pages 207–226. Springer, 1998a. N. N. Schraudolph. Accelerated gradient descent by factor-centering decomposition. Technical Report IDSIA-33-98, Istituto Dalle Molle di Studi sull’Intelligenza Artiﬁciale, 1998b. N. N. Schraudolph. Online local gain adaptation for multi-layer perceptrons. Technical Report IDSIA-09-98, Istituto Dalle Molle di Studi sull’Intelligenza Artiﬁciale, Galleria 2, CH-6928 Manno, Switzerland, 1998c. N. N. Schraudolph. Local gain adaptation in stochastic gradient descent. In ICANN, pages 569–574. IEE, London, 1999. H. Schwenk and Y. Bengio. Boosting neural networks. Neural Computation, 12(8):1869–1887, 2000. H. Schwenk and Y. Bengio. Training methods for adaptive boosting of neural networks for character recognition. In M. Jordan, M. Kearns, and S. Solla, editors, Advances in Neural Information Processing Systems 10. MIT Press, Cambridge, MA, 1998. M. W. Spratling and M. H. Johnson. Neural coding strategies and mechanisms of competition. Cognitive Systems Research, 5(2):93–117, 2004. C. Thornton. The howl effect in dynamic-network learning. In Proceedings of the International Conference on Artiﬁcial Neural Networks, pages 211–214, 1992. K. M. Ting and Z. Zheng. Improving the performance of boosting for naive bayesian classiﬁcation. In Paciﬁc-Asia Conference on Knowledge Discovery and Data Mining, pages 296–305, 1999. Y. H. Yu and R. F. Simmons. Descending epsilon in back-propagation: A technique for better generalization. In Proceedings of the International Joint Conference on Neural Networks (IJCNN), volume 3, pages 167–172, 1990. S. Zhong and J. Ghosh. Decision boundary focused neural network classiﬁer. In Intelligent Engineering Systems Through Artiﬁcial Neural Networks (ANNIE). ASME Press, 2000. 2045

same-paper 2 0.93099201 83 jmlr-2007-The On-Line Shortest Path Problem Under Partial Monitoring

Author: András György, Tamás Linder, Gábor Lugosi, György Ottucsák

3 0.91442835 56 jmlr-2007-Multi-Task Learning for Classification with Dirichlet Process Priors

Author: Ya Xue, Xuejun Liao, Lawrence Carin, Balaji Krishnapuram

Abstract: Consider the problem of learning logistic-regression models for multiple classiﬁcation tasks, where the training data set for each task is not drawn from the same statistical distribution. In such a multi-task learning (MTL) scenario, it is necessary to identify groups of similar tasks that should be learned jointly. Relying on a Dirichlet process (DP) based statistical model to learn the extent of similarity between classiﬁcation tasks, we develop computationally efﬁcient algorithms for two different forms of the MTL problem. First, we consider a symmetric multi-task learning (SMTL) situation in which classiﬁers for multiple tasks are learned jointly using a variational Bayesian (VB) algorithm. Second, we consider an asymmetric multi-task learning (AMTL) formulation in which the posterior density function from the SMTL model parameters (from previous tasks) is used as a prior for a new task: this approach has the signiﬁcant advantage of not requiring storage and use of all previous data from prior tasks. The AMTL formulation is solved with a simple Markov Chain Monte Carlo (MCMC) construction. Experimental results on two real life MTL problems indicate that the proposed algorithms: (a) automatically identify subgroups of related tasks whose training data appear to be drawn from similar distributions; and (b) are more accurate than simpler approaches such as single-task learning, pooling of data across all tasks, and simpliﬁed approximations to DP. Keywords: classiﬁcation, hierarchical Bayesian models, Dirichlet process

4 0.58435988 17 jmlr-2007-Building Blocks for Variational Bayesian Learning of Latent Variable Models

Author: Tapani Raiko, Harri Valpola, Markus Harva, Juha Karhunen

Abstract: We introduce standardised building blocks designed to be used with variational Bayesian learning. The blocks include Gaussian variables, summation, multiplication, nonlinearity, and delay. A large variety of latent variable models can be constructed from these blocks, including nonlinear and variance models, which are lacking from most existing variational systems. The introduced blocks are designed to ﬁt together and to yield efﬁcient update rules. Practical implementation of various models is easy thanks to an associated software package which derives the learning formulas automatically once a speciﬁc model structure has been ﬁxed. Variational Bayesian learning provides a cost function which is used both for updating the variables of the model and for optimising the model structure. All the computations can be carried out locally, resulting in linear computational complexity. We present experimental results on several structures, including a new hierarchical nonlinear model for variances and means. The test results demonstrate the good performance and usefulness of the introduced method. Keywords: latent variable models, variational Bayesian learning, graphical models, building blocks, Bayesian modelling, local computation

5 0.55043834 28 jmlr-2007-Dynamic Conditional Random Fields: Factorized Probabilistic Models for Labeling and Segmenting Sequence Data

Author: Charles Sutton, Andrew McCallum, Khashayar Rohanimanesh

Abstract: In sequence modeling, we often wish to represent complex interaction between labels, such as when performing multiple, cascaded labeling tasks on the same sequence, or when long-range dependencies exist. We present dynamic conditional random ﬁelds (DCRFs), a generalization of linear-chain conditional random ﬁelds (CRFs) in which each time slice contains a set of state variables and edges—a distributed state representation as in dynamic Bayesian networks (DBNs)—and parameters are tied across slices. Since exact inference can be intractable in such models, we perform approximate inference using several schedules for belief propagation, including tree-based reparameterization (TRP). On a natural-language chunking task, we show that a DCRF performs better than a series of linear-chain CRFs, achieving comparable performance using only half the training data. In addition to maximum conditional likelihood, we present two alternative approaches for training DCRFs: marginal likelihood training, for when we are primarily interested in predicting only a subset of the variables, and cascaded training, for when we have a distinct data set for each state variable, as in transfer learning. We evaluate marginal training and cascaded training on both synthetic data and real-world text data, ﬁnding that marginal training can improve accuracy when uncertainty exists over the latent variables, and that for transfer learning, a DCRF trained in a cascaded fashion performs better than a linear-chain CRF that predicts the ﬁnal task directly. Keywords: conditional random ﬁelds, graphical models, sequence labeling

6 0.51403004 12 jmlr-2007-Attribute-Efficient and Non-adaptive Learning of Parities and DNF Expressions (Special Topic on the Conference on Learning Theory 2005)

7 0.51046163 74 jmlr-2007-Separating Models of Learning from Correlated and Uncorrelated Data (Special Topic on the Conference on Learning Theory 2005)

8 0.50770855 86 jmlr-2007-Truncating the Loop Series Expansion for Belief Propagation

9 0.50168204 7 jmlr-2007-A Stochastic Algorithm for Feature Selection in Pattern Recognition

10 0.50156152 33 jmlr-2007-Fast Iterative Kernel Principal Component Analysis

11 0.4978309 32 jmlr-2007-Euclidean Embedding of Co-occurrence Data

12 0.49460921 51 jmlr-2007-Loop Corrections for Approximate Inference on Factor Graphs

13 0.48755282 68 jmlr-2007-Preventing Over-Fitting during Model Selection via Bayesian Regularisation of the Hyper-Parameters (Special Topic on Model Selection)

14 0.48663738 14 jmlr-2007-Behavioral Shaping for Geometric Concepts

15 0.47382477 69 jmlr-2007-Proto-value Functions: A Laplacian Framework for Learning Representation and Control in Markov Decision Processes

16 0.47317955 25 jmlr-2007-Covariate Shift Adaptation by Importance Weighted Cross Validation

17 0.47194704 72 jmlr-2007-Relational Dependency Networks

18 0.47074258 19 jmlr-2007-Classification in Networked Data: A Toolkit and a Univariate Case Study

19 0.46682614 29 jmlr-2007-Dynamic Weighted Majority: An Ensemble Method for Drifting Concepts

20 0.46123204 81 jmlr-2007-The Locally Weighted Bag of Words Framework for Document Representation