Стохастическая арифметика
Есть идея о том, как контролировать точность компьютерных вычислений. Представление с плавающей точкой не дает никакой гарантии точности, поэтому для каждого алгоритма нужно отдельно доказывать корректность. Интервальную арифметику придумали для того, чтобы доказывалось само, но у нее есть проблема с тем, что длины интервалов слишком быстро растут. Если бы имелся механизм, учитывающий функциональную зависимость между аргументами, то, возможно, всё было бы не так плохо.
Я предлагаю другой, возможно, новый подход, который, по идее, дает стохастическое доказательство корректности и учитывает зависимости. Я потратил некоторое время, чтобы проверить, нет ли уже чего-нибудь в этом роде. Вроде бы прослеживается некоторая связь с нечеткой логикой (точнее, с нечеткой интервальной арифметикой -- обобщением интервальной арифметики). Может быть, стоит копать куда-то в строну так называемой вероятностной логики (product logic), чтобы увидеть, что предлагаемое мной уже изобретено. Тем не менее попытаюсь изложить концепцию.
Вместо того, чтобы представлять вещественное число в виде интервала или в формате IEEE 754 (что в общем-то тоже в некотором смысле есть интервал), предлагается задавать число в виде случайной величины с заданным распределением. Для этого надо сделать две вещи:)
с вещественными параметрами к "дискретному")
, где параметры
конечно-преставимы в машине.
Как определить порядок "точнее"? Мне не удалось найти универсального определения, но можно ввести такое понятие, назовем его уровнем значимости, -- положительное число (близкое к нулю), которое выбирается для каждой задачи заранее из каких-то физических или "вычислительных" соображений. Тогда для заданного уровня значимости
два распределения a и b связаны отношением
(a "точнее" b), если для любого интервала \ge 1-\varepsilon)
существует интервал \ge 1-\varepsilon)
.
Для примера можно попробовать двупараметрическое семейство нормальных распределений N(c, s), пополненное дельта-функциями (формально записываемыми как N(c, 0)). Здесь при любом уровне значимости N(c, 0) всегда точнее N(c, s), и вообще\prec N(c, s_2))
при s1 < s2. Если взять разные c, то сравнимость будет зависеть от уровня значимости.
Используя порядок, можно сформулировать задачу выполнения арифметической операции как нахождение какого-нибудь представимого распределения, так чтобы истинное распределение было "точнее" найденного. При этом желательно подыскивать не какое попало, а "поточнее", т.е. "наименьшее" из тех, которые "больше" истинного. (Пока не обращаем внимание на то, что существование "наименьшего", вообще говоря, под вопросом.) Это задача кажется трудоемкой, поэтому, во-первых, надо позаботиться о рациональном выборе представляемого семейства и, во-вторых, о том, чтобы эффективно реализовать арифметику, впоть до привлечения специальных аппаратных средств.
Теперь о зависимостях. Можно считать, что задача формулируется в следующем виде: дано совместное распределение n чисел, результат надо выразить в виде совместного распределения m чисел. Если подойти наивно, то количество информации, требуемое для представления вектора, зависит экспоненциально от длины вектора. Так, скорее всего, не годится. Можно заметить, что почти все элементарные операции над числами бинарны (ну или унарны). Тогда можно хранить только попарные зависимости, коих O(n^2), что гораздо лучше, чем экспонента. Получается, что исходный вектор (а также результатный и все промежуточные) хранится в виде набора n распределий и некоего обобщения ковариационной матрицы -- набора попарных распределений. (Здесь наверно есть избыточность -- вовсе незачем хранить попарное распределение двух независимых чисел...)
Проблем здесь, конечно, куча. Я пока не готов описать арифметику для вышеупомянутого семейства гауссиан даже для простых случаев (ну разве что a+b для независимых). Кроме того, совершенно неясно, что делать с операциями арности больше 2 (хотя бы if, у которого условием стоит a>0).
Я предлагаю другой, возможно, новый подход, который, по идее, дает стохастическое доказательство корректности и учитывает зависимости. Я потратил некоторое время, чтобы проверить, нет ли уже чего-нибудь в этом роде. Вроде бы прослеживается некоторая связь с нечеткой логикой (точнее, с нечеткой интервальной арифметикой -- обобщением интервальной арифметики). Может быть, стоит копать куда-то в строну так называемой вероятностной логики (product logic), чтобы увидеть, что предлагаемое мной уже изобретено. Тем не менее попытаюсь изложить концепцию.
Вместо того, чтобы представлять вещественное число в виде интервала или в формате IEEE 754 (что в общем-то тоже в некотором смысле есть интервал), предлагается задавать число в виде случайной величины с заданным распределением. Для этого надо сделать две вещи:
- Зафиксировать некоторое параметризованное семейство распределений, так чтобы набор параметров можно было представить в виде битовой последовательности (скорее всего ее длина должна быть фиксированной и равно какому-то круглому количеству битов).
- Определить частичный порядок на нашем семестве распределений, так чтобы можно было сказать, что одно распределение "точнее" другого.
с вещественными параметрами к "дискретному"
, где параметры
конечно-преставимы в машине.
Как определить порядок "точнее"? Мне не удалось найти универсального определения, но можно ввести такое понятие, назовем его уровнем значимости, -- положительное число (близкое к нулю), которое выбирается для каждой задачи заранее из каких-то физических или "вычислительных" соображений. Тогда для заданного уровня значимости
два распределения a и b связаны отношением
(a "точнее" b), если для любого интервала
существует интервал
.
Для примера можно попробовать двупараметрическое семейство нормальных распределений N(c, s), пополненное дельта-функциями (формально записываемыми как N(c, 0)). Здесь при любом уровне значимости N(c, 0) всегда точнее N(c, s), и вообще
при s1 < s2. Если взять разные c, то сравнимость будет зависеть от уровня значимости.
Используя порядок, можно сформулировать задачу выполнения арифметической операции как нахождение какого-нибудь представимого распределения, так чтобы истинное распределение было "точнее" найденного. При этом желательно подыскивать не какое попало, а "поточнее", т.е. "наименьшее" из тех, которые "больше" истинного. (Пока не обращаем внимание на то, что существование "наименьшего", вообще говоря, под вопросом.) Это задача кажется трудоемкой, поэтому, во-первых, надо позаботиться о рациональном выборе представляемого семейства и, во-вторых, о том, чтобы эффективно реализовать арифметику, впоть до привлечения специальных аппаратных средств.
Теперь о зависимостях. Можно считать, что задача формулируется в следующем виде: дано совместное распределение n чисел, результат надо выразить в виде совместного распределения m чисел. Если подойти наивно, то количество информации, требуемое для представления вектора, зависит экспоненциально от длины вектора. Так, скорее всего, не годится. Можно заметить, что почти все элементарные операции над числами бинарны (ну или унарны). Тогда можно хранить только попарные зависимости, коих O(n^2), что гораздо лучше, чем экспонента. Получается, что исходный вектор (а также результатный и все промежуточные) хранится в виде набора n распределий и некоего обобщения ковариационной матрицы -- набора попарных распределений. (Здесь наверно есть избыточность -- вовсе незачем хранить попарное распределение двух независимых чисел...)
Проблем здесь, конечно, куча. Я пока не готов описать арифметику для вышеупомянутого семейства гауссиан даже для простых случаев (ну разве что a+b для независимых). Кроме того, совершенно неясно, что делать с операциями арности больше 2 (хотя бы if, у которого условием стоит a>0).