Search

Since its introduction in 1957, Lloyd's algorithm for $k$-means clustering has been extensively studied and has undergone several improvements. While in its original form it does not guarantee any approximation factor at all, Arthur and Vassilvitskii (SODA 2007) proposed $k$-means++ which enhances Lloyd's algorithm by a seeding method which guarantees a $\mathcal{O}(\log k)$-approximation in expectation. More recently, Lattanzi and Sohler (ICML 2019) proposed LS++ which further improves the solution quality of $k$-means++ by local search techniques to obtain a $\mathcal{O}(1)$-approximation. On the practical side, the greedy variant of $k$-means++ is often used although its worst-case behaviour is provably worse than for the standard $k$-means++ variant. We investigate how to improve LS++ further in practice. We study two options for improving the practical performance: (a) Combining LS++ with greedy $k$-means++ instead of $k$-means++, and (b) Improving LS++ by better entangling it with Lloyd's algorithm. Option (a) worsens the theoretical guarantees of $k$-means++ but improves the practical quality also in combination with LS++ as we confirm in our experiments. Option (b) is our new algorithm, Foresight LS++. We experimentally show that FLS++ improves upon the solution quality of LS++. It retains its asymptotic runtime and its worst-case approximation bounds.

Using the newly developed 530 MeV positron beam from the Mainz Microtron MAMI and employing a bent silicon crystal, we demonstrate the first successful manipulation with high efficiencies of the trajectories of positrons through planar channeling and volume reflection. This uncovered the presence of fine structure within the angular distribution of charged particles when they are channeled between the planes of bent crystals. The alignment of our experimental findings with simulation results not only demonstrates a deeper understanding of the interactions between charged particle beams and bent crystals but also signals a new phase in the development of innovative methodologies for slow extraction in circular accelerators operating in the GeV range, with implications for worldwide accelerators. Our results also mark a considerable progression in the generation of advanced x-ray sources through the channeling process in periodically bent crystals, rooted in a comprehensive understanding of the interactions between positron beams and such crystals.

Recently, a simple but powerful language for expressing and learning general policies and problem decompositions (sketches) has been introduced in terms of rules defined over a set of Boolean and numerical features. In this work, we consider three extensions of this language aimed at making policies and sketches more flexible and reusable: internal memory states, as in finite state controllers; indexical features, whose values are a function of the state and a number of internal registers that can be loaded with objects; and modules that wrap up policies and sketches and allow them to call each other by passing parameters. In addition, unlike general policies that select state transitions rather than ground actions, the new language allows for the selection of such actions. The expressive power of the resulting language for policies and sketches is illustrated through a number of examples., Comment: ICAPS 2024

We report the measurement of the helicity asymmetry $E$ for the $p\pi^0$ and $n\pi^+$ final states using, for the first time, an elliptically polarized photon beam in combination with a longitudinally polarized target at the Crystal Ball experiment at MAMI. The results agree very well with data that were taken with a circularly polarized photon beam, showing that it is possible to simultaneously measure polarization observables that require linearly (e.g.~$G$) and circularly polarized photons (e.g.~$E$) and a longitudinally polarized target. The new data cover a photon energy range 270 - 1400 MeV for the $p\pi^0$ final state (230 - 842 MeV for the $n\pi^+$ final state) and the full range of pion polar angles, $\theta$, providing the most precise measurement of the observable $E$. A moment analysis gives a clear observation of the $p\eta$ cusp in the $p\pi^0$ final state.

Early detection of melanoma, a potentially lethal type of skin cancer with high prevalence worldwide, improves patient prognosis. In retrospective studies, artificial intelligence (AI) has proven to be helpful for enhancing melanoma detection. However, there are few prospective studies confirming these promising results. Existing studies are limited by low sample sizes, too homogenous datasets, or lack of inclusion of rare melanoma subtypes, preventing a fair and thorough evaluation of AI and its generalizability, a crucial aspect for its application in the clinical setting. Therefore, we assessed 'All Data are Ext' (ADAE), an established open-source ensemble algorithm for detecting melanomas, by comparing its diagnostic accuracy to that of dermatologists on a prospectively collected, external, heterogeneous test set comprising eight distinct hospitals, four different camera setups, rare melanoma subtypes, and special anatomical sites. We advanced the algorithm with real test-time augmentation (R-TTA, i.e. providing real photographs of lesions taken from multiple angles and averaging the predictions), and evaluated its generalization capabilities. Overall, the AI showed higher balanced accuracy than dermatologists (0.798, 95% confidence interval (CI) 0.779-0.814 vs. 0.781, 95% CI 0.760-0.802; p<0.001), obtaining a higher sensitivity (0.921, 95% CI 0.900- 0.942 vs. 0.734, 95% CI 0.701-0.770; p<0.001) at the cost of a lower specificity (0.673, 95% CI 0.641-0.702 vs. 0.828, 95% CI 0.804-0.852; p<0.001). As the algorithm exhibited a significant performance advantage on our heterogeneous dataset exclusively comprising melanoma-suspicious lesions, AI may offer the potential to support dermatologists particularly in diagnosing challenging cases.

We consider the following natural problem that generalizes min-sum-radii clustering: Given is $k\in\mathbb{N}$ as well as some metric space $(V,d)$ where $V=F\cup C$ for facilities $F$ and clients $C$. The goal is to find a clustering given by $k$ facility-radius pairs $(f_1,r_1),\dots,(f_k,r_k)\in F\times\mathbb{R}_{\geq 0}$ such that $C\subseteq B(f_1,r_1)\cup\dots\cup B(f_k,r_k)$ and $\sum_{i=1,\dots,k} g(r_i)$ is minimized for some increasing function $g:\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}_{\geq 0}$. Here, $B(x,r)$ is the radius-$r$ ball centered at $x$. For the case that $(V,d)$ is the shortest-path metric of some edge-weighted graph of bounded treewidth, we present a dynamic program that is tailored to this class of problems and achieves a polynomial running time, establishing that the problem is in $\mathsf{XP}$ with parameter treewidth., Comment: updated funding information

The vast majority of ASR research uses corpora in which both the training and test data have been pre-segmented into utterances. In most real-word ASR use-cases, however, test audio is not segmented, leading to a mismatch between inference-time conditions and models trained on segmented utterances. In this paper, we re-release three standard ASR corpora - TED-LIUM 3, Gigapeech, and VoxPopuli-en - with updated transcription and alignments to enable their use for long-form ASR research. We use these reconstituted corpora to study the train-test mismatch problem for transducers and attention-based encoder-decoders (AEDs), confirming that AEDs are more susceptible to this issue. Finally, we benchmark a simple long-form training for these models, showing its efficacy for model robustness under this domain shift., Comment: Submitted to ICASSP 2024

The $k$-center problem is a classical clustering problem in which one is asked to find a partitioning of a point set $P$ into $k$ clusters such that the maximum radius of any cluster is minimized. It is well-studied. But what if we add up the radii of the clusters instead of only considering the cluster with maximum radius? This natural variant is called the $k$-min-sum-radii problem. It has become the subject of more and more interest in recent years, inspiring the development of approximation algorithms for the $k$-min-sum-radii problem in its plain version as well as in constrained settings. We study the problem for Euclidean spaces $\mathbb{R}^d$ of arbitrary dimension but assume the number $k$ of clusters to be constant. In this case, a PTAS for the problem is known (see Bandyapadhyay, Lochet and Saurabh, SoCG, 2023). Our aim is to extend the knowledge base for $k$-min-sum-radii to the domain of fair clustering. We study several group fairness constraints, such as the one introduced by Chierichetti et al. (NeurIPS, 2017). In this model, input points have an additional attribute (e.g., colors such as red and blue), and clusters have to preserve the ratio between different attribute values (e.g., have the same fraction of red and blue points as the ground set). Different variants of this general idea have been studied in the literature. To the best of our knowledge, no approximative results for the fair $k$-min-sum-radii problem are known, despite the immense amount of work on the related fair $k$-center problem. We propose a PTAS for the fair $k$-min-sum-radii problem in Euclidean spaces of arbitrary dimension for the case of constant $k$. To the best of our knowledge, this is the first PTAS for the problem. It works for different notions of group fairness.

Photoproduction of $\pi^0\pi^{\pm}$-pairs from quasifree nucleons bound in the deuteron has been investigated to study the helicity dependence of this reaction. Measurements with a liquid deuterium target were used to extract the unpolarized cross sections for reactions on protons and neutrons. A deuterated, longitudinally polarized solid-butanol target, together with a circularly polarized photon beam, determined the double polarization observable $E$. From these results the spin-dependent cross sections $\sigma_{1/2}$ and $\sigma_{3/2}$, corresponding to the anti-parallel and parallel spin configurations of the beam photon and target nucleon, have been derived. The measurements were performed at the Mainz MAMI accelerator with tagged, circularly-polarized photon beams produced via bremsstrahlung from longitudinally polarized electron beams. The reaction products were detected with an almost $4\pi$ solid-angle covering calorimeter composed of the Crystal Ball and TAPS detectors, supplemented by plastic scintillation detectors for charged particle identification. The results are sensitive to sequential decays of nucleon resonances via intermediate states and also to the decay of nucleon resonances by emission of charged $\rho$ mesons, and are compared to recent model results., Comment: 9 pages, 6 figures

Quantitative tissue information, like the light scattering properties, is considered as a key player in the detection of cancerous cells in medical diagnosis. A promising method to obtain these data is optical coherence tomography (OCT). In this article, we will therefore discuss the refractive index reconstruction from OCT data, employing a Gaussian beam based forward model. We consider in particular samples with a layered structure, meaning that the refractive index as a function of depth is well approximated by a piece-wise constant function. For the reconstruction, we present a layer-by-layer method where in every step the refractive index is obtained via a discretized least squares minimization. For an approximated form of the minimization problem, we present an existence and uniqueness result. The applicability of the proposed method is then verified by reconstructing refractive indices of layered media from both simulated and experimental OCT data., Comment: 27 pages, 12 figures, 4 tables

Non-invasive imaging plays a crucial role in diagnosing and studying eye diseases. However, existing photoacoustic ophthalmoscopy (PAOM) techniques in mice have limitations due to handling restrictions, suboptimal optical properties, limited availability of light sources and permissible light fluence at the retina. This study introduces an innovative approach that utilizes Rose Bengal, a contrast agent, to enhance PAOM contrast. This enables visualization of deeper structures like the choroidal microvasculature and sclera in the mouse eye using visible light. The integration of near-infrared-II optical coherence tomography (NIR-II OCT) provides additional tissue contrast and insights into potential NIR-II PAOM capabilities. To optimize imaging, we developed a cost-effective 3D printable mouse eye phantom and a fully 3D printable tip/tilt mouse platform. This solution elevates PAOM to a user-friendly technology, which can be used to address pressing research questions concerning several ocular diseases such as myopia, glaucoma and/or age-related macular degeneration in the future., Comment: 14 pages, 4 figures

Background: Convolutional neural network (CNN)-based melanoma classifiers face several challenges that limit their usefulness in clinical practice. Objective: To investigate the impact of multiple real-world dermoscopic views of a single lesion of interest on a CNN-based melanoma classifier. Methods: This study evaluated 656 suspected melanoma lesions. Classifier performance was measured using area under the receiver operating characteristic curve (AUROC), expected calibration error (ECE) and maximum confidence change (MCC) for (I) a single-view scenario, (II) a multiview scenario using multiple artificially modified images per lesion and (III) a multiview scenario with multiple real-world images per lesion. Results: The multiview approach with real-world images significantly increased the AUROC from 0.905 (95% CI, 0.879-0.929) in the single-view approach to 0.930 (95% CI, 0.909-0.951). ECE and MCC also improved significantly from 0.131 (95% CI, 0.105-0.159) to 0.072 (95% CI: 0.052-0.093) and from 0.149 (95% CI, 0.125-0.171) to 0.115 (95% CI: 0.099-0.131), respectively. Comparing multiview real-world to artificially modified images showed comparable diagnostic accuracy and uncertainty estimation, but significantly worse robustness for the latter. Conclusion: Using multiple real-world images is an inexpensive method to positively impact the performance of a CNN-based melanoma classifier.