Здравствуйте, denisko, Вы писали:
PD>>У меня нет времени изучать все и всяческие методы. Объясни на пальцах, по каким критериям будешь обучать. D>Нагенерирую очень много случайных ядер фильтров (картинок из +1 и -1).
Ты умеешь генерировать изображения кошек и собак ? Объясни как. А без этого ты сколь угодно большое число изображений не получишь.
>Каждый из них классификатор -- у кого-то свертка с силуэтами/мордами с какой то подгруппой кошек будет отличаться от какой-то подргуппы собак
Еще раз — что за критерий. Как выделять-то будешь ? У тебя есть хоть какие-то соображения, как найти на изображении уши, лапы , хвост или морду ? Имей в виду, там будут самые разные кошки и собаки в фас, профидь и как угодно.
>AdaBoost показывает, что если у меня куча классификаторов, то я могу разделить классы из обучающей выборки с любой заданной точностью хоть 99,999999999999999999999999%. Далее жульничаю -- беру ВСЕ имеющиеся фото кошек (производительность то бесконечная) и ВСЕ фото собак.
Именно что жульничаешь. Чтобы ребенку научиться, ему совсем не нужны миллионы изображений. Он не будет классифицировать Он как-то иначе это делает. Но это тоже к слову. Главное — выше.
On 30/04/2010 19:53, barn_czn wrote:
> Конкретизирую. Речь идет о машине Тьюринга с бесконечной лентой, > временем передвижения по ленте = 0, временем записи и чтения на ленту = 0.
Если на ленте счётное число ячеек, то, думаю, всё и так ясно
Интересно пофантазировать насчёт несчётной ленты...
Posted via RSDN NNTP Server 2.1 beta
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Здравствуйте, nikov, Вы писали:
N>Пример с Busy beaver показывает, что это не совсем так. А вот наличие неограниченных вычислительных ресурсов + знание элементов этой последовательности действительно позволило бы автоматически решать любую строго сформулированную задачу. А пока что всех достижений математики достаточно, чтобы вычислить только 5 ее первых членов. И мы даже не знаем, способен ли в принципе человеческий разум продвинуться сколь угодно далеко в вычислении членов в этой последовательности, не говоря уже о том, чтобы научить этому машину.
Ну и не очень то и нужны 5+ члены этой последовательности.
На C# за пару минут тоже можно написать генерацию последовательности, так что достижений математики никогда не хватит для определения того что она на консоль выведет. Но на бесконечном компьютере это бы удалось. Но ничего интересного там бы все равно не было.
(можно было бы и покороче, но совсем тогда будет нечитаблельно)
static BigInteger GF(BigInteger n, Func<BigInteger, BigInteger> func)
{
var temp = n;
for (BigInteger Num = 1; Num < n; Num++)
temp = func(temp);
return temp;
}
static void Main()
{
Func<BigInteger, BigInteger> F0 = (_ => BigInteger.Pow(_, 2));
Func<BigInteger, BigInteger> F1 = _ => GF(_, F0);
Func<BigInteger, BigInteger> F2 = _ => GF(_, F1);
Func<BigInteger, BigInteger> F3 = _ => GF(_, F2);
var res = F3(5);
Console.WriteLine(res.ToByteArray().Take(10).ToArray());
}
Здравствуйте, barn_czn, Вы писали:
N>>Вот другая задача (так называемая mortal matrix problem): написать алгоритм, который принимает натуральные числа M, N и массив, состоящий из M целочисленных квадратных матриц N x N. Для любых входных данных он должен определить, существует ли произведение этих матриц в каком-либо порядке (возможно, с повторениями), дающее нулевую матрицу. Эта задача также undecidable.
_>Ну да, перебор бесконечного кол-ва вариантов может никогда не закончится.
Ну, в принципе, мы могли бы надеяться, что какой-то умный алгоритм может отсечь все бесперспективные ветки, и свести любой перебор к конечному, но оказывается, что это невозможно.
Ещё один практически интересный пример — знаменитая десятая проблема Гильберта: написать алгоритм, который получив на вход любое диофантово уравнение (то есть обычное полиномиальное уравнение с несколькими переменными, принимающими только целые значения), определит, имеет ли оно хотя бы одно решение. Также undecidable, как показал Ю. В. Матиясевич в 1970 году. А вот, скажем, алгоритмическая разрешимость аналогов 10-й проблемы Гильберта для уравнений 3 степени и для уравнений в рациональных числах до сих пор остается открытой.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, barn_czn, Вы писали:
PD>>>Просто точной химической теории не существует. Все расчетные методы дают плюс-минус...
_>>А зачем нам вообще химия? Мы физику будем использовать. Точность уравнений Шредингера в масштабе атомов (да даже наверно ядер) еще никто под сомнение не поставил.
PD>Постановку задачи — уравнения Шредингера — никто под сомнение не ставил. Точного решения этой задачи для систем сложнее атом водорода, не имеется.
Не имеется аналитического решения, в виде формул. Но оно нам и не нужно, у нас есть супер-вычислитель, который может достичь любой наперед заданной точности. Уравнения квантовой физики — это дифф. уравнения второго порядка, посчитать — никаких проблем.
_>>Я так думаю что химия как наука вообще утратила бы значение имей мы действительно супер-мега-проц. Потому что базовые законы природы формулируются в физике. Вычислять сложные модели просто не на чем.
PD>Увы, не так. Нет точной теории. Все, что ты слышал про атомы (орбитали, валентные связи и т.д.) — не более чем приближения.
Квантовая механика наша теория, самая точная на сегодняшний день. Я даже не знаю что такое орбитали и валентные связи. Все что мне надо есть в таблице Менделеева.
Все законы химии (ну или почти все) могли бы выть обнаружены в виртуальной (моделируемой) хим. лаборатории, если бы мы сразу знали квантовую теорию и имели супер-мега-проц.
Знания химии нам столько же полезны как полезно знание деления столбиком в отсутствии калькулятора. Кто из вас последний раз делил столбиком? Или умножал? Да никто, сразу открываем калькулятор и нет проблем.
Ну нет просто еще таких калькуляторов чтоб не ставя эксперимент предсказать свойства материалов и прочие закономерности.
Зато появились приближенные методы (деление столбиком).. дайте срок, появится и калькулятор ).
N>>Как я понимаю, речь изначально была о машине, которую можно разогнать до любой скорости, так что любой останавливающийся алгоритм можно выполнить настолько быстро, что не успеешь глазом моргнуть (или даже ещё быстрее), задав подходящую скорость. Речь не идет о машине, которая может выполнить бесконечное (а тем более, несчётное) количество операций за конечное время. Верно?
_>Конкретизирую. Речь идет о машине Тьюринга с бесконечной лентой, временем передвижения по ленте = 0, временем записи и чтения на ленту = 0.
Я не понимаю, как так может быть. Ведь тогда два (и более) последовательных состояния машины будут существовать в один момент, а ее архитектура не предусматривает одновременного хранения нескольких состояний.
Здравствуйте, Silver_s, Вы писали:
S_>На C# за пару минут тоже можно написать генерацию последовательности, так что достижений математики никогда не хватит для определения того что она на консоль выведет.
Почему ты в этом уверен? Это ведь просто вычисление очень большого числа по простому алгоритму (я правильно понял?). Почему нельзя надеяться вычислить его несколько старших разрядов быстрым обходным путем?
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, denisko, Вы писали:
PD>>>У меня нет времени изучать все и всяческие методы. Объясни на пальцах, по каким критериям будешь обучать. D>>Нагенерирую очень много случайных ядер фильтров (картинок из +1 и -1).
PD>Ты умеешь генерировать изображения кошек и собак ? Объясни как. А без этого ты сколь угодно большое число изображений не получишь.
Да не проблема. Во первых не нужно думать что генерированые изображения должны быть высокого качества реалистичности. Мы не решаем задачу определения всех параметров кошки по ее фото. Мы принимаем решение на основе фото и двух моделей генерации этого фото.
Поймите, что конкретно эта задача решаема на достаточно мощном компе потому что в ней нет принципиальной невычислимости.
На практике да, сегодня этой мощности нет для такого решения в лоб.
А про то как это делает ребенок — пусть биологи разбираются.
Здравствуйте, nikov, Вы писали:
N>Здравствуйте, barn_czn, Вы писали:
N>>>Как я понимаю, речь изначально была о машине, которую можно разогнать до любой скорости, так что любой останавливающийся алгоритм можно выполнить настолько быстро, что не успеешь глазом моргнуть (или даже ещё быстрее), задав подходящую скорость. Речь не идет о машине, которая может выполнить бесконечное (а тем более, несчётное) количество операций за конечное время. Верно?
_>>Конкретизирую. Речь идет о машине Тьюринга с бесконечной лентой, временем передвижения по ленте = 0, временем записи и чтения на ленту = 0.
N>Я не понимаю, как так может быть. Ведь тогда два (и более) последовательных состояния машины будут существовать в один момент, а ее архитектура не предусматривает одновременного хранения нескольких состояний.
Лента бесконечная, кол-во нескольких состояний < кол-ва бесконечного числа состояний. Правда?
Тебе не нравится что машина делает все мгновенно? )) Ок, Специально для тебя мы сделаем задержку между командами. Сколько хочеш, 1/(3* 10^9) секунды пойдет?
Здравствуйте, barn_czn, Вы писали:
N>>Я не понимаю, как так может быть. Ведь тогда два (и более) последовательных состояния машины будут существовать в один момент, а ее архитектура не предусматривает одновременного хранения нескольких состояний.
_>Лента бесконечная, кол-во нескольких состояний < кол-ва бесконечного числа состояний. Правда?
Я имею в виду внутреннее состояние машины, не считая ленты.
_>Тебе не нравится что машина делает все мгновенно? )) Ок, Специально для тебя мы сделаем задержку между командами. Сколько хочеш, 1/(3* 10^9) секунды пойдет?
Меня бы устроила задержка, которую я могу выбирать сам, в зависимости от ресурсоемкости алгоритма.
Здравствуйте, nikov, Вы писали:
S_>>На C# за пару минут тоже можно написать генерацию последовательности, так что достижений математики никогда не хватит для определения того что она на консоль выведет.
N>Почему ты в этом уверен? Это ведь просто вычисление очень большого числа по простому алгоритму (я правильно понял?). Почему нельзя надеяться вычислить его несколько старших разрядов быстрым обходным путем?
Полной уверенности быть не может, но есть предположение что с увеличением результирующего числа, число обходных путей сокращается, громоздкость решения повышается (даже если нужно только несколько разрядов выдернуть).
И с учетом того что есть очень много способов нагенерировать такие числа компактными алгоритмами, а число обходных путей должно быть существенно меньше.
B>>Вообщем этого быть не может потому что такого не может быть. Мы же знаем что целых чисел меньше чем вещественных. А допуская такую машину мы бы могли пересчитать и вещественные. А жаль! Хорошая машина получилась бы Приятная темка!
_>А с чего вы взяли что такой машиной можно пересчитать вещественные числа? Как считать несчетные множества? _>И зачем главное. _>А запрет на существование такой машины может появится только из физики. Никаких противоречий со стороны математики не может быть.
Логика очень простая. Если машина выполняет любой алгоритм за 0 секунд, то разбор грамматики с алфавитом 0-9 тоже выполняет (алгоритм разбора очевиден). Если длина лексемы не ограничена (это ж математика что нам мешает так считать?), то это и есть все вещественные числа. Понятно, что каждому шагу алгоритма можно поставить в соответствие число.. дальше сами продолжите. Получится что мы их посчитаем. Ну, не знаю как предположение, но вроде логично. Там еще было веселое предположение. В обычной логике есть алгоритмы, которые не заканчиваются. Если предположить что такие выполняются на такой машине, то если прошло время больше 0, то можно такой алгоритм остановить и считать что получен отрицательный ответ. Какиие дальше выводы можно сделать.. если интересно можно поколупаться.. Ну, и с теоремой Геделя тоже облом получается. Я читал доказательство Успенского, там и так есть претензии.. Так на странице 8 есть предположение что словарное множество перечислимо.. Это справдливо только если ограничивать длину (см. пример выше грамматики вещественных чисел). Ну, и у меня есть основания утверждать что множество истинных утверждений тоже континуум. А так как доказательства это подмножества истиных утверждений,.. дальше понятно? Почему-то Успенский решил что их счетное число. А тут еще и такая машинка Вообщем веселуха..
Здравствуйте, minorlogic, Вы писали:
M>Совершенно не коректный вопрос.
M>Любую задачу можно решить ПОЛНЫМ перебором если существуют критерии успешности.
Здравствуйте, Lloyd, Вы писали:
L>Здравствуйте, minorlogic, Вы писали:
M>>Совершенно не коректный вопрос.
M>>Любую задачу можно решить ПОЛНЫМ перебором если существуют критерии успешности.
L>, если перебираемое множество — конечное.
Согласен, но не так уж и много ззадач которые невозможно апроксимировать конечным множеством
Здравствуйте, Lloyd, Вы писали:
L>Здравствуйте, minorlogic, Вы писали:
M>>Совершенно не коректный вопрос.
M>>Любую задачу можно решить ПОЛНЫМ перебором если существуют критерии успешности.
L>, если перебираемое множество — конечное.
Согласен, но не так уж и много ззадач которые невозможно апроксимировать конечным множеством
Здравствуйте, barn_czn, Вы писали:
_>Самый самый самый лучший ход в шахматах ищется перебором ! _>И машину не надо собирать. _>А он наверно нейросеть соорудил. _>Специалисты по нейросетям тоже репу чешут и когда она работает и когда чуш выдает.
Ну да. Если бы нейросети могли выдавать ответ "не знаю" им бы цены не было. В смысле, выдавали бы вместе с ответом достоверную степень уверенности в ответе. Тогда бы массив разных сетей после не сложных арифметических манипуляций мог бы существенно повысить качество (метафора — один элемент не знает, зато другой знает).
Такой эффект можно слегка воссоздать — кластеризовать ответы от многих сетей(1000 экземпляров), каждая немного по-другому обучена, немного другой архитектуры. Когда ответы распылены — малая степень доверия. Когда плотные кластеры — к ответам внутри скоплений больше доверия (метафора — когда врут все по-разному, когда говорят правду одинаково).Это не обязано всегда срабатывать, но испортить врядли сильно сможет. Разве что только перфоманс просадить.
nikov,
VD>>Чушь это. Особенно при условии наличия неограниченной производительности.
N>Допустим, у тебя есть компьютер, у которого ты можешь настраивать количество операций в секунду (и можешь задать его сколь угодно большим). Интересно, как бы ты вычислил на нем хотя бы несколько десятков следующих членов этой последовательности (Busy beaver)? N>Пусть программа печатает хотя бы только первую и последнюю десятичные цифры от каждого члена последовательности.
Ну, задача нахождения элементов последовательности просто сводится к задаче остановки. Правда я не знаю, решается ли задача остановки для каждого фиксированного n > |B(q, s, q+, s+, d+)|, где B(q, s, q+, s+, d+) — это однозначная двоичная кодировка машины, |.| — длина двоичного вектора. Определённо, задача остановки решается для малых n, а вот существует ли "граница неразрешимости" не могу сказать.
minorlogic,
M>>>Любую задачу можно решить ПОЛНЫМ перебором если существуют критерии успешности.
L>>, если перебираемое множество — конечное.
M> Согласен, но не так уж и много ззадач которые невозможно апроксимировать конечным множеством
Да, всего-то несчётное множество...
Весь этот зоопарк содержится в классе RP, который содержится в R. И количество элементов (то есть задач) в R — счётно. А всё, что снаружи — те самые алгоритмически неразрешимые задачи.
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
