Generalised Entropy and Asymptotic Complexities of Languages Export

@incollection{citeulike:5835410, abstract = {In this paper the concept of asymptotic complexity of languages is introduced. This concept formalises the notion of learnability in a particular environment and generalises Lutz and Fortnow's concepts of predictability and dimension. Then asymptotic complexities in different prediction environments are compared by describing the set of all pairs of asymptotic complexities w.r.t. different environments. A geometric characterisation in terms of generalised entropies is obtained and thus the results of Lutz and Fortnow are generalised.}, author = {Kalnishkan, Yuri and Vovk, Vladimir and Vyugin, Michael}, citeulike-article-id = {5835410}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/978-3-540-72927-3_22}, citeulike-linkout-1 = {http://www.springerlink.com/content/fj7rg53357h424p8}, comment = {Provides a way of geometrically comparing losses for prediction problems (games).}, doi = {10.1007/978-3-540-72927-3_22}, journal = {Learning Theory}, keywords = {complexity, convexity, entropy, game\_theory, online}, pages = {293--307}, posted-at = {2009-09-24 11:08:02}, priority = {4}, title = {Generalised Entropy and Asymptotic Complexities of Languages}, url = {http://dx.doi.org/10.1007/978-3-540-72927-3_22}, year = {2007} }

TY - CHAP ID - citeulike:5835410 L3 - citeulike-article-id:5835410 N2 - In this paper the concept of asymptotic complexity of languages is introduced. This concept formalises the notion of learnability in a particular environment and generalises Lutz and Fortnow’s concepts of predictability and dimension. Then asymptotic complexities in different prediction environments are compared by describing the set of all pairs of asymptotic complexities w.r.t. different environments. A geometric characterisation in terms of generalised entropies is obtained and thus the results of Lutz and Fortnow are generalised. JF - Learning Theory EP - 307 TI - Generalised Entropy and Asymptotic Complexities of Languages SP - 293 KW - complexity KW - convexity KW - entropy KW - game_theory KW - online N1 - Provides a way of geometrically comparing losses for prediction problems (games). AU - Kalnishkan, Yuri AU - Vovk, Vladimir AU - Vyugin, Michael PY - 2007/// UR - http://dx.doi.org/10.1007/978-3-540-72927-3_22 ER -