Name
Abstract | ||
|---|---|---|
The problem of inferring a finite binary sequence w* is an element of (-1, 1)(n) is considered. It is supposed that at epochs t = 1, 2,..., the learner is provided with random half-space data in the form of finite binary sequences u((t)is an element of) {-1, 1}(n) which have positive inner-product with w*. The goal of the learner is to determine the underlying sequence w* in an efficient, on-line fashion from the data {u((t)), t greater than or equal to 1}. In this context, it is shown that the randomized, on-line directed drift algorithm produces a sequence of hypotheses {w((t)) is an element of {-1, 1}(n), t greater than or equal to 1} which converges to w* in finite time with probability 1. It is shown that while the algorithm has a minimal space complexity of 2n bits of scratch memory, it has exponential time complexity with an expected mistake bound of order Ohm(e(0.139n)). Batch incarnations of the algorithm are introduced which allow for massive improvements in running time with a relatively small cost in space (batch size). In particular, using a batch of O(n log n) examples at each update epoch reduces the expected mistake bound of the (batch) algorithm to O(n) (in an asynchronous bit update mode) and O(1) (in a synchronous bit update mode). The problem considered here is related to binary integer programming and to learning in a mathematical model of a neuron. (C) 1999 John Wiley & Sons, Inc. |
Year | DOI | Venue |
|---|---|---|
1999 | 3.0.CO;2-3" target="_self" class="small-link-text"10.1002/(SICI)1098-2418(199907)14:43.0.CO;2-3 | Random Struct. Algorithms |
Keywords | Field | DocType |
binary sequence | Boolean function,Bit-length,Discrete mathematics,Combinatorics,Binary pattern,Computer science,Random binary tree,Binary Independence Model,Binary expression tree,Binary number,Binary constraint | Journal |
Volume | Issue | ISSN |
14 | 4 | 1042-9832 |
Citations | PageRank | References |
0 | 0.34 | 14 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shao C. Fang | 1 | 13 | 4.86 |
| Santosh S. Venkatesh | 2 | 381 | 71.80 |