<p>While I'm still not entirely sure what you're looking for, you might try reading Avrim Blum's talk on <a href="http://www.cs.cmu.edu/~avrim/Talks/lipari00.ps" rel="nofollow">Online Learning and Prediction</a>, and that might help you focus on areas of interest. </p>

CC BY-SA 2.5
2011-02-26T04:46:02.437Z
2011-02-26T04:46:02.437Z
Suresh Venkat
<p>Consider the following online problem:</p>

<blockquote>
  <p>For $\sigma$ and $k$ fixed, given a string of symbols from alphabet
  $[1..\sigma]$, given one by one, guess a set $S$ of $k$ symbols such that the
  next symbol belongs in $S$, in space independent of the length of the past 
  string.</p>
</blockquote>

<p>This problem is similar to online cache management in the sense that failing the guess is a miss, while guessing correctly is a catch. It is much more general than cache management in the sense that symbols can be added to (the cache) $S$ without having generated a miss, just based on correlations previously learned (e.g. $b$ always follows $a$). It presents the same problem of analysis (competitive analysis and the like) than other online problems in the sense that the worst case is intractable while some good performance can be expected on practical instances.</p>

<p>It could have application to caching with pre-fetching. I thought of it while thinking about the dream specs of a diary application on a smart phone (i.e. reduced screen and costly typing), which given the past submissions of the user (went to bed, woke up, ate eggs, took the bus, etc...) must suggest on the screen $k$ activities to be logged next, a menu for others and a field to enter a new one (using the menu is a miss, writing a new one is unavoidable for any solution).  In this case one should consider the space taken by the algorithm: remembering the whole section of previous queries is not an option, only a finite, lossy (ditching outliers) summary of it. One could give additional information to the guesser such as the time of the day, but I do not know how to fit it nicely in the theoretical model.</p>

<p>Was such a problem or a variant already studied? <strong>Under which name</strong>? Using which model (Dorrigiv and Lopez-Ortiz "cooperative" analysis comes to mind)?</p>

CC BY-SA 2.5
2011-02-26T03:48:08.777Z
this is rather broad: one variant of this is a classic online setting. another variant would be online learning from distributional data. So a short answer is YES, it has been extensively studied.
Suresh Venkat
CC BY-SA 2.5
2011-02-26T04:10:28.880Z
I will suggest points I think that would improve your answer, without downvoting: Instead of having an additional space requirement, require the algorithm to be streaming. If the best part of your interest in this question is the mentioned application (diary) , you should include this in the original question. Given this framework, we can use statistical knowledge to solve it easier (e.g. your sleep cycle is more predictable than a random string of symbols). As @Suresh Venkat notes, given your choices, you can find a lot of material on these problems.
chazisop
CC BY-SA 2.5
2011-02-26T04:22:03.633Z
Thanks chazisop. I tried to make the question more specific, in particular adding the space requirement. I don't know how to express formally the time hints. What would be a good set of terms ("online learning" brought too many other things)?
J.y B.y
<ds.algorithms><reference-request><lg.learning><terminology><online-algorithms>
Has this online problem been studied before ? 
J.y B.y
# Has this online problem been studied before ? 

(Asked by: username_0 on 2011-02-26)

Consider the following online problem:

> For $\sigma$ and $k$ fixed, given a string of symbols from alphabet
> $[1..\sigma]$, given one by one, guess a set $S$ of $k$ symbols such that the
> next symbol belongs in $S$, in space independent of the length of the past
> string.

This problem is similar to online cache management in the sense that failing the guess is a miss, while guessing correctly is a catch. It is much more general than cache management in the sense that symbols can be added to (the cache) $S$ without having generated a miss, just based on correlations previously learned (e.g. $b$ always follows $a$). It presents the same problem of analysis (competitive analysis and the like) than other online problems in the sense that the worst case is intractable while some good performance can be expected on practical instances.

It could have application to caching with pre-fetching. I thought of it while thinking about the dream specs of a diary application on a smart phone (i.e. reduced screen and costly typing), which given the past submissions of the user (went to bed, woke up, ate eggs, took the bus, etc...) must suggest on the screen $k$ activities to be logged next, a menu for others and a field to enter a new one (using the menu is a miss, writing a new one is unavoidable for any solution). In this case one should consider the space taken by the algorithm: remembering the whole section of previous queries is not an option, only a finite, lossy (ditching outliers) summary of it. One could give additional information to the guesser such as the time of the day, but I do not know how to fit it nicely in the theoretical model.

Was such a problem or a variant already studied? **Under which name**? Using which model (Dorrigiv and Lopez-Ortiz "cooperative" analysis comes to mind)?

**Tags:** ds.algorithms, reference-request, lg.learning, terminology, online-algorithms

> **Comments:**
> **username_1**: this is rather broad: one variant of this is a classic online setting. another variant would be online learning from distributional data. So a short answer is YES, it has been extensively studied.  
> **username_2**: I will suggest points I think that would improve your answer, without downvoting: Instead of having an additional space requirement, require the algorithm to be streaming. If the best part of your interest in this question is the mentioned application (diary) , you should include this in the original question. Given this framework, we can use statistical knowledge to solve it easier (e.g. your sleep cycle is more predictable than a random string of symbols). As @username_1 notes, given your choices, you can find a lot of material on these problems.  
> **username_0**: Thanks username_2. I tried to make the question more specific, in particular adding the space requirement. I don't know how to express formally the time hints. What would be a good set of terms ("online learning" brought too many other things)?  

---

## 1 answers

### Answer by username_1 on 2011-02-26. Score: 3 | Accepted answer

While I'm still not entirely sure what you're looking for, you might try reading Avrim Blum's talk on [Online Learning and Prediction](http://www.cs.cmu.edu/~avrim/Talks/lipari00.ps), and that might help you focus on areas of interest.


---

