Curse of dimensionality

[antoshka1303]

Сижу учу машинное обучение, помогите понять что такое проклятие размерности?

[JMH]

В Вашем случае, вероятно, подразумевается, что с увеличением числа степеней свободы системы (числа параметров) на $n$ сложность вычислений (выраженная численно) умножается на $n$.

[antoshka1303]

кажется да, не могу найти доходчивую литературу на эту тему

[antoshka1303]

помогите найти доходчивое объяснение с рисунками и формулами, очень срочно надо!!!

[Munin]

JMH в сообщении #596420 писал(а):

В Вашем случае, вероятно, подразумевается, что с увеличением числа степеней свободы системы (числа параметров) на $n$ сложность вычислений (выраженная численно) умножается на $n$.

А не на $N^n$?

[antoshka1303]

Munin в сообщении #596635 писал(а):

JMH в сообщении #596420 писал(а):

В Вашем случае, вероятно, подразумевается, что с увеличением числа степеней свободы системы (числа параметров) на $n$ сложность вычислений (выраженная численно) умножается на $n$.

А не на $N^n$?

Хорошо, пусть так.
Не могли бы вы помочь мне найти доходчивое объяснение с рисунками и формулами, очень срочно надо!!! заранее спасибо

[JMH]

Munin в сообщении #596635 писал(а):

JMH в сообщении #596420 писал(а):

В Вашем случае, вероятно, подразумевается, что с увеличением числа степеней свободы системы (числа параметров) на $n$ сложность вычислений (выраженная численно) умножается на $n$.

А не на $N^n$?

Да, конечно, ведь имеется ввиду $O$-нотация.

-- Ср июл 18, 2012 09:52:11 --

Касательно литературы:
Michael Sipser, Introduction to the Theory of Computation
Dexter Kozen, Automata and Computability

[antoshka1303]

JMH в сообщении #596719 писал(а):

Munin в сообщении #596635 писал(а):

JMH в сообщении #596420 писал(а):

В Вашем случае, вероятно, подразумевается, что с увеличением числа степеней свободы системы (числа параметров) на $n$ сложность вычислений (выраженная численно) умножается на $n$.

А не на $N^n$?

Да, конечно, ведь имеется ввиду $O$-нотация.

-- Ср июл 18, 2012 09:52:11 --

Касательно литературы:
Michael Sipser, Introduction to the Theory of Computation
Dexter Kozen, Automata and Computability

Спасибо, пойду в библиотеку

[JMH]

antoshka1303 в сообщении #596729 писал(а):

Спасибо, пойду в библиотеку

Поищите online

[antoshka1303]

JMH в сообщении #596731 писал(а):

antoshka1303 в сообщении #596729 писал(а):

Спасибо, пойду в библиотеку

Поищите online

В Michael Sipser, Introduction to the Theory of Computation ничего не нашел, чтобы с формулами и рисунками было пояснение

[_hum_]

Судя по статье в англоязычной Википедии, под Curse of dimensionality в машинном обучении понимают несколько иное, чем в теории вычислительной сложности алгоритмов. Как-то там все завязывается на специфику геометрии многомерных пространств (соотношения объемов и проч.). Так что, возможно, указанные книги не совсем будут в тему (если они чисто по вычислительной сложности).

[JMH]

Приношу свои извинения - я, собственно, не имел ввиду, что в этих книгах объясняется сам термин. Там объясняется, как оценивается вычислительная сложность алгоритмов, а, стало быть, как учитывать число степеней свободы системы в рассчёте таковой.

Если _hum_ прав, то те книги Вам не подойдут и, собственном, всё, что я до сих пор говорил о предмете беседы неприменимо.