F^{[2]}(y)$ proving the required inclusion $S_{1}\supset F^{[2]}(y)$.

Prove that $S_{2}\supset F^{[2]}(y)$. We have

$\displaystyle S_{2}$ $\displaystyle=[(C_{1}+rQ_{0})\,{{\cap}}\,C]+\varepsilon
Q_{0}$
$\displaystyle=[\\{(F(u^{\prime})+\operatorname{d}(u^{\prime},u)Q_{0})+\operatorname{d}(x,u)Q_{0}\\}\,{{\cap}}\,\\{F(v)+\operatorname{d}(x,v)Q_{0}\\}]+L\operatorname{d}(x,y)Q_{0}\,.$

Therefore, thanks to the triangle inequality, (5.11) and (3.9)

$S_{2}\supset[(F(u^{\prime})+\operatorname{d}(u^{\prime},x)Q_{0})\,{{\cap}}\,(F(v)+\operatorname{d}(x,v)Q_{0})]+L\operatorname{d}(x,y)Q_{0}=T_{y}(x,u^{\prime},v)\supset
F^{[2]}(y).$

In the same way we show that $S_{3}\supset F^{[2]}(y)$. Hence,
$\widetilde{A}\supset S_{1}\,{{\cap}}\,S_{2}\,{{\cap}}\,S_{3}\supset
F^{[2]}(y)$.

Combining this inclusion with definition (5.25) and representation (5.24), we
conclude that $F^{[2]}(x)+\tau Q_{0}\supset F^{[2]}(y)$. By interchanging the
roles of $x$ and $y$ we obtain also the inclusion $F^{[2]}(y)+\tau
Q_{0}\supset F^{[2]}(x)$. These two inclusions imply inequality

$\operatorname{d_{H}}(F^{[2]}(x),F^{[2]}(y))\leq\tau=\tilde{\gamma}(L)\,\operatorname{d}(x,y)=\lambda_{1}\,\tilde{\gamma}(L)\,\rho(x,y)$

proving (1.8) with $\gamma=\lambda_{1}\,L(3L+1)/(L-1)$. We recall that
$L=\lambda_{2}/\lambda_{1}$, so that inequality (1.8) holds with any
$\gamma\geq\lambda_{2}\,(3\lambda_{2}+\lambda_{1})/(\lambda_{2}-\lambda_{1})$.

The proof of Theorem 5.5 is complete. $\blacksquare$

## References

  * [1] Z. Artstein, Extension of Lipschitz selections and an application to differential inclusions, Nonlinear Anal. 16 (1991) 701–704.
  * [2] J.-P. Aubin, H. Frankowska, Set-valued analysis, Systems & Control: Foundations & Applications, 2. Birkhauser Boston, 1990.
  * [3] G. Basso, Computation of maximal projection constants, J. Funct. Anal. 277 (2019) 3560–3585.
  * [4] Y. Benyamini, J. Lindenstrauss, Geometric nonlinear functional analysis, Vol. 1, in: American Mathematical Society Colloquium Publications, 48. American Mathematical Society, Providence, RI, 2000. xii+488 pp.
  * [5] Yu. Brudnyi, P. Shvartsman, Generalizations of Whitney’s extension theorem, Internat. Math. Res. Notices (1994), no. 3, 129–139.
  * [6] Yu. Brudnyi, P. Shvartsman, The Whitney problem of existence of a linear extension operator. J. Geom. Anal., 7 (1997), no. 4, 515–574.
  * [7] Yu. Brudnyi, P. Shvartsman, Whitney Extension Problem for Multivariate $C^{1,\omega}$-functions. Trans. Amer. Math. Soc. 353, No. 6, (2001) 2487–2512.
  * [8] B. Chalmers, G. Lewicki, A proof of the Grunbaum conjecture, Studia Math. 200 (2010), no. 2, 103–129.
  * [9] L. Danzer, B. Grünbaum, V. Klee, Helly’s Theorem and its relatives. in: AMS Symposium on Convexity, Seattle, Proceedings of Symposium on Pure Mathematics, Vol. 7, Amer. Math. Soc., Providence, RI, 1963, pp. 101–180.
  * [10] C. Fefferman, A sharp form of Whitney extension theorem, Ann. of Math. 161 (2005), no. 1, 509–577.
  * [11] C. Fefferman. Whitney extension problem for $C^{m}$. Ann. of Math. 164, no. 1, (2006) 313–359.
  * [12] C. Fefferman, Whitney extension problems and interpolation of data, Bull. Amer. Math. Soc. 46 (2) (2009) 207–220.
  * [13] C. Fefferman, A. Israel, Fitting Smooth Functions to Data, CBMS Regional Conference Series in Mathematics, 135. American Mathematical Society, Providence, RI, 2020. xi+160 pp.
  * [14] C. Fefferman, A. Israel, G. K. Luli, Finiteness principles for smooth selection, Geom. Funct. Anal. 26 (2016), no. 2, 422–477.
  * [15] C. Fefferman, B. Pegueroles, Efficient algorithms for approximate smooth selection, J. Geom. Anal. 31 (2021), no. 7, 6530–6600.
  * [16] C. Fefferman, P. Shvartsman, Sharp finiteness principles for Lipschitz selections, Geom. Funct. Anal. 28 (2018) 1641–1705.
  * [17] B. Grünbaum, Projection constants, Trans. Amer. Math. Soc. 95 (1960) 451–465.
  * [18] M. D. Kirszbraun, Über die zusammenziehenden und Lipschitzchen Transformationen, Fundam. Math. 22 (1934) 77–108.
  * [19] K. Przesławski, L. E. Rybinski, Concepts of lower semicontinuity and continuous selections for convex valued multifunctions, J. Approx. Theory 68 (1992) 262–282.
  * [20] K. Przesławski, D. Yost, Continuity properties of selectors and Michael’s theorem, Mich. Math. J. 36 (1989) 113–134.
  * [21] K. Przesławski, D. Yost, Lipschitz Retracts, Selectors and Extensions, Mich. Math. J. 42 (1995) 555–571.
  * [22] M. Rieffel, Lipschitz extension constants equal projection constants. Operator theory, operator algebras, and applications, 147–162, Contemp. Math., 414, Amer. Math. Soc., Providence, RI, 2006.
  * [23] P. Shvartsman, On Lipschitz selections of affine-set valued mappings, Geom. Funct. Anal. 11 (2001), no. 4, 840–868.
  * [24] P. Shvartsman, Lipschitz selections of set-valued mappings and Helly’s theorem, J. Geom. Anal. 12 (2002), no. 2, 289–324.
  * [25] P. Shvartsman, Barycentric selectors and a Steiner-type point of a convex body in a Banach space, J. Funct. Anal. 210 (2004), no. 1, 1–42.
  * [26] P. Shvartsman, The Whitney extension problem and Lipschitz selections of set-valued mappings in jet-spaces. Trans. Amer. Math. Soc. 360 (2008), no. 10, 5529–5550.
  * [27] H. Whitney. Analytic extension of differentiable functions defined in closed sets. Trans. Amer. Math. Soc. 36 (1934) 63–89.


# What explains the success of cross-modal fine-tuning with ORCA?

Paloma García-de-Herreros1 Vagrant Gautam††footnotemark: 1 Philipp Slusallek1,
2
Dietrich Klakow1 Marius Mosbach3,4
1Saarland University 2DFKI 3McGill University 4Mila – Quebec AI Institute
<EMAIL_ADDRESS>Equal contribution.

###### Abstract

ORCA (Shen et al., 2023) is a recent technique for cross-modal fine-tuning,
i.e., applying pre-trained transformer models to modalities beyond their
training data. The technique consists primarily of training an embedder and
fine-tuning the embedder and model. Despite its high performance on a variety
of downstream tasks, we do not understand precisely how each of these
components contribute to ORCA’s success. Therefore, we run a series of
ablations and find that embedder training does not help 2D tasks at all,
contrary to what the original paper posits. In 1D tasks, some amount of
embedder training is necessary but more is not better. In 4 out of 6 datasets
we experiment with, it is model fine-tuning that makes the biggest difference.
Through our ablations and baselines, we contribute a better understanding of
the individual components of ORCA.

What explains the success of cross-modal fine-tuning with ORCA?

Paloma García-de-Herreros††thanks:  Equal contribution.1 Vagrant
Gautam††footnotemark: 1 Philipp Slusallek1, 2 Dietrich Klakow1 Marius
Mosbach3,4 1Saarland University 2DFKI 3McGill University 4Mila – Quebec AI
Institute<EMAIL_ADDRESS>

##  1 Introduction

Modern AI is based on a pipeline of pre-training general-purpose models on
vast amounts of data and then adapting them to specific tasks. Examples across
natural language processing (NLP) and computer vision (CV) typically focus on
within-modality adaptation across, e.g., tasks or domains, but there is also a
recent line of work that looks at leveraging pre-trained models across
modalities, e.g., Frozen Pretrained Transformers (FPT) Lu et al. (2021), ORCA
Shen et al. (2023), OmniPred Song et al. (2024), Unified PDE Solver (UPS) Shen
et al. (2024), inter alia.

ORCA is a recent example of a method for cross-modal fine-tuning (Shen et al.,
2023). It consists of a three-phase pipeline, shown in Figure 1. First, a pre-
trained transformer is selected, and a custom embedder and predictor are
created to support any combination of input-output dimensions. Second, the
embedder is trained to minimize the distance between a target and a proxy
dataset, in order to map the target dataset into the embedding space of the
pre-trained model. Finally, all three components are fine-tuned on data from
the target task.

According to Shen et al. (2023), the reason for ORCA’s success is the training
of the custom embedder. We expand on their ablations to better understand the
contributions of ORCA’s individual components, focusing on ablating the second
and third stages of the pipeline. Our specific research questions are:

Figure 1: The ORCA pipeline. Stage 2 involves training the task-specific
embedder. Stage 3 fine-tunes the embedder, the pre-trained encoder, and the
predictor.

  1. 1.

How does the choice of proxy dataset affect performance? (§3)

  2. 2.

Does doing (more) embedder training improve performance? (§4)

  3. 3.

What do the embedder and the pre-trained model contribute individually? (§5)

  4. 4.

How much pre-training is necessary for cross-modal transfer? (§6)

By disentangling the contributions of embedder training and model fine-tuning,
our results provide a more nuanced perspective on the success of cross-modal
fine-tuning with ORCA. Additionally, our findings highlight the importance of
strong baselines and careful ablations when making claims about why a method
works.

(a) NinaPro

(b) CIFAR-100

(c) Darcy Flow

(d) Satellite

(e) DeepSEA

(f) ECG

Figure 2: Per-epoch fine-tuning performance on 2D tasks (above) and 1D tasks
(below) when the embedder is trained with different proxy datasets or not
trained at all, i.e., naive fine-tuning.

##  2 Experimental setup

Unless otherwise specified, we follow the ORCA paper in using RoBERTa-base Liu
et al. (2019) and Swin-base Liu et al. (2021) as the pre-trained transformers,
a convolutional architecture for the embedder, and a linear transformation for
the predictor (see Appendix C for details). We also use optimal transport
dataset distance (OTDD; Alvarez-Melis and Fusi, 2020) as the loss function
during embedder training. All our experiments use their publicly available
code.111https://github.com/sjunhongshen/ORCA/ For training, we use the same
hyperparameters as they do, except for the batch size when training on
Satellite (64) and ECG (32) data. We evaluate on six target datasets that
appear in the original paper, chosen to represent all pairs of dimensions and
types, and we experiment with various proxy datasets. Dataset details are
shown in Appendix B.

### Target datasets.

We select three 2D datasets (NinaPro, CIFAR-100, and Darcy Flow) and three 1D
datasets (Satellite, DeepSEA, and ECG) from the NAS-Bench-360 benchmark Tu et
al. (2022).

### Proxy datasets.

The original paper uses CIFAR-10 (Krizhevsky, 2009) as the proxy dataset for
all 2D tasks, and CoNLL 2003 Tjong Kim Sang and De Meulder (2003) for all 1D
tasks. We experiment with additional proxy datasets to analyze their influence
on overall performance.

For the 2D tasks, we compare to two other image datasets that maintain the
same number of classes: MNIST Deng (2012), a different image dataset, and
Fakedata222From torchvision.datasets., a dataset of randomly classified white
noise images Paszke et al. (2019).

For the 1D tasks, we compare to a custom-created fake dataset classifying
randomly generated language feature vectors into the same number of classes as
CoNLL.

(a) NinaPro

(b) CIFAR-100

(c) Darcy Flow

(d) Satellite

(e) DeepSEA

(f) ECG

Figure 3: Per-epoch embedder training comparing OTDD ($\downarrow$) (metric
minimized during this stage) to downstream task performance ($\downarrow$).

##  3 How does the choice of proxy dataset affect performance?

In this section, we experiment with the choice of proxy dataset for the tasks.
As a baseline, we compare to just fine-tuning the embedder, model and
predictor, without training the embedder first.

As Figure 2 shows, all fine-tuning curves for the 2D datasets (first row)
overlap, indicating that the choice of proxy dataset is not important. Even
fake data as a proxy dataset results in the same performance. Similarly, for
the 1D tasks (second row), there is no real difference between using CoNLL and
fake embeddings. Together, this shows that the choice of proxy dataset for
embedder training does not matter for ORCA to work.

Comparing to a naive fine-tuning baseline allows us to evaluate the claim that
“ORCA consistently outperforms naive fine-tuning” (Shen et al., 2023). We find
that embedder training does play a role in the 1D tasks, but does not matter
for 2D tasks, even in the early stages of fine-tuning.

##  4 (More) embedder training is not the secret to ORCA’s success

The previous results motivate us to more closely examine the role of embedder
training in ORCA. In this stage, the OTDD metric is used to quantify the
distance between the proxy and target embeddings. The authors minimize OTDD,
claiming that “as the dataset distance decreases, the fine-tuning accuracy
increases” (Shen et al., 2023).

However, when we examine the relationship between OTDD and downstream task
performance, we find that embedder training is unnecessary in two out of six
tasks (Figures 3(a) and 3(c)). For the remaining four tasks, training the
embedder more can even lead to worse task performance.

As this section and the previous one show that embedder training does not
affect final performance on the 2D tasks, we focus on the 1D tasks for our
remaining experiments.

##  5 Which components of ORCA are really necessary?

|  Satellite |  DeepSEA |  ECG
---|---|---|---
|
Freezing both |  |  |
Freezing the model |  |  |
Freezing the embedder |  |  |
Figure 4: Freezing just the embedder, just the model, or both, before full
fine-tuning. We also evaluate the impact of training vs. not training the
embedder before freezing.

(a) Satellite

(b) DeepSEA

(c) ECG

Figure 5: Effect of different amounts of pre-training data on downstream
performance.

To better understand how the fine-tuning phase affects the multiple components
of ORCA, we experiment with freezing different parts of the pipeline: the
embedder, the pre-trained model, or both. We compare our results with the
original setup.

Row 1 of Figure 4 shows the results of freezing both the embedder and the pre-
trained model, and only fine-tuning the predictor. Across all datasets, the
frozen versions perform much worse than the original setup, regardless of
embedder training. This indicates that these datasets are not simple enough to
be solved by training a simple predictor.

In row 2, we freeze only the pre-trained model, but fine-tune the embedder and
the predictor. These frozen versions also perform much worse than the original
setup, indicating that fine-tuning the pre-trained model is a critical
component of ORCA, regardless of dataset and embedder training.

Finally, in row 3, we only freeze the embedder, allowing the fine-tuning stage
to affect both the model and the predictor. As we already saw in Figure 2,
training the embedder is important across all three datasets. However, once
this training is done, even if it is frozen, adapting the pre-trained model is
sufficient for good task performance. This shows that while training the
embedder is important for ORCA’s success on these datasets, it need not be
fine-tuned beyond that.

##  6 Pre-training is not always necessary

Our previous results show that fine-tuning the model is necessary for good
downstream task performance, but they do not show whether using pre-trained
models is necessary for this. To answer this question, we use RoBERTa models
pre-trained on different amounts of English data. Specifically, we compare the
original RoBERTa-base model to a randomly initialized model with no training
data, along with three variants trained on less data (Warstadt et al., 2020),
as shown in Appendix E.

Figure 5 shows that performance varies widely depending on the dataset. For
Satellite, all models perform the same, showing that the task is simple enough
to be solved even without pre-training. With DeepSEA and ECG, on the other
hand, pre-training data on the scale of 30B tokens results in clearly better
performance. These results highlight the importance of comparing to a no pre-
training baseline, for ORCA—and indeed all cross-modal fine-tuning work—to
ensure that pre-training is actually necessary for the success of the method.

Until the 30B data scale, however, DeepSEA performance remains within the
variance of simply fine-tuning a randomly-initialized model, whereas ECG does
benefit from even a small amount of pre-training. This shows that even for
non-trivial tasks, the amount of pre-training has a noticeable effect only at
certain scales.

##  7 Conclusion

We perform a series of ablations to investigate how the different components
of ORCA, a recently-proposed method for cross-modal fine-tuning, affect its
performance. Contrary to the original results, we find that embedder training
does not help 2D tasks at all, compared to just fine-tuning without training
the embeddder. In 1D tasks, some amount of embedder training is necessary, but
unlike the claim in the original paper, more embedder training can even hurt
performance on the target task. In a series of experiments where we freeze
components of the ORCA pipeline, we find that fine-tuning the model is crucial
for good task performance. It is not necessary, however, to further train the
embedder after stage two. Finally, we find that for one of the 1D tasks, using
a pre-trained model is actually not necessary, indicating the importance of no
pre-training baselines in evaluations of cross-modal transfer.

## References

  * Alvarez-Melis and Fusi (2020) David Alvarez-Melis and Nicolo Fusi. 2020.  Geometric dataset distances via optimal transport.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 21428–21439. Curran Associates, Inc.
  * Deng (2012) Li Deng. 2012.  The MNIST database of handwritten digit images for machine learning research [best of the web].  _IEEE Signal Processing Magazine_ , 29(6):141–142.
  * Krizhevsky (2009) Alex Krizhevsky. 2009.  Learning multiple layers of features from tiny images.  Technical report.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  RoBERTa: A robustly optimized BERT pretraining approach.  _CoRR_ , abs/1907.11692.
  * Liu et al. (2021) Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. 2021.  Swin Transformer: Hierarchical vision transformer using shifted windows.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , pages 10012–10022.
  * Lu et al. (2021) Kevin Lu, Aditya Grover, Pieter Abbeel, and Igor Mordatch. 2021.  Pretrained transformers as universal computation engines.  _arXiv preprint_.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019.  PyTorch: An imperative style, high-performance deep learning library.  In _Advances in Neural Information Processing Systems 32_ , pages 8024–8035. Curran Associates, Inc.
  * Petitjean et al. (2012) François Petitjean, Jordi Inglada, and Pierre Gancarski. 2012.  Satellite image time series analysis under time warping.  _IEEE Transactions on Geoscience and Remote Sensing_ , 50(8):3081–3095.
  * Shen et al. (2023) Junhong Shen, Liam Li, Lucio M. Dery, Corey Staten, Mikhail Khodak, Graham Neubig, and Ameet Talwalkar. 2023.  Cross-modal fine-tuning: Align then refine.  In _Proceedings of the 40th International Conference on Machine Learning_ , volume 202 of _Proceedings of Machine Learning Research_ , pages 31030–31056. PMLR.
  * Shen et al. (2024) Junhong Shen, Tanya Marwah, and Ameet Talwalkar. 2024.  Ups: Towards foundation models for pde solving via cross-modal adaptation.  _arXiv preprint arXiv:2403.07187_.
  * Shen et al. (2019) Shu Shen, Kang Gu, Xin-Rong Chen, Ming Yang, and Ru-Chuan Wang. 2019.  Movements classification of multi-channel semg based on cnn and stacking ensemble learning.  _IEEE Access_ , 7:137489–137500.
  * Song et al. (2024) Xingyou Song, Oscar Li, Chansoo Lee, Daiyi Peng, Sagi Perel, Yutian Chen, et al. 2024.  OmniPred: Language models as universal regressors.  _arXiv preprint_.
  * Tjong Kim Sang and De Meulder (2003) Erik F. Tjong Kim Sang and Fien De Meulder. 2003.  Introduction to the CoNLL-2003 shared task: Language-independent named entity recognition.  In _Proceedings of the Seventh Conference on Natural Language Learning at HLT-NAACL 2003_ , pages 142–147.
  * Tu et al. (2022) Renbo Tu, Nicholas Roberts, Mikhail Khodak, Junhong Shen, Frederic Sala, and Ameet Talwalkar. 2022.  NAS-bench-360: Benchmarking neural architecture search on diverse tasks.  In _Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track_.
  * Warstadt et al. (2020) Alex Warstadt, Yian Zhang, Xiaocheng Li, Haokun Liu, and Samuel R. Bowman. 2020.  Learning which features matter: RoBERTa acquires a preference for linguistic generalizations (eventually).  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 217–235, Online. Association for Computational Linguistics.

##  Appendix A Limitations

### Choice of datasets.

We only experiment with three 2D datasets and three 1D datasets, and we do not
consider the experiments from the original paper on tabular data, where our
findings may not hold. Additionally, due to the widely varying patterns we
find in our results, we believe that this is not sufficient for our findings
to generalize beyond these specific datasets to the modalities that they
represent. This points to a limitation of cross-modal fine-tuning work in
general, which would benefit from a larger set of datasets, and in particular,
more challenging tasks, as we find that the Satellite dataset is very simple.

### Choice of pre-trained models.

Our experiments focus on 1D tasks, for which we only experiment with encoder-
only architectures (specifically RoBERTa-type models) even though other
encoder-only models and even other architectures (e.g., encoder-decoder and
decoder-only models) could also be used. We caution against claims about
generalization of our results for these tasks to pre-trained models beyond
just RoBERTa.

### Ablating stage one.

Our experiments focus on stages two and three of the ORCA pipeline, but stage
one, i.e., the creation of the task-specific embedder and predictor, is not
something we vary. In Shen et al. (2023) and in our work, the task-specific
embedder consists of a convolutional layer, a layer norm, and a positional
embedding, and the predictor consists of a linear projection. It would be
interesting to test a much simpler method of converting dimensions in the
embedder than a convolutional architecture, e.g., a linear projection, which
we leave to future work.

### Evaluating what is being transferred.

In Section 5, we show that pre-training is necessary for some cross-modal
transfer, but we still do not know exactly what is being transferred. The
cross-modal transfer literature posits that pre-trained knowledge is somehow
exploited in downstream tasks, but since we do not know how to quantify
“knowledge” in this setting, we cannot make this claim. It is just as
plausible that models pre-trained on tokens beyond a certain scale find
better, more general solutions that are a good initialization for adapting to
a new task. One way to further probe the transfer hypothesis would be by
limiting the number of parameters that are allowed to change during fine-
tuning, e.g., by using parameter-efficient fine-tuning with LoRA. We leave an
exploration of this to future work.

##  Appendix B Dataset details

Dim. | Target dataset | Type | Metric | # classes | Proxy dataset | # classes
---|---|---|---|---|---|---
| NinaPro | Point | 0-1 error ($\downarrow$) | 18 |  |
2D | CIFAR-100 | Point | 0-1 error ($\downarrow$) | 100 | CIFAR-10 | 10
| Darcy Flow | Dense | relative $l_{2}$ ($\downarrow$) | 10 |  |
| Satellite | Point | 0-1 error ($\downarrow$) | 24 |  |
1D | DeepSEA | Point (multi-label) | 1 - AUROC ($\downarrow$) | 36 | CoNLL-2003333We were unable to replicate the exact workflow to create the language features passed to the model, so we used the ones provided in the original ORCA GitHub. | 7
| ECG | Point | 1 - F1 ($\downarrow$) | 4 |  |
Table 1: Target datasets of each type along with the proxy datasets used for
them in ORCA (Shen et al., 2023)

Table 1 shows the target and original proxy datasets considered, along with
their dimension, type, number of classes, and the metric used to measure
target task performance. The tasks are classified into two types, taking into
account whether the task’s output is a singular prediction (point) or multiple
predictions (dense). The target datasets are described in more detail below.

Figure 6: CIFAR-100 examples.

### CIFAR-100: Standard Image Classification.

The dataset consists of 32x32 color images divided into 100 classes, based on
the object represented by the image. Some examples can be seen in Figure 6.

Figure 7: Example from the Darcy Flow dataset.

### Darcy Flow: Solving Partial Differential Equations (PDEs).

The only regression task considered. Although, for the training stages, the
dataset is divided into a total of 10 inferred classes. The dataset consists
of 2D grids specifying the initial conditions of a fluid, as an output the
same 2D grid on a later time is predicted.

### DeepSEA: Predicting Functional Effects From Genetic Sequences.

The dataset consists of a collection of genomic profiles to estimate the
behavior of chromatin proteins, classifying it into 36 classes.

### ECG: Detecting Heart Disease.

The dataset is formed by recordings of up to a minute of Electrocardiograms
classified into four classes: normal, disease, other, or noisy rhythms. Figure
8 shows an example of each of the classes.

Figure 8: Examples of ECG recordings of the 4 different classes Figure 9:
Samples of movements in NinaPro BD5 Shen et al. (2019), the dataset contains
the electromyography signals of the movements.

### NinaPro: Classifying Electromyography Signals.

It takes a subset of NinaPro BD5, to classify the electromyography (sEMG)
signals of a collection of hand movements in 18 classes. Some examples of the
movements can be seen in Figure 9.

Figure 10: Example of Satellite Petitjean et al. (2012)

### Satellite: Satellite Image Time Series Analysis.

Algorithm 1 Efficient approximation of OTDD using class-wise subsampling from
(Shen et al., 2023)

Input: target dataset $\\{x^{t},y^{t}\\}$, number of target classes $K^{t}$,
source dataset $S=\\{x^{s},y^{s}\\}$, subsample size $b$, subsample round $R$

for each class $i\in[K^{t}]$ in the target dataset do

Compute class weight
$w_{i}=\frac{number\>of\>target\>data\>in\>class\>i}{total\>number\>of\>target\>data}$

Generate data loader $D_{i}$ consisting of data in class $i$

end for

for $i\in[K^{t}]$ do

for $r\in[R]$ do

Subsample $b$ target data points $D_{ir}$ uniformly at random from $D_{i}$

Compute class-wise distance $d_{ir}=OTDD(D_{ir},S)$

end for

Approximate class-wise OTDD by $d_{i}=\frac{1}{R}\sum^{R}_{i=1}{d_{ir}}$

end for

Approximate OTDD by $d=\sum^{K^{t}}_{i=1}{w_{i}\dot{d}_{i}}$

The dataset consists of satellite image time series (SITS), tracking the land
changes over the years, classifying them into 24 land cover types.

##  Appendix C Embedder and predictor details

As described in Figure 1, in the first stage of the ORCA workflow Shen et al.
(2023), a task-specific embedder and predictor are created to support any
combination of input-output dimensions. Throughout all our experiments, we
kept the same architectures used in the original paper, which we will explain
in this section.

### Task-specific Embedding Network

The architecture is composed of a convolutional layer with an input channel of
the target dataset and an output channel of the dimension of the pre-trained
model embedding space. The kernel size and stride can be treated as a
hyperparameter, but in all our experiments for the 2D tasks both are set to
four and, for the 1D tasks, are computed based on the input and target
sequence length. After this, a layer norm and a positional embedder are added
to obtain the final representation.

### Task-specific Predictor

Given the diversity of the tasks considered, two different architectures are
implemented depending on the target task type. For the point tasks, average
pooling along the sequence length dimension is applied, to obtain 1D tensors
with the same length as the dimension of the pre-trained model embedding
space. Then to map to the number of classes of the target dataset, a linear
layer is used. For dense tasks, a linear layer is applied to the sequence
outputs to adjust the tensor shape. Then, this tensor is molded to the desired
output dimension.

##  Appendix D OTDD approximation implementation

Following the original ORCA implementation Shen et al. (2023), we also used an
approximation of OTDD using class-wise subsampling, as described in Algorithm
1.

As described in the original paper, to tackle potential memory issues when
computing OTDD, the dimensionality of the feature vectors is reduced by taking
the average along the sequence length dimension. On top of that, the target
dataset is divided into subsets based on the labels, each of these subsets
will be approximated with the average of batch samples (the number of maximum
samples taken from each class is determined for every dataset). Then the OTDD
between each class representative and a sample of the proxy dataset (5000
samples for CIFAR-10 and 2000 for CONLL 2003) is computed. Finally, the
overall OTDD is approximated by the weighted sum of the OTDD of all the
classes in the task dataset.

##  Appendix E Details on pre-trained RoBERTa models

Table 2 provides information about the amount of training data seen by the
different RoBERTa variants released by Warstadt et al. (2020).

Model | Training data
---|---
roberta-base | ~30B
roberta-base-1B-2 | 1B
roberta-base-100M-3 | 100M
roberta-base-10M-3 | 10M
roberta-base-random | 0
Table 2: Models for pre-trained knowledge comparison, and their training data
in number of tokens.


# How Much Annotation is Needed
to Compare Summarization Models?

Chantal Shaib1 Joe Barrow3††footnotemark:  Alexa F. Siu2
Byron C. Wallace1 Ani Nenkova2
1Northeastern University, 2Adobe Research, 3Pattern Data
{shaib.c<EMAIL_ADDRESS>
{asiu<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
Work completed while at Adobe Research.

###### Abstract

Modern instruction-tuned models have become highly capable in text generation
tasks such as summarization, and are expected to be released at a steady pace.
In practice one may now wish to choose confidently, but with minimal effort,
the best performing summarization model when applied to a new domain or
purpose. In this work, we empirically investigate the test sample size
necessary to select a preferred model in the context of news summarization.
Empirical results reveal that comparative evaluation converges quickly for
both automatic and human evaluation, with clear preferences for a system
emerging from under 100 examples. The human preference data allows us to
quantify how well automatic scores can reproduce preference rankings across a
variety of downstream summarization tasks. We find that, while automatic
metrics are stable at smaller sample sizes, only some automatic metrics are
able to moderately predict model win rates according to human preference.

How Much Annotation is Needed
to Compare Summarization Models?

Chantal Shaib1††thanks: Work completed while at Adobe Research. Joe
Barrow3††footnotemark:  Alexa F. Siu2 Byron C. Wallace1 Ani Nenkova2
1Northeastern University, 2Adobe Research, 3Pattern Data {shaib.c,
<EMAIL_ADDRESS>{asiu<EMAIL_ADDRESS><EMAIL_ADDRESS>

##  1 Introduction

Instruction fine-tuned language models are highly capable summarizers, and new
such models are now released often. Continuously comparing such models using
large, reference-based benchmark assessments is a costly task, especially if
one wants to use them in a new domain. Here we demonstrate on data for news
summarization that, in both human and automatic evaluations, preferences
toward a summarization model emerge over test sets of about 50 samples.
Collecting human judgements, GPT evaluations or—if available—human references
for this size of dataset is reasonable. Further, we validate GPT evaluations
and two popular reference-based evaluations, ROUGE-1 and BERTScore, in terms
of their ability to predict human preferences on a set of 36 testing contexts.
We collect human judgements in the context of three different summarization
tasks and three sources of input. For these variations, we compute the
accuracy of automated scores to reproduce human preferences between pairs of
systems.

##  2 Background

Our goal is to establish the amount of test data needed to decide which of two
summarization models produces better summaries, for a given distribution of
the inputs (different sources of text to be summarized) and different task
contexts for which the summary is to be used.

Figure 1: Distributions of average ROUGE-1 and BERTScores across 1000 re-
samples. Differences between systems emerge clearly and quickly for XSUM and
Newsroom.

It is common to approach evaluation as a rate-then-compare task, in which
outputs from systems are rated for quality on a scale, and then average scores
are used to compare systems. But it is well known that inputs may differ
considerably in difficulty Nenkova and Louis (2008). Paired tests for
statistical significance, that evaluate the differences of scores between two
systems on the same input is the basis for comparison are therefore more
appropriate Rankel et al. (2011); Dror et al. (2018). Most contemporary work
has fully embraced this approach, largely abandoning scoring of outputs and
instead soliciting preferences among two or more choices Novikova et al.
(2018). Given the developments in LLMs, pairwise win rates have become the _de
facto_ standard for reporting comparisons between instruction fine-tuned
models. In this work, we similarly adopt the win rate approach to comparing
systems, and empirically identify the smallest test set size that reliably
reveals preferences.

Most closely related to our work is the study on estimating power of tests for
statistical significance, i.e., the minimum test size necessary to detect
statistical differences of a given size Card et al. (2020). Our work is
aligned with the main question in this prior work, but we present empirical
estimates of differences between systems, without making any assumptions of
tests to be used or size of effect we want to detect. Our findings can inform
future work on power estimation.

Prior related work proposes ways of carrying out the evaluation, either
automatically or manually Laban et al. (2022a); Zhang* et al. (2020); Fabbri
et al. (2022); Zhong et al. (2022); Liu et al. (2022), and of measuring the
correlation between system rankings produced by human and automatic
evaluations on a given benchmark Gehrmann et al. (2023). We do not propose new
ways for evaluation but introduce a new method of validating automatic
evaluations that does not rely on the benchmark, but rather measures the
accuracy of automatic scores in reproducing human judgements across different
input distributions and intended use-cases.

##  3 Unnecessarily Large Benchmarks

We first compare two models, FlanT5-XXL (Chung et al., 2022) and StableLM
(Andonian et al., 2021) via automatic scores over three news summarization
benchmarks: CNN/DM (See et al., 2017; Hermann et al., 2015), XSUM (Narayan et
al., 2018), and Newsroom Grusky et al. (2018). We use the test set splits of
these datasets from Huggingface.111https://huggingface.co/docs/datasets/index

CNN/Daily Mail and XSUM contain about 10K test inputs. The Newsroom test set
split has over 100k samples. For efficiency, we randomly sample 10k examples
from this set to scale it down to a size comparable to the other two datasets.
We then generate summaries with FlanT5 and StableLM for all articles in the
test sets, using the summarization prompts that these models have been trained
on (see Appendix A). For each test split we sample 1000 times with replacement
smaller test set sizes ranging from $[5,\texttt{len}(dataset)]$. We evaluate
the two models with the commonly used ROUGE-1 (Lin, 2004) and BERTScore
(Zhang* et al., 2020).222We also run experiments with BLEU (Papineni et al.,
2002) and SummaC-ZS (Laban et al., 2022b), and report these results in
Appendix B. Both scores compare a summary with a human-written reference
summary. ROUGE does so using tokens, while BERTScore relies on embeddings.

We show score variations for FlanT5 and StableLM across the three datasets in
Figure 1.

For all three datasets, a preference for one of the models emerges early: The
winning model as scored over 10k test points emerges after just 25-50
samples.333Even with respect to automatic evaluations, these findings have
considerable implications. For many LLMs, simply producing outputs for all 10K
test set is computationally expensive and slow. Manual (human) evaluation with
such large test sets is practically impossible.

Given these findings, we collect human judgements on 100 samples from each of
the data sources, varying the task context in which the judgement is made. We
also add GPT-4 as another summarization model to be evaluated, and later
report the accuracy of GPT-based evaluation against the aggregated human
judgements.

##  4 Human Preferences

We hire annotators on Upwork444https://www.upwork.com/nx/enterprise-homepage/.
Specifically, we hire three individuals for CNN/DM and Newsroom, and one for
XSUM. We select 100 inputs for annotation from each dataset, which given the
trends we observed in the previous section, would be sufficient to reveal
human preference.555See Appendix F for details about cost and hours for all
annotations.

Figure 2: Aggregated annotator win rates for the CNN/DM dataset for the
overall metric. Model preferences remain fairly stable across all sample sizes
except in one case for sample size of 25.

We also add summaries produced by GPT-4 for evaluation on the smaller dataset.
FlanT5, StableLM and GPT-4 represent encoder-decoder, decoder-only (open-
source), and decoder-only (closed-source) models, respectively.

We instruct annotators to rank the summaries for each input in order of
preference. This is a typical evaluation setting in which win rates—the
percentage of input for which the model was preferred over the other—provide
the clearest score for each model pair.

We provide three different scenarios to measure how preference may change
based on context: _(i)_ Rank the summaries in order of preference; _(ii)_
Assuming you are monitoring the news for important world events, rank the
summaries in order of preference; _(iii)_ Which summary best captures the main
details of the event being reported on? _(iv)_ Which summary contains the
fewest unnecessary details?666We also ask if the summaries have text quality
issues (e.g., formatting, grammar, unusual symbols, or other artifacts). We
then present the reader with the full article and ask them to mark if any of
the summaries contain factual errors. We provide a brief analysis of these
results in Appendix E.

For GPT-4, we linearly append the summaries with the instructions and provide
these as prompts to the model.

###  4.1 Stability of Preference

First, we look at confirming whether smaller test samples are sufficient to
make the same conclusion as with a larger sample. We apply the same procedure
described in Section 3, where we resample 1000 test sets of size 25 and 50
from the 100 for which we have human judgements. Figure 2 shows the win rates
for the CNN/Daily Mail test set for each of the three pairs of models, on the
full test set of 100 samples, as well as the min, max and average win rate
recorded across the 1000 smaller test sets.

While there is some variation in the strength of the preference for a model,
the overall preference is preserved in the smaller samples. In only one
case—the comparison between FlanT5 and StableLM—does the overall preference
change for the minimum value of win rates from the one thousand samples of
size 25. With 50 samples in the evaluation set, all three of the minimum,
maximum and average win rates lead to the same conclusion about which system
in the pair is better as that from the full 100 sample test set.

Similarly for the other two datasets, Newsroom and XSUM, none of the overall
preferences flip for test sets of size 50 and only one minimum value for the
25 samples flips the preference. We provide the complete tables in Appendix C.

These results indicate that, even for human evaluation, smaller test set
samples ($n$=50) are adequate to conclude which is the preferred summarization
model.

In many cases, the strength of the preference is of interest. As shown in the
variation between the minimum and maximum win rates, the strength as captured
by win rates can vary considerably depending on the test set. We leave for
future work analysis of the test size required to obtain reliable conclusions
about the strength of the preference.

###  4.2 Human Preference Varies by Task and Input Source

We now turn to comparing model preferences relative to downstream task use.

Figure 3: Aggregated annotator win rates across all metrics. Model preferences
can change depending on the task setting.

Figure 3 shows the variation of aggregated preferences on the full 100 sample
test set for CNN/Daily Mail. The context of the task can dramatically change
the win rates for a given model. When contextualized in a specific use-case,
human preferences flip from the overall rating for two out of the three model
comparisons.

The overall win rate for StableLM over FlanT5 is 54% indicating a weak
preference for StableLM. In the world event use case however, the win-rate for
FlanT5 increases to 53%, flipping to a preference for FlanT5. Similarly, the
win rate of StableLM over GPT-4 in the overall condition is 21% but it flips
to 76% in the main details setting. The win rates of FlanT5 over GPT-4 remain
stable across all tasks, always in favor of GPT-4.

Similarly, win rates according to the aggregate human preference for two
systems vary depending with the source of data. In the next section we discuss
how this observed variability changes the approach to validation of automatic
evaluations.

##  5 Validating Automatic Evaluation

We presented qualitative evidence that the context in which preferences are
made change the human preferences dramatically. We also provided clear
examples of cases when human preference for the same two models can flip
depending on the context. This judgement variability poses a novel requirement
for validating automatic evaluation approaches. We cannot combine win rates
across settings and compute correlations between human preferences and
automatic scores because these come from different distributions. We do,
however, have a sufficient number of pairs for comparison: 3 models evaluated
on 3 sources of data, on 4 context of use. This yields 9 overall preferences
and 27 contextually dependent preferences.

For four automatic methods for evaluation, we compute the accuracy of the
automatic score in reproducing human preferences. Specifically, we compute the
percentage of pairwise comparisons for which the automatic evaluation agrees
with the human win rates on which system is the better one. This is a coarse
requirement because it does not capture the size of the win rate. For example
the win rate of one system over another in human preferences is 51% but an
automatic score predicts that its win rate is 79%, the automatic score will be
considered accurate.

Table 1 shows the accuracy for four automatic evaluations: ROUGE-1, BERTScore,
G-Eval, and GPT-4 as an annotator. In the case of GPT-4 as an annotator, we
provide GPT-4 with the exact same instructions as the human annotators. For
the first three approaches, a win for a model is declared if the score
assigned by the method for this input is higher than that for the other model.
In cases when the scores for an input are the same, there is a tie. In the
fourth case, using GPT-4 as an annotator provides ratings, so the wins are
decided by the ranking returned by GPT-4 (rather than a proxy score). In this
case, there are no ties because the annotators were asked to do a forced
choice comparison. We find that ROUGE-1 and GPT-4 as an annotator are able to
moderately predict the aggregated human preferences across the different
tasks, compared to BERTScore and G-Eval which are not able to do so as
reliably.

Metric | Accuracy (%)
---|---
ROUGE-1 | 78
BERTScore | 56
G-Eval | 44
GPT-4 (as annotator) | 78
Table 1: Accuracy of automatic metrics compared to human evaluations. GPT-4
as-an-annotator and ROUGE-1 score have the highest accuracy in predicting
which model is selected by human annotators in each setting task setting.

##  6 Conclusions

We presented automatic and human evaluation designed to establish the minimum
amount of data necessary to evaluate contemporary summarization models.
Comparative evaluations establish which model performs better with test set of
50 inputs. For human evaluation, a test size of 50 is sufficient to
confidently establish which is the model that people prefer. Human preference
varies, however, depending on the intended use of the summary and on the
source of data for summarization. This variation calls for new methods for
validating automatic scores and we propose one. We find that all four
automatic evaluations better than deciding preferences randomly but lead to
erroneous conclusions for many pairwise comparisons.

## Limitations

We only evaluate over benchmark news datasets, where it is possible that our
observations may not be reflected in other, more niche domains. In part, this
choice is due to lack of availability of quality summarization datasets with
references (and further motivating the need for evaluation over small
samples), however it is important for future work to consider more specialized
cases. Another limitation is that we do not collect human annotations nor
GPT-4 summaries over the entire test set splits. This poses a challenge as
collecting these evaluations and summaries over such a big dataset is costly.

## Acknowledgements

We gratefully acknowledge the National Science Foundation (RI 2211954) for
supporting this work.

## References

  * Andonian et al. (2021) Alex Andonian, Quentin Anthony, Stella Biderman, Sid Black, Preetham Gali, Leo Gao, Eric Hallahan, Josh Levy-Kramer, Connor Leahy, Lucas Nestler, Kip Parker, Michael Pieler, Shivanshu Purohit, Tri Songz, Wang Phil, and Samuel Weinbach. 2021.  GPT-NeoX: Large Scale Autoregressive Language Modeling in PyTorch.
  * Card et al. (2020) Dallas Card, Peter Henderson, Urvashi Khandelwal, Robin Jia, Kyle Mahowald, and Dan Jurafsky. 2020.  With Little Power Comes Great Responsibility.  _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 9263–9274.
  * Chung et al. (2022) Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Eric Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, Albert Webson, Shixiang Shane Gu, Zhuyun Dai, Mirac Suzgun, Xinyun Chen, Aakanksha Chowdhery, Sharan Narang, Gaurav Mishra, Adams Yu, Vincent Zhao, Yanping Huang, Andrew Dai, Hongkun Yu, Slav Petrov, Ed H. Chi, Jeff Dean, Jacob Devlin, Adam Roberts, Denny Zhou, Quoc V. Le, and Jason Wei. 2022.  Scaling instruction-finetuned language models.
  * Dror et al. (2018) Rotem Dror, Gili Baumer, Segev Shlomov, and Roi Reichart. 2018.  The hitchhiker’s guide to testing statistical significance in natural language processing.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1383–1392, Melbourne, Australia. Association for Computational Linguistics.
  * Fabbri et al. (2022) Alexander Fabbri, Chien-Sheng Wu, Wenhao Liu, and Caiming Xiong. 2022.  QAFactEval: Improved QA-based factual consistency evaluation for summarization.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 2587–2601, Seattle, United States. Association for Computational Linguistics.
  * Gehrmann et al. (2023) Sebastian Gehrmann, Elizabeth Clark, and Thibault Sellam. 2023.  Repairing the Cracked Foundation: A Survey of Obstacles in Evaluation Practices for Generated Text.  _Journal of Artificial Intelligence Research_ , 77:103–166.
  * Grusky et al. (2018) Max Grusky, Mor Naaman, and Yoav Artzi. 2018.  Newsroom: A dataset of 1.3 million summaries with diverse extractive strategies.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 708–719, New Orleans, Louisiana. Association for Computational Linguistics.
  * Hermann et al. (2015) Karl Moritz Hermann, Tomáš Kočiský, Edward Grefenstette, Lasse Espeholt, Will Kay, Mustafa Suleyman, and Phil Blunsom. 2015.  Teaching machines to read and comprehend.  In _Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 1_ , NIPS’15, page 1693–1701, Cambridge, MA, USA. MIT Press.
  * Laban et al. (2022a) Philippe Laban, Tobias Schnabel, Paul N Bennett, and Marti A Hearst. 2022a.  Summac: Re-visiting nli-based models for inconsistency detection in summarization.  _Transactions of the Association for Computational Linguistics_ , 10:163–177.
  * Laban et al. (2022b) Philippe Laban, Tobias Schnabel, Paul N. Bennett, and Marti A. Hearst. 2022b.  SummaC: Re-Visiting NLI-based Models for Inconsistency Detection in Summarization.  _Transactions of the Association for Computational Linguistics_ , 10:163–177.
  * Lin (2004) Chin-Yew Lin. 2004.  ROUGE: A package for automatic evaluation of summaries.  In _Text Summarization Branches Out_ , pages 74–81, Barcelona, Spain. Association for Computational Linguistics.
  * Liu et al. (2022) Yixin Liu, Alexander R Fabbri, Pengfei Liu, Yilun Zhao, Linyong Nan, Ruilin Han, Simeng Han, Shafiq Joty, Chien-Sheng Wu, Caiming Xiong, and Dragomir Radev. 2022.  Revisiting the Gold Standard: Grounding Summarization Evaluation with Robust Human Evaluation.  _arXiv_.
  * Narayan et al. (2018) Shashi Narayan, Shay B. Cohen, and Mirella Lapata. 2018.  Don’t give me the details, just the summary! topic-aware convolutional neural networks for extreme summarization.  _ArXiv_ , abs/1808.08745.
  * Nenkova and Louis (2008) Ani Nenkova and Annie Louis. 2008.  Can you summarize this? identifying correlates of input difficulty for multi-document summarization.  In _Proceedings of ACL-08: HLT_ , pages 825–833, Columbus, Ohio. Association for Computational Linguistics.
  * Novikova et al. (2018) Jekaterina Novikova, Ondrej Dusek, and Verena Rieser. 2018.  Rankme: Reliable human ratings for natural language generation.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT, New Orleans, Louisiana, USA, June 1-6, 2018, Volume 2 (Short Papers)_ , pages 72–78. Association for Computational Linguistics.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics_ , pages 311–318, Philadelphia, Pennsylvania, USA. Association for Computational Linguistics.
  * Rankel et al. (2011) Peter Rankel, John Conroy, Eric Slud, and Dianne O’Leary. 2011.  Ranking human and machine summarization systems.  In _Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing_ , pages 467–473, Edinburgh, Scotland, UK. Association for Computational Linguistics.
  * See et al. (2017) Abigail See, Peter J. Liu, and Christopher D. Manning. 2017.  Get to the point: Summarization with pointer-generator networks.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1073–1083, Vancouver, Canada. Association for Computational Linguistics.
  * Zhang* et al. (2020) Tianyi Zhang*, Varsha Kishore*, Felix Wu*, Kilian Q. Weinberger, and Yoav Artzi. 2020.  Bertscore: Evaluating text generation with bert.  In _International Conference on Learning Representations_.
  * Zhong et al. (2022) Ming Zhong, Yang Liu, Da Yin, Yuning Mao, Yizhu Jiao, Pengfei Liu, Chenguang Zhu, Heng Ji, and Jiawei Han. 2022.  Towards a unified multi-dimensional evaluator for text generation.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 2023–2038, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.

## Appendix

###  A Summarization Prompt Details

For the summarization prompts, we use prompts and input structures that the
models have been trained on. Table 2 shows the input for each model, where
[TEXT] is replaced with the article to be summarized.

Model | Prompt
---|---
FlanT5 |  [TEXT]\nWhat is a one-paragraph summary of the above article?
StableLM |  | <|SYSTEM|># StableLM Tuned (Alpha version)
---
\- StableLM is a helpful and harmless open-source AI language
model developed by StabilityAI.
\- StableLM is able to facilitate human communication by
providing a summary of a given text.
\- StableLM is able to provide summaries that are useful and
relevant to the given text.
<|USER|> [TEXT].
Summarize the given piece of text.
<|ASSISTANT|>
GPT-4 |  | "role": "user",
---
"content": ”[TEXT] \n\n Summarize the above text. \n\n"

Table 2: Input and prompt structure for each summarization model. [TEXT] is
replaced with the article to be summarized.

###  B BLEU and SummaC-ZS

Figure 4 shows the distributions of averaged BLEU and SummaC-ZS scores over
all three datasets. BLEU scores have trouble capturing meaningful scores
across longer inputs as seen with StableLM. SummaC-ZS uses NLI-models to score
sentence-level information – similar to ROUGE-1 and BERTScore, we can start
differentiating models earlier than the full sample size.

Figure 4: Distributions of averaged BLEU and SummaC-ZS scores across 1000 re-
samples for CNN/DM, XSUM, and Newsroom.

###  C Human Evaluation Win Rates and Sample Sizes: XSUM and Newsroom

We provide the aggregated win rates across annotators for XSUM (Figure 5) and
Newsroom (Figure 6). Both datasets show the same trend as in Figure 2, where
the win rate pair ranking is preserved in the minimum, maximum, and average
win rates across 1000 trials. This holds across sample sizes of 50, but not in
all cases with sample size of 25.

Figure 5: Win rates aggregated by annotators (XSUM). Figure 6: Win rates
aggregated by annotators (Newsroom).

###  D Human Evaluation Win Rates and Tasks: XSUM and Newsroom

Similar to Figure 3, we show the win rates across different tasks for XSUM and
Newsroom in Figure 7. These results support the finding that preference
changes between downstream scenarios.

Figure 7:  Aggregated annotator win rates across all metrics over the XSUM and
Newsroom datasets.

###  E Annotator Agreement on Text Quality and Factuality

For CNN/DM we report the agreement scores over factuality and text quality
questions that we collect in our surveys in Table 3. We expect the agreement
scores for factuality to be much higher; it is possible that this is an
indicator for different tolerance for minor errors (e.g., vague wording) or
may be indicative of the cognitive load involved in judging factuality.
Similarly for text quality, the threshold for artifacts or other issues may
differ between annotators.

CNN/DM
---
Annotators | Factuality $\kappa$ | Text Quality $\kappa$
1, 2 | 0.522 | 0.053
1, 3 | 0.249 | 0.539
2, 3 | 0.133 | -0.081

Table 3: Agreement scores, Cohen’s kappa.

###  F Annotation Details

#### Costs

We hired seven professional proofreaders from Upwork, who were each recruited
to read 100 articles and rank 3 summaries per article. We paid each annotator
a flat fee of $325 to evaluate the summaries When asked for a time estimate
after they completed, responses ranged between 10 and 13 hours to complete the
study, meaning annotators were compensated at roughly $25-$30 per hour. The
annotators typically completed the work over one to three days.

#### Annotation Platform

We presented the annotators with a custom interface for ranking the summaries
and answering questions, shown in Figure 8. Annotators were encouraged to take
extended breaks during annotation to reduce task fatigue.

(a) Summaries, as presented to the annotators.

(b) Text quality issues and the ranking interface for the summaries. Each box
with the summary label can be dragged-and-dropped into any order.

(c) Article, as presented to the annotator.

(d) Factuality questions asked about each summary.

Figure 8: The annotation interface. For each article, annotation happens
across two pages. The first page contains the summaries (8(a)) and rankings
(8(b)), and the second page contains the article (8(c)) and factuality
questions (8(d)).


# Computing $k$-Crossing Visibility through $k$-levels

Frank Duque Email<EMAIL_ADDRESS>Research supported by the Universidad
Nacional de Colombia research, grant HERMES-58357. Escuela de Matemáticas,
Universidad Nacional de Colombia Sede Medellín

###### Abstract

Let $\mathcal{A}$ be an arrangement of straight lines in the plane (or planes
in $\mathbb{R}^{3}$). The $k$-crossing visibility of a point $p$ on
$\mathcal{A}$ is the set of point $q$ in elements of $\mathcal{A}$ such that
the segment $pq$ intersects at most $k$ elements of $\mathcal{A}$. In this
paper, we obtain algorithms for computing the $k$-crossing visibility. In
particular we obtain $O(n\log n+kn)$ and $O(n\log n+k^{2}n)$ time algorithms,
for arrangements of lines in the plane and planes in $\mathbb{R}^{3}$; which
are optimal for $k=\Omega(\log n)$ and $k=\Omega(\sqrt{\log n})$,
respectively. We also introduce another algorithm for computing $k$-crossing
visibilities on polygons, which reaches the same asymptotical time as the one
presented by Bahoo et al. The ideas introduced in this paper can be easily
adapted for obtaining $k$-crossing visibilities on other arrangements whose
$(\leq k)$-level is known.

##  1 Introduction

Visibility is a natural phenomenon in everyday life. We see objects to
determine our location, plan movements without colliding with other objects,
or interact with our environment. Similarly, the concept of visibility is
fundamental in several areas of Computer Science; including Robotics [6, 17,
18, 21], Computer Vision [14, 16], and Computer Graphics [10, 23, 12]. In the
case of Computational Geometry, the notion of visibility has also been used
extensively in the context of the art gallery problem [20, 24, 15, 22].

The development of wireless network connections has motivated the study of a
new kind of visibility. Consider locating a router in a building, so that any
device within the building will receive a strong enough signal to guarantee a
stable Internet connection. There are two main limitations when trying to
connect a device to a wireless network: its distance to the wireless router
and the number of walls that separate it from the router. However, in many
builds, the primary limitation is the number of walls that separate the device
from the router, rather than the distance between them [1]. Given an
arrangement $\mathcal{A}$ of straight lines, rays and segments in
$\mathbb{R}^{2}$ (or planes in $\mathbb{R}^{3}$), and two points $p$ and $q$,
we say that $p$ and $q$ are $k$-crossing visible if the interior of the line
segment $pq$ intersects at most $k$ elements of $\mathcal{A}$. The set of
points in $\mathbb{R}^{2}$ ($\mathbb{R}^{3}$) that are $k$-crossing visible
from $p$ is called the $k$-crossing visibility region of $p$. Thus if $p$ and
$\mathcal{A}$ correspond to the router and the obstacles, respectively, the
$k$-crossing visibility region corresponds to the possible positions of the
devices, such that they are separated by at most $k$ walls. In Figure 1 we
illustrate in yellow the $2$-crossing visibility region of a point on an
arrangement of segments.

Figure 1: Illustration of the $2$-crossing visibility region (yellow) and the
$2$-crossing visibility (blue) of the red point on an arrangement of lines.

Let $\mathcal{A}$ be an arrangement of straight lines, rays and segments in
$\mathbb{R}^{2}$ (or planes in $\mathbb{R}^{3}$). The $k$-crossing visibility
of a point $p$ in $\mathbb{R}^{2}$ ($\mathbb{R}^{3}$) on $\mathcal{A}$,
denoted by $\mathcal{V}_{k}\left(p,\mathcal{A}\right)$, is the portion of the
elements of $\mathcal{A}$ that are in the $k$-crossing visibility region of
$p$. In Figure 1, we illustrate $\mathcal{V}_{2}\left(p,\mathcal{A}\right)$ in
blue for a point $p$ and an arrangement of lines $\mathcal{A}$. In this paper,
we are interested in algorithms for computing
$\mathcal{V}_{k}\left(p,\mathcal{A}\right)$ and determining upper bounds for
the size of this arrangement.

The concept of $k$-crossing visibility was first introduced by Mouad and
Shermer [19] in what they originally called the Superman problem: Given a
simple polygon $P$, a sub-polygon $Q\subset P$, and a point $p$ outside $P$,
determine the minimum number of edges of $P$ that must be made opaque such
that no point of $Q$ is $0$-crossing visible to $p$. Dean et al. [11] studied
pseudo-star-shaped polygons, in which the line of visibility can cross one
edge, corresponding to $k$-crossing visibility where $k=1$. Bajuelos et al [5]
subsequently explored the concept of $k$-crossing visibility for an
arbitrarily given $k$, and presented an $O(n^{2})$-time algorithm to construct
$\mathcal{V}_{k}\left(p,P\right)$ for an arbitrary given point $p$. Recently
Bahoo et al.[4] introduced an algorithm that computes
$\mathcal{V}_{k}\left(p,P\right)$ in $O(nk)$-time.

######  Theorem 1.1 (Bahoo et al. [4]).

Given a simple polygon $P$ with $n$ vertices and a query point $p$ in $P$, the
region of $P$ that is $k$-crossing visible from $p$, can be computed in
$O(kn)$ time.

In this work we obtain another proof of Theorem 1.1 and we prove Theorem 1.2,
Theorem 1.4, Proposition 1.3 and Proposition 1.5.

######  Theorem 1.2.

Let $\mathcal{A}$ be an arrangement of $n$ lines in the plane, and let $p$ be
a query point. Then $\mathcal{V}_{k}\left(p,\mathcal{A}\right)$ can be
computed in $O(n\log n+kn)$ time.

Given an arrangement $\mathcal{A}$ of straight lines, rays and segments in the
plane (or planes in $\mathbb{R}^{3}$), the combinatorial complexity of
$\mathcal{A}$, is the total number of vertices and edges (and faces) defined
by $\mathcal{A}$.

######  Proposition 1.3.

The maximum combinatorial complexity of the $k$-crossing visibility on
arrangements of $n$ straight lines in the plane is $\theta(kn)$.

######  Theorem 1.4.

Let $\mathcal{A}$ be an arrangement of $n$ planes in $\mathbb{R}^{3}$, and let
$p$ be a query point. Then $\mathcal{V}_{k}\left(p,\mathcal{A}\right)$ can be
computed in $O(n\log n+k^{2}n)$ expected time.

######  Proposition 1.5.

The maximum combinatorial complexity of the $k$-crossing visibility on
arrangements of $n$ planes in $\mathbb{R}^{3}$ is $\theta(k^{2}n)$.

Note that, by Proposition 1.3 and Proposition 1.5, Theorem 1.2 and Theorem 1.4
are optimal for $k=\Omega(\log n)$ and $k=\Omega(\sqrt{\log n})$,
respectively.

Given an arrangement $\mathcal{A}$ of objects in $\mathbb{R}^{2}$ (or
$\mathbb{R}^{3}$), the $(\leq k)$-level-region of $\mathcal{A}$ is the set of
points in $\mathbb{R}^{2}$ (or $\mathbb{R}^{3}$) with at most $k$ elements of
$\mathcal{A}$ lying above it. In the following, we denote by ${(\leq
k)level}\left(\mathcal{A}\right)$, to the portion of the elements of
$\mathcal{A}$ that are in the $(\leq k)$-level-region of $\mathcal{A}$.

Let $\mathcal{T}$ be the transformation

$\displaystyle\mathcal{T}\left(\left(x,y\right)\right)$
$\displaystyle=\left(x/y,1/y\right)$ in the $\mathbb{R}^{2}$ case, or
$\displaystyle\mathcal{T}\left(\left(x,y,z\right)\right)$
$\displaystyle=\left(x/z,y/z,1/z\right)$ in the $\mathbb{R}^{3}$ case.

In this paper we obtain a linear time reduction, of the problem of obtaining
$\mathcal{V}_{k}\left(p,\mathcal{A}\right)$ to the problem of obtaining
${(\leq k)level}\left(\mathcal{A}\right)$, by applying $\mathcal{T}$. As
consequence we obtain another proof of Theorem 1.1 and we prove Theorem 1.2,
Theorem 1.4, Proposition 1.3 and Proposition 1.5. This reduction can be easily
adapted for obtaining $k$-crossing visibilities on another arrangements whose
$(\leq k)$-level is known.

This paper is organized as follows. In Section 2 we first determine several
properties of $\mathcal{T}$, then we use them to prove Theorem 1.2, Theorem
1.1 and Proposition 1.3. In Section 3 we translate the properties of
$\mathcal{T}$ from $\mathbb{R}^{2}$ to $\mathbb{R}^{3}$ obtaining Theorem 1.4
and Proposition 1.5.

##  2 Results in $\mathbb{R}^{2}$

Let $\mathcal{D}$ be the set of points $\left(x,y\right)\in\mathbb{R}^{2}$
such that $y\neq 0$. Throughout this section, $O$ denotes the point
$\left(0,0\right)\in\mathbb{R}^{2}$ and $\mathcal{T}$ denotes the
transformation $\mathcal{T}:\mathcal{D}\rightarrow\mathcal{D}$ such that
$\mathcal{T}\left(\left(x,y\right)\right)=\left(x/y,1/y\right).$

In this section, we prove that $\mathcal{T}$ determines a bridge between
$k$-crossing visibility and $(\leq k)$-levels in $\mathbb{R}^{2}$. Then, we
use this result to prove Theorem 1.1, Theorem 1.2 and Proposition 1.3.

###  2.1 Properties of $\mathcal{T}$

Given $D\subset\mathcal{D}$ we denote by $\mathcal{T}\left[D\right]$ the image
of $D$ under $\mathcal{T}$. We also denote by
$\mathcal{T}\left[\mathcal{A}\right]$ the set images of the elements of
$\mathcal{A}$ under $\mathcal{T}$. In this section, we first prove several
properties of $\mathcal{T}$. Then, we determine $\mathcal{T}\left[D\right]$
for different instances of $D$. Finally, we prove that
$\mathcal{V}_{k}\left(O,\mathcal{A}\right)$ can be obtained from ${(\leq
k)level}\left(\mathcal{T}\left[\mathcal{A}\right]\right)$.

######  Proposition 2.1.

$\mathcal{T}$ is self-inverse.

###### Proof.

Let $\left(x,y\right)\in\mathcal{D}$, then
$\mathcal{T}o\mathcal{T}(\left(x,y\right))=\mathcal{T}(\left(x/y,1/y\right))=\left(x,y\right)$.
∎

######  Proposition 2.2.

$\mathcal{T}$ sends straight lines to straight lines. More precisely, if $L$
is the straight line in $\mathcal{D}$ with equation $ax+by+c=0$ then
$\mathcal{T}\left[L\right]$ is the straight line in $\mathcal{D}$ with
equation $ax+cy+b=0$.

###### Proof.

Let $L^{\prime}$ be the straight line with equation $ax+cy+b=0$. If
$\left(x_{0},y_{0}\right)\in\mathcal{D}$ is in $L$ then $ax_{0}+by_{0}+c=0$;
thus, as $a\frac{x_{0}}{y_{0}}+c\frac{1}{y_{0}}+b=0$, then
$\mathcal{T}\left(x_{0},y_{0}\right)$ is in $L^{\prime}$. Similarly, if
$\left(x_{0},y_{0}\right)\in\mathcal{D}$ is in $L^{\prime}$ then
$\mathcal{T}^{-1}\left(x_{0},y_{0}\right)=\mathcal{T}\left(x_{0},y_{0}\right)$
is in $L$. ∎

######  Proposition 2.3.

$\mathcal{T}$ preserve incidences between points and lines. More precisely the
point $p$ is in the straight line $L$ if and only if $\mathcal{T}(p)$ is in
the straight line $\mathcal{T}\left[L\right]$.

###### Proof.

Let $p=(x_{0},y_{0})$ be a point in $\mathcal{D}$ and let $L:ax+by+c=0$ be a
straight line in $\mathcal{D}$. This proof follows from the fact that
$(x_{0},y_{0})$ satisfies $ax+by+c=0$ if and only if
$\left(\frac{x_{0}}{y_{0}},\frac{1}{y_{0}}\right)$ satisfies
$\mathcal{T}\left[L\right]:ax+cy+b=0$. ∎

Given a line $L$ in $\mathcal{D}$, we denote by $L^{+}$ the set of points in
$L$ whose second coordinate is greater than zero, and we denote by $L^{-}$ the
set of points in $L$ whose second coordinate is less than zero.

######  Proposition 2.4.

Let $L$ be a straight line in $\mathcal{D}$. Then
$\mathcal{T}\left[L^{+}\right]=\mathcal{T}\left[L\right]^{+}$ and
$\mathcal{T}\left[L^{-}\right]=\mathcal{T}\left[L\right]^{-}$. Moreover, if
$p_{1},p_{2},\ldots,p_{k}$ are in $L^{+}$ (or they are in $L^{-}$) ordered by
their distance to the $x$-axis from the closest to the furthest, then
$\mathcal{T}(p_{1}),\mathcal{T}(p_{2}),\ldots,\mathcal{T}(p_{k})$ are in
$\mathcal{T}\left[L^{+}\right]$ (or they are in
$\mathcal{T}\left[L^{-}\right]$, respectively), ordered by their distance to
the $x$-axis from the furthest to the closest.

###### Proof.

As $\mathcal{T}$ sends straight lines to straight lines and it does not change
the sign of the second coordinate, then
$\mathcal{T}\left[L^{+}\right]=\mathcal{T}\left[L\right]^{+}$ and
$\mathcal{T}\left[L^{-}\right]=\mathcal{T}\left[L\right]^{-}$. If the second
coordinates of $p_{i}$ and $p_{j}$ are $y_{i}$ and $y_{j}$, respectively, then
the second coordinates of $\mathcal{T}(p_{i})$ and $\mathcal{T}(p_{j})$ are
$1/y_{i}$ and $1/y_{j}$, respectively. This proof follows from the fact that
$|y_{i}|<|y_{j}|$ if and only if $|1/y_{i}|>|1/y_{j}|$. ∎

Let $\mathcal{D}^{+}$ denote the set of points in $\mathcal{D}$ whose second
coordinate is greater than zero, and let $\mathcal{D}^{-}$ denote the set of
points in $\mathcal{D}$ whose second coordinate is less than zero. The proofs
of Proposition 2.5 and Proposition 2.6 follows from Proposition 2.4.

######  Proposition 2.5.

Let $D$ be a line segment contained in a straight line $L$, whose endpoints
are $p$ and $q$.

  * •

If both $p$ and $q$ are in $\mathcal{D}^{+}$ ($\mathcal{D}^{-}$), then
$\mathcal{T}\left[D\right]$ is the line segment contained in $\mathcal{D}^{+}$
($\mathcal{D}^{-}$) whose endpoints are $\mathcal{T}(p)$ and $\mathcal{T}(q)$.

  * •

If $p$ is in the $x$-axis and $q$ is in $\mathcal{D}^{+}$ ($\mathcal{D}^{-}$),
then $\mathcal{T}\left[D\right]$ is the ray contained in $\mathcal{D}^{+}$
($\mathcal{D}^{-}$), defined by the straight line $\mathcal{T}\left[L\right]$
and the point $\mathcal{T}(q)$.

Given a $D\subset\mathcal{D}$ we denote by $\overline{D}$ the closure of $D$
in $\mathbb{R}^{2}$.

######  Proposition 2.6.

Let $D$ be a no horizontal ray contained in a straight line $L$, whose
endpoint is $p$.

  * •

If both $p$ and $D$ are in $\mathcal{D}^{+}$ ($\mathcal{D}^{-}$), then
$\mathcal{T}\left[D\right]$ is the line segment contained in $\mathcal{D}^{+}$
($\mathcal{D}^{-}$), whose endpoints are $\mathcal{T}(p)$ and the intersection
of $\overline{\mathcal{T}\left[L\right]}$ with the $x$-axis.

  * •

If $p$ is in the $x$-axis and $D$ is in $\mathcal{D}^{+}$ ($\mathcal{D}^{-}$),
then $\mathcal{T}\left[D\right]$ is the ray defined by the part of the
straight line $\mathcal{T}\left[L\right]$ in $\mathcal{D}^{+}$
($\mathcal{D}^{-}$).

######  Proposition 2.7.

Let $D$ be a horizontal ray contained in a straight line $L$ whose endpoint is
$p$. If $D$ is contained in $\mathcal{D}^{+}$ ($\mathcal{D}^{-}$), then
$\mathcal{T}\left[D\right]$ is the horizontal ray in $\mathcal{D}^{+}$
($\mathcal{D}^{-}$), defined by the straight line $\mathcal{T}\left[L\right]$
and the point $\mathcal{T}(p)$. If $D$ is contained in $\mathcal{D}^{+}$, then
$D$ and $\mathcal{T}\left[D\right]$ have the same direction; in the other
case, $D$ and $\mathcal{T}\left[D\right]$ have opposite direction.

###### Proof.

If $L$ has equation $by+c=0$ then $\mathcal{T}\left[L\right]$ is the
horizontal line with equation $cy+b=0$. Thus, if $D$ is contained in
$\mathcal{D}^{+}$ ($\mathcal{D}^{-}$) then $\mathcal{T}\left[D\right]$ is also
contained in $\mathcal{D}^{+}$ ($\mathcal{D}^{-}$); moreover,
$\mathcal{T}\left[D\right]$ is the horizontal ray defined by the straight line
$\mathcal{T}\left[L\right]$ and the point $\mathcal{T}(p)$. As
$\mathcal{T}\left(x_{0},y_{0}\right)=\left(\frac{x_{0}}{y_{0}},\frac{1}{y_{0}}\right)$,
the direction of $D$ only changes if $D$ is contained in $\mathcal{D}^{-}$. ∎

From Proposition 2.2, Proposition 2.5, Proposition 2.6 and Proposition 2.7 we
conclude that: If $D$ is a straight line, ray or segment contained in
$\mathcal{D}^{+}$ ($\mathcal{D}^{-}$) then $\mathcal{T}\left[D\right]$ is a
straight line, ray or segment contained in $\mathcal{D}^{+}$
($\mathcal{D}^{-}$).

######  Proposition 2.8.

Let $L$ be a straight line in $\mathcal{D}$. Then $O\in\overline{L}$ if and
only if $\mathcal{T}\left[L\right]$ is a vertical line.

###### Proof.

This proof follows from the fact that $\overline{L}$ has equation $ax+by=0$ if
and only if $\mathcal{T}\left[L\right]$ has equation $ax+b=0$ ∎

Let $\mathcal{V}_{k}^{+}\left(O,\mathcal{A}\right)$ denote the portions of the
elements of $\mathcal{V}_{k}\left(O,\mathcal{A}\right)$ in $\mathcal{D}^{+}$,
$i.e.$

$\mathcal{V}_{k}^{+}\left(O,\mathcal{A}\right)=\left\\{D\cap\mathcal{D}^{+}:D\in\mathcal{V}_{k}\left(O,\mathcal{A}\right)\right\\}$

Similarly, let $\mathcal{V}_{k}^{-}\left(O,\mathcal{A}\right)$ denote the
portions of $\mathcal{V}_{k}\left(O,\mathcal{A}\right)$ in $\mathcal{D}^{-}$,
$i.e.$

$\mathcal{V}_{k}^{-}\left(O,\mathcal{A}\right)=\left\\{D\cap\mathcal{D}^{-}:D\in\mathcal{V}_{k}\left(O,\mathcal{A}\right)\right\\}$

Let ${(\leq k)level^{+}}\left(\mathcal{A}\right)$ denote the portion of the
elements of ${(\leq k)level}\left(\mathcal{A}\right)$ in $\mathcal{D}^{+}$,
$i.e.$

${(\leq
k)level^{+}}\left(\mathcal{A}\right)=\left\\{D\cap\mathcal{D}^{+}:D\in{(\leq
k)level}\left(\mathcal{A}\right)\right\\}$

The $(\leq k)$-lower-level-region of $\mathcal{A}$ is the set of points in
$\mathbb{R}^{2}$ ($\mathbb{R}^{3}$) with at most $k$ elements of $\mathcal{A}$
lying below it. Let ${(\leq k)level^{-}}\left(\mathcal{A}\right)$ denote the
portion of the elements of $\mathcal{A}$ in both $\mathcal{D}^{-}$ and the
$(\leq k)$-lower-level-region of $\mathcal{A}$.

######  Lemma 2.9.

Let $\mathcal{A}$ be an arrangement of straight lines, segments or rays. Then:

  1. 1.

$\mathcal{V}_{k}^{+}\left(O,\mathcal{A}\right)=\mathcal{T}\left[{(\leq
k)level^{+}}\left(\mathcal{T}\left[\mathcal{A}\right]\right)\right]$.

  2. 2.

$\mathcal{V}_{k}^{-}\left(O,\mathcal{A}\right)=\mathcal{T}\left[{(\leq
k)level^{-}}\left(\mathcal{T}\left[\mathcal{A}\right]\right)\right]$.

###### Proof.

We prove 1, the proof of 2 is similar.

Let $p\in\mathcal{D}^{+}$ be such that $p\in D$ for some $D\in\mathcal{A}$,
and let $L$ be the line that contains $p$ and $O$. Then $p\in L^{+}$,
$\mathcal{T}\left[D\right]\in\mathcal{T}\left[\mathcal{A}\right]$ and
$\mathcal{T}(p)\in\mathcal{T}\left[D\right]$. As $\mathcal{T}$ preserves
incidences, by Proposition 2.8 and Proposition 2.4, the line segment between
$O$ and $p$ crosses at most $k$ elements of $\mathcal{A}$, if and only if,
there are at most $k$ elements of $\mathcal{T}\left[\mathcal{A}\right]$ laying
above $\mathcal{T}(p)$. ∎

###  2.2 Proofs of results in $\mathbb{R}^{2}$

######  Theorem 2.10 (Everett et al. [13]).

Let $\mathcal{A}$ be an arrangement of $n$ lines in the plane. Then ${(\leq
k)level}\left(\mathcal{A}\right)$ can be computed in $O(n\log n+kn)$ time.

We use Theorem 2.10 in order to prove Theorem 1.2.

###### Proof of Theorem 1.2.

Without loss of generality, we may assume that $p$ is at the origin, otherwise
$p$ and the elements of $\mathcal{A}$ can be translated. We also may assume
that the $x$-axis does not contain an element of $\mathcal{A}$ or an
intersection between two elements of $\mathcal{A}$, otherwise, the elements of
$\mathcal{A}$ can be rotated.

By Proposition 2.2, $\mathcal{T}\left[\mathcal{A}\right]$ is an arrangement of
$n$ straight lines. Thus, as the $k$-crossing visibility of $O$ on
$\mathcal{A}$ can be obtained from
$\mathcal{V}_{k}^{+}\left(O,\mathcal{A}\right)$ and
$\mathcal{V}_{k}^{-}\left(O,\mathcal{A}\right)$, this proof follows from Lemma
2.9 and Theorem 2.10. ∎

Let $\mathcal{A}$ be an arrangement of straight lines, rays and segments. The
vertical decomposition (also known as trapezoidal decomposition) of
$\mathcal{A}$ is obtained by erecting vertical segments upwards and downwards
from each vertex in $\mathcal{A}$ and extend them until they meet another line
or all the way to infinity.

######  Lemma 2.11.

Let $\mathcal{A}$ be an arrangement of $n$ straight lines, rays and segments.
Then ${(\leq k)level}\left(\mathcal{A}\right)$ can be obtained from a vertical
decomposition of $\mathcal{A}$ in $O(kn)$ time.

###### Proof.

Suppose that the vertical decomposition of $A$ is known. Then for each vertex,
extend a vertical segment upwards until it reaches $k+1$ elements of
$\mathcal{A}$ or its way to infinity; such vertex is in ${(\leq
k)level}\left(\mathcal{A}\right)$ if and only if the vertical segment reaches
its way to infinity. ∎

###### Another proof of Theorem 1.1.

As in the proof of Theorem 1.2, we may assume that $p$ is at the origin and
the $x$-axis does not contain edges of $P$. By Proposition 2.5,
$\mathcal{T}\left[P\right]$ is an arrangement of at most $2n$ line segments or
rays. Thus, as the $k$-crossing visibility of $O$ on $P$ can be obtained from
$\mathcal{V}_{k}^{+}\left(O,P\right)$ and
$\mathcal{V}_{k}^{-}\left(O,P\right)$, by Lemma 2.9 and Lemma 2.11, it is
enough to obtain the vertical decomposition of
$\mathcal{T}\left[P\right]\cap\mathcal{D}^{+}$ and
$\mathcal{T}\left[P\right]\cap\mathcal{D}^{-}$ in linear time; we do this for
$\mathcal{T}\left[P\right]\cap\mathcal{D}^{+}$, the other case is similar.

Let $L:y+c=0$ be a horizontal line, high enough that all the endpoints of
$\mathcal{T}\left[P\right]\cap\mathcal{D}^{+}$ are below $L$. Let
$L^{\prime}=\mathcal{T}\left[L\right]$ and note that $L^{\prime}$ is a
horizontal line with equation $cy+1=0$. Suppose that the points in $P$ above
$L^{\prime}$ are blue and the others are red. Let $P^{\prime}$ be the polygon
in $\mathcal{D}^{+}$ obtained from $P$ by scaling vertically its red part,
keeping the endpoints on $L^{\prime}$ fixed.

In [8] Chazelle prove that the vertical decomposition of a polygon can be
computed in linear time (see also Amato et al. [3]). Thus, as $P^{\prime}$ is
contained in $\mathcal{D}^{+}$, by Proposition 2.5
$\mathcal{T}\left[P^{\prime}\right]$ is a polygon, and the vertical
decomposition of $\mathcal{T}\left[P^{\prime}\right]$ can be computed in
linear time. Note that a point $\mathcal{T}(q)$ in
$\mathcal{T}\left[P\right]\cap\mathcal{D}^{+}$ is below $L$ if and only if $q$
is blue. Thus the vertical decomposition of
$\mathcal{T}\left[P\right]\cap\mathcal{D}^{+}$ can be obtained from the
vertical decomposition of $\mathcal{T}\left[P^{\prime}\right]$ below $L$. ∎

###### Proof of Proposition 1.3.

In [2] Alon et al. prove that the maximum combinatorial complexity of the
$(\leq k)$-level on arrangements of $n$ straight lines in the plane is
$\theta(nk)$. Note that the arrangement $\mathcal{A}$, that reaches this
bound, can be considered with all the points of intersection in
$\mathcal{D}^{+}$. Thus, the combinatorial complexity of ${(\leq
k)level^{+}}\left(\mathcal{A}\right)$ is also $\theta(nk)$, and by Lemma 2.9
the combinatorial complexity of
$\mathcal{V}_{k}^{+}\left(O,\mathcal{T}\left[\mathcal{A}\right]\right)$ is
$\theta(nk)$. ∎

##  3 Results in $\mathbb{R}^{3}$

Let $\mathcal{D}$ be the set of points $\left(x,y,z\right)\in\mathbb{R}^{3}$
such that $z\neq 0$. Throughout this section, $O$ denotes the point
$\left(0,0,0\right)\in\mathbb{R}^{3}$ and $\mathcal{T}$ denotes the
transformation $\mathcal{T}:\mathcal{D}\rightarrow\mathcal{D}$ be such that

$\mathcal{T}\left(\left(x,y,z\right)\right)=\left(x/z,y/z,1/z\right).$

The proofs of Proposition 3.1, Proposition 3.2, Proposition 3.3, Proposition
3.4, Proposition 3.5 and Lemma 3.6, can be obtained as in Section 2.

######  Proposition 3.1.

$\mathcal{T}$ is self-inverse.

###### Proof.

Let $\left(x,y,z\right)\in\mathcal{D}$, then
$\mathcal{T}o\mathcal{T}(\left(x,y,z\right))=\mathcal{T}(\left(x/z,y/z,1/z\right))=\left(x,y,z\right)$.
∎

######  Proposition 3.2.

$\mathcal{T}$ sends planes to planes. More precisely, if $\pi$ is the plane in
$\mathcal{D}$ with equation $ax+by+cz+d=0$ then $\mathcal{T}\left[\pi\right]$
is the plane in $\mathcal{D}$ with equation $ax+by+dz+c=0$.

###### Proof.

Let $\pi^{\prime}$ be the plane with equation $ax+by+dz+c=0$. If
$\left(x_{0},y_{0},z_{0}\right)\in\mathcal{D}$ is in $\pi$ then
$ax_{0}+by_{0}+cz_{0}+d=0$; thus, as
$a\frac{x_{0}}{z_{0}}+b\frac{y_{0}}{z_{0}}+d\frac{1}{z_{0}}+c=0$, then
$\mathcal{T}\left(x_{0},y_{0},z_{0}\right)$ is in $\pi^{\prime}$. Similarly,
if $\left(x_{0},y_{0},z_{0}\right)\in\mathcal{D}$ is in $\pi^{\prime}$ then
$\mathcal{T}^{-1}\left(x_{0},y_{0},z_{0}\right)=\mathcal{T}\left(x_{0},y_{0},z_{0}\right)$
is in $\pi$. ∎

######  Proposition 3.3.

$\mathcal{T}$ preserve incidences between points and planes. More precisely
the point $p$ is in the plane $\pi$ in $\mathcal{D}$ if and only if
$\mathcal{T}(p)$ is in the plane $\mathcal{T}\left[\pi\right]$ in
$\mathcal{D}$.

###### Proof.

Let $p=(x_{0},y_{0},z_{0})$ be a point in $\mathcal{D}$ and let
$\pi:ax+by+cz+d=0$ be a plane in $\mathcal{D}$. This proof follows from the
fact that $(x_{0},y_{0},z_{0})$ satisfies $ax+by+cz+d=0$ if and only if
$\left(\frac{x_{0}}{z_{0}},\frac{y_{0}}{z_{0}},\frac{1}{z_{0}}\right)$
satisfies $\mathcal{T}\left[\pi\right]:ax+by+dz+c=0$. ∎

Given a plane $\pi$ in $\mathcal{D}$, we denote by $\pi^{+}$ the set of points
in $\pi$ whose third coordinate is greater than zero, and we denote by
$\pi^{-}$ the set of points in $\pi$ whose third coordinate is less than zero.

######  Proposition 3.4.

Let $\pi$ be a plane in $\mathcal{D}$. Then
$\mathcal{T}\left[\pi^{+}\right]=\mathcal{T}\left[\pi\right]^{+}$ and
$\mathcal{T}\left[\pi^{-}\right]=\mathcal{T}\left[\pi\right]^{-}$. Moreover,
if $p_{1},p_{2},\ldots,p_{k}$ are in $\pi^{+}$ (or they are in $\pi^{-}$)
ordered by their distance to the plane $z=0$ from the closest to the furthest,
then $\mathcal{T}(p_{1}),\mathcal{T}(p_{2}),\ldots,\mathcal{T}(p_{k})$ are in
$\mathcal{T}\left[\pi^{+}\right]$ (or they are in
$\mathcal{T}\left[\pi^{-}\right]$, respectively), ordered by their distance to
the plane $z=0$ from the furthest to the closest.

###### Proof.

As $\mathcal{T}$ sends planes to planes and it does not change the sign of the
third coordinate, then
$\mathcal{T}\left[\pi^{+}\right]=\mathcal{T}\left[\pi\right]^{+}$ and
$\mathcal{T}\left[\pi^{-}\right]=\mathcal{T}\left[\pi\right]^{-}$. If the
third coordinates of $p_{i}$ and $p_{j}$ are $z_{i}$ and $z_{j}$,
respectively, then the third coordinates of $\mathcal{T}(p_{i})$ and
$\mathcal{T}(p_{j})$ are $1/z_{i}$ and $1/z_{j}$, respectively. This proof
follows from the fact that $|z_{i}|<|z_{j}|$ if and only if
$|1/z_{i}|>|1/z_{j}|$. ∎

Given a $D\subset\mathcal{D}$ we denote by $\overline{D}$ the closure of $D$
in $\mathbb{R}^{3}$.

######  Proposition 3.5.

Let $L$ be a straight line in $\mathcal{D}$. Then $O\in\overline{L}$ if and
only if $\mathcal{T}\left[L\right]$ is a vertical line.

###### Proof.

As
$\mathcal{T}\left(td_{1},td_{2},td_{3}\right)=\left(\frac{d_{1}}{d_{3}},\frac{d_{2}}{d_{3}},\frac{1}{td_{3}}\right)$,
$\mathcal{T}^{-1}\left(a,b,t\right)=\mathcal{T}\left(a,b,t\right)=\frac{1}{t}\left(a,b,1\right)$
and $\mathcal{T}$ is self-inverse then $O\in\overline{L}$ if and only if
$\mathcal{T}\left[L\right]$ is a vertical line. ∎

######  Lemma 3.6.

Let $\mathcal{A}$ be an arrangement of planes. Then:

  1. 1.

$\mathcal{V}_{k}^{+}\left(O,\mathcal{A}\right)=\mathcal{T}\left[{(\leq
k)level^{+}}\left(\mathcal{T}\left[\mathcal{A}\right]\right)\right]$.

  2. 2.

$\mathcal{V}_{k}^{-}\left(O,\mathcal{A}\right)=\mathcal{T}\left[{(\leq
k)level^{-}}\left(\mathcal{T}\left[\mathcal{A}\right]\right)\right]$.

###### Proof.

Similar to the proof of Lemma 2.9. ∎

The proofs of Theorem 1.4 and Proposition 1.5 follows from Theorem 3.7 and
Theorem 3.8, in a similar way as in the proof of Theorem 1.2 and the proof of
Proposition 1.3 in Section 2.

######  Theorem 3.7 (Chan [7]).

Let $\mathcal{A}$ be an arrangement of $n$ planes in $\mathbb{R}^{3}$. Then
${(\leq k)level}\left(\mathcal{A}\right)$ can be computed in $O(n\log
n+k^{2}n)$ expected time.

######  Theorem 3.8 (Clarkson et al. [9]).

Let $k\geq 1$. Then the maximum combinatorial complexity of $(\leq k)$-level
on arrangements of $n$ hyperplanes in $\mathbb{R}^{d}$ is
$\theta\left(n^{\lfloor d/2\rfloor}k^{\lceil d/2\rceil}\right)$.

## References

  * [1] Oswin Aichholzer, Ruy Fabila-Monroy, David Flores-Peñaloza, Thomas Hackl, Jorge Urrutia, and Birgit Vogtenhuber.  Modem illumination of monotone polygons.  Computational Geometry, 68:101–118, 2018.
  * [2] Noga Alon and Ervin Györi.  The number of small semispaces of a finite set of points in the plane.  Journal of Combinatorial Theory, Series A, 41(1):154–157, 1986\.
  * [3] Nancy M Amato, Michael T Goodrich, and Edgar A Ramos.  A randomized algorithm for triangulating a simple polygon in linear time.  Discrete & Computational Geometry, 26(2):245–265, 2001.
  * [4] Yeganeh Bahoo, Prosenjit Bose, Stephane Durocher, and Thomas Shermer.  Computing the $k$-crossing visibility region of a point in a polygon.  In Charles J. Colbourn, Roberto Grossi, and Nadia Pisanti, editors, Combinatorial Algorithms, pages 10–21, Cham, 2019. Springer International Publishing.
  * [5] Antonio Bajuelos, Santiago Canales, Gregorio Hernández, and Mafalda Martins.  A hybrid metaheuristic strategy for covering with wireless devices.  J. Univers. Comput. Sci., 18(14):1906–1932, 2012.
  * [6] Amy J Briggs and Bruce Randall Donald.  Visibility-based planning of sensor control strategies.  Algorithmica, 26(3):364–388, 2000.
  * [7] Timothy Chan.  Random sampling, halfspace range reporting, and construction of $(\leq k)$-levels in three dimensions.  SIAM Journal on Computing, 30(2):561–575, 2000.
  * [8] Bernard Chazelle.  Triangulating a simple polygon in linear time.  Discrete & Computational Geometry, 6(3):485–524, 1991.
  * [9] Kenneth Clarkson and Peter Shor.  Applications of random sampling in computational geometry, ii.  Discrete & Computational Geometry, 4(5):387–421, 1989.
  * [10] Michael F Cohen, John R Wallace, and Pat Hanrahan.  Radiosity and realistic image synthesis.  Morgan Kaufmann, 1993.
  * [11] James Dean, Andrzej Lingas, and Jörg-Rüdiger Sack.  Recognizing polygons, or how to spy.  The Visual Computer, 3(6):344–355, 1988.
  * [12] Susan E Dorward.  A survey of object-space hidden surface removal.  International Journal of Computational Geometry & Applications, 4(03):325–362, 1994.
  * [13] Hazel Everett, Jean-Marc Robert, and Marc van Kreveld.  An optimal algorithm for the ($\leq k$)-levels, with applications to separation and transversal problems.  International Journal of Computational Geometry Applications, 06(03):247–261, 1996.
  * [14] Olivier Faugeras and Olivier Autor Faugeras.  Three-dimensional computer vision: a geometric viewpoint.  MIT press, 1993.
  * [15] Subir Kumar Ghosh.  Visibility algorithms in the plane.  Cambridge university press, 2007.
  * [16] Ziv Gigus, John Canny, and Raimund Seidel.  Efficiently computing and representing aspect graphs of polyhedral objects.  IEEE Trans. Pattern Anal. Mach. Intell., 13(6):542–551, jun 1991\.
  * [17] Jean-Claude Latombe.  Robot motion planning, volume 124.  Springer Science & Business Media, 2012.
  * [18] Tomás Lozano-Pérez and Michael A Wesley.  An algorithm for planning collision-free paths among polyhedral obstacles.  Communications of the ACM, 22(10):560–570, 1979.
  * [19] Naji Mouawad and Thomas Shermer.  The superman problem.  The Visual Computer, 10(8):459–473, 1994.
  * [20] Joseph O’Rourke et al.  Art gallery theorems and algorithms, volume 57.  Oxford University Press Oxford, 1987.
  * [21] M Peshkin and A Sanderson.  Reachable grasps on a polygon: the convex rope algorithm.  IEEE Journal on Robotics and Automation, 2(1):53–58, 1986.
  * [22] Thomas C Shermer.  Recent results in art galleries (geometry).  Proceedings of the IEEE, 80(9):1384–1399, 1992.
  * [23] Csaba D Toth, Joseph O’Rourke, and Jacob E Goodman.  Handbook of discrete and computational geometry.  CRC press, 2017.
  * [24] Godfried T Toussaint.  Shortest path solves edge-to-edge visibility in a polygon.  Pattern Recognition Letters, 4(3):165–170, 1986.