Все выпуски

В данной статье осуществляется сравнение эффективности некоторых современных методов и практик стохастической оптимизации применительно к задаче цифрового предыскажения сигнала (DPD), которое является важной составляющей процесса обработки сигнала на базовых станциях, обеспечивающих беспроводную связь. В частности, рассматривается два круга вопросов о возможностях применения стохастических методов для обучения моделей класса Винера – Гаммерштейна в рамках подхода минимизации эмпирического риска: касательно улучшения глубины и скорости сходимости данного метода оптимизации и относительно близости самой постановки задачи (выбранной модели симуляции) к наблюдаемому в действительности поведению устройства. Так, в первой части этого исследования внимание будет сосредоточено на вопросе о нахождении наиболее эффективного метода оптимизации и дополнительных к нему модификаций. Во второй части предлагается новая квази-онлайн-постановка задачи и, соответственно, среда для тестирования эффективности методов, благодаря которым результаты численного моделирования удается привести в соответствие с поведением реального прототипа устройства DPD. В рамках этой новой постановки далее осуществляется повторное тестирование некоторых избранных практик, более подробно рассмотренных в первой части исследования, и также обнаруживаются и подчеркиваются преимущества нового лидирующего метода оптимизации, оказывающегося теперь также наиболее эффективным и в практических тестах. Для конкретной рассмотренной модели максимально достигнутое улучшение глубины сходимости составило 7% в стандартном режиме и 5% в онлайн-постановке (при том что метрика сама по себе имеет логарифмическую шкалу). Также благодаря дополнительным техникам оказывается возможным сократить время обучения модели DPD вдвое, сохранив улучшение глубины сходимости на 3% и 6% для стандартного и онлайн-режимов соответственно. Все сравнения производятся с методом оптимизации Adam, который был отмечен как лучший стохастический метод для задачи DPD из рассматриваемых в предшествующей работе [Pasechnyuk et al., 2021], и с методом оптимизации Adamax, который оказывается наиболее эффективным в предлагаемом онлайн-режиме.

In this paper, we test the performance of some modern stochastic optimization methods and practices with respect to the digital pre-distortion problem, which is a valuable part of processing signal on base stations providing wireless communication. In the first part of our study, we focus on the search for the best performing method and its proper modifications. In the second part, we propose the new, quasi-online, testing framework that allows us to fit our modeling results with the behavior of real-life DPD prototype, retest some selected of practices considered in the previous section and approve the advantages of the method appearing to be the best under real-life conditions. For the used model, the maximum achieved improvement in depth is 7% in the standard regime and 5% in the online regime (metric itself is of logarithmic scale). We also achieve a halving of the working time preserving 3% and 6% improvement in depth for the standard and online regime, respectively. All comparisons are made to the Adam method, which was highlighted as the best stochastic method for DPD problem in [Pasechnyuk et al., 2021], and to the Adamax method, which is the best in the proposed online regime.

Метод спектрального анализа стохастической матрицы применяется для построения индикатора, позволяющего определять тематику научных текстов без использования ключевых слов. Эта матрица представляет собой матрицу условных вероятностей биграмм, построенную по статистике используемых в тексте символов алфавита без учета пробелов, цифр и знаков препинания. Научные тексты классифицируются по взаимному расположению инвариантных подпространств матрицы условных вероятностей пар буквосочетаний. Индикатор разделения — величина косинуса угла между правым и левым собственными векторами, отвечающими максимальному и минимальному собственным значениям. Вычислительный алгоритм использует специальное представление параметра дихотомии, в качестве которого выступает интеграл от нормы квадрата резольвенты стохастической матрицы биграмм по окружности заданного радиуса в комплексной плоскости. Стремление интеграла в бесконечность свидетельствует о приближении контура интегрирования к собственному значению матрицы. В работе приведены типовые распределения индикатора идентификации специальностей. Для статистического анализа были проанализированы диссертации по основным 19 специальностям ВАК без учета классификации внутри специальности, по 20 текстов на специальность. Выяснилось, что эмпирические распределения косинуса угла для физико-математических и гуманитарных специальностей не имеют общего носителя, поэтому могут быть формально разделены по значению этого индикатора без ошибки. Хотя корпус текстов был не особенно большой, тем не менее при произвольном отборе диссертаций ошибка идентификации на уровне 2 % представляется очень хорошим результатом по сравнению с методами, основанными на семантическом анализе. Также выяснилось, что можно составить паттерн текста по каждой из специальностей в виде эталонной матрицы биграмм, по близости к которой в норме суммируемых функций можно безошибочно идентифицировать тематику написанного научного произведения, не используя ключевые слова. Предложенный метод можно использовать и в качестве сравнительного индикатора большей или меньшей строгости научного текста или как индикатор соответствия текста определенному научному уровню.

The method of the stochastic matrix spectrum analysis is used to build an indicator that allows to determine the subject of scientific texts without keywords usage. This matrix is a matrix of conditional probabilities of bigrams, built on the statistics of the alphabet characters in the text without spaces, numbers and punctuation marks. Scientific texts are classified according to the mutual arrangement of invariant subspaces of the matrix of conditional probabilities of pairs of letter combinations. The separation indicator is the value of the cosine of the angle between the right and left eigenvectors corresponding to the maximum and minimum eigenvalues. The computational algorithm uses a special representation of the dichotomy parameter, which is the integral of the square norm of the resolvent of the stochastic matrix of bigrams along the circumference of a given radius in the complex plane. The tendency of the integral to infinity testifies to the approximation of the integration circuit to the eigenvalue of the matrix. The paper presents the typical distribution of the indicator of identification of specialties. For statistical analysis were analyzed dissertations on the main 19 specialties without taking into account the classification within the specialty, 20 texts for the specialty. It was found that the empirical distributions of the cosine of the angle for the mathematical and Humanities specialties do not have a common domain, so they can be formally divided by the value of this indicator without errors. Although the body of texts was not particularly large, nevertheless, in the case of arbitrary selection of dissertations, the identification error at the level of 2 % seems to be a very good result compared to the methods based on semantic analysis. It was also found that it is possible to make a text pattern for each of the specialties in the form of a reference matrix of bigrams, in the vicinity of which in the norm of summable functions it is possible to accurately identify the theme of the written scientific work, without using keywords. The proposed method can be used as a comparative indicator of greater or lesser severity of the scientific text or as an indicator of compliance of the text to a certain scientific level.

Распределенные седловые задачи имеют множество различных приложений в оптимизации, теории игр и машинном обучении. Например, обучение генеративных состязательных сетей может быть представлено как минимаксная задача, а также задача обучения линейных моделей с регуляризатором может быть переписана как задача поиска седловой точки. В данной статье исследуются распределенные негладкие седловые задачи с липшицевыми целевыми функциями (возможно, недифференцируемыми). Целевая функция представляется в виде суммы нескольких слагаемых, распределенных между группой вычислительных узлов. Каждый узел имеет доступ к локально хранимой функции. Узлы, или агенты, обмениваются информацией через некоторую коммуникационную сеть, которая может быть централизованной или децентрализованной. В централизованной сети есть универсальный агрегатор информации (сервер или центральный узел), который напрямую взаимодействует с каждым из агентов и, следовательно, может координировать процесс оптимизации. В децентрализованной сети все узлы равноправны, серверный узел отсутствует, и каждый агент может общаться только со своими непосредственными соседями.

Мы предполагаем, что каждый из узлов локально хранит свою целевую функцию и может вычислить ее значение в заданных точках, т. е. имеет доступ к оракулу нулевого порядка. Информация нулевого порядка используется, когда градиент функции является трудно вычислимым, а также когда его невозможно вычислить или когда функция не дифференцируема. Например, в задачах обучения с подкреплением необходимо сгенерировать траекторию для оценки текущей стратегии. Этот процесс генерирования траектории и оценки политики можно интерпретировать как вычисление значения функции. Мы предлагаем подход, использующий технику сглаживания, т. е. применяющий метод первого порядка к сглаженной версии исходной функции. Можно показать, что стохастический градиент сглаженной функции можно рассматривать как случайную двухточечную аппроксимацию градиента исходной функции. Подходы, основанные на сглаживании, были изучены для распределенной минимизации нулевого порядка, и наша статья обобщает метод сглаживания целевой функции на седловые задачи.

Distributed saddle point problems (SPPs) have numerous applications in optimization, matrix games and machine learning. For example, the training of generated adversarial networks is represented as a min-max optimization problem, and training regularized linear models can be reformulated as an SPP as well. This paper studies distributed nonsmooth SPPs with Lipschitz-continuous objective functions. The objective function is represented as a sum of several components that are distributed between groups of computational nodes. The nodes, or agents, exchange information through some communication network that may be centralized or decentralized. A centralized network has a universal information aggregator (a server, or master node) that directly communicates to each of the agents and therefore can coordinate the optimization process. In a decentralized network, all the nodes are equal, the server node is not present, and each agent only communicates to its immediate neighbors.

We assume that each of the nodes locally holds its objective and can compute its value at given points, i. e. has access to zero-order oracle. Zero-order information is used when the gradient of the function is costly, not possible to compute or when the function is not differentiable. For example, in reinforcement learning one needs to generate a trajectory to evaluate the current policy. This policy evaluation process can be interpreted as the computation of the function value. We propose an approach that uses a smoothing technique, i. e., applies a first-order method to the smoothed version of the initial function. It can be shown that the stochastic gradient of the smoothed function can be viewed as a random two-point gradient approximation of the initial function. Smoothing approaches have been studied for distributed zero-order minimization, and our paper generalizes the smoothing technique on SPPs.

Предложен метод отображения промежуточных представлений C-, C++-программ в пространство векторов (эмбеддингов) для оценки производительности программ на этапе компиляции, без необходимости исполнения. Использование эмбеддингов для данной цели позволяет не проводить сравнение графов исследуемых программ непосредственно, что вычислительно упрощает задачу сравнения программ. Метод основан на серии трансформаций исходного промежуточного представления (IR), таких как: инструментирование — добавление фиктивных инструкций в оптимизационном проходе компилятора в зависимости от разности смещений в текущей инструкции обращения к памяти относительно предыдущей, преобразование IR в многомерный вектор с помощью технологии IR2Vec с понижением размерности по алгоритму t-SNE (стохастическое вложение соседей с t-распределением). В качестве метрики производительности предлагается доля кэш-промахов 1-го уровня (D1 cache misses). Приводится эвристический критерий отличия программ с большей долей кэш-промахов от программ с меньшей долей по их образам. Также описан разработанный в ходе работы проход компилятора, генерирующий и добавляющий фиктивные инструкции IR согласно используемой модели памяти. Приведено описание разработанного программного комплекса, реализующего предложенный способ оценивания на базе компиляторной инфраструктуры LLVM. Проведен ряд вычислительных экспериментов на синтетических тестах из наборов программ с идентичными потоками управления, но различным порядком обращений к одномерному массиву, показано, что коэффициент корреляции между метрикой производительности и расстоянием до эмбеддинга худшей программы в наборе отрицателен вне зависимости от инициализации t-SNE, что позволяет сделать заключение о достоверности эвристического критерия. Также в статье рассмотрен способ генерации тестов. По результатам экспериментов, вариативность значений метрики производительности на исследуемых множествах предложена как метрика для улучшения генератора тестов.

The method for mapping of intermediate representations (IR) set of C, C++ programs to vector embedding space is considered to create an empirical estimation framework for static performance prediction using LLVM compiler infrastructure. The usage of embeddings makes programs easier to compare due to avoiding Control Flow Graphs (CFG) and Data Flow Graphs (DFG) direct comparison. This method is based on transformation series of the initial IR such as: instrumentation — injection of artificial instructions in an instrumentation compiler’s pass depending on load offset delta in the current instruction compared to the previous one, mapping of instrumented IR into multidimensional vector with IR2Vec and dimension reduction with t-SNE (t-distributed stochastic neighbor embedding) method. The D1 cache miss ratio measured with perf stat tool is considered as performance metric. A heuristic criterion of programs having more or less cache miss ratio is given. This criterion is based on embeddings of programs in 2D-space. The instrumentation compiler’s pass developed in this work is described: how it generates and injects artificial instructions into IR within the used memory model. The software pipeline that implements the performance estimation based on LLVM compiler infrastructure is given. Computational experiments are performed on synthetic tests which are the sets of programs with the same CFGs but with different sequences of offsets used when accessing the one-dimensional array of a given size. The correlation coefficient between performance metric and distance to the worst program’s embedding is measured and proved to be negative regardless of t-SNE initialization. This fact proves the heuristic criterion to be true. The process of such synthetic tests generation is also considered. Moreover, the variety of performance metric in programs set in such a test is proposed as a metric to be improved with exploration of more tests generators.

Работа посвящена исследованию связей между дискретными и непрерывными моделями финансовых процессов и их вероятностных характеристик. Во-первых, установлена связь между процессами цен акций, хеджирующего портфеля и опционов в моделях, обусловленных биномиальными возмущениями и предельными для них возмущениями типа броуновского движения. Во-вторых, указаны аналоги в коэффициентах стохастических уравнений с различными случайными процессами, непрерывными и скачкообразными, и в коэффициентах соответствующих детерминированных уравнений для их вероятностных характеристик.

Изложение результатов исследования связей и нахождения аналогий, полученных в настоящей работе, привело к необходимости адекватного изложения предварительных сведений и результатов из финансовой математики, а также описания связанных с ней объектов стохастического анализа.

В работе частично новые и известные результаты изложены в доступной форме для тех, кто не является специалистом по финансовой математике и стохастическому анализу и кому эти результаты важны с точки зрения приложений. Конкретно, представлены следующие разделы.

• В одно- и $n$-периодных биномиальных моделях предложен единый подход к определению на вероятностном пространстве риск-нейтральной меры, с которой дисконтированная цена опциона становится мартингалом. Полученная мартингальная формула для цены опциона пригодна для численного моделирования. В следующих разделах подход на основе риск-нейтральных мер применяется для исследования финансовых процессов в моделях непрерывного времени.

• В непрерывном времени рассмотрены модели цены акций, хеджирующего портфеля и опциона в форме стохастических уравнений с интегралом Ито по броуновскому движению и по компенсированному процессу Пуассона. Изучение свойств процессов, являющихся решениями стохастических уравнений, в этом разделе опирается на один из центральных объектов стохастического анализа — формулу Ито, методике применения которой уделено особое внимание.

• Представлена знаменитая формула Блэка –Шоулза, дающая решение уравнения в частных производных для функции $v(t, x)$, которая при подстановке $x = S (t)$, где $S(t)$ — цена акций в момент времени $t$, дает цену опциона в модели с непрерывным возмущением броуновским движением.

• Предложен аналог формулы Блэка – Шоулза для случая модели со скачкообразным возмущением процессом Пуассона. Вывод этой формулы опирается на технику риск-нейтральных мер и лемму независимости.

The paper is devoted to the study of relationships between discrete and continuous models financial processes and their probabilistic characteristics. First, a connection is established between the price processes of stocks, hedging portfolio and options in the models conditioned by binomial perturbations and their limit perturbations of the Brownian motion type. Secondly, analogues in the coefficients of stochastic equations with various random processes, continuous and jumpwise, and in the coefficients corresponding deterministic equations for their probabilistic characteristics. Statement of the results on the connections and finding analogies, obtained in this paper, led to the need for an adequate presentation of preliminary information and results from financial mathematics, as well as descriptions of related objects of stochastic analysis. In this paper, partially new and known results are presented in an accessible form for those who are not specialists in financial mathematics and stochastic analysis, and for whom these results are important from the point of view of applications. Specifically, the following sections are presented.

• In one- and n-period binomial models, it is proposed a unified approach to determining on the probability space a risk-neutral measure with which the discounted option price becomes a martingale. The resulting martingale formula for the option price is suitable for numerical simulation. In the following sections, the risk-neutral measures approach is applied to study financial processes in continuous-time models.

• In continuous time, models of the price of shares, hedging portfolios and options are considered in the form of stochastic equations with the Ito integral over Brownian motion and over a compensated Poisson process. The study of the properties of these processes in this section is based on one of the central objects of stochastic analysis — the Ito formula. Special attention is given to the methods of its application.

• The famous Black – Scholes formula is presented, which gives a solution to the partial differential equation for the function $v(t, x)$, which, when $x = S (t)$ is substituted, where $S(t)$ is the stock price at the moment time $t$, gives the price of the option in the model with continuous perturbation by Brownian motion.

• The analogue of the Black – Scholes formula for the case of the model with a jump-like perturbation by the Poisson process is suggested. The derivation of this formula is based on the technique of risk-neutral measures and the independence lemma.