Было бы действительно интересно увидеть какой-нибудь промышленный пример применения Data Mining, в духе Delloite нужно решить следующую задачу и вот так вот, мы её решили — статья про то-то и то-то.
И еще, а приходится ли вам самим обращаться к компаниям или только они вас находят? Слышал, что они часто сами не совсем понимают, что им может дать Data Mining и решение каких задачи в принципе может им помочь. Интересно было бы услышать про ваш опыт в этом вопросе.
P.S. При прочтении сначала показалось, что Gradient Boosting Machines — это практически Random Forest, оказалось, что нет. Если кому-то вдруг тоже так показалось, то разница объяснена в одной из ссылок:
Заголовок
объяснение
The common ensemble techniques like random forests rely on simple averaging of models in the ensemble. The family of boosting methods is based on a different, constructive strategy of ensemble formation. The main idea of boosting is to add new models to the ensemble sequentially. At each particular iteration, a new weak, base-learner model is trained with respect to the error of the whole ensemble learnt so far. The first prominent boosting techniques were purely algorithm-driven, which made the detailed analysis of their properties and performance rather difficult (Schapire, 2002). This led to a number of speculations as to why these algorithms either outperformed every other method, or on the contrary, were inapplicable due to severe overfitting (Sewell, 2011).
Перед тем как предъявлять кому-то алгоритм решения задачи тысячелетия, АВТОР этого алгоритма должен понять и донести разницу между его алгоритмом и всеми другими попытками решить эту задачу.
В данной статье я указал, что все используемые вами структуры в принципе допускают алгебраическое представление: JSS, CSS, CTS, а значит эта ваша задача показать, что они не попадают под действие соответствующей теоремы о невыразимости.
Статья не претендует на доказательства P ?= NP, в ней просто предлагается алгоритм решения 3-SAT
эквивалентно, данная статья не даёт ответа на вопрос равенства P и NP
Если говорить о статье, в ней приводится именно конструктивное доказательство алгоритма и, кстати, solver от предыдущей работы ни разу не дал ложного решения с практической точки зрения — если формула выполнима он давал выполняемый набор, если нет — набора, соответственно, не выдавалось. И все это за полиномиальное время. 100% верно на всех наших экспериментах (включая формулы из SAT Comp). То есть всегда.
в статье приводится полиномиальный алгоритм решения 3-SAT.
представление этой задачи в виде структур компактных троек, который никто за 40 лет не предлагал, поэтому и нет ссылок — это новая работа, новый подход. И новая NP-полная задача. Искать сходства или различия с существующими подходами и алгоритмами — это не то, чем занимался автор.
т.е. банально никто на самом деле не проверял, а не было ли предложено похожих и/или эквивалентных методов? Просто никто не будет читать работу, которая не объясняет в явной форме, чем она принципиально отличается от других: «это новая работа, новый подход.» — это не ответ. Всех интересует, чем же она действительно отличается, иначе смысл заниматься её изучением? Известно сотни NP полных задач и представлений, которые выросли из определенных задач и приложений. Весь вопрос в чем новизна подхода и представления, зачем и почему?
Статья не претендует на доказательства P ?= NP, в ней просто предлагается алгоритм решения 3-SAT
Если говорить о статье, в ней приводится именно конструктивное доказательство алгоритма и, кстати, solver от предыдущей работы ни разу не дал ложного решения с практической точки зрения — если формула выполнима он давал выполняемый набор, если нет — набора, соответственно, не выдавалось. И все это за полиномиальное время. 100% верно на всех наших экспериментах (включая формулы из SAT Comp). То есть всегда.
Я чего-то не понимаю, но, мне кажется, эти утверждения противоречат друг другу?
In the late 19th century, Leopold Kronecker formulated notions of computability, defining primitive recursive functions. These functions can be calculated by rote computation, but they are not enough to make a universal computer, because the instructions which compute them do not allow for an infinite loop. In the early 20th century, David Hilbert led a program to axiomatize all of mathematics with precise axioms and precise logical rules of deduction which could be performed by a machine. Soon, it became clear that a small set of deduction rules are enough to produce the consequences of any set of axioms. These rules were proved to be enough to produce every theorem by Kurt Gödel in 1930. Gödel's completeness theorem of 1930 implicitly contains a definition of a universal computer, because the logical rules acting on some axioms of arithmetic will eventually prove as a theorem the result of any computation.
The actual notion of computation was isolated soon after, starting with Gödel's incompleteness theorem. This theorem showed that axiom systems were limited when reasoning about the computation which deduces their theorems. Church and Turing independently demonstrated that Hilbert's Entscheidungsproblem (decision problem) was unsolvable,[1] thus identifying the computational core of the incompleteness theorem. This work, along with Gödel's work on general recursive functions, established that there are sets of simple instructions, which, when put together, are able to produce any computation. The work of Gödel showed that the notion of computation is essentially unique.
— формальные определения FOL можно посмотреть здесь
если говорить упрощенное, то даны такие утверждения
1) A и B — эквивалентны
2) A — не может выразить задачу в P
3) B — тьюринг-полон
формальное описание по ссылкам.
Как же так эквивалентные формализмы имеют разную вычислительную сложность?
В ней присутствует абсолютно те же проблемы, что и в предыдущей версии, но это отдельная тема для обсуждения (постараюсь детально покрыть это в следующий раз). Планирую составить небольшой список здравых вещей, которые должна покрывать статья, чтобы её всерьёз начали рассматривать — это всё довольно известные вещи, никакой магии.
Если в кратце, то всегда есть random instances — причем известно, как генерировать случайные «сложные» примеры (это опишу в следующий раз в части «зависимость сложности от числа переменных»), всегда есть набор сложных комбинаторных задач в духе задач на графы — клика с весами, случайные графы и что-нибудь в духе графа Petersen'а c задачей найти какой-нибудь путь, задачи планирования и расписаний популярны. Как правило идет отдельный benchmark с индустриальными задачами — их даёт какой-нибудь Boeing или Microsoft (это для примера), отдельный набор с невыполнимыми задачами — проверить насколько быстро solver'ы определяют, что формула UNSAT.
Авторы делают невероятно самоуверенные утверждения: «Это бесконечный источник природной энергии для всего человечества»
Как написано выше, это один из индикаторов того, что мы должны очень внимательно проверить работу, которая заявляет, что она перевернет весь мир энергетики. Всего навсего к этому очень серьёзному утверждению, хочется получить солидное доказательство.
Что это значит? Это бесконечный источник природной энергии для всего человечества. Вернее источник энергии уже есть — это Солнце. Ведь если замостить солнечными батареями 1000 кв. километров в пустыне, то этой энергии хватит на потребление для всего мира! Но пока это нельзя использовать, потому что невозможно передать эту энергию в любую точку мира. Наша разработка позволяет это сделать!
О, вы на 100% поняли мою мысль — именно это я и имел ввиду.
С одной стороны нам нужны описания Хабов с какими-то специфичными правилами, с другой стороны соблюдение этих правил должно ложиться на сообщество. Возможно, что стоит обратиться к опыту reddit и\или Википедии — у специализированных reddit'ов есть выбранные модераторы (например, по аналогии я бы проголосовал за Zelenyikot в разделе космонавтика — люди доказавшие свою компетентность в рамках Хабра), а Вики требует размещать оригинальные исследования, только если соответствующие публикации в нужном количестве.
Но тут очень сложно заранее выбрать баланс и адекватный уровень, именно поэтому, мне показалось правильным вынести это на обсуждение.
— Результат своей работы я обсуждал на ряде межокружных конференций и среди профессионалов. Результаты были представлены в Институте математики и механики УрО РАН и в журнале «Автоматика и механика», выпускаемом Российской Академией Наук, — рассказал «Хорошим новостям» доктор физико-математических наук Анатолий Панюков. – Чем дольше профессионалы не могут найти опровержения, тем результат считается более правильным.
Тут сразу возникают вопросы: почему задача тысячелетия опубликована в журнале «Автоматика и механика»? Это же не профильный журнал, почему не в International Symposium on Fundamentals of Computation Theory? Почему не на конференции в SAT?
И потом решение будет действительным, если его признают профессионалы, а не если они не смогут найти опровержение.
И самое главное, если P = NP, рушится вся современная криптография и SAT имеет полиномиальное решение, где прототип? Как только будет прототип, который не будет иметь экспоненциального поведения в асимпотике, его решение тут же получит мировую славу.
Было бы здорово, если вы выложили лекции, задания, слайды в сеть, и конечно, на пятёрку с плюсом был бы вариант с онлайн обучением (в духе edx, coursera, udacity) т.е. с заочкой в какой-то форме.
И маленький хинт — список курсов, которые могут быть полезны студентам и\или вам, чтобы сравнить материал\подходы:
И еще, а приходится ли вам самим обращаться к компаниям или только они вас находят? Слышал, что они часто сами не совсем понимают, что им может дать Data Mining и решение каких задачи в принципе может им помочь. Интересно было бы услышать про ваш опыт в этом вопросе.
P.S. При прочтении сначала показалось, что Gradient Boosting Machines — это практически Random Forest, оказалось, что нет. Если кому-то вдруг тоже так показалось, то разница объяснена в одной из ссылок:
The common ensemble techniques like random forests rely on simple averaging of models in the ensemble. The family of boosting methods is based on a different, constructive strategy of ensemble formation. The main idea of boosting is to add new models to the ensemble sequentially. At each particular iteration, a new weak, base-learner model is trained with respect to the error of the whole ensemble learnt so far. The first prominent boosting techniques were purely algorithm-driven, which made the detailed analysis of their properties and performance rather difficult (Schapire, 2002). This led to a number of speculations as to why these algorithms either outperformed every other method, or on the contrary, were inapplicable due to severe overfitting (Sewell, 2011).
В данной статье я указал, что все используемые вами структуры в принципе допускают алгебраическое представление: JSS, CSS, CTS, а значит эта ваша задача показать, что они не попадают под действие соответствующей теоремы о невыразимости.
эквивалентно, данная статья не даёт ответа на вопрос равенства P и NP
в статье приводится полиномиальный алгоритм решения 3-SAT.
Верно?
т.е. банально никто на самом деле не проверял, а не было ли предложено похожих и/или эквивалентных методов? Просто никто не будет читать работу, которая не объясняет в явной форме, чем она принципиально отличается от других: «это новая работа, новый подход.» — это не ответ. Всех интересует, чем же она действительно отличается, иначе смысл заниматься её изучением? Известно сотни NP полных задач и представлений, которые выросли из определенных задач и приложений. Весь вопрос в чем новизна подхода и представления, зачем и почему?
Я чего-то не понимаю, но, мне кажется, эти утверждения противоречат друг другу?
на всякий случай, добавил в комментарии информацию о связи тьюринг полноты и слайды по логике первого порядка
In the late 19th century, Leopold Kronecker formulated notions of computability, defining primitive recursive functions. These functions can be calculated by rote computation, but they are not enough to make a universal computer, because the instructions which compute them do not allow for an infinite loop. In the early 20th century, David Hilbert led a program to axiomatize all of mathematics with precise axioms and precise logical rules of deduction which could be performed by a machine. Soon, it became clear that a small set of deduction rules are enough to produce the consequences of any set of axioms. These rules were proved to be enough to produce every theorem by Kurt Gödel in 1930. Gödel's completeness theorem of 1930 implicitly contains a definition of a universal computer, because the logical rules acting on some axioms of arithmetic will eventually prove as a theorem the result of any computation.
The actual notion of computation was isolated soon after, starting with Gödel's incompleteness theorem. This theorem showed that axiom systems were limited when reasoning about the computation which deduces their theorems. Church and Turing independently demonstrated that Hilbert's Entscheidungsproblem (decision problem) was unsolvable,[1] thus identifying the computational core of the incompleteness theorem. This work, along with Gödel's work on general recursive functions, established that there are sets of simple instructions, which, when put together, are able to produce any computation. The work of Gödel showed that the notion of computation is essentially unique.
— формальные определения FOL можно посмотреть здесь
1) A и B — эквивалентны
2) A — не может выразить задачу в P
3) B — тьюринг-полон
формальное описание по ссылкам.
Как же так эквивалентные формализмы имеют разную вычислительную сложность?
В ней присутствует абсолютно те же проблемы, что и в предыдущей версии, но это отдельная тема для обсуждения (постараюсь детально покрыть это в следующий раз). Планирую составить небольшой список здравых вещей, которые должна покрывать статья, чтобы её всерьёз начали рассматривать — это всё довольно известные вещи, никакой магии.
helda.helsinki.fi/bitstream/handle/10138/40026/sc2013_proceedings.pdf?sequence=2
helda.helsinki.fi/handle/10138/40026
Если в кратце, то всегда есть random instances — причем известно, как генерировать случайные «сложные» примеры (это опишу в следующий раз в части «зависимость сложности от числа переменных»), всегда есть набор сложных комбинаторных задач в духе задач на графы — клика с весами, случайные графы и что-нибудь в духе графа Petersen'а c задачей найти какой-нибудь путь, задачи планирования и расписаний популярны. Как правило идет отдельный benchmark с индустриальными задачами — их даёт какой-нибудь Boeing или Microsoft (это для примера), отдельный набор с невыполнимыми задачами — проверить насколько быстро solver'ы определяют, что формула UNSAT.
Сейчас набирает популярность pseudo-boolean instances — Satisfibility Modulo Theories:
вот тут можно об это прочитать
research.microsoft.com/en-us/um/people/leonardo/sbmf09.pdf
Если это интересно, могу расспросить участников\организаторов SAT competition и написать короткий обзор.
Для многих людей Хабр — это ресурс с репутацией, в некоторой степени репутацией сообщества. Мне за державу обидно.
Я не против проекта, я за то, чтобы он был сделан качественно и в соответствии с базовыми стандартами.
Как написано выше, это один из индикаторов того, что мы должны очень внимательно проверить работу, которая заявляет, что она перевернет весь мир энергетики. Всего навсего к этому очень серьёзному утверждению, хочется получить солидное доказательство.
С одной стороны нам нужны описания Хабов с какими-то специфичными правилами, с другой стороны соблюдение этих правил должно ложиться на сообщество. Возможно, что стоит обратиться к опыту reddit и\или Википедии — у специализированных reddit'ов есть выбранные модераторы (например, по аналогии я бы проголосовал за Zelenyikot в разделе космонавтика — люди доказавшие свою компетентность в рамках Хабра), а Вики требует размещать оригинальные исследования, только если соответствующие публикации в нужном количестве.
Но тут очень сложно заранее выбрать баланс и адекватный уровень, именно поэтому, мне показалось правильным вынести это на обсуждение.
Тут сразу возникают вопросы: почему задача тысячелетия опубликована в журнале «Автоматика и механика»? Это же не профильный журнал, почему не в International Symposium on Fundamentals of Computation Theory? Почему не на конференции в SAT?
И потом решение будет действительным, если его признают профессионалы, а не если они не смогут найти опровержение.
И самое главное, если P = NP, рушится вся современная криптография и SAT имеет полиномиальное решение, где прототип? Как только будет прототип, который не будет иметь экспоненциального поведения в асимпотике, его решение тут же получит мировую славу.
И маленький хинт — список курсов, которые могут быть полезны студентам и\или вам, чтобы сравнить материал\подходы:
Introduction to Recommender Systems
www.coursera.org/course/recsys
Learning from Data
work.caltech.edu/telecourse.html
Data Analysis
www.coursera.org/course/dataanalysis
Computing for Data Analysis
www.coursera.org/course/compdata
Introduction to Artificial Intelligence
www.udacity.com/course/cs271