extfieldsofstudy:
Physics
Computer Science

text:
Recognition of a person named entity from the text written in a natural language

This work is devoted to the semantic analysis of texts, which were written in a natural language. The main goal of the research was to compare latent Dirichlet allocation and latent semantic analysis to identify elements of the human appearance in the text. The completeness of information retrieval was chosen as the efficiency criteria for methods comparison. However, it was insufficient to choose only one method for achieving high recognition rates. Thus, additional methods were used for finding references to the personality in the text. All these methods are based on the created information model, which represents person’s appearance.

Introduction
Named entity recognition belongs to the category of information retrieval tasks. Nowadays, there are many methods for extracting knowledge from the text. Despite the fact that this problem is relatively new, it is already one of the most important directions in the field of computer technology. A large amount of information in the text is described implicitly. For example, if extracted information relates to the elements of human appearance, maybe it becomes possible to conclude about person's professional activities or habits. However, this task is not always easy as it seems because of the features of natural languages. Usually, the text is written in a free form and, therefore, it is quite difficult to interpret the meaning of words. [1] This paper presents an investigation which method is better for recognition of the appearance elements of a man from the text, composed in a natural language. These two methods were selected for investigation since they are very common and show very good results in practice. In particular, the study was carried by the example of the Russian language. However, it is necessary to bear in mind that latent semantic analysis and latent Dirichlet allocation can be used for a large variety of natural languages.

The information model of person's appearance
First of all, it was necessary to create an information model for providing a research basis. This model should met the following requirements: • Scalability. Requirements could be changed after experiments.
• Model should fit easily into one of the common programming paradigms.
• Visibility. It should be easy to find necessary information. • Fullness. The model should contain detailed description of person's appearance so that it was possible to visualize a human. The frame representation language (FRL) was chosen as a formal description of person's appearance since it has all necessary parameters. Figure 1 shows the information model of person's appearance in FRL. Each slot of the frame has a gender determination procedure, which starts after the slot has been filled. The gender determination process relies heavily on morphological aspects of slot's value. "M" is a predefined set of possible parameters for the appearance model.

Latent semantic analysis and latent Dirichlet allocation
Latent semantic analysis (LSA) is a method for processing text information in a natural language, which examines the dependency of keywords on collection of documents (or sentences). The main purpose is to find a vector of documents, which is as close as possible to the specified keyword. [2] The algorithm of latent semantic analysis is as follows: • Select specified keywords. These keywords should describe the appearance of a person.
• Construct frequency matrix A, in which columns are documents and rows are keywords. Each element of the matrix should represent the occurrence of the keyword in the document. • Apply a TF-IDF method on the basis of a frequency matrix to ensure that results are relevant.
[3] • It is necessary to use singular value decomposition on the basis of a resulting matrix. SVD separates the frequency matrix into a matrix of documents (U), a matrix of keywords (Vt) and a diagonal matrix (S). Latent Dirichlet allocation (LDA) serves the same purpose as LSA -it finds the dependency between the specified keyword and related documents, but in another form. LDA provides the information about how likely each keyword refers to each topic. On the other hand, the result contains probability of the document belonging to one of the topic. [5] LDA takes at least three parameters as an input: • Number of iterations.
• Number of topics.
• Text in a natural language.
• Set of keywords.
The algorithm of this method is as follows: • Compose the list of keywords. These keywords should describe the appearance of a person.
• Assign topic for every word in each document. This assignment can be arbitrary or based on any external signs (in this case, it can be the same frequency matrix as in the LSA method). • Calculate the percentage of topics, which relates to specified document p(t|d) and the probability that the word relates to current topic p(w|t). A specified word relates to the topic with probability: • Repeat the previous iteration of a predetermined number of times.
Both methods have much in common. The performance of these methods is low for the large document collection. Latent semantic analysis treats the text as a set of words that do not have any semantic links; so does latent Dirichlet allocation. However, this approach has an advantage in partial disambiguation from words with several meanings.

Person entity recognition
A person is one the most difficult named entity to recognize in the text. It is very easy to recognize the person if the text contains the name or surname of the entity. Nevertheless, such cases are extremely rare and references to an individual occurs differently. It is necessary to perform pre-processing of the text to increase the accuracy of latent semantic methods. LSA and LDA should perform searching of person's appearance only in documents, which contain such description. [6,9] One common approach is to use contextual rules. Every rule represents a standard regular expression, which is constructs from the training sample as follows: • Any mention of a person should be replaced with a special word {PERSON}.
• If the word in a training sample is an element of a human appearance, it should be set in its initial form. • All other words should be replaced with its parts of speech.
• After processing the entire training sample, similar contextual rules should be combined using special characters. The '?' symbol means that this position can be omitted, the '+' symbol means that the position can be repeated one or more times in a row and the '|' symbol represents logical "or". • Optionally, some phrases can be listed at the end of the training sample, which indicates that the sentence excludes the possibility of containing the entity.
Thus, the outputs are kind of regular expressions, which are applied to the text to define a named entity with it. The next step is to resolve the reference of pronouns in the third person. Reference resolution of pronouns in the third form is one of the most common, but at the same time the simplest case, but completeness of information retrieval receives a great boost. This task can be considered as a problem of binary classification. Therefore, it is a good opportunity to use support vector machines (SVM). The simplest case of SVM was programmed using the linear classifier. Thereby the training sample must be compiled carefully to avoid the case of linear inseparability. [7,8] The list of parameters for support vector machines which were used for training: • Number of sentences between antecedent and anaphora.
• Whether the antecedent is in the nominative.
• Position of the anaphora in the sentence.
• Position of the antecedent in the sentence.
• Number of nouns and pronouns, which are located in sentences with antecedent and anaphora.
• Is the antecedent and anaphora case matches.
• Is the antecedent and anaphora genus matches.
• Is antecedent and anaphora both in a plural or singular form.

Latent semantic methods comparison
All methods, which were mentioned in this paper, were written in Python 3. Pymorphy2 library was used for any morphological operations. It uses the "OpenCorpora" dictionary that counts about million and a half tokens at this moment. A training set for support vector machines consists of five hundred samples. The training set for contextual rules also counts five hundred sentences. Latent semantic analysis and latent Dirichlet allocation do not need any training data.
Let N be a total number of person's appearance elements, and N r -the number of items found by one of the method. These two methods are compared by calculation of the completeness of information retrieval, which is as follows: [10] Experiment results are shown in table 1. Natural language texts used in the experiment were taken from areas that had been used to compile OpenCorpora, such as imaginative literature, blogs, Wikipedia and legal texts. Table 1 shows that if the search is performed only based on text passages that contain person references, the accuracy of recognition will increase greatly. In turn, the latent semantic analysis shows slightly better results for the recognition of human appearance in comparison with latent Dirichlet allocation regardless of the volume of the input information.

Conclusion
Completeness of information retrieval on the subject of human appearance has been investigated using the methods of latent semantic analysis and latent Dirichlet allocation. The completeness of information retrieval was chosen as the efficiency criteria for methods comparison. Both methods have shown quite good results in practice. However, LSA is slighter better than LDA in case of recognition the appearance of a person. Preprocessing the text with finding references to the person greatly increases the accuracy of both methods. The program was written in Python 3 with the usage of pymorphy2 library for morphological analysis. OpenCorpora was chosen as a main dictionary, with the help of which words were put in their normal forms.


extfieldsofstudy:
Computer Science
Mathematics

text:
Compress-and-Estimate Source Coding for a Vector Gaussian Source

We consider the remote vector source coding problem in which a vector Gaussian source is to be estimated from noisy linear measurements. For this problem, we derive the performance of the compress-and-estimate (CE) coding scheme and compare it to the optimal performance. In the CE coding scheme, the remote encoder compresses the noisy source observations so as to minimize the local distortion measure, independent from the joint distribution between the source and the observations. In reconstruction, the decoder estimates the original source realization from the lossy-compressed noisy observations. For the CE coding in the Gaussian vector case, we show that, if the code rate is less than a threshold, then the CE coding scheme attains the same performance as the optimal coding scheme. We also introduce lower and upper bounds for the performance gap above this threshold. In addition, an example with two observations and two sources is studied to illustrate the behavior of the performance gap.

I. INTRODUCTION
The Distortion-Rate Function (DRF) describes the minimum attainable average distortion when recovering an information source compressed to within a target bit rate for asymptotically large blocklength. The setting in which the source sequence is not directly available at the encoder and only noisy observations are provided is referred to as the remote or indirect source coding setting [1,Sec. 3.5]. In general, the optimal coding scheme in the indirect source coding setting depends on the joint statistics of the underlying source and the noisy observations. Therefore, the optimal scheme is not applicable when the encoder is designed without knowledge of this statistics. Namely, the encoder is either unaware of the existence of the underlying source and regards the observed process as the target for compression, or utilizes a general-purpose compression strategy that does not adapt to the underlying source. Under these limitations, the encoder will compress its sequence of observations based on a distortion criterion defined only with respect to this observed sequence. The decoder, having full knowledge of the joint statistics of the underlying source and its observations, estimates the source from the output of the encoder. This compress-and-estimate (CE) scheme was proposed and studied in [2]. In this paper we extend the results of [2] to the Gaussian vector remote source coding problem, thus providing a better understanding of the loss of performance caused by partial system knowledge at the remote encoders.
Previous Work: The indirect source coding problem was first considered in [3], where it was shown that the optimal trade-off between code-rate and distortion is characterized by a single-letter expression, denoted as the indirect DRF (iDRF). Moreover, it was proven in [1], [4] that the iDRF can be achieved by first estimating the remote source from the input to the observer, and then encoding this estimate optimally with respect to the code-rate constraint. Therefore, the optimal indirect source coding scheme can be referred to as the estimate-and-compress scheme. The CE scheme for the indirect source coding setting was introduced in [5] and was motivated by the difficulty in implementing an estimation step before encoding. A single-letter expression characterizing the minimal distortion in the CE setting with multiple encoders was derived in [2]. Moreover, it was shown in [2] that this expression has a closed form expression in the quadratic Gaussian setting of a scalar Gaussian source observed through multiple linear measurements corrupted by Gaussian noise. The optimal rate-allocation across the multiple encoders was considered in [6].
Other works that consider communication with non-optimal encoding due to missing source statistics or codebook information include the oblivious processing channel coding problem of [7], the minimax source coding of [8], and the mismatched encoding problem of [9]. In particular, as explained in this paper, the CE scheme can be seen as a special case of the mismatched encoding problem.
Contributions: In this work, we consider the CE scheme in the quadratic Gaussian setting with a vector Gaussian source. Namely, we consider the minimal distortion in estimating a vector Gaussian source from an encoded version of its noisy measurement, where the encoder employs a source code that is optimal with respect to the noisy measurements under a quadratic distortion. For this setting, we show that the CE scheme is optimal when the code-rate is below a certain threshold that depends on the spectrum of the observed vector. That is, when the code-rate is below this threshold, lack of underlying source statistics causes no penalty in the distortion. Above this threshold, we derive upper and lower bounds on the distortion difference between the CE scheme and the optimal scheme using an inequality between the arithmetic mean and the geometric mean (AM-GM inequality). In addition, we consider an example with two sources and two observations to illustrate the behavior of performance gap. Paper Organization: The remainder of the paper is organized as follows: in Sec II we introduce the problem formulation. The main results are presented in Sec. III. Sec. IV concludes the paper.
Throughout, for the sake of brevity, we only provide a sketch of the proofs in the body text. The complete proofs are available in the appendices.
Notation: We denote [n] = {1, . . . , n} for n ∈ N, and a + = max{a, 0}, for a ∈ R. Also, we define log + (x) as log(max{1, x}). With I L we indicate the identity matrix of size L × L. With diag(v) we indicate the matrix with the elements of v on the diagonal. For a square matrix C, denote by λ l (C) the l th largest eigenvalue. For C positive semi-definite and for k ∈ [rank(C)], we define functions R k (C) and θ k (C, R) as follows: and II. SYSTEM MODEL We consider the indirect source coding setting in Fig. 1 in which an M -dimensional Gaussian source is observed through a vector additive white Gaussian noise (AWGN) channel at a remote encoder. The random source sequence X n = (X n 1 . . . X n M ) is obtained through n i.i.d. draws from the jointly Gaussian distribution with zero mean and covariance matrix I. The remote encoder obtains the noisy observation vector for some A ∈ R L×M , assumed full rank, with noise Z ∼ N (0, σ 2 I L ) ∈ R L . The encoder produces the index m ∈ 1 . . . 2 nR to encode its observation and the index m is noiselessly communicated to a central processing unit that produces the reconstruction sequence X n (m). Given a value R, we wish to determine the minimum average quadratic distortion between the original source sequence X n and its reconstruction X n , normalized over the source dimension M , which is: where the expectation is taken with respect to all source and channel realizations.
Remark II.1. The model in (3) in which X has a general covariance matrix Σ X can be reduced to the case Σ X = I without loss of generality. This is obtained by letting In the following, we assume that the matrix A in (3) is full rank and define r = min{M, L}. We use {λ l , l ∈ [L]} to denote the eigenvalues of AA T , sorted in descending order. Note that the covariance matrix of Y, i.e. Σ Y , and the conditional covariance matrix of X|Y, i.e. Σ X|Y , are respectively obtained as Following (5) where the infimum is taken over all joint probability distributions of Y and X such that the per letter mutual information I(Y; X) does not exceed R.
The iDRF for the model in (3) can be rewritten as where mmse(X|Y) is the minimum mean square error (MMSE) when estimating X from Y, i.e.
The solution of the optimization in (6) through the formulation in (7) results in the classic water-filling assignment of the compression rate for each observation. This solution yields a simple expression for the inverse of the iDRF, which is the rate-distortion function where where θ is chosen so that l D l = D. The expression in (10) shows that, in the optimal compression scheme, (10). In other words, the MMSE error in estimating each source component is controlled by the solution of the water-filling problem so that if the i th eigenvalue is below the water level, no rate is assigned to the compression of the estimate of the i th observation.
Compress-and-Estimate Vector Source Coding: The CE setting [5] considers the remote source coding problem in which each remote encoder compresses its noisy observation sequence so as to minimize a local distortion measure that depends only on the distribution of its observed sequence, and is otherwise independent from the distribution of the underlying source. The CE-DRF is the single letter expression of the distortion that can be attained by the CE coding scheme for the case of an i.i.d. source observed through a memoryless channel. Given a local distortion measure d l and a probability distribution P * Y,Y that satisfies I(Y; Y) = R and Ed(Y l , Y l ) = D(R), where D(R) is the classic distortion-rate function with respect to compressing Y under distortion measure d l , the CE-DRF is defined as where the infimum is over all estimators of X given the noisy reconstructions Y. For the observation model in (3), the quadratic distortion in (4) at the central unit and as a local distortion at the remote encoder, the CE-DRF is expressed as where the joint distribution P Y, Y is described by the backward Gaussian channel Y = Y + UZ, where U is an orthogonal matrix that diagonalizes Σ Y , and the noise Z ∼ N (0,

III. MAIN RESULT
In the following, we derive conditions under which the CE-DRF in the vector quadratic Gaussian setting equals the iDRF. In addition, we derive bounds, both upper and lower, to the performance gap between the CE-DRF and the iDRF. We also provide a two-dimensional example and characterize the performance gap in different regions of R.

A. Conditions for Equality
We begin by deriving the conditions under which the CE-DRF and the iDRF coincide. To do so, we re-write the iDRF as the inverse of the rate-distortion function in (9).
In Prop. III.1, we express D X|Y (R) as a piecewise function of R over the intervals In each one of those intervals, the water-filling solution prescribes for k eigendirections of Σ X|Y to be compressed at the remote encoder. In other words, k in (14) corresponds to the number of D l > θ in (9).
We then obtain an expression of the CE-DRF.
Proposition III.2. When the rate R satisfies the CE-DRF in (12) is obtained as By comparing the expressions in Prop. III.1 and Prop. III.2 we note that, for R ≤ min{R 2 (Σ Y ), R 2 (Σ X|Y )}, the expressions in (14) and (16) are equal. This condition for equality can be generalized as in the following proposition.
The result in Prof. III.3 generalizes a previous result in [5] where equality was shown for the case of L = M = 1. Note that if r 0 = L = M , then we have D CE (R) = D X|Y (R) for any R. The functions D X|Y (R) and D CE (R) are continuous decreasing functions of R. We note that D CE (R) is only smooth between each pair of two rate thresholds, that is in the intervals . Each rate threshold R k (Σ Y ) determines a change in the slope of D CE (R). Despite the fundamental difference between these two functions, in the low rate regime of Prop. III.3 the two functions actually coincide.
Discussion: Note that both the CE and the optimal compression schemes suffer from a distortion mmse(X|Y), which follows from the fact that Y, instead of X, is observed. Moreover, the forward channel between the observation and its reconstruction for both transmission schemes corresponds to a vector additive Gaussian noise channel. In the optimal compression scheme, the noise is added along the eigenvectors of the covariance matrix Σ X|Y , while in the CE scheme the noise follows the direction of the eigenvectors of the matrix Σ Y . This distinction implies that the CE scheme might allocate compression resources to eigendirections which are not useful in estimating the underlying source X. As an example, assume that there exists λ l = 0. Recall (5a), when the l th eigenvalue of AΣ X A T is zero, the l th eigenvalue of Σ Y equals σ 2 , which solely comes from the covariance matrix of noise σ 2 I, and the l th eigenvalue of Σ X|Y satisfies λ l (Σ X|Y ) = λ l /(λ l + σ 2 ) = 0. Hence, the l th components in both optimal and CE settings are pure noise and contain no information of the source. For the optimal scheme, we see that the compression rate allocated for this component is always zero. In other words, the optimal scheme never activates a component that does not contain source information. However, we note that the CE scheme might activate components that are pure noise when R is sufficiently large. This is due to the fact that, in the optimal scheme, the encoder knows the joint statistics and can therefore avoid wasting rate resources on useless observations. In contrast, the encoder in the CE setting cannot recognize a pure noise component since it lacks knowledge of the source. On the other hand, when the rate is sufficiently small, only the largest eigendirection is actively compressed, in which case, perhaps surprisingly, the CE performance equals the optimal performance.

B. Performance Gap
We next upper bound the performance gap between the CE and the optimal performance, defined as for the regimes in which the equality conditions of Prop. III.3 does not hold.
Theorem III.4. The difference between the CE-DRF and the iDRF is bounded as Proof: Only a sketch of the proof is presented here. As an example, assume that there exists an R for which (13) and (15) hold for the same k. As argued above, this implies that the two schemes actively compress the same number of components. For this value of R we have where (20) follows from the classic AM-GM inequality. Through a similar reasoning, the inequality in (19) is obtained by exploiting a reverse AM-GM inequality in [10] to bound the largest difference between the CE and the optimal performance.
Th. III.4 shows that the difference between the CE-DRF and the optimal distortion is upper bounded by a function that decreases exponentially with R/L. To complement the result in Th. III.4, we introduce the following lower bound to the performance gap between the CE and the optimal performance.
Theorem III.5. For R > R 2 (Σ Y ), the difference between CE-DRF and iDRF is lower bounded as Proof: We provide a sketch of proof here. Suppose k satisfies (15). We have The first inequality follows from the fact that k satisfies (15) but not necessarily (13), and hence could be a non-optimal choice for the setting with full knowledge. The second inequality follows from a lower bound on the difference between AM and GM in [11,Sec. II]. Finally, (21) follows by noting the bound on R given in (15) and the fact that λ l 's are in descending order.
Recall that the performance gap can be zero for small R, the lower bound (21) is valid for The results in Th. III.4 and Th. III.5 show that the gap between the CE and the optimal performance decays exponentially in the rate-per-observation, R/L. The upper and lower bounds are always monotonically decreasing but, from numerical observations, they appear to be loose in the region for small R. Nonetheless they correctly capture the asymptotic decrease in the gap between the performance of the two schemes.

C. Two Observations, Two Sources Example
In this section we consider the case with two sources and two observations, i.e. M = L = 2. For brevity, we consider only the scenario Recall that, by the definition in (1), Following the assumption in (23). Given the considerations above, we derive the performance gap in three regions: (i) R ∈ (0, R 2 (Σ X|Y )], (ii) R ∈ (R 2 (Σ X|Y ), R 2 (Σ Y )], and (iii) R ∈ (R 2 (Σ Y ), ∞).
• R ∈ (R 2 (Σ X|Y ), R 2 (Σ Y )]: Here we have (25) In this region, the performance gap increases with R, and the maximal gap is which is achieved at In this case we have We see that in this region, the performance gap decays exponentially in 2R/L = R, which corresponds to the behavior predicted by Th. III.4 and Th. III.5.

IV. CONCLUSION
We have derived the performance of compress-and-estimate (CE) coding for a Gaussian vector, observed at the remote encoder through linear observations and further corrupted by additive white Gaussian noise. In the CE coding scheme, the remote encoder compresses its observation according to a local distortion measure which depends solely on the observation distribution and rate-per-symbol constraint. An estimator receives the encoded observations and uses them to estimate the remote source sequence. For this setting, we showed that when the rate is smaller than a threshold, the CE setting attains the optimal source coding performance. This threshold is obtained as a rather straightforward function of the eigenvalues of the observation matrix. Since the operation at the remote encoder depends only on the distribution of the observation, this result shows instances in which the optimal coding performance can be attained without the full system knowledge at the remote encoder. In addition, we derived upper and lower bounds on the performance gap between the CE scheme and the optimal scheme where the encoder has full knowledge of the underlying source statistics, which shows that the decay in the performance loss is exponential in the rate-per-observation in the region where the rate-per-symbol is large. Finally, for the case of two observations and two sources, a complete characterization of the behavior of the performance gap is derived.


Depth estimation using structured light flow -- analysis of projected pattern flow on an object's surface --

Shape reconstruction techniques using structured light have been widely researched and developed due to their robustness, high precision, and density. Because the techniques are based on decoding a pattern to find correspondences, it implicitly requires that the projected patterns be clearly captured by an image sensor, i.e., to avoid defocus and motion blur of the projected pattern. Although intensive researches have been conducted for solving defocus blur, few researches for motion blur and only solution is to capture with extremely fast shutter speed. In this paper, unlike the previous approaches, we actively utilize motion blur, which we refer to as a light flow, to estimate depth. Analysis reveals that minimum two light flows, which are retrieved from two projected patterns on the object, are required for depth estimation. To retrieve two light flows at the same time, two sets of parallel line patterns are illuminated from two video projectors and the size of motion blur of each line is precisely measured. By analyzing the light flows, i.e. lengths of the blurs, scene depth information is estimated. In the experiments, 3D shapes of fast moving objects, which are inevitably captured with motion blur, are successfully reconstructed by our technique.

Introduction
3D shape reconstruction techniques by projecting special light to objects (i.e., active lighting techniques) have been important research topics. Since they have significant advantages, e.g., a textureless object can be robustly reconstructed with dense and high accuracy irrespective of light conditions, commercial 3D scanners are primarily based on active lighting techniques. Among two important active lighting techniques, such as structured light and photometric stereo, structured light techniques, which encode the positional information of projector pixels into projected patterns, have been widely researched and developed due to their robustness, high precision, and density.
Recently, capturing 3D shapes of moving objects from a moving sensor has become increasingly important, such as measuring a scene from self-driving cars, etc., and solution is strongly desired. The one-shot scanning technique, which is one of structured light techniques, is a promising technique because it required just single image and unaffected by motion. In general, one-shot scanning techniques embed the pattern's positional information into a small area of the pattern for decoding [11,6,10,20], and thus, the projected pattern tends to be complicated to increase robustness and density. If object/sensor motion is faster than an assumption, the reflected patterns are easily blurred out, resulting in unstable and inaccurate reconstruction.
To solve such motion blur problem, one may consider applying an algorithm developed for deblurring photographs. However, although the phenomena look similar, the optical processes are completely different 1 and such algorithms cannot be applied to structured light. In this paper, we analyze the information that is implied in the motion of a projected pattern (hereafter "light flow") to recover the shape. In fact, it is shown that light flows are explained by three factors such as depth, normal, and velocity of the object surface and extracting one of them from a single light flow is impossible, but possible with two light flows. In this paper, we propose a technique to decouple the three values from multiple light flows. It is also revealed that light flows includes only little depth information, and thus, accurate detection of motion blur is required for practical depth estimation. To achieve this, we project the pattern of parallel lines onto the objects so that a blur size is precisely measured as the width of the band of motion blur of each line.
The contributions of this paper is as follows: (1) Depth from light flows, which does not require a decoding process, or a matching process, is presented. (2) Shape recovery of "fast motion," where motion speed is faster than the shutter speed causing blurred patterns, is achieved. (3) Two algorithms using two different patterns are proposed to reconstruct shapes of fast moving objects. By using our technique, multiple fast moving objects, which are almost impossible to scan with state of the art techniques, can be reconstructed, for example, rotating blades of a fan are reconstructed by using a normal camera and a video projector.

Related works
There are two major shape recovery techniques using active light, such as photometric stereo and structured light. Photometric stereo recovers the surface normal of each pixel using multiple images captured by a camera while changing the light source direction [5,4,3,9]. Although photometric stereo can recover surface normals, they cannot recover absolute 3D distances; thus, their applicability is limited. The structured light technique has been used for practical applications [16,22,12]. Two primary approaches to encode positional information into patterns are temporal and spatial encoding. Because temporal encoding requires multiple images, it is not suitable for capturing moving objects [17,18]. Spatial encoding requires only a single image and is possible to capture fast-moving objects [11,6,10,20]. For example, some commercial devices realize 30 fps at VGA resolution [11]. Another technique can scan the shape of a rotating blade [6]. Although such techniques can capture fast moving objects, they still require the patterns to be captured clearly. If the pattern is blurred due to unexpected fast motion, the accuracy is reduced or reconstruction fails. Kawasaki et al. needed to use a high-speed camera to measure a rotating blade [6]. In contrast, our technique uses a different approach, i.e., shapes are reconstructed from motion blur of a projected pattern. This helps to decrease the difficulty for scanning fast moving objects and allows off-the-shelf devices to be used for such extreme conditions. Another limitation of structured light techniques is that they are highly dependent on the locally decoded pattern information. If decoding the positional information fails for some reason, such as noise, specularity, blur, etc., shape reconstruction will subsequently fail. To avoid this limitation, some techniques are based on geometric constraints rather than decoding [15,13,8,20] or active usage of defocus effect by coded aperture [7]. One problem with such techniques is that, because they are heavily dependent on geometric constraints or special devices, strong motion blur cannot be handled.
Our technique uses relationship between two overlapped patterns and such techniques have been researched. The Moire method is a well-known technique where a highfrequency pattern is projected on an objected and is observed by a high-frequency gate, which generates Moire patterns [19,2]. Recently, a technique that uses the intersection of multiple parallel line patterns was proposed to achieve an entire scene reconstruction [1]. Both techniques assume a static scene and recover shape from geometric constraints, whereas our technique recovers shape from a temporal gradient. To the best of our knowledge, no such technique has been proposed previously.
3. Analysis of projected pattern flow

Overview
In this section, we briefly overview information that can be obtained from apparent motion of projected patterns. We assume that the projectors and the camera are relatively static and calibrated. If the object moves, the observed patterns move along epipolar lines. For the target scene, we assume that the regions around the measured 3D points can be regarded as locally planer and depth of the points are changing. Otherwise, we would not be able to observe continuous motions of patterns moving with the scene motions.
Without losing generality, the relationships between the motions of the target surfaces and the patterns can be considered within the epipolar planes. Fig. 1 shows the relationship.
Let the apparent position of the pattern be p, and the apparent motion of the pattern (i.e., light flow) be dp dt . dp dt depends on the surface depth z, surface normal n, and the depth velocity dz dt as shown in Fig. 1. dp dt is proportional to dz dt , and represented as where F is a nonlinear function that can be defined from the projection model and calibration parameters of the projectors and cameras (i.e., the information of the epipolar geometry of the projector-camera pair is included in F ). By limiting the geometry within a epipolar plane, the normal direction at a point on the surface can be represented by a scalar variable, thus, F (z, n) is a 2D real function.
Here, we assume that we have N projectors. The light flows can be observed for each projector.
In case of N = 3, where we use three patterns from three projectors, the observed light flows are dpi dt where i = 1, 2, 3, and we obtain three equations where F i is the same function with Eqn. 1 for pattern i. By eliminating dz dt , we obtain two equations: The unknown variables are z and n, and F 1 , F 2 , F 3 are known functions since they are defined from calibration parameters. Since we have two equations with two unknowns, we can estimate z and n by numerically solving these equations. Note that, from Eqn. 3, geometrical information are obtained from "ratio" of the pattern motions dpi dt / dpj dt (i = j), rather than dpi dt themselves. In case of N = 2, we obtain only one equation by eliminating dz dt , which is dp1 dt / dp2 dt = F 1 (z, n)/F 2 (z, n). Since we have one equation with two unknowns, we cannot determine z, n for this case.
However, if we use additional information such as knowledges of the projected patterns, we can estimate z. As described in the following sections, we propose to use uniformly spaced parallel patterns from "two" projectors to estimate depths. Moreover, we also show a special case of N = 2, where the two patterns are projected from a "single" projector. In the case of single projector, we should use non-uniformly spaced parallel pattens.
In case of N = 1, we use only one pattern, we obtain only dp1 dt = F 1 (z, n) dz dt . Obviously, we cannot solve z, n, dz dt from the form. As explained here, we can estimate depths if we can observe three patterns from three projectors. However, to achieve this, three patterns should be decoupled from captured images, which is not an easy task. One solution may be using three color channels, however, crosstalks between color channels are problematic. On the other hand, decoupling two patterns are relatively stable, since crosstalks between red-blue channels are small. Thus, in this paper, we propose a technique which requires only two colors, i.e. two projection patterns, for shape reconstruction.

Depth estimation with two-pattern case
In this section, we explain depth estimation with two patterns using uniformly spaced parallel lines. To achieve this, we estimate the light flows "in the projectors' image coordinates" instead of in the camera's image coordinates. Then, we can avoid considering normals of the surfaces as shown in the the following discussions.
First, we assume a pixel p while observing a target object from a camera. We define the ray from the camera corresponding to p as r, the intersection between the object and r as s, and the depth of s as z . Thus,  We assume that the object is moving with respect to the camera; thus, depth z changes. Let a small displacement of z be ∆z. Then, the position of s is expressed as follows: s + ∆s = (z + ∆z)r.
(5) Fig. 2 shows the relationships between the symbols used in this section. The projector can be geometrically regarded as an "inverse camera," i.e., the relationship between a 3D coordinate s of point s and the 2D coordinate on the pattern pixel coordinate q that illuminates s can be formulated in the same as the projections of the camera. This can be expressed as follows: where s is the coordinates of s in the camera coordinate system; R and t are the rotation matrix and the translation vector of the rigid transformation from the camera coordinates to the projector coordinates, respectively; and f is a perspective projection function that is the same as the normalized camera. We assume that the pattern image illuminated from the projector is parallel lines that is near the vertical direction, and the epipolar lines are assumed to be near the horizontal direction. Thus, the pattern intensity only varies with the horizontal coordinate, which we define as q h . Then, where f h ((x, y, z) T ) ≡ (−x/z).  Let the relationship between the depth z and q h be substituted by a function g. Thus, Here assume that pattern coordinate q h is changed by ∆q h for a small displacement ∆z of z. ∆q h can be observed as light flow. Then, the ratio between the changes can be approximated by the derivative of g: Function g (z) changes depending on the depth z.
Since two projectors are assumed in this analysis, there are two pattern coordinates for each projector, such as q h1 and q h2 , and two functions for each projector, such as g 1 and g 2 . Thus, can be reduced to Here, function h is defined as follows: where h(z) is a function of z and does not depend on ∆z.
If h(z) is a monotonic function in the domain of the working distances of z, there is an inverse function h −1 for this domain, and depth z can be estimated from the ratio of the two light flows (∆q h1 and ∆q h2 ) as follows: Function h(z) depends on the pixel position p, i.e., for different pixel positions, h becomes different functions. Thus, let h(z) for a pixel position p be expressed as h p (z).
Similarly to F , the information of the epipolar geometry is included in h, where the explicit dependency is based on Eqn. 8.
An example of the camera setup is shown in Fig. 3 (this setup is also used in the later experiments), and h p (z) for this example setup is shown in Fig. 4(a), where p is on a horizontal line in a camera image (including the image center) and the vertical axis represents z. As can be seen, h(z) actually varies depending on z and h −1 p can be defined for each pixel. In real implementation, we can sample pairs of z and the function value h p (z) as {(z, h p (z))|z ∈ {z 1 , z 2 , · · · , z n }} and h −1 p can be approximated by interpolation of the samples. Then, depth estimation can be processed efficiently.
Note that the positional setup of the projector and the camera affects severely to the sensitivity of the depth estimation. For example, an example of a bad setup is shown in Fig. 4(b), where the two projectors are placed in parallel. Although this setup look similar to the setup of Fig. 3, the gradient of h p (z) becomes much smaller, thus, depth estimation using h −1 p becomes much sensitive to observation noises. Specifically, if the projectors and the camera are placed in perfect fronto-parallel configuration, h p (z) becomes constant and h −1 p does not exist. In the proposed method, the required input value is the ratio of the light flows ∆q h1 /∆q h2 , whereas the absolute values of q h1 or q h2 are not required. If the pattern image is repetitive, the depth can be estimated from only the relative local changes as described later. This means that we do not need to encode the absolute pixel position into the pattern image and this is an important advantage of our method.
The light flows are observed as the motion on the image planes of the projectors in Fig. 2, rather than the motion on the image plane of the camera as shown in Fig. 1. Observing light flows on the projectors' image planes is possible if we use knowledge of the projected pattern, such as uniformly spaced parallel lines. As described later, we use the uniform intervals as "scales" on the projectors' image planes. Also, in the discussion of this section, normal directions of the object surface are not considered. This is because the relationships between the light flows and the object motion are considered on the fixed "ray" from the camera along r. h p (z) does not depend on the intrinsic parameters of the projector-camera pair, since the displacements ∆q h1 and ∆q h2 are represented in normalized coordinates. For real measurements, displacements in the units of projector pixels ∆q hp1 and ∆q hp2 are observed instead. The ratio of these values can be converted by where f 1 and f 2 are the focal lengths of the projectors.

Experimental systems 4.1. System configurations
As experimental systems, we have constructed a twoprojector system and single-projector system. For twoprojector system, the projectors and the camera are positioned so that the camera can observe overlapping patterns projected by the projectors. The two projectors project uniformly-spaced parallel lines and because discrimination of the two patterns is required for reconstruction, different colors are used. The setup with two projectors and a camera is shown in Fig. 7(b). For single-projector system, one projector projects two non-uniformly-spaced parallel line sets with different color. The setup with single projector and a camera is shown in Fig. 7(a).
For both systems, the projected patterns are static and do not change; thus, synchronization is not required. The camera and projector(s) are assumed to be calibrated (i.e., the intrinsic parameters of the devices and their relative positions and orientations are known). Depths are estimated by the light flow analysis as already described.

Light flow estimation with two projectors
In the analysis of section 3.2, pattern motion on the projectors' image planes (∆q h1 and ∆q h2 ) were used. To observe these values, we propose to use a uniformly spaced line pattern with constant intervals as "scale" for measuring the pattern motion. In this method, the length of blur is retrieved from the observed image as the width of the band of blurred lines. Then, the ratio of the blur on the projector plane can be calculated by dividing the length by the line intervals on the same image. Since the line intervals are constant on the projector's image plane, the ratio becomes a pattern motion on the projector's image plane.
The blur of the parallel lines are observed only for each lines, thus, the resolution of this approach is relatively sparse. However, it has a great potential to reconstruct extremely fast motion using only a single image.
The method is as follows: The projected pattern is a set of parallel vertical lines. The captured lines projected onto the object move with the motion of the object. The exposure time of the camera is assumed to be set so that the apparent motion of the vertical line of the image is observed as motion blurs of the lines.
Let the width of the motion blur of the line defined as ∆r. ∆r cannot be used directly as ∆q h in Eqn. 9, because ∆q h is a displacement on the projected pattern image, whereas ∆r is a displacement on the captured camera image. If vertical lines at uniform intervals are projected, ∆r can be normalized by the apparent intervals on the camera image and can be used as ∆q h . If the apparent motion blur of the line on a local patch in the camera image is ∆r and the interval between the lines on the same patch is B, then ∆q h can be approximated as follows: In the current implementation, the blur is detected just by simple adaptive binarization. Then, ∆r and B of Eqn. 15 are estimated with sub-pixel accuracy by localizing crossing positions of the profile with the threshold levels of the adaptive binarization (the positions marked by red circles in Fig. 5(e)).
By projecting vertical lines from two projectors in different colors (e.g., red and blue) and by estimating ∆q h1 and ∆q h2 from the different color channels, depth estimation from motion blur becomes possible. Fig. 5 shows the pattern images in (a, b), projected line patterns with motion blurring in (c), an apparent line interval (i.e., B) and a size of blur (i.e., ∆r) in (d), and the light flow estimation by interpolating ∆r/B.
If the target surfaces have object boundaries, the line patterns cannot be detected outside the boundaries. Thus, blurred patterns are disconnected and values of ∆r or B become abnormal at those points. Since the assumption of smooth surfaces are not fulfilled there, we remove these regions. In the current implementation, we specify the upper and lower limits for the intervals B and label pixels as outliers where B exceeds this range. The outlier points are removed from the 3D reconstruction. The boundary points are removed from the reconstruction process using this technique.
The line directions of the pattern are not required to be perpendicular to scan lines. This is because although blur widths ∆r and line intervals B along scan lines are affected by the apparent line directions, the ratio ∆r/B are not affected by the directions.
In this method, the spatial resolution of the light flows is as coarse as the apparent line intervals, but fast-moving objects that are only observable as motion blur can be measured.
About the precision of the method, we can conduct a coarse analysis on depth precision based on Fig. 4(a). Let ∆r and B be 10 and 30 pixels, which is a typical setup of the experiments shown later. Also, let precisions of those values be 1/4 subpixels. Then, the errors of log (∆r)/B is ap- Threshold level of adaptive banalization  proximately 0.049 (we take log because h −1 takes log values). In Fig. reffig:depthfigratiofunc(a), this is about 0.02-0.03m depth errors at 0.5m distance, and about 0.06m depth errors at 1.0m distance.

Light flow estimation with a single projector
We have explained depth estimation method with two patterns projected from two projectors. Now, we consider the special case of two patterns, where the two patterns are projected from a single projector. In this case, depth estimation becomes impossible because of degenerate conditions. Specifically, the function h(z) becomes constant functions for all the camera pixels, thus, h −1 cannot be defined.
Even in this case, by applying different modulation for these patterns, depth estimation becomes possible. For example, we modulate the pattern intervals so that the intervals becomes wide by two times at the right side with respect to the left side (Fig. 6). This modulation is achieved with the mapping of the horizontal coordinate p 0 by p new , are applied. Then, non-constant h(z) can be obtained. With this technique, we can estimate depth using two patterns projected from a single projector with the same algorithm as the two-projectors case.

Evaluation with planar board
The first experiment was conducted with two-projector system ( Fig. 7(b)). The camera resolution was 1600 × 1200  pixels, projector resolution was 1280 × 800 pixels, and the baselines between the camera and the two projectors were both approximately 400mm.
For evaluation, we attached a target board onto the motorized stage, and captured it with the camera while the board was moving under different conditions, such as different shutter speed and different projection pattern. The RMSE was calculated after plane fitting to the estimated depth. Results are shown in Fig.8.
Since the spatial accuracy of the flow estimation with the line pattern is an approximation and is affected by the apparent sizes of the blur bands and the apparent line intervals, we smoothed the flow estimation with Gaussian kernels with σ values of 2, 30, and 60 (the apparent line intervals were around 40 pixels in the experiment.) In the results, we can clearly observe that the increase in the shutter speed improves the RMSE. This is because the longer shutter speed makes the longer bands for blur of lines, which helps to increase the accuracy on estimating the ratio of light flows. Although we also captured data with the shutter speed of 500 ms, the bands began to overlap each other and the depth estimation failed. For the shutter speed of 400 ms, filtering with σ = 60 did not improve the result than the case of σ = 30. This can be because the spatial resolution in the case of 400 ms shutter speed was worse than the case of 300 ms. Fig. 10 shows examples of the actual captured image and reconstructed depth maps with our method. As can be seen, depth are correctly reconstructed just from relative information of flows without coded positions. We also applied the line based technique to textured materials, such as newspaper and RMSE was about 30mm for the shutter speed of 300 ms. This is because our image processing is based on simple thresholding and easily affected by textures; solution is our important future work.
We also recover the moving planar board with four other methods for comparison, such as grid based reconstruction [21], wave based reconstruction [14], random dot based reconstruction, which is equivalent to Kinect [11], and stereo-based reconstruction using two cameras. As clearly shown in the graph, longer shutter speed (equivalent to fast motion) drastically decreases the accuracy, and no technique can recover meaningful shapes when shutter speed exceeds 300 ms.
The above performance decrease of the conventional methods is caused by motion blurred patterns. Fig. 9 show examples of the projected patterns, the real captured images, and the line detection results at the shutter speed of 300 ms. As can be seen, the line detection results become unstable with severely blurred pattern, resulting in failure reconstruction. As for the two camera stereo case, since light flow is view-dependent, which is apparently shown in (i) and (j), it fails to find correspondences for reconstruction (the sizes and directions of the blur are different).

Arbitrary shape reconstruction
We applied our method to object with curved surfaces and fast motion as shown in Figs. 11, 12, and 13.
The first target was a rotating fan using the uniformly spaced line pattern (Fig. 11). As can be seen, the blades are blurred even with the fastest shutter speed (1ms) as shown in (a), whereas a projected pattern made a clear band of blur for each line as shown in (b,c). Using the detected bands and their width, light flows are estimated as (d,e), and depths are correctly reconstructed as shown in (f) using the calculated ratio of the light flows. Note that, in the flow val-ues shown in (d,e) at the "front" parts of the blades (marked by red and black ellipses in (a) and (d)) are larger than the other parts. Because the fan blades are curved so that the air can be accelerated mostly by the front parts of the blade, the changing velocity at these parts are the highest. In this example, boundaries of the fan blades are removed from the reconstruction as outliers as described in Sec. 4.2.
The second target was a thrown ball using the same setup. Similar to the blades, ball has strong blur on captured image ( Fig. 12(a)), whereas the projected pattern made a clear band of blur for each line ((b,c)). Using the detected bands, depths are correctly reconstructed, as shown in overlapped three frames of depth maps in (d). From (d), the motion of the ball moving from the camera can be clearly observed.
Finally, two balls were thrown and shapes are reconstructed by a single projector setup as shown in Fig. 7(a). Fig. 13(a) shows that projected lines were strongly blurred on the target objects, however two color bands are robustly extracted by our algorithm as shown in (b) and (c). Then, shapes are correctly reconstructed as shown in (d). In the next frame, two balls are reconstructed at further distance as shown in (e).

Conclusion
In this paper, we have proposed techniques to reconstruct the shape of fast moving objects which are captured with motion blur of a projected pattern using the ratio of light flows of two projections. With the proposed technique, the distances can be directly calculated from local displacement information. Encoding and decoding of global positional information from the pattern is not required, which is usually a difficult task. We have presented two types of setups, i.e., single and two projectors configurations, to efficiently estimate the light flow and the depth of an object. Our experimental results demonstrate that depth is actually recovered by the ratio of the light flows on several moving objects, such as planar board, rotating fan and thrown ball.
There are, of course, limitations in the proposed method, such as the spatial resolution becoming as coarse as the line intervals. However, this is the first technique which achieves depth estimation only from a flow of projected pattern, which is observed as a blur with the best of our knowledge. In addition, if we use a precision device like laser projector with phase based analysis which can realize high precision pixel detection, it can improve the accuracies and spatial resolution in theory, which will be our future research.


Crowd-Sourced Iterative Annotation for Narrative Summarization Corpora

We present an iterative annotation process for producing aligned, parallel corpora of abstractive and extractive summaries for narrative. Our approach uses a combination of trained annotators and crowd-sourcing, allowing us to elicit human-generated summaries and alignments quickly and at low cost. We use crowd-sourcing to annotate aligned phrases with the text-to-text generation techniques needed to transform each phrase into the other. We apply this process to a corpus of 476 personal narratives, which we make available on the Web.

Introduction
With the tremendous amounts of text published on the Web every day, automatic text summarization is more relevant than ever. Web content must compete for readers' attention, and the existence of click bait links shows that content providers are very aware that a short, appealing summary may be their only chance to attract readers. For the readers' part, summaries stating exactly what a piece of content is about protects them from wasting time on topics that do not interest them.
Research on summarization has long focused on extraction: selecting the most salient sentences from a text without any modifications. These summaries can be incoherent or incomprehensible due to unresolved pronouns and references, and sentences containing irrelevant information (Nenkova and McKeown, 2011), and this is particularly problematic with informal web text. Thus abstractive summarization is critical for the web, with rewriting of extracted sentences, as humans write summaries (Jing and McKeown, 1999).
To develop an abstractive summarization system, we need data: parallel corpora that align extractive summaries with abstractive summaries. Such corpora would allow researchers to develop text-to-text generation approaches to produce abstractive summaries from extractive ones. While there are many summarization copora available, most provide abstractive summaries only (Meyer et al., 2016), extractive summaries only or unaligned abstractive and extractive summaries (e.g., as in (Over et al., 2007;Dang and Owczarzak, 2008)).
In this work, we present an iterative annotation process for producing aligned summaries annotated with text-to-text generation techniques. Figure 1 shows a human-written abstractive summary and human-selected extractive summary from our corpus. The extractive summary suggests the narrator was already uneasy and leaves the reader wondering why. This information is unimportant, but the extractive summary must include it because it is in the same sentence as the bloody woman, just as it must include an extra character: the man in medical attire. Text-to-text generation techniques, such as sentence compression, could be used to rewrite this extractive summary to more closely match the abstractive summary.
Abstractive: While driving home I saw a woman covered in blood standing by the side of the road. As I passed she attempted to launch herself at my car.
Extractive: As I'm looking around as to what the fuck is going on, we approach the roundabout and there is a man in medical attire next to a woman in white pyjamas, with blood covering her clothing. I go straight, and as we go past the woman attempts to launch herself at my car. While the extractive summary contains some extraneous information, it does include every-thing present in the abstractive summary. We use crowd-sourcing with Amazon Mechanical Turk (AMT) to produce our extractive summaries, and workers are given the abstractive summaries as a prompt, ensuring high-quality extractive summaries despite using inexpensive crowd-sourcing. In the next stage of our annotation process, we use AMT workers (Turkers) to align phrases from the extractive summaries to the abstractive summaries. Finally, we use Turkers to annotate the aligned phrases with the five rewriting operations identified by Jing and McKeown (1999) -reduction (compression), combination (fusion), syntactic transformation, lexical paraphrasing, generalization/specification -indicating how best to rewrite each extracted phrase. We make our corpus available on the Web 1 .

Related Work
Text-to-text generation for abstractive summarization is the task of revising extracted sentences using techniques such as sentence compression (Knight and Marcu, 2000;Lin, 2003;Zajic et al., 2007;Liu and Liu, 2009) and fusion (Barzilay and McKeown, 2005). Unfortunately, corpora for text-to-text generation are rare and timeconsuming to produce. Marcu (1999) created a corpus of nearly 7,000 abstractive and extractive summaries of news articles by automatically extracting sentences based on a human-written summary, building a large corpus at the cost of some noise. Murray et al (2005) created a corpus of 61 paired, human-written abstractive/extractive summaries of meeting transcripts, but the gain in summary quality achieved using human annotators is offset by the small size of the corpus.
This work uses personal narratives, widely found on social networks, weblogs, and online forums. The availability of online narrative begins to address a problem facing the text-to-text generation approach to summarization: lack of data. Gordon and Swanson (2009) trained a classifier to identify narratives in blog posts with 75% precision and built a corpus of 937,994 narratives. Ouyang and McKeown (2015) created a corpus of 4,647 narratives collected automatically from Reddit, achieving 94% precision in collecting only narrative text. They argue that the Most Reportable Event (MRE) is the most salient event and thus the shortest possible summary; they annotated a subset of 476 narratives by extracting sentences that referred to MREs.
The Murray et al corpus includes alignments between phrases in the extractive summaries and sentences in the abstractive summaries. However, none of the corpora described above provides an analysis of how a summarizer might transform an extracted phrase into its abstractive form. While corpora exist for some rewrites in McKeown and Jing (1999), such as compression (Ziff-Davis, Filippova and Altun (2013), Kajiwara and Komachi (2016)), fusion (McKeown et al (2010)), and lexical paraphrasing/syntactic reordering (Ganitkevitch et al (2013)), these corpora exist in isolation. A human summarizer may apply multiple rewrites to a single phrase, and our work captures this information with annotations for all of the rewrites over each alignment.

Data Collection
We use the annotated subset of 476 personal narratives in Ouyang and McKeown (2015), although we do not use their annotations.

Stage One: Abstractive Summaries
We partitioned the 476 stories into 7 slices of 68 narratives. The narratives were written for 19 different prompts, which roughly correspond to topics (eg. "Your best 'Accidentally Racist' story?"). We randomly assigned an equal number of narratives from each prompt to each of the seven slices.
We trained four graduate student annotators from our university's Department of English and Comparative Literature. Each was assigned four slices: one in common with each other annotator, and one among all annotators. Each participated in a 30-minute training session: they were told to imagine they were about to tell a story to a friend and wanted to ask, "Did I tell you about. . . ?" They should write one or two sentences to complete the question and include any context they thought necessary for their friend to understand it.
We evaluated interannotator agreement on this task using an AMT HIT (Human Intelligence Task) where Turkers were shown summaries written by two different annotators, but not the narrative itself. We then asked the Turkers to decide whether or not the summaries described the same event, and if so, whether one or both of the summaries contained important information not found in the other. We required Turkers to complete a qualification test before working on the HIT, ensuring they had read and understood the task instructions. The test consisted of pairs of example summaries constructed so that the correct answers to our two questions were clear: the paired summaries were identical except for pieces of extra information that we inserted into one or both summaries. Three Turkers worked on each hit, and we considered a pair of summaries to be in agreement if at least two out of three Turkers indicated that the summaries described the same event.
Abstract A: My neighbor's mom saved me from being kidnapped into a car when I was six.
Abstract B: Someone tried to kidnap me when I was six, but a neighbor's mom grabbed me before they got me.
Abstract A: I ran my mouth off at this rude woman.
Abstract B: I held a door for a lady and she told someone on the phone that I had rudely ran around her.
(b) Disagreeing abstractive summaries. Our annotators achieved 90.38% observed agreement, producing a total of 1088 different abstractive summaries. Figure 2 shows a pair of agreeing and a pair of disagreeing abstractive summaries. With the disagreeing summaries, we see that annotators A and B focused on different aspects of the narrative: A summarized the narrator's confrontation with the rude woman, while B explains why the narrator was angry with the woman. Figure 3 shows a pair of agreeing summaries where Turkers indicated that both summaries contained important information not found in the other summary. We see that annotator A focused on the event's emotional effect on the narrator, while annotator C emphasized the irresponsible friend's bad behavior.

Stage Two: Extractive Summaries
To produce the corresponding extractive summaries, we created another HIT that showed Turkers a narrative, one of its abstractive summaries, and instructions to compose an equivalent summary by selecting as few sentences as possible from the narrative. We once again required Turkers to complete a qualification test before working on our HITs. The test consisted of a single story and abstractive summary, written so that the summary was a word-for-word paraphrase of a single sentence in the narrative that did not overlap with any other sentences. We also required that Turkers be at least 18 years old and have completed at least 10,000 HITs with 98% acceptance on previous HITs. Three Turkers worked on each of our HITs, and Turkers achieved substantial agreement on which sentences they selected: Fleiss's κ of 0.748. Figure 4 shows an extractive summary where they achieved perfect agreement.
Abstractive: At a concert, I grabbed a chunk of dirt in mid-air that was being thrown at a woman, and security thought I was throwing the dirt.  Combining our abstractive and extractive summaries, we have 476 narratives, 408 with two abstractive summaries and 68 with four. For each abstractive summary, we have six extractive summaries, one for each Turker and an additional three created by aggregating the Turkers' summaries: sentences selected by at least one (union), two (majority), and all three (intersect) Turkers.

Stage Three: Phrase Alignments
We used another AMT HIT to produce phrase alignments between the extractive and abstractive summaries. We showed Turkers one of the abstractive summaries produced in Stage One and its corresponding extractive summary produced in Stage Two (using union aggregation). The task was to align phrases between the summaries, and to submit as many alignments as they could find.
To avoid confusing terminology, the instructions referred to the abstractive summary as the "summary" and the extractive summary as the "excerpt." We defined aligning as "matching phrases from the summary with phrases from the excerpt that effectively mean the same things." The HIT interface ( Figure 5), allowed Turkers to select phrases by highlighting, save alignments as they went along, and submit all their saved alignments at the end. Three Turkers worked on each HIT.
As in the previous stages, we required Turkers to complete a qualification test where we showed Turkers one phrase from an abstractive summary and four phrases from the corresponding extractive summary and asked them to decide which of the four extractive options would make a good alignment with the abstractive phrase. We also presented them with a link to a demo of the interface, so that they could try the highlighting and saving functions before working on the actual HIT.

Stage Four: Rewriting Operations
Our final HIT asked Turkers to review the alignments produced in Stage Three, and to identify the rewrite operation(s) involved in transforming the extractive phrase into the abstractive phrase. When performing the task, Turkers were only concerned with one rewrite at a time, and simply had to select whether the presented alignment employed that rewrite or not. We designed our task in this way because an alignment could employ more than one rewrite, and we wanted the Turkers to consider each rewrite independently.
We defined the rewrite operations for the Turkers as follows, and provided examples of each.
• Reduction keeps key parts word-for-word and removes less important information. • Lexical paraphrasing replaces words or word sequences with paraphrases, ie. other words that have the same meaning. • Syntactic reordering changes the grammatical structure (eg. passive vs active).
• Generalization replaces longer strings of detail with shorter, more general descriptions. • Specification replaces short, general descriptions with longer strings of detail. As in Stages Two and Three, we tested the Turkers' understanding of the task before allowing them to work on the HITs. Since we ask about one rewrite operation at a time, we designed separate qualification tests for each rewrite. For each test, we selected one abstractive/extractive summary pair and constructed two different alignment examples where one alignment employed the rewrite in question and the other did not. The Turkers were asked whether or not the rewrite was used in each of the two alignments. For each alignment, we put up four HITs (we combined generalization and specification so that Turkers could choose one or neither, but not both). Table 1 lists each rewrite and how many alignments used it; we include an alignment when at least 2 out of 3 Turkers agreed it used the rewrite. We found that generalization was by far the most popular rewrite operation, and reduction was the least, likely because reduction's definition was the most demanding, as it required word-for-word matching outside of the removed parts. Figure 6 shows an example each of generalization and its counterpart specification from our annotations.

Rewrite Operation Counts
Generalization: Very rarely do I ever get a "thanks" or a smile of appreciation. → I never get any thanks.
Specification: I had the alien abduction dream. → I had a sleep paralysis dream where I was abducted by aliens. Figure 6: Examples of the two most common rewrite operations, generalization and specification.

Discussion
We evaluated our Stage Three and Four data from the Turkers by assigning confidence levels to the alignments and judging annotator agreement on the rewrite labels. It would be difficult to determine interannotator agreement in Stage Three because Turkers could submit any number of alignments of any size for each HIT. Instead, we evaluated on the level of individual alignments. A confident alignment had to agree with another alignment, where two alignments agreed if (1) different Turkers submitted them; (2) the selected abstractive phrases overlapped enough that at least half of the shorter phrase was covered by the overlap; and (3) the selected extractive phrases overlapped enough that at least half of the shorter was covered. A precise alignment does not contain an extractive phrase that was over two sentences long, because the longer the alignment, the more difficult to identify the rewrite components involved. Thus a confident alignment is one where at least two different Turkers aligned the same spans, within a margin of error of a few words, while a precise alignment is one where it is easier to pinpoint the spans where rewrite operations apply.
Out of the 6173 alignments the Turkers produced, 5836 (95%) were confident, 5602 (91%) were precise, and 5281 (86%) were both. When we evaluated the rewrite labels produced for these confident and precise alignments, we found that many were labeled for multiple rewrite techniques at once, indicating that quality phrase transformations often involved stitching together rewrites instead of performing them separately. Figure 7 below displays an example of such an alignment, which was labeled for lexical paraphrasing (3/3 Turker agreement), syntactic reordering (2/3 agreement), and generalization (2/3 agreement). Table 2 further displays the interactions between rewrites in the form of a co-occurence matrix of the five rewrites we tested on AMT, plus fusion, which we identified automatically.

Conclusion
We have presented a new corpus of 1088 aligned abstractive and extractive summaries, totaling 6173 phrase-level alignments, each annotated with rewrite operations, which we make available on the Web. Our iterative annotation process uses trained annotators to generate abstractive summaries and Amazon Mechanical Turk to produce extractive summaries, phrase alignments, and rewrite annotations. We found substantial agreement among annotators and Turkers for all tasks, demonstrating our ability to elicit highquality summaries and alignments despite using inexpensive crowd-sourcing.
Our corpus provides summaries of a very different type of text from the traditional newswire articles: personal narratives, a genre that natural language processing research is just beginning to explore. This data is widely found on the Web and brings challenges such as informal language and extreme content. We hope that others will make use of these aligned, personal narrative summaries and their annotated rewrite operations, which we make available on the Web. Our next step will be to exploit this data to create an abstractive summarization system using text-to-text generation. We also hope that the success of our annotation method, using both trained annotators and crowdsourcing, will encourage other researchers to create similar corpora.


s2fieldsofstudy:
Computer Science
Mathematics

text:
Polynomial-Time Approximation for Nonconvex Optimization Problems with an L1-Constraint

Nonconvex optimization problems with an L1-constraint are ubiquitous, and are found in many application domains including: optimal control of hybrid systems, machine learning and statistics, and operations research. This paper shows that nonconvex optimization problems with an L1-constraint can be approximately solved in polynomial time. We first show that nonlinear integer programs with an L1-constraint can be solved in a number of oracle steps that is polynomial in the dimension of the decision variable, for each fixed radius of the L1-constraint. When specialized to polynomial integer programs, our result shows that such problems have a time complexity that is polynomial in simultaneously both the dimension of the decision variables and number of constraints, for each fixed radius of the L1-constraint. We prove this result using a geometric argument that leverages ideas from stochastic process theory and from the theory of convex bodies in high-dimensional spaces. We conclude by providing an additive polynomial time approximation scheme (PTAS) for continuous optimization of Lipschitz functions subject to Lipschitz constraints intersected with an L1-constraint, and we sketch a generalization to mixed-integer optimization.

complexity. Lenstra (and refinements by subsequent authors) [3,9,10,13,18] showed that the integer linear program (ILP) given by min{c ′ x | Ax ≤ b, x ∈ Z n } with c ∈ Q n , b ∈ Z m , and A ∈ Z m×n can be: (1) solved in polynomial time in the number of constraints m when the dimension n is fixed, and (2) solved in polynomial time in dimension n when the number of constraints m is fixed. A related result [20] shows the ILP given by min{c ′ x | Ax = b, x ∈ Z n + } with c ∈ Q n , b ∈ Z m , and A ∈ Z m×n can be solved in psuedopolynomial time when the number of constraints m is fixed. More recently, it has been shown that integer polynomial optimization min{p(x) | Ax ≤ b, x ∈ Z n }, where p(x) is a polynomial satisfying certain properties, can be approximately [6,12] or exactly [7] solved in polynomial time for fixed dimension n.
However, little is known about which other classes of integer programs can be solved in fixed-parameter polynomial time. This paper proves that nonlinear integer programs of the form can be solved in polynomial-time oracle complexity for fixed values of λ ∈ R + , where · 1 is the usual ℓ 1 -norm. Such constraints are common in integer programs: For instance, capacity constraints like {x : x ≥ 0, ∑ i x i ≤ λ } are equivalent to {x : If the functions f , g can be computed in polynomial time, such as linear or (possibly non-convex) quadratic functions, then our result implies (1) can be solved in polynomial (in simultaneously both the dimension n and number of constraints) time for fixed λ . This is in contrast to past algorithms [3,6,7,9,10,12,13,18] that only apply to integer programs with polynomial objective and linear constraints and (depending on the algorithm) are polynomial in either dimension (for fixed number of constraints) or number of constraints (for fixed dimension). Section 2 covers preliminaries, and Section 3 develops our algorithm to solve (1). We prove the number of integer-valued vectors in the scaled ℓ 1 -ball is upper-bounded by a polynomial in n using stochastic process theory, and this new result is used to show that our algorithm has polynomial complexity when applied to problems with (weighted) L1-constraints. Next, Section 4 gives an algorithm to compute a polynomial or exponential in n upper bound on the number of oracle operations required to solve a given integer program min{ f (x) | g(x) ≤ 0, x ∈ Z n } for when: g is a convex function that can be optimized in polynomial time, and the continuous relaxation of the feasible set {x : g(x) ≤ 0} is bounded. Section 5 presents a side result in which we provide an additive polynomial time approximation schemes (PTAS) for optimizing where f , g are Lipschitz: for all i and some κ ∈ R + . This generalizes results that give a PTAS for optimization of Lipschitz functions [4] or polynomials [5,15] over the continuous unit simplex.

Preliminaries
Let R n , Q n , Z n , and N n be the set of n-dimensional real-, rational-, integer-, and natural number-valued vectors, respectively, where the natural numbers are N = {0, 1, . . .}. Recall the usual inner product g, x = ∑ j g j x j , and let • be the Hadamard or elementwise product operator, such that z = x • y ⇐⇒ z i = x i · y i , ∀i ∈ [n]. We use the ℓ p norm notation: to be the unit ℓ 1 -, ℓ 2 -, and ℓ ∞ -balls centered at the origin, respectively. For any λ ∈ R + and set K ⊂ R n , the scaled set is λ K : If K, D ⊂ R n are convex sets, then the covering number of K by copies of D is defined as the quantity where #V is the cardinality of the set V , and ⊕ denotes the Minkowski summation operator defined as A related value is the packing number of K by copies of D, which is defined as the quantity A basic inequality [2] relating these two quantities is P(K, 2D) ≤ N(K, D) ≤ P(K, D).

Polynomial-Time Solvability with a Bounded L1-Constraint
This section shows (1) can be solved in polynomial time for fixed λ . We use stochastic process theory and the theory of convex bodies in high-dimensional spaces to characterize the complexity of scaled ℓ p -balls, which we then use to upper bound the number of integers within scaled ℓ p -balls centered at the origin. Surprisingly, we find that the number of integers in the scaled ℓ 1 -ball is polynomial in dimension when the radius of the ball is fixed, which is in sharp contrast to the number of integers within the scaled ℓ ∞ -ball. We use this result to design an algorithm to solve (1), and we prove its polynomial-time complexity. Our algorithm is then generalized to integer programs with a weighted L1-constraint.

Characterizing the Integer Complexity of Lp-Balls
Covering numbers provide one useful measure of the complexity of a set in Euclidean space. Exactly determining covering numbers is difficult, but fortunately stochastic process theory provides several approaches for bounding the covering number. One approach is Sudakov's minoration [17,22,24], which relates the covering number of a symmetric convex set K to its Gaussian mean width:

Proposition 1 (Sudakov's Minoration [22])
Let K ⊂ R n be a symmetric convex set, and recall that N(K, rB 2 ) is the covering number of K by ℓ 2 -balls with radius r. We have the bound where g ∈ R n is a vector whose entries are iid Gaussian random variables with zero mean and unit variance.
Another useful approach is a basic volume-based inequality [24] for bounding the covering number; however, these bounds can be loose.

Proposition 2 (Volume Estimate of Covering Number [24])
For any symmetric convex sets K, D ⊂ R n we have .
When K/λ = D/r, this simplifies to ( λ r ) n ≤ N(λ K, rK) ≤ (2 + λ r ) n . The above approaches for bounding the covering number of a symmetric convex set can be used to derive bounds for the ℓ 1 -, ℓ 2 -, and ℓ ∞ -balls. Asymptotic bounds are found in [24], but we need non-asymptotic bounds for our purposes.

Proposition 3
Recall that λ B 1 , λ B 2 , and λ B ∞ are the ℓ 1 -, ℓ 2 -, and ℓ ∞ -balls centered at the origin and with radius λ . If r ≤ λ , then we have The upper bounds hold unconditionally, that is for all λ ≥ 0.
Proof Since λ B 1 is symmetric and convex, we can upper bound its covering number using the Sudakov minoration. The first step is to compute the Gaussian mean width, which is achieved by noting that Hölder's inequality and the symmetry of λ B 1 give where we have used the elementary bound max j |g j | ≤ √ 2 log n. Combining this with Sudakov's minoration (5) gives which simplifies to N(λ B 1 , rB 2 ) ≤ n (λ / √ 2r) 2 . The upper bound follows by noting The lower bound is given in [24], and the argument is that one copy of rB 2 is needed for each vertex of λ B 1 .
Bounds for the covering number of λ B ∞ follow from the simplified expression in Proposition 2 for the situation where An upper bound for the covering number of λ B 2 follows by noting

and a lower bound follows by noting
This says the number of ℓ ∞ -balls we need to cover an ℓ 1 -ball is polynomial in n for fixed λ /r. This is significant because in general (e.g., the ℓ ∞ -balls) covering an n-dimensional convex body requires an exponential in n number of balls.
The reason for our interest in covering numbers is that they can be used to count the number of integers within a convex set. In particular, we have the bounds: Proof The upper bound follows if we can show that two integer-valued vectors cannot lie within the same 1 2+δ B ∞ covering-ball. To prove this, suppose the opposite is true. Then there exists some point o such that u, v are two integer-valued vectors with The above result can be used to bound the number of integer-valued vectors within the ℓ 1 -, ℓ 2 -, and ℓ ∞ -balls.

Remark 3
The relevant outcome for our purposes is that #(λ B 1 ∩ Z n ) is polynomial in n when λ is fixed. As is well known, the above result says that #(λ B ∞ ∩ Z n ) is exponential in n. Our bounds for the ℓ 2 -ball are ambiguous, though we conjecture that #(λ B 2 ∩ Z n ) is exponential in n.
Remark 4 A simplified set of bounds for λ ≥ 1 implied by the above theorem are Algorithm 1 Solve L1-constrained integer programs To show ϕ is bijective, observe that it can be written as ϕ(u) = Mu − e 1 where M is a lower bidiagonal (square) matrix with 1 on the main diagonal and −1 on the diagonal below, and e 1 is a vector whose first entry is 1 and the remaining entries are 0. The matrix M can be seen to have full rank, and so ϕ must be bijective. The computational complexity follows because we perform one subtraction operation per entry of the result vector, which has dimension k. ⊓ ⊔ Theorem 2 Algorithm 1 solves (1) in O(n ((2+δ )⌊λ ⌋) 2 /2+1 ) oracle steps, for any δ ∈ (0, 1) and where computing f , g comprises a single oracle step.
Proof Recall that #(λ B 1 ∩ Z n ) ≤ n ((2+δ )⌊λ ⌋) 2 /2 by Corollary 1, the sets M ⌊λ ⌋+1 n , SignPerm(h) are of finite cardinality and such that each single combination can be computed in O(1) oracle time [16,23], and computing v requires O(n) oracle time by Lemma 1. Hence it suffices to show that Algorithm 1 will enumerate over every point x ∈ λ B 1 ∩ Z n exactly once. Let A be the set of points that are enumerated by Algorithm 1. Suppose x ∈ A then by the second inner loop this must mean that |x| ∈ A. Since |x| = ϕ(u) for some u ∈ M ⌊λ ⌋+1 n this means by Lemma 1 that ∑ n i=1 |x| i ≤ λ . Hence x ∈ λ B 1 ∩ Z n and A ⊆ λ B 1 ∩ Z n . Now suppose x ∈ λ B 1 ∩ Z n , then |x| ∈ λ B 1 ∩ N n . By Lemma 1, ϕ is bijective: Therefore, there exists a unique u ∈ M ⌊λ ⌋+1 n such that u = ϕ −1 0 (|x|). Since Algorithm 1 iterates over all u ∈ M ⌊λ ⌋+1 n , |x| must be generated by some iteration of the second inner loop. Hence λ B 1 ∩ Z n ⊆ A, and so A = λ B 1 ∩ Z n since we have shown both set inclusions. Note that since ϕ is a bijection and each permutation vector in SignPerm is distinct, this means each point cannot be enumerated more then once.
⊓ ⊔ Remark 5 A simplified result implied by the above theorem is that the oracle complexity is O(n 4λ 2 +1 ).

(Non-convex) Integer Quadratically-Constrained Quadratic Program (IQCQP):
If Proof Using the result of Theorem 2 it suffices to compute the time complexity of the oracle for f , g to determine the overall time complexity of each instance, which will result in the form O((P(n, m, s) + ns) · n ((2+δ )⌊λ ⌋) 2 /2 ), where P is a polynomial of n, m, s and O(ns) is the arithmetic complexity for generating each iteration by Lemma 1 and [16,23]. For ILP, since the dot product of two vectors in Q n can be computed in O(s 2 n) time and g is comprised of m constraints this means that the complexity f , g is of order O(s 2 mn) and hence the resulting complexity bound. For IQP, since resolving quadratic forms of matrices in Q n×n requires time complexity of O(s 2 n 2 ) we obtain that the complexity of evaluating f , g is of order O(s 2 mn 2 ). Likewise, for IQCQP the time complexity of resolving the quadratic constraints dominates the complexity of evaluating the objective function, hence the time complexity of resolving this oracle is O(s 2 mn 2 ). ⊓ ⊔ Remark 6 A simplified result from the above corollary is that the arithmetic complexity is: O(s 2 mn 4λ 2 +1 ) for ILP, and O(s 2 mn 4λ 2 +2 ) for IQP and IQCQP.

Algorithm for Solving Weighted L1-Constrained Integer Programs
The algorithm and analysis in the previous section easily generalize to the case of an integer program with a weighted L1-constraint: If we define the effective dimension n = ∑ i 1(w i ≤ λ ), the effective radius µ = λ /(min i w i ), and the effective decision variable y ∈ Z n with a bijection between the components of y and the non-zero components of x (i.e., x i such that w i ≤ λ ); then we can rewrite this problem as where M gives the bijection (i.e., x = My). We can then solve this problem by applying Algorithm 1, and similar results to Theorem 2 and Corollary 2 can be shown but with n and µ taking the place of n and λ .

Bounding the Running Time of a Given Integer Program
Here, we provide a polyomial-time algorithm to generate upper bounds on the number of oracle operations required to solve an integer program with a bounded feasible region and convex constraints g(x) that can be optimized in polynomial time. Let C = {x : g(x) ≤ 0} be the continuous relaxation for the feasible region of (16). Our algorithm is deterministic and provides bounds that are polynomial or exponential in dimension n. The trivial bound on complexity for when the feasible region lies within λ B ∞ is (1 + 2⌊λ ⌋) n (see Corollary 1), and our algorithm can potentially provide polynomial in n bounds for specific problem instances. Algorithm 2 describes our procedure. The intuition is that the algorithm finds a radius ρ such that ρB 1 covers C, and then bounds the oracle complexity using Theorem 2. When the feasible set C is nonnegative (i.e., C ⊂ R n + ), the minimum radius is readily computed by solving max x ∑ i x i g(x i ) ≤ 0 . When C is general (i.e., C ⊂ R n ), directly finding the minimum radius is difficult in this case. So the algorithm takes a different approach: It performs a change of variables x = u − v where u, v ≥ 0, computes bounds on u, v, and converts (16) into another instance of (16) with a nonnegative feasible region. The correctness and polynomial-time complexity of Algorithm 2 is given by the following result: Theorem 3 Suppose C ⊂ R n is bounded, and that g(x) can be optimized in polynomial time. Then Algorithm 2 runs in polynomial time, and the value bnd computed by the algorithm is an upper bound on the oracle complexity for solving (16).
Proof This algorithm runs in polynomial time because it consists of solving 2n + 1 convex optimization problems with at most 2n variables, each of which can be solved in polynomial time by assumption on g and the linearity of the objective functions. Next we prove that the value bnd provides an upper bound on the oracle complexity.
where the last equality holds since s,t ≥ 0. And l, u are constructed so that for all x ∈ C: if s = max{x, 0} and t = max{−x, 0}, then we have x = s − t with 0 ≤ s ≤ u and 0 ≤ t ≤ l. Hence we have max Thus C ∩ Z n ⊆ ρB 1 ∩ Z n for ρ as defined in the algorithm. This means we can solve (16) by using Algorithm 1 to solve (1) with ρ ≡ λ , and so the oracle complexity for solving (16) is bounded by the rate given in Theorem 2. ⊓ ⊔ Remark 7 When C lies in a single orthant, the value ρ is tight in the sense that Remark 8 Algorithm 2 can be modified to return simplified bounds by changing the last statement of the algorithm to "bnd := n 4ρ 2 +1 ".
The next proposition shows that our algorithm returns non-trivial bounds. More specifically, it returns polynomial bounds for some instances of (16) and exponential bounds for other instances of (16).
y − x ∞ ≤ ε/κ. Thus the set of all points x generated by the algorithm are the centers of (ε/κ)B ∞ copies that form a covering of λ B 1 .
⊓ ⊔ Remark 11 A simplified result implied by the above theorem for ε > 0 is that the oracle complexity is O(n 4(λ κ/ε) 2 +1 ) Remark 12 Algorithm 3 can be suitably modified, as in Section 3.3, to solve minimization problems with weighted L1-constraints.

Conclusion
Using a geometric argument based on stochastic process theory and the theory of convex bodies in high-dimensional spaces, we showed the number of integers within a scaled ℓ 1 -ball is polynomial in dimension when the radius of the ball is fixed. This result was used to develop an algorithm that solves L1-constrained integer programs and has oracle complexity that is polynomial in dimension when the radius of the L1-constraint is fixed. Our result implies polynomial (in both the dimension of the decision variables and constraints) arithmetic time complexity for instances of integer programming with fixed radius L1-constraints and polynomial-time computable objective function and constraints (e.g., problems where the objective and constraints are linear or quadratic). Next we used these results to develop a polynomial-time algorithm that generates polynomial or exponential in dimension bounds on the oracle complexity for solving integer programs with convex constraints, and an additive PTAS for continuous optimization of problems with Lipschitz objective and Lipschitz constraints intersected with an L1-constraint.