Fabien Lauer

On the exact minimization of saturated loss functions for robust regression and subspace estimation

This paper deals with robust regression and subspace estimation and more precisely with the problem of minimizing a saturated loss function. In particular, we focus on computational complexity issues and show that an exact algorithm with polynomial time-complexity with respect to the number of data can be devised for robust regression and subspace estimation. This result is obtained by adopting a classification point of view and relating the problems to the search for a linear model that can approximate the maximal number of points with a given error. Approximate variants of the algorithms based on ramdom sampling are also discussed and experiments show that it offers an accuracy gain over the traditional RANSAC for a similar algorithmic simplicity.

Introduction

Robust estimation is a classical problem raised by the presence of outliers in the data. Such outliers are points that do not coincide with the underlying data distribution being learned and that must be rejected in order to estimate an accurate model. A standard approach, entering the statistical framework of redescending M-estimators [START_REF] Rousseeuw | Robust regression and outlier detection[END_REF][START_REF] Rousseeuw | Robust regression and outlier detection[END_REF], relies on the minimization of a saturated loss function. Indeed, this saturation ensures that outliers yielding gross errors have a very limited influence on the estimation as the gradient of the loss at these points is zero. However, saturated loss functions are inherently nonconvex and their minimization is a highly nontrivial task. For some applications, suboptimal solutions or other heuristics such as the RANdom SAmple Consensus (RANSAC) [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF] can provide satisfactory models. Yet, robust estimation problems also appear for instance iteratively in a bounded-error framework for problems where the data is assumed to be generated by a collection of models with unknown assignments of the data points to the models, such as in switching linear regression [START_REF] Bemporad | A bounded-error approach to piecewise affine system identification[END_REF][START_REF] Bako | Identification of switched linear systems via sparse optimization[END_REF][START_REF] Lauer | On the complexity of switching linear regression[END_REF][START_REF] Lauer | Hybrid System Identification: Theory and Algorithms for Learning Switching Models[END_REF] or subspace clustering [START_REF] Vidal | Subspace clustering[END_REF][START_REF] Liu | Robust recovery of subspace structures by low-rank representation[END_REF][START_REF] Bako | Subspace clustering through parametric representation and sparse optimization[END_REF]. In such applications, the models are often estimated one by one while considering the data assigned to other models as outliers. In this context, relying on suboptimal solutions can lead to highly unsatisfactory results with many misclassifications of data points. Robust methods based on convex relaxations [START_REF] Liu | Robust recovery of subspace structures by low-rank representation[END_REF][START_REF] Bako | Subspace clustering through parametric representation and sparse optimization[END_REF][START_REF] Bako | Analysis of a nonsmooth optimization approach to robust estimation[END_REF] or iteratively hard-thresholding [START_REF] Bhatia | Robust regression via hard thresholding[END_REF] offer some guarantees but are only optimal under particular conditions on the data.

Instead, in this paper, we aim at unconditional optimality and discuss the computational complexity of globally minimizing a saturated loss function for the robust estimation of linear models, let it be regression ones or subspaces. In particular, the paper focuses on the question of the existence of an algorithm with a polynomial time-complexity with respect to the number of data, N . To this end, we devise an algorithm by enumerating all classifications of the points into two categories: those for which saturation of the loss occurs and those for which it does not. This classification point of view is also motivated by the equivalent formulation of the problem as the maximization of the number of points approximated by a linear model with a bounded error combined with the minimization of a standard (non-saturated) loss over these points only. Indeed, this leads to the distinction between points with error less than and greater than a predefined threshold. Since there are 2 N binary classifications of N points, such a combinatorial approach based on the enumeration of all of them yields an algorithm with exponential complexity in O(2 N ). Yet, we adopt its classification viewpoint and show that the number of classifications, and thus the complexity, can be reduced to a polynomial function of N . From this classification viewpoint, the minimization of a saturated squared loss for regression can be related to the least trimmed squares estimator [START_REF] Rousseeuw | Robust regression and outlier detection[END_REF], for which exact algorithms with polynomial complexity wrt. N have been proposed in [START_REF] Hössjer | Exact computation of the least trimmed squares estimate in simple linear regression[END_REF]; [START_REF] Li | An algorithm for computing exact least-trimmed squares estimate of simple linear regression with constraints[END_REF]. However, these are restricted to problems with a single variable (one-dimensional data) and work with a fixed number of inliers rather than an error threshold.

While a polynomial complexity appears convenient, the degree of the polynomials can limit the applicability of the exact algorithms. Therefore, we also briefly discuss approximate variants of the algorithms devised to leverage the computational load by avoiding the complete enumeration of the classifications through random sampling.

Notation We write vectors in lowercase bold letters and matrices in uppercase bold letters. We define sign(u) as taking value +1 if and only if u ≥ 0 and -1 otherwise. sign 0 (u) is defined similarly except that sign 0 (0) = 0. The indicator function 1 A is 1 when the Boolean expression A is true and 0 otherwise.

Paper organization Section 2 gives the precise formulations of the regression and subspace estimation problems we consider. Then, Section 3 shows how these can be solved in polynomial time with respect to N . Section 4 discusses the approximate variants of the algorithms and Section 5 provides a few numerical results. Finally, Section 6 gives concluding remarks.

Problem formulation

In general terms, in an estimation problem, one can fit a model to the data by minimizing a loss function of the error between the model output and the data.1 For instance, standard loss functions include the p -losses defined for p ≥ 0 and all values of the error e ∈ R as

p (e) = 1 |e|>0 , if p = 0 |e| p , if p ∈ (0, +∞). (1)
Here, we concentrate on robust estimation in the presence of outliers and formulate the problem in terms of a saturated loss function p, : R → R + , defined for p ∈ {0, 1, 2} by

∀ > 0, p, (e) = 1 |e|> , if p = 0 (min(|e|, )) p , if p ∈ {1, 2}.
(2) Indeed, saturating the loss function limits the influence of outliers in the overall cost function to be minimized and thus on the resulting estimate. The statistical properties of these types of loss functions have been studied in the framework of redescending M-estimators, see e.g., [START_REF] Rousseeuw | Robust regression and outlier detection[END_REF]. For p = 0, this approach is also related to bounded-error estimation. Indeed, we can equivalently view it as the maximization of the number of points for which the error is small and below the threshold . For p > 0, a similar viewpoint can be taken with the additional feature that the small errors are measured by a standard p -loss function and further minimized.

In this paper, we will focus the discussion on the corresponding optimization problem whose difficulty comes from the nonconvexity of the saturated losses.

The computation of the argument e as a function of the model parameters and the precise form of the optimization problem depends on the specific problem considered and will be detailed next for regression and subspace estimation.

Robust regression via saturated loss minimization

The aim of linear regression is to estimate a linear model f (x) = w T x from a data set {(x i , y i )} N i=1 of regression vectors x i ∈ R d and target outputs y i ∈ R. Here, we adopt an error-minimizing approach and more precisely focus on saturated loss functions as defined above in order to confine the influence of outliers on the global cost. Let us define the index sets I = {1, . . . , N } and

I 1 (w) = {i ∈ I : |y i -w T x i | < }, (3)
before formally stating the robust regression problem we consider.

Problem 1 ( p, -linear regression). Given a data set {(x i , y i )} N i=1 ⊂ R d × R and a threshold > 0, find a global solution to min

w∈R d J p (w), (4)
where

J p (w) = N i=1 p, (y i -w T x i ) (5) =      N -|I 1 (w)|, if p = 0 i∈I1(w) |y i -w T x i | p + p (N -|I 1 (w)|), if p ∈ {1, 2} .
The formulation of Problem 1 emphasizes the connection between saturated loss minimization and bounded-error estimation, i.e., the maximization of the number of points approximated with a bounded error that are here marked with index in I 1 (w).

This also draws a connection with the classification problem of separating between points that are approximated with a bounded error by an optimal model and those that are not. In particular, given the solution to this classification problem, i.e., I 1 (w * ) for some global minimizer w * of J p (w), a (perhaps different2 ) global solution ŵ can be recovered by solving Problem 1 under the constraint I 1 (w) = I 1 (w * ). Then, for p = 0, J p (w) is a mere constant and it suffices to find a w such that |y i -w T x i | < for all i ∈ I 1 (w * ) to satisfy the constraint. Conversely, for other values of p, the cost function J p (w) simplifies to a sum of error terms over a fixed set of points plus a constant. Hence, its minimization amounts to a standard regression problem with a non-saturated loss and we can compute ŵ by solving ŵ ∈ argmin

w∈R d      max i∈I1(w * ) |y i -w T x i |, if p = 0 i∈I1(w * ) |y i -w T x i | p , otherwise. (6)
Such standard problems have polynomial complexities in O(d 2 N ) for p = 2 and O(d 4 N 4 ) for p ∈ {0, 1}.

Robust subspace estimation via saturated loss minimization

A d s -dimensional subspace of R d can be thought of as the column space of a d × d s matrix B with orthonormal columns. In this case, the projection of a vector x ∈ R d onto the subspace can be written as BB T x and the corresponding scalar approximation error as (I -BB T )x . Therefore, subspace estimation from a data set {x i } N i=1 with a fixed subspace dimension equal to d s can be set as the search for a matrix B ∈ R d×ds such that B T B = I and that the approximation error is minimized over the data set. In the presence of outliers, a robust estimation can be obtained from the minimization of a saturated loss function (as defined in (2)) of this approximation error.

For any B ∈ R d×ds , we define the index set

I 1 (B) = {i ∈ I : (I -BB T )x i < }, (7)
in order to state the problem of robust subspace estimation as follows.

Problem 2 ( p, -subspace estimation). Given a data set {x i } N i=1 ⊂ R d , a subspace dimension d s and a threshold > 0, find a global solution to min

B∈R d×ds J S p (B), s.t. B T B = I, (8)
where

J S p (B) = N i=1 p, (I -BB T )x i (9) =      N -|I 1 (B)|, if p = 0 i∈I1(B) (I -BB T )x i p + p (N -|I 1 (B)|), if p ∈ {1, 2}.
As for robust regression, our formulation emphasizes the classification point of view: if the classification of the point indexes into I 1 (B * ) was known for some optimal B * , a (possibly different) global solution B to Problem 2 could be obtained by solving a more simple subspace estimation subproblem of the form B ∈ argmin

B∈R d×ds      max i∈I1(B * ) (I -BB T )x i , if p = 0 i∈I1(B * ) (I -BB T )x i p , otherwise (10)
s.t. B T B = I.
For instance, for p = 2, the solution to ( 10) is computable in O(d 2 N ) time via the singular value decomposition of the matrix X 1 made of the data points x i with index i ∈ I 1 (B * ) as columns, X 1 = U ΣV T , by extracting a subset of columns u k from U : B = [u 1 , . . . , u ds ].

Exact algorithms with polynomial time-complexity with respect to N

We now turn to the analysis of the computational complexity of Problems 1-2 wrt. N , i.e., for a fixed data dimension d. In particular, we will show that, under simple assumptions on the genericity of the point distributions, these complexities are no more than polynomial.

Assumption 1. In Problem 1, the points {[y i , x T i ] T } N i=1 ∪ {0} are in general position, i.e., no hyperplane passing through the origin of R d+1 contains more than

d points from {[y i , x T i ] T } N i=1 .
Assumption 2. In Problem 2, the points {x i } N i=1 are in general position, i.e., no hyperplane of R d contains more than d of these points.

Sections 3.1 and 3.2 will prove the existence of exact algorithms that run in polynomial time for Problems 1 and 2. In both cases, these algorithms will be devised with the following approach. As discussed above, thanks to the formulations ( 5) and ( 9) expressing the objective functions in terms of the index sets I 1 (w) and I 1 (B) of points with error less than , we can compute an optimal solution ŵ or B from the knowledge of the optimal set I * 1 = I 1 (w * ) or I * 1 = I 1 (B * ). Thus, the algorithm can perform a combinatorial search for the index set I * 1 rather than a continuous optimization over w or B. The number of sets I 1 ⊆ I being finite, we can enumerate them and compute the optimal continuous variables and objective function values for each one of them with the guarantee of finding a global solution. The main difficulty with this approach is that the number of sets I 1 ⊆ I is 2 N and thus exponential in N . However, we will show below that the sets I 1 (w) and I 1 (B) can be obtained via linear classification for any w and B and that all the corresponding linear classifications can be enumerated in polynomial time wrt. N .

This reduction to a polynomial complexity is based on recent results from [START_REF] Lauer | On the complexity of piecewise affine system identification[END_REF], where it is shown that the number of hyperplanes producing different classifications of N points is on the order of O(N d ) in R d and that the complexity of constructing these hyperplanes is of a similar order, i.e., all hyperplanes can be computed in O(N d ) operations.3 More precisely, we will need an adaptation of these results, stated as Proposition 1 below, in order to deal with linear instead of affine classifiers and to work under less restrictive conditions on the distribution of the points. Indeed, Proposition 3 in [START_REF] Lauer | On the complexity of piecewise affine system identification[END_REF] requires the points to be in general position to avoid having too many (i.e., a number proportional to N ) undetermined classifications of points lying exactly on the separating hyperplane. In our framework below, we apply this proposition not to data points but to their projection in a space where this assumption cannot hold. Hence, we will instead prove that the number of projected points falling on the hyperplane cannot exceed a certain constant if the original data points are in general position and build the algorithm to explicitly deal with these points.

Proposition 1. For any binary linear classifier h(x) = sign(h T x), h ∈ R d , and any finite set of

N ≥ d points S = {x i } N i=1 , there is a subset of points S h ⊂ S of cardinality |S h | = d -1 and a separating hyperplane of normal h S h passing through the points in S h , i.e., ∀x ∈ S h , h T S h x = 0, with h S h = 1, ( 11
)
which yields the same classification of S in the sense that

∀x i ∈ S \ {x ∈ S : h T S h x = 0}, h(x i ) = sign(h T S h x i ). ( 12
)
Note that the set {x ∈ S : h T S h x = 0} includes S h but can also include more than d -1 points if S is not in general position.

Proof sketch. The general sketch of the proof is similar to the one of Proposition 3 in [START_REF] Lauer | On the complexity of piecewise affine system identification[END_REF]: the hyperplane of normal h is transformed to the one of normal h S h via a series of translation and rotations, while making sure that the classification remains unchanged except for the points that end up lying on the hyperplane. The first difference is that the set of classifiers is restricted to linear instead of affine ones by only considering hyperplanes passing through the origin, and thus with one less degree of freedom and one less point to choose in S h to fix the hyperplane. Technically, this removes the need for the first translation and only rotations are used to transform the hyperplane. Another difference is that, due to the lack of assumption on the distribution of the points, the number of additional points through which the hyperplane passes after a rotation is unbounded (otherwise than by N ). Thus, the statement in ( 12) explicitly excludes all points on the hyperplane and appears slightly weaker than the one in [START_REF] Lauer | On the complexity of piecewise affine system identification[END_REF] in that it might apply to less points.

p, -linear regression

We first focus on Problem 1 and start with a classification-based reformulation of the set of indexes I 1 (w * ) of points with error smaller than . This relies on the construction of a classification data set

Z = {z i } 2N i=1 , with z i = [y i -, -x T i ] T , if i ≤ N [-y i-N -, x T i-N ] T , if i > N . ( 13
)
Lemma 1. Given a parameter vector w ∈ R d , the set I 1 (w) defined in (3) is given by

I 1 (w) = i ∈ I : q i = q i+N = -1, q i = sign h(w) T z i , (14)
where h(w) = [1, w T ] T and Z = {z i } 2N i=1 as in (13). Proof. For any i ∈ I, we have i ≤ N and q i = sign(h(w) T z i ) = sign(y i --w T x i ), while q i+N = sign(h(w) T z i+N ) = sign(-y i -+ w T x i ). Thus,

|y i -w T x i | < ⇔ y i --w T x i < 0 ∧ -y i -+ w T x i < 0 ⇔ q i = -1 ∧ q i+N = -1
and recalling the definition of I 1 (w) in (3) completes the proof.

We will also need the following.

Lemma 2. Given a data set {(x i , y i )} N i=1 satisfying Assumption 1, no hyperplane of R d+1 passing through the origin can pass through more than d points of each of the sets

Z 1 = {z i = [y i - , -x T i ] T } N i=1 , Z 2 = {z i = [-y i-N -, x T i-N ] T } 2N i=N +1
and thus through more than 2d points of

Z = Z 1 ∪ Z 2 .
Proof. By Assumption 1, each of the sets Z 1 ∪{0} and Z 2 ∪{0} is also in general position. Thus, no hyperplane of R d+1 can pass through more than d points in each of these sets, and hence through more than a total of n ≤ 2d points of Z.

Using the classification viewpoint of Lemma 1, we can state the following result which considers the case where more than d data points can be approximated with error less than by a linear model. Note that there are always at least d such points and that the case where there are precisely d is trivial since any group of d points yields an optimal solution.

Proposition 2. Assume that the global minimum of Problem 1 is J * p < p (N -d). Then, under Assumption 1, in R d+1 , there is a hyperplane of normal h ∈ R d+1 passing through the origin and n ∈ [d, 2d] points of Z as in (13) such that h 1 > 0 and i) a global solution can be computed by solving 2 n ≤ 2 2d standard subproblems (6) that can be built from h, ii) for p = 0, w = h 2:d+1 /h 1 is an approximate solution with J 0 (w) ≤ J * 0 + n ≤ J * 0 + 2d. Proof. First note that, as a direct consequence of Lemma 2, we always have n ≤ 2d.

Part i) Let W * p be the set of global minimizers of Problem 1. By Lemma 1, for all w * ∈ W * p there is a hyperplane of normal h(w * ) classifying the 2N points of Z into I 1 (w * ) and I \ I 1 (w * ). By Proposition 1, there is an equivalent hyperplane of normal

h * passing through n ≥ d points of R d+1 , such that ∀i ∈ {1, . . . , 2N } \ I 0 , sign z T i h(w * ) = sign z T i h * , (15)
where I 0 = {i : z T i h * = 0}. Thus, the set I 1 (h * 2:d+1 /h * 1 ) computed as in Lemma 1 differs from I 1 (w * ) by at most n = |I 0 | entries and I 1 (w * ) must be one of the 2 n sets I s 1 = {i ∈ I : q i = q i+N = -1, q i = sign(h(w) T z i ), if i / ∈ I 0 , q i = q i k = s k , otherwise}, where we indexed the entries in I 0 as I 0 = {i 1 , . . . , i n } and s ∈ {-1, +1} n encodes the classification of the corresponding points. Solving the subproblem (6) over the data points with index in I s 1 for all s ∈ {-1, +1} n then yields at least one global solution in W * p . Given that J * p < p (N -d), we have |I 1 (w * )| > d for all w * ∈ W * p , which implies h * 1 > 0 as follows. First, note that I 1 (w * ) \ I 0 is not empty: by Lemma 2, I 0 contains no more than d indexes within I while I 1 (w * ) ⊆ I and |I 1 (w * )| > d. Then, by Lemma 1 and the sign equalities (15), for some

i ∈ I 1 (w * ) \ I 0 , z T i h * < 0 and z T i+N h * < 0. Assume h * 1 = 0, then z T i h * = -x T i h * 2:d+1 = -z T i+N h *
, which shows a contradiction with the previous statement. Similarly, letting h * 1 < 0 and using

z T i h * < 0 yields z T i+N h * = -z T i h * -2 h * 1 > -2 h * 1 > 0, and a contradiction with z T i+N h * < 0. Thus, h * 1 > 0. Part ii) For p = 0, given h * 1 > 0, sign(z T i h * ) = sign(z T i h * /h * 1 ). Thus, if s * is a choice of s yielding an optimal solution with s * k = sign(z T i k h * ), k = 1, . . . , n, by Lemma 1, I 1 (w * ) = I s * 1 = I 1 (h * 2:d+1 /h * 1 )
. Given that for p = 0 any w such that I 1 (w) = I 1 (w * ) yields the same cost J 0 (w) = J 0 (w * ), we conclude that in this case w = h * 2:d+1 /h * 1 ∈ W * 0 . Since s * k = sign(z T i k h * ) only occurs for at most n values of k, I 1 (w) deviates by at most n entries from this case and |I 1 (w)| ≤ |I 1 (w * )| + n, yielding the second statement.

Proposition 2 shows that a global minimizer of Problem 1 can be obtained from a particular separating hyperplane of Z. In addition, this hyperplane can be built from a subset of Z of cardinality n ∈ [d, 2d] as the one that passes through the origin of R d+1 and the n points in the subset. Since any subset of d points among these n points yields the same hyperplane, it suffices to find one particular subset of d points among Z. Hence, the problem is reduced to a combinatorial search with 2N d main iterations. This is formally stated in Algorithm 1 and the theorem below.

Theorem 1. Under Assumption 1 and given that subproblem (6) can be solved in O(N c ) time with a constant c ≥ 1 independent of N , Algorithm 1 solves Problem 1 in O(N c+d ) operations.

Proof. For all subsets of d points of Z, Algorithm 1 computes the hyperplane passing through these points and of orientation such that h 1 > 0. By Proposition 2, at least one of these hyperplanes with normal h is such that the inner loop over s in Algorithm 1 finds a global solution.

The computational complexity of Algorithm 1 is the number of subsets of d points among 2N times the time needed for a single iteration, which includes computing a normal vector h, classifying Z with h, the inner loop over s and the subproblem (6). The normal h of a hyperplane passing through the origin and d points {z i k } d k=1 in R d+1 can be computed as a unit vector in the null space of [z i1 , . . . ,

z i d ] T , extracted in O(d 3 ). If h 1 < 0, then -h is a normal for the hyperplane of opposite orientation. Given that z T i+N h = -z T i h -2 h 1 , the classification step takes O(N (d + 2)) instead of O(2N (d + 1)
). The inner loop contains 2 n ≤ 2 2d iterations with O(N c ) operations each to solve an instance of ( 6) over at most N data points. Overall, we obtain a time complexity of

T (N ) = O 2N d (d 3 + (d + 2)N + 2 2d N c ) = O N d d! (d 3 + (d + 2)N + 2 2d N c ) = O N d+c .
As an example, applying Theorem 1 for the saturated square loss, 2, , yields the exact Algorithm 1 for robust regression with complexity in the order of O(N d+1 ).

p, -subspace estimation

The results for subspace estimation will be derived via a quadratic lifting of the classification problem of assigning point indexes to I 1 (B).

Definition 1 (Veronese map of degree 2). The Veronese map of degree 2 is the map

ν : R d → R D , x → [x 2 1 , x 1 x 2 , . . . , x 2 2 , x 2 x 3 , . . . , x 2 d-1 , x d-1 x d , x 2 d ] T ,
where

D = d(d + 1)/2.
Using this map, we build a new data set

Z = {z i } N i=1 , with z i = -2 ν(x i ) (16)
and establish a correspondence between subspace estimation and the classification of this data set.

Lemma 3. Given a subspace basis B = [b 1 , . . . , b ds ] ∈ R d×d S such that B T B = I and a set Z as in (16), the set I 1 (B) defined in (7) is given by

I 1 (B) = {i ∈ I : h(B) T z i < 0}, (17)
where h 1 (B) = 1 and h 2:

D+1 (B) = s - ds j=1 ν(b j ) with the selection vector 4 s ∈ {0, 1} D such that ∀x ∈ R d , ν(x) T s = d k=1 x 2 d . Proof. For any i ∈ I, we have (I -BB T )x i < ⇔ x T i (I -BB T ) T (I -BB T )x i < 2 ⇔ x T i (I -BB T )x i < 2 ⇔ x T i x i - ds j=1 x T i (b j b T j )x i < 2 ⇔ ν(x i ) T s - ds j=1 ν(x i ) T ν(b j ) < 2 ⇔ ν(x i ) T   s - ds j=1 ν(b j )   -2 < 0 ⇔ h(B) T z i < 0.
Thus, the definition of I 1 (B) coincides with (17).

We will also need the following manipulation of Assumption 2.

Lemma 4. Under Assumption 2, no hyperplane of R D+1 passes through the origin and more than D points of Z as defined in (16).

Proof. Assumption 2 and the fact that the Veronese map is biregular, i.e., the image of points in general position in R d under the Veronese map ν are again in general position, imply that

V = {ν(x i )} N i=1 is in general position in R D .
Therefore, there is no hyperplane of R D that passes through more than D points of this set. Since the projection onto R D of any hyperplane of R D+1 passing through the origin and more than D points of Z must pass through more than D points of V, there is no such hyperplane. Proposition 3. Under Assumption 2, in R D+1 , there is a hyperplane of normal h ∈ R D+1 passing through the origin and exactly D points of Z as in (16) such that a global solution to Problem 2 can be found by solving 2 D subspace estimation subproblems (10).

Proof sketch. The proof works as the first part of the one of Proposition 2, except that we use Lemma 3 instead of Lemma 1 and Lemma 4 instead of Lemma 2 to bound from above the number of points lying on the hyperplane by D instead of 2d. It is also simpler as the classification of x i is directly given by the one of z i without taking into account an additional z i+N .

Compared with the regression case and Proposition 2, Proposition 3 does not ensure h 1 > 0 and thus the algorithm needs to test both orientations for every hyperplane. This yields Algorithm 2 for which we have the following result.

Theorem 2. Under Assumption 2 and given that subproblem (10) can be solved in O(N c ) time for a constant c ≥ 1 independent of N , Algorithm 2 solves Problem 2 in O(N c+d(d+1)/2 ) operations.

Proof. For all subsets of D points of Z, Algorithm 2 computes the hyperplane passing through the points. By Proposition 3, at least one of these hyperplanes with normal h is such that a global minimizer B can be recovered by solving an instance of (10) in the inner loops over S and s.

The computational complexity, T (N ), of Algorithm 2 is the number of subsets of D points among N , N D , times the time needed for computing a normal vector h, O(D 3 ), classifying Z with h, O(DN ), and performing the inner loops over S and s with the subproblem (10), O(2 × 2 D N c ):

T (N ) = O N D (D 3 + DN + 2 D+1 N c ) = O(N D+c )
Recalling that D = d(d + 1)/2 completes the proof.

As an example, applying Theorem 2 for the saturated square loss, 2, , yields the exact Algorithm 2 for robust subspace estimation with complexity in the order of O(N 1+d(d+1)/2 ).

Algorithm 2 Exact p, -subspace estimation

Input: a data set {x i } N i=1 , a threshold > 0. Initialize J * ← 2 N . for all S h ⊂ Z with |S h | = D do
Compute the normal h of the hyperplane passing through the points in S h ∪ {0}.

Classify the points: ∀i ∈ I, q i = sign 0 (h T z i ). for all S ⊆ S h do for all s ∈ {-1, +1} do # for all orientation I 1 = {i ≤ N : q i = s} ∪ {i ≤ N : x i ∈ S} Compute B as in (10) with I 1 replacing I 1 (B * ). if J S p ( B) < J * then Update J * ← J S p ( B), B * ← B. end if end for end for end for return J * , B *

Random sampling

We now detail more practical (but approximate) variants of the algorithms above. These are based on random sampling of subsets of points rather than a complete enumeration. As such, they share some features with the well-known RANSAC method [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF] for robust estimation.

RANSAC The RANSAC method iterates through small subsets of s points and estimates a linear model at each iteration from these s points only. Then, the model that best approximates the maximum number of points can be retained, the rationale being that it should be possible to find a small subset of points within the set inliers and thus to estimate a good model from inliers only. However, this approach has two major drawbacks. First, since only s points are used to estimate the models, even if all the N s subsets are completely enumerated, the RANSAC cannot guarantee the recovery of an optimal solution, unless s equals the unknown number of inliers. And in this case, the computational complexity becomes exponential in N as soon as we assume that a certain fraction of the N points are inliers. The second weakness is related to the tuning of s which should be made in accordance with the noise level and the fraction of inliers: larger values of s tend to filter more efficiently the noise but also generate more subsets corrupted by outliers and decrease the probability of selecting a subset of inliers only.

Random sampling variants of Algorithms 1-2

Inspired by the RANSAC method, we can develop approximate variants of Algorithms 1-2, in which the complete enumeration of the subsets S is replaced by random sampling. Note that though this approach also relies on randomly sampling subsets of points, it remains quite different from the RANSAC. Indeed, the RANSAC directly estimates a linear model from the points in a subset, whereas here the subsets of points are only used to determine the classification of the entire data set into inliers and outliers. Therefore, it remains possible for such approximate variants to find the optimal set of inliers from which it can compute an exact solution. As in the RANSAC, the accuracy of the resulting model mostly depends on the number N iters of iterations and thus of tested subsets. However, contrarily to the RANSAC, there is no other hyperparameter to tune: the size of the subsets is fixed to d (for regression) or D (for subspace estimation) from the analysis of Sect. 3.

Experiments

This section reports a few numerical results regarding first the exact algorithm for regression and then its approximate variant based on random sampling.

Exact algorithm

We here evaluate the gain in computing time offered by the exact polynomial algorithms. In particular, we focus on Algorithm 1 for 0, -regression and compare its computing time with that needed to solve Problem 1 with standard tools that can also compute exact solutions such as mixed-integer programming solvers. Specifically, for p = 0, Problem 1 can be reformulated as the mixed-integer linear program (MILP)

min w∈[-W,W ] d ,β∈{0,1} N N i=1 β i (18) s.t. y i -w T x i -≤ M β i , i = 1, . . . , N, w T x i -y i -≤ M β i , i = 1, . . . , N,
with binary variables β i encoding 1 |yi-w T xi|< and a constant M large enough to upper bound any absolute error term, i.e., set as M ≥ max i∈{1,...,N } |y i | + dW x i ∞ .

Experiments are conducted for random data sets of increasing size N generated by y i = x T i w 0 + ξ i + ν i for x i uniformly distributed in [-5, 5] d , w 0 = [1, -0.5, 0.8] T , a zero-mean Gaussian noise ξ i of variance 0.1 and an outlying Gaussian noise ν i of mean 100 and variance 1000 added only to 40% of the data. Computing times reported in Table 1 refer to a parallel implementation in Matlab of Algorithm 1 and the use of CPLEX for solving (18) (which also benefits from parallel processing) on a laptop equipped with an i5-7440HQ processor at 2.8GHz.

While CPLEX can compete with Algorithm 1 on small data sets (N = 100), the worst-case exponential complexity of MILPs makes it far slower when N increases. In addition, its computing time highly varies between different trials for the same data set size, whereas that of Algorithm 1 is not influenced by the data and remains pretictable for given problem dimensions.

Table 1: Comparison of the computing time (mean ± standard deviation over 4 trials) of Algorithm 1 and that of solving the MILP (18). "n/a" appears when the method did not terminate after 10 hours.

N 100 300 1000 MILP (18) 0.5 ± 0.2 s 11.3 ± 18.5 min n/a Algorithm 1 3.9 ± 0.1 s 43.2 ± 0.8 s 25 ± 0.4 min 0.4 0.5 0.6 0.7 0.8 0.9 0

Approximate variant

We now compare the variant of Algorithm 1 for p = 2 proposed in Sect. 4 with the RANSAC when both algorithms use the same number of iterations (N iters = 3000). Figure 1 shows how the errors, w 0 -w 2 / w 0 2 , between the target vector w 0 and the estimate w evolve with the fraction r of outliers (ν i = 0 for rN data points). More precisely, we plot the mean errors over 100 trials with w 0 uniformly drawn in [-5, 5] d , d = 4. The RANSAC uses s = 2d, but similar results are obtained for other values. The plot in Fig. 1 indicates that the proposed random sampling can perform better than the RANSAC in highly perturbed regimes with 70% of outliers or more. In addition, the random sampling variant of Algorithm 1 is obviously much faster than its exact version, leading to computing times similar to those of RANSAC and about 0.1 second in these experiments.

Conclusions

The paper analyzed the complexity of globally minimizing saturated loss functions for robust regression and subspace estimation with respect to the number of data. By deriving explicit connections between these estimation problems and linear classification, the paper could build on recent results on the enumeration of linear classifications to show that these global optimization problems have no more than a polynomial complexity in the number of data. Experiments showed that this provides a significant gain in speed when compared to a mixed-integer programming approach.

However, the developed algorithms have an exponential complexity wrt. the data dimension, which strongly limits their practical use. Therefore, approximate variants were proposed based on random sampling. Experiments showed that these variants can yield an increase of accuracy for a similar computational cost when compared with another classical method based on random sampling, namely, the RANSAC.

Figure 1 :

 1 Figure 1: Error versus the fraction of outliers.

Note that we focus on problems where the dimensionality is significantly smaller than the number of data and where regularization of linear models might not be necessary. However, given the nature of the proposed approach, introducing a convex regularizer should not raise difficulties.

Problem 1 may have multiple global solutions, especially when p = 0.

Note that a polynomial bound on the number of linear classifications of N points such as the one obtained with the celebrated Sauer's lemma and Vapnik-Chervonenkis dimension of hyperplanes is not sufficient for our purposes, since it does not provide an algorithm to explicitly enumerate the classifications.

s is defined bys l = 1 iff l ∈ {l k } D k=1 with l 1 = 1 and l k = l k-1 + d -k + 2.

Algorithm 1 Exact p, -regression Input: a data set {(x i , y i )} N i=1 , a threshold > 0. Initialize J * ← p N . for all S ⊂ Z with cardinality |S| = d do Compute the normal h to the hyperplane passing through S ∪ {0} with orientation such that h 1 ≥ 0.

if h 1 = 0 then Classify the points: ∀i ∈ {1, . . . , 2N },

Remark Note that a number of details can be included in Algorithm 1 to make it more efficient in practice. First, it can be easily parallelized. Then, a number of computations can be spared. For instance, since the changes in s can only incur a difference of at most n on |I s 1 |, the inner loop over s can be skipped when I 1 computed with q i = sign(h T z i ) is such that p (N -|I 1 |) > J * p + p n. Also, for p = 0, since J p (w) = N -|I s 1 | is constant for a fixed classification, we do not need to solve (6) to update J * and w * can be computed only once at the end of the procedure.


Renato Miguel Basso
email: rmbasso@gmail.com

Possible weak demonstratives: a preliminary analysis

Introduction: weak definites and their properties

The phenomenon of weak definites has attracted the attention of linguists mainly because it poses serious challenges to one of the most well established consensus about the semantics (and use) of definite articles: the uniqueness (either as an assertion or as a presupposition) associated with it. Examples such as (1) and ( 2) do not seem to require, at least in Brazilian Portuguese (BrP), a unique referent; they also convey "enriched meanings" -the two most distinguishing features of weak definites (cf. [START_REF] Aguilar-Guevara | Weak definites and reference to kinds[END_REF], Vogel, 2011, among others):

1) Pra chegar até aqui, você tem que pegar o ônibus.

To arrive until here you have to take the bus. 'To get here, you must take the bus.' 2) Bom, gente, agora vou sair, vou no mercado. (i.e. do shopping)

Well guys now willfirst-person leave gofirst-person in+the market 'Well guys, I'm leaving now, I'm going to the market.'

In the literature we find the following properties associated with weak definites, all of them exemplified by the example in (3) below: a) (apparent) violation of the uniqueness presupposition b) enriched meaning c) sloppy identity in elliptical contexts d) narrow scope e) lexical restriction f) compatibility only with modifiers that establish (or result in) subtypes of the nouns they modify 3) João foi para o hospital.

'John went to the hospital' a) (apparent) violation of the uniqueness presupposition the identity of the hospital is irrelevant, and (3) can be used in a context in which the participants know that there is more than one (salient) hospital. b) enriched meaning John went to the hospital to be treated, for healing, or because he works there... c) sloppy identity in elliptical contexts John went to the hospital and Mary did too (possibly to different hospitals) d) narrow scope Every student was sent to the hospital (distributive interpretation; i.e., the students were sent to different hospitals) e) lexically restricted John went to the clinic. -no weak interpretation f) accepts only modifiers that establish subtypes (or subkinds) of the nouns they modify John went to the mental hospital -weak interpretation is possible John went to the old hospital -no weak interpretation

Although a lot of work has been devoted to the weak definite article, analyzing this phenomenon either as a type of kindreference [START_REF] Aguilar-Guevara | Weak definites and reference to kinds[END_REF] or as a type of semantic incorporation [START_REF] Carlson | The Meaningful Bounds of Incorporation[END_REF][START_REF] Bosch | Weak Definites and German preposition-determiner contractions[END_REF], no attention has been devoted to the other sort of determiner which has a definite interpretation, namely demonstratives.

As we shall see in the following sections (mainly in "A semantic analyses for demonstrative descriptions"), although there are some controversies about the semantics of demonstratives, we argue that demonstrative and definite descriptions form a class; our evidence is examples such as1 : deictic uses anaphoric uses descriptive uses (i.e., non-deictic, nonanaphoric) (a) The cat is sleeping (pointing to a cat) (b) That cat is sleeping (pointing to a cat) (c) A womani walked in. The womani was smiling (d) A womani walked in. That womani smiled to another women (e) The student who finishes the exam may leave the room (f) That student who finishes the exam may leave the room

Given that demonstratives and definite descriptions show similar uses and interpretations, it is reasonable to consider them as forming a unified class; the next step is to argue for a unified semantics for them, and this can be done if we take each one as some sort of description and not as referential terms -that is why (among other reasons) we claim that demonstratives are a kind of definite description (cf. [START_REF] King | Complex demonstratives: a quantificational account[END_REF][START_REF] Roberts | Demonstratives as definites[END_REF][START_REF] Wolter | That's That: The Semantics and Pragmatics of Demonstrative Noun Phrases[END_REF][START_REF] Elbourne | Demonstratives as individual concepts[END_REF][START_REF] Basso | A semântica das relações anafóricas entre eventos[END_REF]. So our main question is: can demonstrative descriptions give rise to weak interpretations in the sense that the uniqueness in their use is not (apparently) required?

Based on the following examples, our first answer is 'no': The examples from (4) to (7) have only a strong interpretation (i.e., they refer to specific individuals) and show none of the other properties related to weak interpretations: 8) João foi pra esse / aquele hospital.

João gopast to this / that hospital 'John went to this / that hospital.' a) no (apparent) violation of the uniqueness presupposition there is only one (specific) hospital b) no enriched meaning to be treated, for healing... c) no sloppy identity in elliptical contexts ... and Mary did too (same hospital) d) absence of narrow scope interpretation Every student was sent to this/that hospital (no distributive interpretation) e) lexically restricted does not apply f) accepts only adjectives that establish subtypes of the nouns they does not apply Considering the similarities between definites and demonstratives, why can't demonstrative descriptions (henceforth, DEMD2 ) have weak interpretations in the same way that definite descriptions can? Is there any kind of context in which DEMDs have a weak interpretation? The answers to these questions can improve our understanding of the semantics of demonstratives and also of the phenomenon of weak definite. In fact, as we will argue in the last section, the existence of weak demonstratives is a strong argument in favor of considering the demonstrative in a DEMD as a determiner (i.e., a DP which selects for an NP) combining both in the semantic and syntactic level with an NP, contra [START_REF] Kaplan | Demonstratives[END_REF], [START_REF] Braun | Structured Characters and Complex Demonstratives[END_REF], [START_REF] Borg | Complex Demonstratives[END_REF] and [START_REF] Dever | Complex Demonstratives[END_REF], which claim either that DEMD are direct referential terms with no internal composition or that DEMDs are not real syntactic constituents, but a simple demonstrative plus an appositional structure. Before we answer these questions and discuss the issues of the semantic statuses of demonstratives we need to have a theory about weak definites as well as a theory about DEMDs.

In this paper we adopt Aguilar-Guevara & Zwarts's (2010) theory for weak definites, as shown in the next section, and we treat DEMDs as a type of definite description, which have specific presuppositions associated with them, as proposed by [START_REF] Wolter | That's That: The Semantics and Pragmatics of Demonstrative Noun Phrases[END_REF]. Next we will look at demonstrative reference to kinds (in the section "Demonstrative reference to kinds"). After presenting our theoretical assumptions, we shall go back to possible weak demonstratives. In the section "Why not weak demonstratives?" we explain why it seems impossible to normally have weak interpretations with DEMDs, and afterwards we will present a specific context in which it is indeed possible to have weak interpretations with DEMDs and we will also show the reasons why. Finally, we discuss the importance of the existence of weak demonstratives for a theory of DEMDs. Our main conclusions are presented in the "Conclusion".

Aguilar-Guevara and Zwarts's (2010) theory for weak definites

According to Aguilar-Guevara and Zwarts's (2010) theory, weak definites maintain the uniqueness presupposition associated with definites although not with respect to particular concrete individuals but with respect to kinds3 .

Their analyses involve an instantiation or realization relation R, and a notion of stereotypical usage events U (which accounts for the enriched meaning associated with weak definites). These ideas can explain, in principle, the main properties of weak definites. Consider the following sentence: As the formula in (9') shows, there is no quantification over 'hospitals' (H) but only an instantiation relation applied to the kind 'hospital' (R(Ref(e); H)), which is the goal (or theme) of the "going event"; and there is a set of usage (common, typical) events associated with hospital (U(e; H)), which involves healing or treatment events among others. The absence of quantification can account for the sloppy identity in anaphora as well as for the narrow scope reading. The usage events constraint can account for the lexical restrictions associated with weak readings and also for the fact that only modifiers which results in subkinds can maintain the weak interpretation (as claimed by the authors, usage events can be established only with kinds and/or subkinds).

There are of course more subtleties and further developments of this theory. Be it as it may, to our purposes in this paper, the two most important features of Aguilar-Guevara and Zwarts's (2010) theory are (a) the maintenance of the uniqueness associated with definite descriptions and (b) the assumption that weak interpretations involve kinds and/or subkinds. With a theory which assumes uniqueness and appeals to kinds (and subkinds), in the next section we'll consider the semantics of demonstratives.

A semantic analysis for demonstrative descriptions

In principle, it is possible to have two different approaches for DEMDs4 : (i) a direct reference approach, as proposed by [START_REF] Kaplan | Demonstratives[END_REF], [START_REF] Braun | Complex Demonstratives and Their Singular Contents[END_REF], [START_REF] Dever | Complex Demonstratives[END_REF], etc. (note that each author argues for a direct reference approach but their proposals are not the same); and (ii) indirect reference approach, in which the demonstrative can be treated as a quantifier [START_REF] King | Complex demonstratives: a quantificational account[END_REF] or as a determiner [START_REF] Roberts | Demonstratives as definites[END_REF][START_REF] Elbourne | Demonstratives as individual concepts[END_REF][START_REF] Wolter | That's That: The Semantics and Pragmatics of Demonstrative Noun Phrases[END_REF].

As expected, all of these approaches have their merits and problems. From a syntactic and semantic point of view, demonstratives are more naturally treated as determiners (for counter-arguments to this, see, e.g., [START_REF] Dever | Complex Demonstratives[END_REF], alongside with definite descriptions.

Thus, considering Roberts's (2002), Elbourne's (2008) and [START_REF] Wolter | That's That: The Semantics and Pragmatics of Demonstrative Noun Phrases[END_REF] proposals, we shall adopt the latter because it is more economical and covers a wider range of data5 .

According to Wolter's theory, definite and demonstrative descriptions share the same assertion content but differ with respect to their presuppositions. The only difference between these descriptions -leaving aside the distal/proximal properties showed by 'this' versus 'that'6 -is that definite descriptions presuppose uniqueness with respect to a conversational situation or context; i.e., maximal or default situation, while DEMDs presuppose uniqueness with respect to a proper subpart of a conversational situation or context; i.e., not the maximal situation, but a nondefault situation.

To illustrate this point, consider a scenario where there are two different paintings in an art gallery; in this context, ( 10) is bad even with a pointing gesture, and (11), with a pointing gesture, is good: 10) # I like the painting7 . 11) I like this painting. In Wolter's theory the pointing gesture associated with demonstratives is used to establish a non-default situation. So, in the scenario above, when someone points to a single painting, a non-default situation is established in which there is only one painting (which is the one being pointed to). In this non-default situation, the use of a DEMD like 'this painting' is felicitous exactly because there is only one painting in the non-default situation -this scenario satisfies the uniqueness presupposed by the demonstrative (which is the same as the presupposition associated with the definite, but which acts in the maximal situation in the case of definite descriptions).

These intuitions can be apprehended by the formulations below (Wolter's definitions p.64):

[[then]]: λP.P(sn) is a singleton set. If defined, denotes ιx.P(x)(sn) [[thatn]]: λP.P(sn) is a singleton set and sn is non-default. If defined, denotes ιx.P(x)(sn)

Wolter's theory is naturally extended to deal with non-referential uses of demonstratives, as anaphoric and descriptive uses.

Our next step is to understand the relation between demonstratives and kind reference, considering that, in accordance with Aguilar-Guevara and Zwarts's (2010) theory, reference to kinds (or subkinds) is necessary in order to have weak interpretations.

Demonstrative reference to kinds

DEMDs cannot normally be used to refer to kinds, as the example ( 12) shows, but it is natural to use DEMDs to refer to subkinds, as in example (13) (at least in Brazilian Portuguese; for the same considerations and conclusions concerning English demonstratives, cf. [START_REF] Bowdle | Generic Demonstratives[END_REF]:

Pointing to a whale :

12) A baleia tá em extinção OK-kind the whale is in extinction 'The whale is in extinction.' 13) Essa baleia/Aquela baleia tá em extinção OK-subkind this whale/ that whale is in extinction 'This whale/ that whale is in extinction.' (12) can mean something like whalek is in extinction or something like a subkind of whales is in extinction; but (13) can only mean that a subkind of whales is in extinction, i.e. the one (subkind) being pointed to or represented by the one (whale) being pointed to.

Consider now another example ("K" is for kind and "SK" is for subkind -a kind interpretation would be something like "Dogs are friendly" and a subkind interpretation, "Golden retrievers are friendly"); pointing to a golden retriever, someone some of the sentences below:

The only way to refer to a kind using DEMDs is when the NP position in the description is filled with a "superordinate term", e.g. 'animal'. In such a context, dog is a sub-kind of animal. The important point is that the demonstrative does not refer to the maximum individual (the top of the taxonomy). We propose that the restrictions of the kind reference displayed by DEMDs is due to the semantics of the demonstrative: to refer to kinds, it is necessary to have the maximal situation, with no further restrictions; but, as proposed by Wolter, demonstratives impose a restriction: they work only on non-default situations, and that is why we cannot normally use DEMDs to refer to kinds, but only to sub-kinds in a taxonomy. In the case of 'animal', the taxonomy has at the top the term 'animal' and 'dog' is then an item below it.

So far, we presented a theory for weak definites which preserves the uniqueness presupposition associated with definites, we argued that demonstratives are a kind of definite which shows specific presupposition (i.e., uniqueness in a non-default situation), and we also showed that demonstrative reference to kinds is not free from certain restrictions; we claimed that these restrictions have to do with the semantics of the demonstratives which allows them to refer to subkinds but not to kinds (only when the NP position is filled with a "superordinate term"). In the next section we return to the possibilities of weak interpretations for DEMDss with the theoretical assumptions seen so far.

Why not weak demonstratives ?

The reason why it is impossible to have weak interpretations of DEMDs is that we need reference to kind to have weak interpretations (according to Aguilar-Guevera and Zwarts's (2010) proposal), but demonstratives are always restricted to smaller domains (i.e., non-default situations) in comparison to the definite description and therefore cannot refer to kinds; since demonstratives cannot refer to kinds (because kind reference works only in maximal or default situations), the only option left for the demonstratives is to refer to instantiations (or "regular individuals"), and so we do not have weak interpretations with DEMDs.

Consider the following illustration for the example (8), repeated below: 8) João foi pra esse/aquele hospital João gopast to this/that hospital 'John went to this/that hospital.'

As the illustration shows, the item 'hospital' in example (8) can, in principle, refer to kind-level or individual-level entities. Weak interpretations need access to the kind-level but, since demonstratives, due to their semantics, cannot have access to the kind-level, the only option left is the individual-level and that is why sentence (8) refers to a specific/particular hospital.

But, as we propose in the next section, there is a particular type of context in which demonstratives can have weak interpretations.

No weak demonstratives at all?

In order to describe the contexts in which we argue that it is possible to have a weak interpretation with DEMDs, consider the two conclusions we arrived at so far: (i) although DEMDs can refer to subkinds by pointing to instantiations if the right contextual conditions are fullfilled, they can refer to kinds only under specific restrictions (i.e., when combined with an "empty name", as in 'this kind of animal'); and (ii) although weak interpretations do not accept all types of modifiers, they do accept modifiers which result in subtypes or subkinds 8 .

Putting these two ideas together, maybe there are some cases in which DEMDs can have weak interpretations. Consider the sentence ( 14) below, a well-behaved weak definite with a modifier: 14) João ligou pro médico do coração / de pele / do olho João callpast the doctor of the heart/of skin/of the eye 'John called the heart/skin/eye doctor.' Imagine now a context in which there is a list showing the names of medical specialties, and Peter, reporting what John did, says (15), while pointing to the label 'dermatology' ('skin doctor'): 15) João chamou esse médico.

João callpast this doctor. 'John called this doctor.'

In the suggested context, (15) has the main properties of "regular" or "ordinary" weak definites: 15) John called this doctor and Mary did it too.

OK if they did not call the same doctor, but doctors which have the same medical specialty, namely skin doctors (i.e., they may have called different skin doctors) enriched meaning: called for medical assistance narrow scope: Every student called this doctor 9 (i.e., every student called the skin doctor, but most likely different ones) But what happened in this case? Our suggestion is that we establish, via contextual information (i.e., by pointing to a list of medical specialties), a taxonomy of subkinds, as the next illustration shows:

kinds DOCTOR subkinds heart-doc. skin-doc. eye-doc. instantiations d1 d2 d3 d4 d5 d6...

In this configuration, there are salient subkinds accessible and the DEMDs may refer to them, giving rise to a weak interpretation. Compare this illustration with the one associated to example (8)in that illustration there are no subkinds accessible10 . In short, our claim is that in the context given for example (15) the use of the demonstrative description with a proper pointing gesture has exactly the same effect of the modifier which combined with definite descriptions results in a subkind.

For another example of this type of context, consider the following scenario, which summarized the press political tendencies from a small kingdom. In this kingdom, each newspaper falls neatly into one of three political tendencies: leftist (4 different newspapers), center (3 different newspapers), and rightist (3 different newspapers). The table below summarizes this scenario, by sorting the newspapers into three columns (the traces (----) stand for the newspapers' names):

NEWSPAPERS Leftist Rightist Center ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
Pointing to the left-hand column, Mary says:

16) João vai ler esse jornal e Maria também. João goPRES to read this newspaper and Mary too 'John will read this newspaper, and Mary will do that too.'

Again, in this context, the weak interpretation is prominent and we claim that the reason for this is that we have established and have access to subkinds of newspapers, and given that the DEMD ('this newspaper') can refer not only to a specific individual but also to a subkinds (i.e., left-hand newspaper no matter which one) it is possible to have a weak interpretation. Reference to subkinds guarantees weak interpretations.

In short, demonstratives cannot have access to kind-level individual because its domain is always smaller compared to the definite, but they can have access to subkind-level individuals; when there is no salient subkinds available, the only alternative for DEMDs is to refer to instantiations (individual-level). That is the reason why without a (contextually salient) taxonomy of subkinds there are no weak demonstratives (" *w " stands for "no weak interpretation"): 17) * w João foi pra esse hospital. João goPAST to this hospital 'John went to this/that hospital' 18) * w João limpou essa/aquela garrafa azul. João cleanPAST this / that bottle blue 'John cleaned this/that bottle blue.' Unless a taxonomy of hospitals and/or blue bottles is in the common-background there are no weak interpretations available.

We are not claiming that these examples are the "best" sentences ever, but only that, given the semantics of the demonstrative we adopted, combined with Aguilar-Guevara and Zwarts's (2010) analysis, the only way to have weak demonstratives is establishing a taxonomy of subkinds.

Weak demonstratives and the semantics of the demonstrative

As we said in the Introduction, the existence of weak demonstratives (and, as a matter of fact, of generic demonstratives) can be seen as evidence against theories which claim that DEMDs are devices of direct reference as proposed by [START_REF] Kaplan | Demonstratives[END_REF]. Since Kaplan's pioneering work, the NP component of DEMD is something that should be explained away: since DEMDs are devices of direct reference they cannot have any internal composition and the NP that appears in them, somehow, should not be part of the proposition expressed by a sentence which contain a DEMD. In fact, Kaplan claimed at an early stage that the role of this NP is just to help the audience to get to the intended referent. This idea can be implemented as saying that in DEMDs the NP acts only on the Kaplanian character, but not on the content, in this way, the NP is not a propositional constituent. We can find some echoes of these ideas in the work of [START_REF] Braun | Structured Characters and Complex Demonstratives[END_REF] and [START_REF] Borg | Complex Demonstratives[END_REF]. This alternative is not an ideal one because it clearly violates semantic innocence (the principle that says that the semantic behavior of any given expression be the same regardless of the context in which it appears).

Another alternative proposed by a referentialist about DEMDs is to claim that in a DEMD the demonstrative and the NP does not form a constituent. This bold alternative is fully embraced and advocated by [START_REF] Dever | Complex Demonstratives[END_REF]; he claims that the NP in a DEMD is an appositive constituent and as so does not appear in the same proposition as the demonstrative, but in a secondary / auxiliary proposition as is the case with other appositives.

However, it seems very difficult to defend any of these proposals in the face of the data shown here. There is a striking parallel behavior with respect to kind reference and generic interpretation when one compares definite and demonstrative descriptions. It is true that there is a contrast between these two constructions, as we claim, in the sense that DEMD can never refer to kinds, but only to subkinds in a given taxonomy structure (or, in others words, always to smaller domain with respect to the definite description). But the point is that in these two descriptions the NP seems to be doing exactly the same, to be playing the same role, and both descriptions do not only have generic interpretation, but also weak interpretations, which makes them even more similar.

Conclusion

In this paper, our point of starting was a theory for weak definites which preserves the uniqueness presupposition commonly associated with definites and which claims that weak interpretations involve reference to kinds. Our aim was to analyze weak interpretation with DEMDs because these descriptions show important similarities with definite ones. We presented and adopted a theory for demonstrative descriptions which claims that their semantics is closely related to the semantics of the definite description and that they differ not with respect to their assertion content but with respect to their presuppositions.

Then we investigated demonstrative reference to kinds because the theory for weak interpretation that we adopted explains the relevant data appealing to kind reference. When we put together all these considerations we can explain the facts concerning the possibilities of weak interpretation with DEMDs.

In our proposal for the existence and constraints concerning weak interpretations for DEMDs we can accommodate, without drastic modifications in the major picture of weak definites, the absence of weak demonstratives (which happens when there is no access to the subkind-level), on the one hand, and the instances of weak demonstratives (which happen when there is access to the subkind-level), on the other hand.

The semantic analysis proposed for demonstratives in this paper also explains why demonstrative descriptions do not usually refer to kinds and why they denote only subkinds or (specific) individuals. Our analysis can also be used as a further argument against the treatment of DEMDs as devices of direct reference and claims that definite and demonstrative descriptions form a natural class.

Finally, our analysis highlights the role of taxonomies and domain restriction in the understanding of noun phrases weak interpretations and can be seen as an argument in favor of Aguilar-Guevera and Zwarts's (2010) proposal11 .

9)

  John went to the hospital According to their analyses we have: 9') e[go-to(e) ^ Ag(e) = John ^ R(Ref(e) ; H) ^ U(e ; H)]

Cf.[START_REF] King | Complex demonstratives: a quantificational account[END_REF],[START_REF] Roberts | Demonstratives as definites[END_REF],[START_REF] Wolter | That's That: The Semantics and Pragmatics of Demonstrative Noun Phrases[END_REF],[START_REF] Basso | A semântica das relações anafóricas entre eventos[END_REF], among many others.

We'll use "demonstrative descriptions" and DEMDs interchangeably.

Although there is a huge and very important literature about kinds, subkinds and prototypes in psychology and cognitive linguistics, (cf.[START_REF] Langacker | Foundations of Cognitive Grammar[END_REF][START_REF] Langacker | Grammar and Conceptualization[END_REF][START_REF] Rosch | Principles of Categorization[END_REF], among many others), we will understand these concepts in the spirit of[START_REF] Carlson | A unified analysis of the English bare plural[END_REF] seminal work on bare nouns in English, as well as in[START_REF] Chierchia | Reference to kinds across languages[END_REF],[START_REF] Dayal | Number marking and (in)definiteness in kind terms[END_REF], Aguilar-Guevara and Zwarts (2010) and several other authors in the tradition of formal semantics. Although these concepts are different, they nonetheless have some overlapping.

Demonstrative descriptions (also known as complex demonstratives) are expressions composed by a demonstrative and an NP (DEM + NP); this is the only kind of demonstrative constructions that we shall consider in this paper. There are some complicated and interesting issues in trying to extend our considerations to plural DEMDs and also to simple demonstratives (singular and/or plural).

A thorough defense of[START_REF] Wolter | That's That: The Semantics and Pragmatics of Demonstrative Noun Phrases[END_REF] proposal is not the aim of this paper.

In BrP, 'esse/este' (proximal) versus 'aquele' (distal). We consider that in spoken BrP there is no more difference between 'esse' and 'este', although these items are still used differently in written BrP.

Even if (10) is accepted in this context, there is a clear preference for using (11).

It is far from easy to define subkinds and taxonomies; in this paper, we follow[START_REF] Dayal | Number marking and (in)definiteness in kind terms[END_REF].

Of course, this sentence (i.e., the construction 'this doctor') should be said while point to the label "dermatology" in the table shown above.

This doesn't mean, of course, that there are not subkinds of hospitals, but only that the example in (8) did not make them available and/or relevant, so they are not accessible to DEMDs.

It should also be clear that this is a first approximation on this topic and that more research will have to be done, including a corpus research and a crosslinguistic one.