Это называется «нейроны в точках данных» и очень часто применяется для инициализации самых разных нейронных сетей. Один из основных подходов, собственно. Хорошая идея, короче, но её придумали до вас.
Кстати, заменять им обучение полностью нет смысла, именно потому, что забывание в общем случае функционально оправдано (и часто даже вводится принудительно). Особенно для столь любимых вами динамических сетей.
Действительно, теорема Кавера утверждает, что линейно неразделимые множества могут быть линейно разделимы в пространстве повышенной размерности. Она не утверждает, как вы, «в пространстве на одну размерность выше», это может быть и 5, и 25 размерностей вверх, и обычно ближе к 25, чем к 5. Даже с нашим астрономическим количеством нейронов, их едва ли хватит, для использования этой теоремы «в лоб» во всём пространстве естественных стимулов.
Второе. Откуда уверенность, что два и более стимула «учителей» могут быть непротиворечиво обобщены? Учителя могут прямо противоречить друг другу, и не потому, что кто-то из них неправ, а именно потому, что повышение размерности рождает неопределённость (координаты в дополнительных размерностях изначально не определены). Вы пишете «это значит, ученик выбрал неправильный базис», но в общем случае для корректного обобщения ученику в качестве базиса понадобится суперпозиция базисов всех учителей. Это опять введение дополнительных размерностей (по второму кругу), количество которых, подозреваю, уже приближается к абсурдному «каждому стимулу по личному измерению». Это, конечно, снимет противоречие, однако никакого практического смысла не имеет.
В итоге, мне кажется, вы пытаетесь свести к формальной системе то, что для этого явно не предназначено. Естественный интеллект совершенно спокойно переносит внутреннюю несовместимость собственных и чужих установок. Как писал Хофштадтер «Мы не что иное, как ходячие мешки противоречий, и наша целостность зависит от того, что в каждый момент времени мы способны сконцентрироваться только на чём-то одном». Избавляться от этого, накручивая размерности, не получится и незачем.
Вы описали не обучение с учителем, а обучение с подкреплением (reinforcement learning).
Использовать в качестве «обучающего сигнала» всю партию — безумие, конечно. На вход должно подаваться состояние мира в данный момент, плюс номер хода для привязки ко времени.
Да, и на случай, если вы подумали, что я целенаправленно злобно критикую ваши статьи, заверяю, что каждую из них плюсанул =) Потому что методы методами, но успешно и наглядно решённую задачу всегда приятно видеть.
Однако, о хорошем говорить скучно =)
Такие очевидно линейно разделимые выборки логичней делить чем-то линейным, специально для этого придуманным. Персептроном, например, логистической регрессией или, для эстетов, support vector machine.
Ну а про Густафсона-Кесселя для эллипсов мы, кажется, говорили уже.
Вы не замечали, что люди меняются? Тот, кто писал ерунду вчера или год назад, завтра или через год вполне может опубликовать нетленку. Точнее, уже не может, потому что его «очистили». Но вот если бы мог!..
Я пытался разобраться в истории D-Wave, и пришёл к выводу (который сами D-Wave вскоре подтвердили), что DW-1 — это не квантовый компьютер, а «квантовое вычислительное устройство», такая специальная аналоговая машина. Она неуниверсальна как машина Тьюринга и поэтому не может называться компьютером, реализует ровно один алгоритм (квантовый алгоритм оптимизации отжигом), чего, тем не менее, достаточно для многих очень интересных применений и решения широкого круга задач (методами оптимизации решается всё, для чего можно построить Лагранжиан — то есть масса задач физики, химии, управления, численных методов и т.д. и т.п. Нейросети, например, можно делать =) ).
Кстати, ведущий инженер D-Wave — Павел Бунык — тоже москвич, из МГУ.
Да, если подменить метрику, это будет другой алгоритм и поэтому называться он будет иначе. Только метрика подменяется не в алгоритме, а в его целевой функции. Если вы подменяете метрику в алгоритме, вы просто искажаете входные данные. Впрочем, мы, кажется, пошли по кругу.
Интересный взгляд на k-means, я подумаю над этим. Я обычно описываю этот алгоритм как решение задачи гравитации множества тел, то есть поиск центра массы =) Также популярно описание как нейронной сети, что я уже упоминал. Впрочем, какой бы ни была метафора, математика не меняется. И эта математика занимается оптимизацией целевой функции — это не требующее доказательств утверждение, потому что вообще _любой_ итеративный алгоритм оптимизирует некоторую целевую функцию, которую можно из него восстановить интегрированием, даже если явно она не задумывалась. Так вот, я уверяю вас, что в функции, которую оптимизирует K-Means, метрика задана явно и это евклидова метрика.
Я хотел бы сослаться на что-то, но у меня литература в основном по нечёткой кластеризации, и даже в учебниках я даже что-то не могу найти полную выкладку KM, видимо, за давностью лет (для Fuzzy K-Means, вывод, впрочем, почти аналогичный). Однако у Вунша, например, таблица методов кластеризации расписана именно по метрикам, и напротив евклидовой стоит КМ:
В замечательной статье Fundmentals of Fuzzy Clustering тоже, насколько я помню, несколько раз упоминается, что многие алгоритмы полностью порождены метрикой, в частности КМ — евклидовой (ну например в параграфе 1.3: «In the previous section, we considered the case where the distance between cluster centers and data points
is computed using the Euclidean distance». Загляните, хорошая статья). Жаль, что не нашёл формул, если так и не найду, на выходных выведу сам — но эти свидетельства, по крайней мере, в мою пользу.
Нет, синтез — это процедурная операция, достаточно задать правила и запустить процесс. Симуляция же, не говоря уж о воссоздании, требует полностью описать систему, что значительно сложнее и вообще слабопредставимо на данный момент
Забавно, что вспомнили именно про кошек. У ИИ-специалистов есть страшная байка на ночь, что мало есть задач сложнее, чем научить машину отличать кошек и собак. В общем виде задача вообще, похоже, нерешаемая.
Что же до общего посыла, то у меня есть любимое определение ИИ: «Искусственный интеллект — это то, что ещё не сделано». В том смысле, что машины уже вполне, даже более, чем успешно справляются со многими задачами, доселе считавшимися исключительно интеллектуальными. Однако парадокс в том, что как только машины начинают с ними справляться, задача тут же перестаёт быть интеллектуальной. Отчасти, кстати, это присуще и биологическим открытиям: скажем, орудия тут же перестали признаком разума, когда обнаружилось, что ими пользуется масса животных, хотя до этого были столпом понятия разумности. Видимо, людям важнее сохранить свой уникальный статус разумных существ, чем действительно понять, что такое интеллект.
Впрочем, я тоже уверен, что любая система сопостовимой с мозгом сложности, получая сопоставимое количество информации на протяжении столь же долгого срока продемонстрирует нам многие черты «сильного ИИ». Это, вероятно, сильно изменит нашу жизнь, но в общественном сознании, боюсь, мало что изменит — просто концепция «сильного ИИ» опять поменяется, и он опять отодвинется в светлое будущее. Думаю, машины раньше получат равные юридические права с людьми, чем люди действительно поверят, что они равны интеллектуально.
Да, главным преимуществом алгоритма ГК на практике считается способность строить несферические кластеры. Но взаимозаменяемость пространств тоже можно проверить.
Проблема с метрикой именно в том, что функция стоимости считается от текущей метрики, а алгоритм оптимизирует функцию от евклидовой метрики. Это разные функции. В случае метрики Махаланобиса — похожие, но это значит, что и результаты будут «похожие» на оптимальные.
1) Работоспособна — это значит сходимость доказуема. Оптимум, найденный k-means с подменённой метрикой, будет действительно оптимумом только если ему соответствует оптимум в евклидовой метрике. Попробуйте взять какую-нибудь экзотическую метрику, не коррелирующую с расстоянием в вашем пространстве признаков — например, largest common subset (его длину, точнее) для тех же строк — и получите результат разбиения на уровне случайного, а то и хуже.
2) K-Means это и есть решение задачи оптимизации, полностью эквивалентное градиентному спуску, за исключением того, что K-Means — это аналитическое решение системы уравнений частных производных, а градиентный спуск — приближеннное решение методами нелинейного программирования _той же самой_ системы уравнений.
3) Ваше описание — это просто смена нотации, с тем же успехом можно описать k-means как нейросеть, например (собственная, нейронная сеть Кохонена и является k-means в нейросетевой нотации, хоть и придумана совсем из других соображений). Это ни в коей мере не отменяет того, что k-means безусловно порождается функцией стоимости, и мы можем вместе это проверить, повторив вывод алгоритма — это всегда полезно для понимания.
4) Мне немного сложно понять ваши выводы, т.к. у нас явно очень разная терминологическая база. Для меня такого понятия как «точность» в кластеризации нет, потому что нет эталонного разбиения, кроме того, k-means никак не подвержен тому, что я знаю под названием «проклятие размерности», потому что число его параметров растёт линейно с размерностью пространства признаков (а не экспоненциально, как у традиционнных нейросетей, например).
Однако точность k-means несомненно зависит от инициализации (кстати, оптимально инициализировать матрицу разбиения, а не центроиды) и точности рассчёта центроида или его
заменителя. Кстати, поинтересуйтесь алгоритмом Густафсона-Кесселя, это обобщённый k-means для всех «околоевклидовых» метрик (довольно остроумная штука: оказывается, перед d^2 в целевой функции есть матрица, которая в случае k-means единичная. Изменения в этой матрице приводят к искажению пространства, и доказано, что можно найти оптимальное искажение для каждого центроида. Вы можете проверить, что разница между матрицами, оптимизированными в евклидовой метрике и в метрике Махаланобиса при одинаковой инициализации, будет ковариационной матрицей между этими метриками, если таковая существует).
Использовать в k-means обобщённую метрику — первейший соблазн, но это не совсем правильно. Метрика — это не просто цифра, это в первую очередь функция, и эта функция является неотъемлемой частью минимизируемой функции стоимости. Если вы меняете метрику, вы меняете целевую функцию (функцию стоимости), а значит должны заново решить задачу минимизации этой функции. Ничего фантастического — построить лагранжиан и решить систему уравнений частных производных, но всё же до сих пор выходят статьи с адаптациями идеи k-means под всякие метрики. По сути, алгоритм целиком порождается именно метрикой, и k-means порождён именно квадратом эвклидова расстояния. Любая же подмена метрики «в лоб», то есть просто подмена циферки, возвращаемой функцией dist, работоспособна ровно в той степени, в которой новая метрика коррелирует с эвклидовой.
Было бы очень интересно узнать реальную точность — найти для сравнения тот же компас или пульсометр вроде бы не должно быть проблемой, да и счётчик Гейгера требует совсем немного усилий. Было бы целое исследование.
Помнится, ещё под WM6 меня поразила программка-осциллограф, снимающая показания через гнездо наушников (наушники, естественно, надо было раскурочить и превратить в щупы). Результаты при этом были более чем на уровне. Интересно, есть ли на Андроиде что-то столь же варварское?)
Прогноз типа «завтра будет то же, что и вчера» хорош как базовая модель, но совсем несложно придумать что-то более эффективное. А ещё лучше найти: ru.wikipedia.org/wiki/Категория: Анализ_временных_рядов
Молодцы. Курс верный. Например, в Wolfram Mathematica над наполнением базы фактов для тех же целей работает около 200 человек уже почти 10 лет =) Желаю обогнать!
Кстати, заменять им обучение полностью нет смысла, именно потому, что забывание в общем случае функционально оправдано (и часто даже вводится принудительно). Особенно для столь любимых вами динамических сетей.
Второе. Откуда уверенность, что два и более стимула «учителей» могут быть непротиворечиво обобщены? Учителя могут прямо противоречить друг другу, и не потому, что кто-то из них неправ, а именно потому, что повышение размерности рождает неопределённость (координаты в дополнительных размерностях изначально не определены). Вы пишете «это значит, ученик выбрал неправильный базис», но в общем случае для корректного обобщения ученику в качестве базиса понадобится суперпозиция базисов всех учителей. Это опять введение дополнительных размерностей (по второму кругу), количество которых, подозреваю, уже приближается к абсурдному «каждому стимулу по личному измерению». Это, конечно, снимет противоречие, однако никакого практического смысла не имеет.
В итоге, мне кажется, вы пытаетесь свести к формальной системе то, что для этого явно не предназначено. Естественный интеллект совершенно спокойно переносит внутреннюю несовместимость собственных и чужих установок. Как писал Хофштадтер «Мы не что иное, как ходячие мешки противоречий, и наша целостность зависит от того, что в каждый момент времени мы способны сконцентрироваться только на чём-то одном». Избавляться от этого, накручивая размерности, не получится и незачем.
Использовать в качестве «обучающего сигнала» всю партию — безумие, конечно. На вход должно подаваться состояние мира в данный момент, плюс номер хода для привязки ко времени.
Однако, о хорошем говорить скучно =)
Ну а про Густафсона-Кесселя для эллипсов мы, кажется, говорили уже.
Кстати, ведущий инженер D-Wave — Павел Бунык — тоже москвич, из МГУ.
Я хотел бы сослаться на что-то, но у меня литература в основном по нечёткой кластеризации, и даже в учебниках я даже что-то не могу найти полную выкладку KM, видимо, за давностью лет (для Fuzzy K-Means, вывод, впрочем, почти аналогичный). Однако у Вунша, например, таблица методов кластеризации расписана именно по метрикам, и напротив евклидовой стоит КМ:
В замечательной статье Fundmentals of Fuzzy Clustering тоже, насколько я помню, несколько раз упоминается, что многие алгоритмы полностью порождены метрикой, в частности КМ — евклидовой (ну например в параграфе 1.3: «In the previous section, we considered the case where the distance between cluster centers and data points
is computed using the Euclidean distance». Загляните, хорошая статья). Жаль, что не нашёл формул, если так и не найду, на выходных выведу сам — но эти свидетельства, по крайней мере, в мою пользу.
Что же до общего посыла, то у меня есть любимое определение ИИ: «Искусственный интеллект — это то, что ещё не сделано». В том смысле, что машины уже вполне, даже более, чем успешно справляются со многими задачами, доселе считавшимися исключительно интеллектуальными. Однако парадокс в том, что как только машины начинают с ними справляться, задача тут же перестаёт быть интеллектуальной. Отчасти, кстати, это присуще и биологическим открытиям: скажем, орудия тут же перестали признаком разума, когда обнаружилось, что ими пользуется масса животных, хотя до этого были столпом понятия разумности. Видимо, людям важнее сохранить свой уникальный статус разумных существ, чем действительно понять, что такое интеллект.
Впрочем, я тоже уверен, что любая система сопостовимой с мозгом сложности, получая сопоставимое количество информации на протяжении столь же долгого срока продемонстрирует нам многие черты «сильного ИИ». Это, вероятно, сильно изменит нашу жизнь, но в общественном сознании, боюсь, мало что изменит — просто концепция «сильного ИИ» опять поменяется, и он опять отодвинется в светлое будущее. Думаю, машины раньше получат равные юридические права с людьми, чем люди действительно поверят, что они равны интеллектуально.
Проблема с метрикой именно в том, что функция стоимости считается от текущей метрики, а алгоритм оптимизирует функцию от евклидовой метрики. Это разные функции. В случае метрики Махаланобиса — похожие, но это значит, что и результаты будут «похожие» на оптимальные.
2) K-Means это и есть решение задачи оптимизации, полностью эквивалентное градиентному спуску, за исключением того, что K-Means — это аналитическое решение системы уравнений частных производных, а градиентный спуск — приближеннное решение методами нелинейного программирования _той же самой_ системы уравнений.
3) Ваше описание — это просто смена нотации, с тем же успехом можно описать k-means как нейросеть, например (собственная, нейронная сеть Кохонена и является k-means в нейросетевой нотации, хоть и придумана совсем из других соображений). Это ни в коей мере не отменяет того, что k-means безусловно порождается функцией стоимости, и мы можем вместе это проверить, повторив вывод алгоритма — это всегда полезно для понимания.
4) Мне немного сложно понять ваши выводы, т.к. у нас явно очень разная терминологическая база. Для меня такого понятия как «точность» в кластеризации нет, потому что нет эталонного разбиения, кроме того, k-means никак не подвержен тому, что я знаю под названием «проклятие размерности», потому что число его параметров растёт линейно с размерностью пространства признаков (а не экспоненциально, как у традиционнных нейросетей, например).
Однако точность k-means несомненно зависит от инициализации (кстати, оптимально инициализировать матрицу разбиения, а не центроиды) и точности рассчёта центроида или его
заменителя. Кстати, поинтересуйтесь алгоритмом Густафсона-Кесселя, это обобщённый k-means для всех «околоевклидовых» метрик (довольно остроумная штука: оказывается, перед d^2 в целевой функции есть матрица, которая в случае k-means единичная. Изменения в этой матрице приводят к искажению пространства, и доказано, что можно найти оптимальное искажение для каждого центроида. Вы можете проверить, что разница между матрицами, оптимизированными в евклидовой метрике и в метрике Махаланобиса при одинаковой инициализации, будет ковариационной матрицей между этими метриками, если таковая существует).
Помнится, ещё под WM6 меня поразила программка-осциллограф, снимающая показания через гнездо наушников (наушники, естественно, надо было раскурочить и превратить в щупы). Результаты при этом были более чем на уровне. Интересно, есть ли на Андроиде что-то столь же варварское?)