| EPSRC Reference: |
GR/M14937/01 |
| Title: |
PREDICTIVE COMPLEXITY: RECURSION-THEORETIC VARIANTS |
| Principal Investigator: |
Vovk, Professor V |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science |
| Organisation: |
Royal Holloway, Univ of London |
| Scheme: |
Standard Research (Pre-FEC) |
| Starts: |
01 October 1998 |
Ends: |
30 September 2001 |
Value (£): |
50,922
|
| EPSRC Research Topic Classifications: |
| Fundamentals of Computing |
|
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
Kolmogorov complexity of a sequence can be defined as the length of the shortest 'programme' describing this sequence. Another possible interpretation (going back to Solomonoff) of this notion is that Kolmogorov complexity is the loss suffered by the 'universal prediction strategy' when predicting on-line the elements of the sequence under the logarithmic loss function. The most natural tool in defining the later version of Kolmogorov complexity is the Bayesian merging scheme. The Bayesian merging scheme has been generalised by the proposer to the 'Aggregating Algorithm', which is applicable to a wide class of loss functions. (The Aggregating Algorithm becomes the Bayesian merging scheme when applied to the log-loss function). With the Aggregating Algorithm, it becomes possible to generalise the notion of Kolmogorov complexity to a wide class of loss function, etc. In this project we plan to study this general notion, which we call predictive complexity. One of the most important applications of Kolmogorov complexity is to the definition of random sequences, and we expect that predictive complexity will generate other useful notions of randomness.
|
|
Key Findings |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Potential use in non-academic contexts |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Impacts |
|
| Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
| Summary |
|
| Date Materialised |
|
|
|
|
Sectors submitted by the Researcher |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
| Project URL: |
|
| Further Information: |
|
| Organisation Website: |
|