All issues

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

The task of embedding an infinity countable graph into continuous metric space is considered. The concept of uniform embedding having no accumulation point in a set of vertex images and having all graph edge images of a limited length is introduced. Necessary and sufficient conditions for possibility of uniform embedding into spaces with Euclid and Lorenz metrics are stated in terms of graph structure. It is proved that tree graphs with finite branching have uniform embedding into space with absolute Minkowski metric.

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

We consider vacuum polarization of a scalar field on the Lie groups with a bi-invariant metric of Robertson-Walker type. Using the method of orbits we found expression for the vacuum expectation values of the energy-momentum tensor of the scalar field which are determined by the representation character of the group. It is shown that Einstein’s equations with the energy-momentum tensor are consistent. As an example, we consider isotropic Bianchi type IX model.

Работа посвящена вопросам приближения периодических функций высокой гладкости средними арифметическими суммами Фурье. Наиболее естественным и простым примером линейного процесса аппроксимации непрерывных периодических функций действительной переменной является приближение элементами последовательностей частичных сумм ряда Фурье. Известно, что последовательности частичных сумм ряда Фурье не являются равномерно сходящимися на всем пространстве C 2$\pi$-периодических непрерывных функций. Значительное число работ данного направления посвящено изучению аппроксимативных свойств методов приближения, которые для заданной функции $f$ образуются с помощью преобразований частичных сумм ее ряда Фурье и позволяют построить последовательности тригонометрических полиномов, которые равномерно сходятся для каждой функции $f \in C$. На протяжении последних десятилетий широко изучаются суммы Валле Пуссена и их частные случаи суммы Фейера. Одним из наиболее важных направлений в этой области является изучение асимптотического поведения верхних граней уклонений средних арифметических сумм Фурье по различным классам периодических функций. Методы исследования интегральных представлений уклонений тригонометрических полиномов, которые порождаются линейными методами суммирования рядов Фурье, возникли и получили свое развитие в работах С.М. Никольского, С.Б. Стечкина, Н.П. Корнейчука, В.К. Дзядыка и их учеников.

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

The paper deals with the problems of approximation of periodic functions of high smoothness by arithmetic means of Fourier sums. The simplest and natural example of a linear process of approximation of continuous periodic functions of a real variable is the approximation of these functions by partial sums of the Fourier series. However, the sequences of partial Fourier sums are not uniformly convergent over the entire class of continuous $2\pi$-periodic functions. In connection with this, a significant number of papers is devoted to the study of the approximative properties of other approximation methods, which are generated by certain transformations of the partial sums of Fourier series and allow us to construct sequences of trigonometrical polynomials that would be uniformly convergent for each function $f \in C$. In particular, over the past decades, de la Vallee Poussin sums and Fejer sums have been widely studied. One of the most important directions in this field is the study of the asymptotic behavior of upper bounds of deviations of arithmetic means of Fourier sums on different classes of periodic functions. Methods of investigation of integral representations of deviations of polynomials on the classes of periodic differentiable functions of real variable originated and received its development through the works of S.M. Nikol’sky, S.B. Stechkin, N.P. Korneichuk, V.K. Dzadyk, etc.

The aim of the work systematizes known results related to the approximation of classes of periodic functions of high smoothness by arithmetic means of Fourier sums, and presents new facts obtained for particular cases. In the paper is studied the approximative properties of $r$-repeated de la Vallee Poussin sums on the classes of periodic functions that can be regularly extended into the fixed strip of the complex plane. We obtain asymptotic formulas for upper bounds of the deviations of repeated de la Vallee Poussin sums taken over classes of periodic analytic functions. In certain cases, these formulas give a solution of the corresponding Kolmogorov–Nikolsky problem. We indicate conditions under which the repeated de la Vallee Poussin sums guarantee a better order of approximation than ordinary de la Vallee Poussin sums.

Модели многозначной классификации возникают в различных сферах современной жизни, что объясняется всё большим количеством информации, требующей оперативного анализа. Одним из математических методов решения этой задачи является модульный метод, на первом этапе которого для каждого класса строится некоторая ранжирующая функция, упорядочивающая некоторым образом все объекты, а на втором этапе для каждого класса выбирается оптимальное значение порога, объекты с одной стороны которого относят к текущему классу, а с другой — нет. Пороги подбираются так, чтобы максимизировать целевую метрику качества. Алгоритмы, свойства которых изучаются в настоящей статье, посвящены второму этапу модульного подхода — выбору оптимального вектора порогов. Этот этап становится нетривиальным в случае использования в качестве целевой метрики качества $F$-меры от средней точности и полноты, так как она не допускает независимую оптимизацию порога в каждом классе. В задачах экстремальной многозначной классификации число классов может достигать сотен тысяч, поэтому исходная оптимизационная задача сводится к задаче поиска неподвижной точки специальным образом введенного отображения $\boldsymbol V$, определенного на единичном квадрате на плоскости средней точности $P$ и полноты $R$. Используя это отображение, для оптимизации предлагаются два алгоритма: метод линеаризации $F$-меры и метод анализа области определения отображения $\boldsymbol V$. На наборах данных многозначной классификации разного размера и природы исследуются свойства алгоритмов, в частности зависимость погрешности от числа классов, от параметра $F$-меры и от внутренних параметров методов. Обнаружена особенность работы обоих алгоритмов для задач с областью определения отображения $\boldsymbol V$, содержащей протяженные линейные участки границ. В случае когда оптимальная точка расположена в окрестности этих участков, погрешности обоих методов не уменьшаются с увеличением количества классов. При этом метод линеаризации достаточно точно определяет аргумент оптимальной точки, а метод анализа области определения отображения $\boldsymbol V$ — полярный радиус.

Multi-label classification models arise in various areas of life, which is explained by an increasing amount of information that requires prompt analysis. One of the mathematical methods for solving this problem is a plug-in approach, at the first stage of which, for each class, a certain ranking function is built, ordering all objects in some way, and at the second stage, the optimal thresholds are selected, the objects on one side of which are assigned to the current class, and on the other — to the other. Thresholds are chosen to maximize the target quality measure. The algorithms which properties are investigated in this article are devoted to the second stage of the plug-in approach which is the choice of the optimal threshold vector. This step becomes non-trivial if the $F$-measure of average precision and recall is used as the target quality assessment since it does not allow independent threshold optimization in each class. In problems of extreme multi-label classification, the number of classes can reach hundreds of thousands, so the original optimization problem is reduced to the problem of searching a fixed point of a specially introduced transformation $\boldsymbol V$, defined on a unit square on the plane of average precision $P$ and recall $R$. Using this transformation, two algorithms are proposed for optimization: the $F$-measure linearization method and the method of $\boldsymbol V$ domain analysis. The properties of algorithms are studied when applied to multi-label classification data sets of various sizes and origin, in particular, the dependence of the error on the number of classes, on the $F$-measure parameter, and on the internal parameters of methods under study. The peculiarity of both algorithms work when used for problems with the domain of $\boldsymbol V$, containing large linear boundaries, was found. In case when the optimal point is located in the vicinity of these boundaries, the errors of both methods do not decrease with an increase in the number of classes. In this case, the linearization method quite accurately determines the argument of the optimal point, while the method of $\boldsymbol V$ domain analysis — the polar radius.

В данной работе рассматривается задача восстановления матрицы корреспонденций для наблюдений реальных корреспонденций в г. Москве. Следуя общепринятому подходу [Гасников и др., 2013], транспортная сеть рассматривается как ориентированный граф, дуги которого соответствуют участкам дороги, а вершины графа — районы, из которых выезжают / в которые въезжают участники движения. Число жителей города считается постоянным. Задача восстановления матрицы корреспонденций состоит в расчете всех корреспонденций израйона $i$ в район $j$.

Для восстановления матрицы предлагается использовать один из наиболее популярных в урбанистике способов расчета матрицы корреспонценций — энтропийная модель. В работе, в соответствии с работой [Вильсон, 1978], приводится описание эволюционного обоснования энтропийной модели, описывается основная идея перехода к решению задачи энтропийно-линейного программирования (ЭЛП) при расчете матрицы корреспонденций. Для решения полученной задачи ЭЛП предлагается перейти к двойственной задаче и решать задачу относительно двойственных переменных. В работе описывается несколько численных методов оптимизации для решения данной задачи: алгоритм Синхорна и ускоренный алгоритм Синхорна. Далее приводятся численные эксперименты для следующих вариантов функций затрат: линейная функция затрат и сумма степенной и логарифмической функции затрат. В данных функциях затраты представляют из себя некоторую комбинацию среднего времени в пути и расстояния между районами, которая зависит от параметров. Для каждого набора параметров функции затрат рассчитывается матрица корреспонденций и далее оценивается качество восстановленной матрицы относительно известной матрицы корреспонденций. Мы предполагаем, что шум в восстановленной матрице корреспонденций является гауссовским, в результате в качестве метрики качества выступает среднеквадратичное отклонение. Данная задача представляет из себя задачу невыпуклой оптимизации. В статье приводится обзор безградиенных методов оптимизации для решения невыпуклых задач. Так как число параметров функции затрат небольшое, для определения оптимальных параметров функции затрат было выбрано использовать метод перебора по сетке значений. Таким образом, для каждого набора параметров рассчитывается матрица корреспонденций и далее оценивается качество восстановленной матрицы относительно известной матрицы корреспонденций. Далее по минимальному значению невязки для каждой функции затрат определяется, для какой функции затрат и при каких значениях параметров восстановленная матрица наилучшим образом описывает реальные корреспонденции.

In this paper, we consider the problem of restoring the correspondence matrix based on the observations of real correspondences in Moscow. Following the conventional approach [Gasnikov et al., 2013], the transport network is considered as a directed graph whose edges correspond to road sections and the graph vertices correspond to areas that the traffic participants leave or enter. The number of city residents is considered constant. The problem of restoring the correspondence matrix is to calculate all the correspondence from the $i$ area to the $j$ area.

To restore the matrix, we propose to use one of the most popular methods of calculating the correspondence matrix in urban studies — the entropy model. In our work, which is based on the work [Wilson, 1978], we describe the evolutionary justification of the entropy model and the main idea of the transition to solving the problem of entropy-linear programming (ELP) in calculating the correspondence matrix. To solve the ELP problem, it is proposed to pass to the dual problem. In this paper, we describe several numerical optimization methods for solving this problem: the Sinkhorn method and the Accelerated Sinkhorn method. We provide numerical experiments for the following variants of cost functions: a linear cost function and a superposition of the power and logarithmic cost functions. In these functions, the cost is a combination of average time and distance between areas, which depends on the parameters. The correspondence matrix is calculated for multiple sets of parameters and then we calculate the quality of the restored matrix relative to the known correspondence matrix.

We assume that the noise in the restored correspondence matrix is Gaussian, as a result, we use the standard deviation as a quality metric. The article provides an overview of gradient-free optimization methods for solving non-convex problems. Since the number of parameters of the cost function is small, we use the grid search method to find the optimal parameters of the cost function. Thus, the correspondence matrix calculated for each set of parameters and then the quality of the restored matrix is evaluated relative to the known correspondence matrix. Further, according to the minimum residual value for each cost function, we determine for which cost function and at what parameter values the restored matrix best describes real correspondence.