Staff

Abstract:
Suppose that we have a method which estimates the conditional probabilities of some unknown stochastic source and we use it to guess which of the outcomes will happen. We want to make a correct guess as often as it is possible. What estimators are good for this? In this work, we consider estimators given by a familiar notion of universal coding for stationary ergodic measures, while working in the framework of algorithmic randomness, i.e., we are particularly interested in prediction of Martin-Löf random points. We outline the general theory and exhibit some counterexamples. Completing a result of Ryabko from 2009 we also show that universal probability measure in the sense of universal coding induces a universal predictor in the prequential sense. Surprisingly, this implication holds true provided the universal measure does not ascribe too low conditional probabilities to individual symbols. As an example, we show that the Prediction by Partial Matching (PPM) measure satisfies this requirement with a large reserve.

Keywords:
algorithmic randomness, stationary ergodic processes, universal coding, universal prediction, prediction by partial matching

Abstract:
Recently, a connection has been established between two branches of computability theory, namely between algorithmic randomness and algorithmic learning theory. Learning-theoretical characterizations of several notions of randomness were discovered. We study such characterizations based on the asymptotic density of positive answers. In particular, this note provides a new learning-theoretic definition of weak 2-randomness, solving the problem posed by (Zaffora Blando, Rev. Symb. Log. 2019). The note also highlights the close connection between these characterizations and the problem of convergence on random sequences.

Keywords:
algorithmic randomness, learning theory, effectivization

Abstract:
Building upon the recent successes in the application of information-theoretic concepts (e.g. Shannon entropy) in quantitative ultrasound, the authors propose a novel tissue characterization method based on the Lempel–Ziv complexity. In this procedure, standard ultrasound B-Mode images are mapped onto words over finite alphabets before the corresponding Lempel–Ziv complexity of ultrasound images is calculated. Such complexity metric may be used to differentiate between types of tissues. Here, the method is utilized as a binary classifier for the malignancy of breast lesions. The method is tested on OASBUD – an open-access breast lesions image database. Images of 48 malignant and 48 benign lesions were used – two images for each lesion. The new procedure slightly outperforms the state-of-art classifier based on pixel entropy as measured in the size of area under the receiver operating curve (ROC AUC), which suggests that it may serve as a basis for computer-assisted breast cancer ultrasound diagnosis and possibly in other standard applications of the quantitative ultrasound.

Keywords:
quantitative ultrasound, tissue characterization, speckles, breast cancer, Lempel–Ziv complexity, applied information theory, space-filling curves

Abstract:
We consider the notion of prediction functions (or predictors) studied before in the context of randomness and stochasticity by Ko, and later by Ambos‐Spies and others. Predictor is a total computable function which tries to predict bits of some infinite binary sequence. The prediction error is defined as the limit of the number of incorrect answers divided by the number of answers given so far. We discuss indefiniteness of prediction errors for weak 1‐generics and show that this phenomenon affects certain c.e. sequences as well. On the other hand, a notion of optimal predictor is considered. It is shown that there is a sequence for which increasingly better predictors exist but for which no predictor is optimal.

Abstract:
Ultradźwiękowe systemy Phased-Array pozwalają na różne tryby skanowania i wizualizacji wad oraz zapewniają wyższą jakość inspekcji niż tradycyjne systemy jednokanałowe. Kolejnym krokiem w rozwoju tych systemów będzie metoda akwizycji pełnej macierzy oraz zaawansowane algorytmy rekonstrukcji obrazów. W artykule przedstawiono zasady działania tych technik oraz wymagania jakie stawiają one przed systemami akwizycji i przetwarzania sygnałów. Zaprezentowano także badawczy system Uniwersalnej Platformy Ultradźwiękowej, który został opracowany specjalnie do testowania i praktycznego wdrażania tych metod. Platforma posłużyła do badań i porównania dwóch metod rekonstrukcji przy wykorzystaniu akwizycji pełnej macierzy – metody STA (Synthetic Transmit Aperture) i metody PWI (Plane Wave Imaging).

Keywords:
UT Phased-Array, akwizycja pełnej macierzy, syntetyczna apertura

Abstract:
Delle Rose et al. (COLT’23) introduced an effective version of the Vapnik-Chervonenkis dimension, and showed that it characterizes improper PAC learning with total computable learners. In this paper, we introduce and study a similar effectivization of the notion of Littlestone dimension. Finite effective Littlestone dimension is a necessary condition for computable online learning but is not a sufficient one—which we already establish for classes of the effective Littlestone dimension 2. However, the effective Littlestone dimension equals the optimal mistake bound for computable learners in two special cases: a) for classes of Littlestone dimension 1 and b) when the learner receives as additional information an upper bound on the numbers to be guessed. Interestingly, a finite effective Littlestone dimension also guarantees that the class consists only of computable functions.

Keywords:
online learning, Littlestone dimension, computability

Abstract:
In perpetual voting, multiple decisions are made at different moments in time. Taking the history of previous decisions into account allows us to satisfy properties such as proportionality over periods of time. In this paper, we consider the following question: is there a perpetual approval voting method that guarantees that no voter is dissatisfied too many times? We identify a sufficient condition on voter behavior ---which we call 'bounded conflicts' condition---under which a sublinear growth of dissatisfaction is possible. We provide a tight upper bound on the growth of dissatisfaction under bounded conflicts, using techniques from Kolmogorov complexity. We also observe that the approval voting with binary choices mimics the machine learning setting of prediction with expert advice. This allows us to present a voting method with sublinear guarantees on dissatisfaction under bounded conflicts, based on the standard techniques from prediction with expert advice.

Abstract:
We consider online learning in the model where a learning algorithm can access the class only via the consistent oracle—an oracle, that, at any moment, can give a function from the class that agrees with all examples seen so far. This model was recently considered by Assos et al. (COLT’23). It is motivated by the fact that standard methods of online learning rely on computing the Littlestone dimension of subclasses, a computationally intractable problem. Assos et al. gave an online learning algorithm in this model that makes at most Cd mistakes on classes of Littlestone dimension d, for some absolute unspecified constant C > 0. We give a novel algorithm that makes at most O(256d) mistakes. Our proof is significantly simpler and uses only very basic properties of the Littlestone dimension. We also show that there exists no algorithm in this model that makes less than 3d mistakes. Our algorithm (as well as the algorithm of Assos et al.) solves an open problem by Hasrati and Ben-David (ALT’23). Namely, it demonstrates that every class of finite Littlestone dimension with recursively enumerable representation admits a computable online learner (that may be undefined on unrealizable samples).

Keywords:
Online learning, consistent oracle, Littlestone dimension

Abstract:
In peer review systems, reviewers are often asked to evaluate various features of submissions, such as technical quality or novelty. A score is given to each of the predefined features and based on these the reviewer has to provide an overall quantitative recommendation. It may be assumed that each reviewer has her own mapping from the set of features to a recommendation, and that different reviewers have different mappings in mind. This introduces an element of arbitrariness known as commensuration bias. In this paper we discuss a framework, introduced by Noothigattu, Shah and Procaccia, and then applied by the organizers of the AAAI 2022 conference. Noothigattu, Shah and Procaccia proposed to aggregate reviewer’s mapping by minimizing certain loss functions, and studied axiomatic properties of this approach, in the sense of social choice theory. We challenge several of the results and assumptions used in their work and report a number of negative results. On the one hand, we study a trade-off between some of the axioms proposed and the ability of the method to properly capture agreements of the majority of reviewers. On the other hand, we show that dropping a certain unrealistic assumption has dramatic effects, including causing the method to be discontinuous.

Abstract:
This paper contributes to the study of CPAC learnability—a computable version of PAC learning—by solving three open questions from recent papers. Firstly, we prove that every improperly CPAC learnable class is contained in a class which is properly CPAC learnable with polynomial sample complexity. This confirms a conjecture by Agarwal et al (COLT 2021). Secondly, we show that there exists a decidable class of hypotheses which is properly CPAC learnable, but only with uncomputably fast-growing sample complexity. This solves a question from Sterkenburg (COLT2022). Finally, we construct a decidable class of finite Littlestone dimension which is not improperly CPAC learnable, strengthening a recent result of Sterkenburg (2022) and answering a question posed by Hasrati and Ben-David (ALT 2023). Together with previous work, our results provide a complete landscape for the learnability problem in the CPAC setting

Keywords:
PAC learnability, CPAC learnability, VC dimension, Littlestone dimension, computability, foundations of machine learning

Abstract:
Can a probabilistic gambler get arbitrarily rich when all deterministic gamblers fail? We study this problem in the context of algorithmic randomness, introducing a new notion – almost everywhere computable randomness. A binary sequence X is a.e. computably random if there is no probabilistic computable strategy which is total and succeeds on X for positive measure of oracles. Using the fireworks technique we construct a sequence which is partial computably random but not a.e. computably random. We also prove the separation between a.e. computable randomness and partial computable randomness, which happens exactly in the uniformly almost everywhere dominating Turing degrees.

Keywords:
algorithmic randomness, martingales, probabilistic computation, almost everywhere domination

Abstract:
A sequence of zeros and ones is called Church stochastic if all subsequences chosen in an effective manner satisfy the law of large numbers with respect to the uniform measure. This notion may be independently defined by means of simple martingales, i.e., martingales with restricted (constant) wagers (hence, simply random sequences). This paper is concerned with generalization of Church stochasticity for arbitrary (possibly non-stationary) measures. We compare two ways of doing this: (i) via a natural extension of the law of large numbers (for non-i.i.d. processes) and (ii) via restricted martingales, i.e., by redefining simple randomness for arbitrary measures. It is shown that in the general case of non-uniform measures the respective notions of stochasticity do not coincide but the first one is contained in the second.

Abstract:
A novel kind of a negative result is presented for the problem of computable prediction. A non-stationary binary stochastic process is constructed for which almost surely no effective method of prediction achieves the infimum of prediction errors defined as the normalized Hamming distance between the sequence of predictions and the realization of the process. Yet it is shown that this process may be effectively predicted almost surely up to an arbitrarily small error since the infimum of prediction errors is zero.

Abstract:
The widely adopted ultrasound Phased-Array (PA) systems for nondestructive testing (NDT) use standard beamforming for line-by-line image creation. The introduction of the new full-matrix capture (FMC) technique enables the implementation of advanced processing algorithms (e.g. the total focusing method, multi-pass adaptive techniques). However, the limited availability of portable PA systems with FMC capabilities prevents widespread introduction. Our goal was to demonstrate the feasibility of a portable PA solution with FMC and advanced processing with the help of a mobile GPU. Using an OEM ultrasound front-end module (us4us Ltd., Poland), we integrated a complete PA system with an embedded Nvidia Tegra X2 module. An external probe adapter enables a direct connection to commercial Olympus-NDT PA probes with up to 128-elements (32-element active RX aperture). The system is fully programmable, both in the front-end (TX/RX schemes, acquisition parameters), as well as in the digital signal processing chain. Raw RF data is acquired and transferred to mobile GPU memory for processing. The algorithm can be conveniently implemented using a standard Nvidia CUDA toolkit. We implemented real-time B-mode imaging with the total focusing method for demonstration purposes. The presented all-in-one system is a fully flexible tool for the research and evaluation of novel Phased-Array FMC methods and complex signal processing algorithms. An extended programmability and real-time access to raw channel data allows to create custom solutions specifically dedicated to any one NDT application. Mobile GPU parallel processing provides a strong enough performance for real-time imaging. Its small size and low-power consumption make the system an ideal candidate for a portable industrial flaw detector with advanced processing.

Abstract:
The medical management of patients with continuous-flow left ventricular assist devices (LVADs) requires frequent measurement and analysis of various physiological parameters. Among the most important is blood pressure (BP), which cannot be reliably measured by the standard oscillometric method because of an impaired pulsation due to continuous flow. The objective of this work is to show the feasibility of ultrasound-based BP measurement in a portable, easy to use device for patients with LVAD in home-based rehabilitation environments, enabling long-term remote monitoring. We have implemented a BP measurement system which uses continuous wave (CW) Doppler ultrasound for blood flow detection. The system is based on a standard cuff design with custom analog CW circuitry connected to a high-performance, low-power 32-bit microcontroller (ARM Cortex-M7). The uC is responsible for system control, as well as Doppler signal acquisition and processing. A dedicated ultrasound probe equipped with an elastic strap is placed over the radial artery. In the target solution, the cuff pressure and CW signal will be analyzed in real-time to provide systolic and/or mean blood pressure. At present, we have acquired raw signals for off-line analysis. The system was tested in clinical experiments both on healthy patients and patients with three types of commercially available LVADs (HeartWare, HeartMate II and HeartMate III). The observed morphology of Doppler signals in patients with LVADs was much more variable between patients and pumps. In most cases, we were able to estimate the systolic pressure, but the measurement of diastolic pressure was not conclusive. We observed variable blood flow patterns generated by the Lavare cycle (a periodic speed modulation feature of some LVADs), which further complicates the estimation. A prototype of an automatic BP measuring device for patients with rotary LVADs has been demonstrated. In the next step, we are planning an animal validation study with invasive blood pressure monitoring

Keywords:
Biomedical monitoring, Doppler effect, Blood pressure, Blood, Pressure measurement, Ultrasonic variables measurement, Standards

Abstract:
Ultrasound Phased-Array (PA) systems for nondestructive testing (NDT) use standard beamforming for line-byline image creation. New methods utilizing full-matrix capture (FMC) enable the application of advance processing algorithms, such as the total focusing method and multi-pass adaptive techniques for enhanced flaw visualization. The effective FMC data acquisition and its real-time processing require a very high data throughput and powerful computational resources. Most commercial PA systems support some form of FMC acquisition, but the limited external data bandwidth prevents this mode of operation from being useful. We have developed a fully programmable ultrasound research system capable of performing FMC data acquisition and image reconstruction with a high framerate. The ultrasound platform is supporting up to 192 parallel TX/RX electronics channels integrated with an embedded control PC and a GPU cluster for parallel processing. The implemented software libraries give the end-user control over TX/RX schemes, the acquisition process and signal processing algorithms. This all-in-one system is a fully flexible tool for the research and evaluation of novel Phased-Array FMC imaging methods and complex signal processing algorithms.

Keywords:
GPU, ultrasound, Phased-Array