Gosplan, Skynet и IoT

avlasov — 11.05.2017 Успехи в области машинного обучения и перманентный экспоненциальный рост вычислительных возможностей не могут не радовать - и одновременно - настораживать. Призрак Gosplan'а бродит по планете, и некоторые жутко пугаются при любом маломальски разумном рассуждении об экономике - эдак ведь ща могучий Deep Learning как все выучит, а через IoT как все реализует, да так, что свободный человек ничего и не заметит даже. Будет думать, что он мол что-то там решает, выбирает чего-то. Конвергенция бла. ВолкGosplan в овечьейлиберальной шкуре. Skynet и Matrix - наивные фантазии сценаристов. Настоящий ИИ все же будет поумнее - зачем ему уничтожать тех, кто старательно возделывает среду его обитания?

Конечно, людей не боящихся мыслить, призрак Gosplan'а не пугает. Например, Анатолий Вассерман предрекает, что скоро вычислительные возможности компьютеров станут настолько велики, что смогут заоптимизировать план всего мирового хозяйства за разумное время. И таким образом, сформируется вычислительная база мирового Gosplan'а - а значит и построения коммунизма на отдельно взятой планете.

На мой взгляд, его оценка слишком теоретическая. Т.е. потребные вычислительные мощности сильно меньше. Перескажу вкратце те рассуждения, что касаются оценки вычислительных затрат. Ключевая операция многих алгоритмов математической оптимизации - решние системы линейных уравнений. На это в общем случае требуется O(N^3) операций, но поскольку в случае задач планирования, в соответствующей матрице очень много нулей, то затраты сокращаются до O(N^2.5) операций. Ну и для оптимизации плана требуется составление примерно стольких вариантов системы, сколько в ней уравнений, т.е. O(N^3.5). При этом N - это кол-во наименований изделий, которые нужно планировать/оптимизировать. Ну и если N порядка милииарда, то N^3.5 получается многова-то.

Я лично встречал другие оценки затрат на решение оптимизационной задачи, немного поменьше типа несколько десятков итераций, каждая из которых требует max(N^3,N^2*M) операций, где M - кол-во ограничений. Это для задач выпуклой оптимизации. Однако, это не используя специальную структуру матриц.

Одновременно, если использовать особенности структуры матрицы системы линейных уравнений, то порой систему можно решить за O(N) операций. Скажем, решение системы с несколькими миллиардами переменных не то чтобы повседневность, но такое случается. Возникает вопрос - насколько это применимо для задач экономического планирования?

Рассмотрим задачу балансирования плана. Допустим у нас ассортимент N наименований и у нас есть вектор b длинны N где указана потребность в каждом продукте. А также есть матрица A прямых затрат. Т.е. каждый столбец в матрице говорит сколько разных изделий расходуется в процессе производства какого-то изделия на выходе. Т.е. если мы помножим A*b то получим затраты продуктов, нужных для производства нашего целевого вектора b. Т.е. чтобы получить на выходе b, нам нужно по крайней мере включить в план промежуточные продукты в кол-ве A*b. Но для их производства тоже нужно потратить какие-то ресурсы/продукты. Их можно посчитать умножим еще раз на матрицу затрат - т.е. A*A*b. Ну и так далее. Составим уравнение. Наша цель - получить b продуктов для конечного потребления, для чего нам нужно суммарно произвести x продуктов, включающих как b так и неизвестное кол-во суммарных промежуточных продуктов. Итого, x-A*x=b. Т.е. x - план (суммарный), A*x - суммарные затраты на выполнение плана, ну а то что осталась, должно быть равно нашему целевому вектору b, который пойдет на конечное потребление. Т.е. у нас получается такая система уравнений (I-A)*x = b.

Если максимальное по модулю собственное число A меньше единицы, то тогда ряд inv(I-A)=I+A+A^2+A^3+.. сходится. Т.е. уравнение можно решать итеративно. При этом ошибка будет сокращаться по крайней мере, на 1-lambda процентов, где lambda - макимальное по модулю собственное число матрицы A. 1-lambda можно трактовать как своеобразную рентабельность. Т.е. условие что lambda меньше единицы, означает что производство рентабельное, матрица продуктивная, затраты меньше нежели выход. Действительно для соответствующего собственного вектора u имеем A*u = lambda*u. Т.е. затраты на производство u равны lambda*u. Ну и если lambda меньше единицы, то у нас что-то останется.

Фактически 1-lambda должно быть заметно больше рентабельности, скажем 10-20%. Ведь есть еще затраты факторов производства, которые мы не учитываем в матрице A. Например, обычно в нее не включают трудовые затраты (их учитывают в другом месте). Т.е. эти затраты так или иначе компенсируются из вектора конечного потребления b. А значит рентабельность 1-lambda должна быть существенно больше рентабельности производства, наблюдаемой в экономике. Таким образом, можно считать что lambda, по крайней мере 0.9, а то и меньше.

Что означает, что на каждой итерации ошибка уменьшается на 10%. Т.е. нужно около 24 итераций чтобы снизить ошибку в 10 раз. Ну и в районе сотни итераций чтобы получить приемлимую точность в сотые доли процента - вряд ли нам нужна бОльшая точноть, хотя если нужна, то можно сделать еще сотню итераций и уменьшить ошибку еще на несколько порядков.

Итого, задачу балансировки плана можно решить за примерно сотню итераций, каждая из которой состоит в умножении вектора на матрицу. Так как в матрице A огромное кол-во нулей, то суммарные затраты будут порядка 100*N*M, где M - среднее кол-во ненулевых элементов в столбцах матрицы A, т.е. среднее кол-во промежуточных продуктов, которые затрачиваются в производстве каждого наименования на одном этапе производственной цепочки. Скажем, если M = 1000, то вычислительные затраты на балансировку плана будут порядка 10^5*N, что сильно меньше нежели N^2.5. Отмечу, что если мы берем гигансткий ассортимент продукции, то M не будет особо расти, ведь все гигантское разнообразие состоит из вариаций каких-то параметров. Винтики разной длинны и разного диаметра, айфоны разных цветов, резисторы разного сопротивления, точности и мощности, ну и т.д. А промежуточные продукты будут затрачиваться примерно те же, просто в разных количествах.

Оставить комментарий

Популярные посты:

• Архив