{'fraction_non_alphanumeric': 0.04155678821496772, 'fraction_numerical': 0.006001636810039101, 'mean_word_length': 4.660319094184251, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Multiple--Instance Learning: Christoffel Function Approach to Distribution Regression Problem

A two--step Christoffel function based solution is proposed to distribution regression problem. On the first step, to model distribution of observations inside a bag, build Christoffel function for each bag of observations. Then, on the second step, build outcome variable Christoffel function, but use the bag's Christoffel function value at given point as the weight for the bag's outcome. The approach allows the result to be obtained in closed form and then to be evaluated numerically. While most of existing approaches minimize some kind an error between outcome and prediction, the proposed approach is conceptually different, because it uses Christoffel function for knowledge representation, what is conceptually equivalent working with probabilities only. To receive possible outcomes and their probabilities Gauss quadrature for second--step measure can be built, then the nodes give possible outcomes and normalized weights -- outcome probabilities. A library providing numerically stable polynomial basis for these calculations is available, what make the proposed approach practical.


I. INTRODUCTION
Multiple instance learning is an important Machine Learning (ML) concept having numerous applications [1]. In multiple instance learning class label is associated not with a single observation, but with a "bag" of observations. A very close problem is distribution regression problem, where a l-th sample distribution of x is mapped to a single y (l) value.
There are numerous heuristics methods developed from both: ML and distribution regression sides, see [2] for review. As in any ML problem the most important part is not so much the learning algorithm, but the way how the learned knowledge is represented. Learned knowledge is often represented as a set of propositional rules, regression function, Neural Network weights, etc. Most of the approaches minimize an error between result and prediction, and some kind of L 2 metric is often used as an error. The simplest example of such approach is least squares-type approximation. However, there is exist different kind of approximation, Radon-Nikodym type, that operates not with result error, but with sample probabilty, see the Ref. [3] as an example comparing two these approaches.
Similar transition from result error to probability of outcomes is made in this paper.
In this work we use Christoffel function as a mean to store knowledge learned. Christoffel function is a very fundamental concept related to "distribution density", quadratures weights, number of observations, etc [4,5]. Recent progress in numerical stability of high order distribution moments calculation [6] allows Christoffel function to be built to a very high order, what make practical the approach of using Christoffel function as way to represent knowledge learned.
The paper is organized as following: In Section II a general theory of distribution regression is discussed and close form result, Eq. (10), is presented. Then in Section III numerical example of Eq. (10) application is presented. In Section IV possible further development is discussed.

II. CHRISTOFFEL FUNCTION APPROACH
Consider distribution regression problem where a bag of N observations x is mapped to a single outcome observation y for l = [1..M].
3 A distribution regression problem can have a goal to estimate y, average of y, distribution of y, etc. given specific value of x. While the Christoffel function can be used as a proxy to probabilty estimation, but for "true" distribution estimation a complete Gauss quadrature should be built, then the nodes would give possible outcomes and normalized weightsoutcome probabilities.
For further development we need x and y bases Q k (x) and Q m (y) and some x and y measure. For simplicity, not reducing the generality of the approach, we are going to assume that x measure is a sum over j index j , y measure is a l , the basis functions If no x observations exist in each bag (N = 0), how to estimate the number of observations for given y value? The answer is Christoffel function λ(y).
The G y is Gramm matrix, K(y, y) is a positive quadratic form with matrix equal to Gramm matrix inverse and is a polynomial of 2d y − 2 order, when the form is expanded. The K(z, y) is a reproducing kernel: P (z) = M l=1 K(z, y (l) )P (y (l) ) for any polynomial P of degree d y − 1 or less. For numerical calculations of K(y, y) see Ref. [6], Appendix C.
The λ(y) define a value similar in nature to "the number of observations", or "probability", "weight", etc [4,5]. (The equation M = dy−1 i=0 λ(y i ) holds, when y i correspond to quadrature nodes build on y-distribution, the y i are eigenvalues of generalized eigenfunctions problem: The asympthotic of λ(y) can also serve as important characteristics of distribution property [4].) The problem now is to modify λ(y) to take into account given x value. If, in addition to y (l) , we have a vector x The result for λ(y|x) is: The λ(y|x) is the answer. The G y|x is very similar to (2), but now the l-th term weight is

III. NUMERICAL ESTIMATION
The major problem of Christoffel function calculation is numerical instability. For given observations all polynomial bases give identical results, but numerical stability of calculations is drastically different, because Gramm matrix condition number depend strongly on basis choice. If Q k (x) and Q m (y) are chosen as orthogonal polynomials with orthogonality measure support matching the x and y support then for discrete measures the Gramm matrix posses a good condition number [7]. The numerical library we developed, see [6] Appendix A, is able to manipulate polynomials in Chebyshev, Legendre, Laguerre and Hermite bases directly, what allows a stable basis to be used and calculate the moments to a very high order, see Ref. [3] as an example. The distribution regression problem does not require hundreds of moments as in [3], the d x and d y are typically lower than 10-15 and also should be substantially lower that N and M values respectively. The numerical calculations are typically stable as long as one of four stable bases from Ref. [6] is used.
The algorithm for λ(y|x) calculation is this. For each l calculate: < Q k > (l) j ) moments for k = [0..2d x − 1], then, using polynomials multiplication operation, from these moments obtain Gramm matrix (6) G (l) =< Q q Q r > (l) x for q, r = [0..d x − 1], inverse it and build λ (l) (x), a rational function (the nominator is a constant and the denominator is a polynomial of 2d x − 2 order) as in (7), then calculate the λ (l) (x) at given value of x, save these as the weight for l-th observation of y (l) . Having the weights, conditional on given ) moments for m = [0..2d y − 1], then, using polynomials multiplication operation, from these moments obtain Gramm matrix (9) , inverse it and build λ(y|x) as in (10). If possible y outcomes and their probabilities are required, then solve generalized eigenvalues problem t , the eigenvalues y i provide possible y-outcomes and the weight for each outcome is λ(y One can see that the y-localization at given x is very clear, and the width of non-vanishing area of λ(y|x) track very close the value of randomness parameter R. The quadrature built on λ measure give both: possible outcomes (quadrature nodes) and weights (outcome probability is normalized weight), presented in the Fig. 1 as vertical lines corresponding to specific y-outcome (as we noted above -on quadrature nodes the quadrature weight match exactly Christoffel function value). These calculations can be applied to any kind of distribution, this simple example was used just to demonstrate application of Christoffel function to representation of learned knowledge and to find possible y-outcomes and their probabilities.

IV. DISCUSSION
In this work a Christoffel function approach to distribution regression problem is proposed. The main idea is to use Christoffel function for knowledge representation. Closed form answer (10) is available. The Christoffel function is used twice: first, to build distribution approximation withing a "bag", then to model y-value distribution of these "bags" using Christoffel function value from the first step as the weight for the observation of y.
When required, possible y outcomes and their probabilities, can be calculated by building Gauss quadrature instead of using plain Christoffel function answer (10), the quadrature nodes give possible outcomes and normalized quadrature weights give each outcome probability. The method can be extended from real-value to discrete attributes (the d x and d y should be properly adjusted).
The approach, proposed in this paper, as most Multiple-Instance learning approaches, has two stages. The question arise, whether consistent one stage approach exist. For the case x and y being random variables two one-stage interpolation approaches: least squares and Radon-Nikodym have been have been studied in [3]. Now, let us try to find similar onestage approach, but for random distribution to random variable mapping, same as the (1) problem, we study in this paper. The idea is to convert the problem "random distribution" to "random variable" to the problem "vector of random variables" to "random variable".
The simplest way is to take the moments of random x distribution as "input vector of random variables". Then least squares and Radon-Nikodym approximations from [3] can be directly applied. In contrast with the problem (1): given x, what can we tell about y, this, converted to vector moments problem, would be: given < Q k > x moments of x-distribution (fixed x 0 case can be modeled by NQ k (x 0 )), what can we tell about y? This problem is solvable in one step. The one-step solution is actually almost identical to 2D problem of image grayscale intensity interpolation we have considered in [3]. There is just one major difference: for image interpolation problem we used basis value at specific point of the raster, but now we would have to use as input the < Q k > x moments of x distribution on which we want to estimate output y. The question arise of numerical stability of one-stage method and the problem of data overfitting. While two-stages approach typically effectively have d x + d y elements in basis, the one-stage approach effectively have d x d y elements in basis. By choosing stable basis in [3] we calculated the moments for d x = d y = 100 without catching an instability, so basis dimension should not be an issue, but the question of data overfitting for one-stage method require more research and to be published separately. The major advantage of using Christoffel function for knowledge representation is that it stores pure weights, and data overfitting parameter can be estimated as d x /N on first stage and about d y /M on second stage, so in practical applications the problem can be always identified from the beginning.