# Musical creativity enabled by nonlinear oscillations of a bubble in water

Ivan S. Maksymov<EMAIL_ADDRESS>Artificial Intelligence and Cyber
Futures Institute, Charles Sturt University, Bathurst, NSW 2795, Australia

###### Abstract

Producing original and arranging existing musical outcomes is an art that
takes years of learning and practice to master. Yet, despite the constant
advances in the field of AI-powered musical creativity, production of quality
musical outcomes remains a prerogative of the humans. Here we demonstrate that
a single bubble in water can be used to produce creative musical outcomes,
when it nonlinearly oscillates under an acoustic pressure signal that encodes
a piece of classical music. The audio signal of the response of the bubble
resembles an electric guitar version of the original composition. We suggest,
and provide plausible theoretical supporting arguments, that this property of
the bubble can be used to create physics-inspired AI systems capable of
simulating human creativity in arrangement and composition of music.

##  I Introduction

Bubbles in liquids underpin many important natural phenomena [1, 2, 3, 4],
including cavitation [1] and sound of running water [5, 6]. Oscillations of
bubbles driven by an acoustic pressure wave are also similar to the behaviour
of a biological brain since both the brain [7] and the bubble [2] are
nonlinear dynamical systems [8]. Subsequently, studies of oscillating bubbles
may help understand certain brain functions that are responsible for
perception of sounds and music. The following experimental evidence speaks in
favour of this proposition.

Firstly, it has been demonstrated that the electric charge impulses that
underpin the nerve signalling are accompanied by acousto-mechanical (sound)
waves that are intrinsically nonlinear [9, 10, 11, 12]. Secondly, it has been
shown that human experience in musics is mediated by nonlinear-acoustical
processes [13] and that the same processes underpin the auditory processing
abilities of some animals [14]. In particular, in an experiment involving owls
exposed to a piece of classical music made up of tones with deliberately
removed fundamental frequency harmonics, the owl’s brain restored the missing
fundamental harmonics [15]. While such a behaviour is of considerable interest
in the field of nonlinear physics [16], effectively the owl’s brain
transferred a musical idea from its original position to a lower frequency,
which is a common examples of octave transposition [14]. Significantly, while
transposition in musics is a nontrivial task that is accessible mostly to
individuals with a formal relevant education, a biological brain can do this
type of audio processing naturally. Thirdly, it is also well-known that
nonlinear-acoustical processes [13] underpin the operation of many musical
instruments [17] and that musicians, as well as many people who love music but
do not have formal background in it, understand nonlinear effects naturally
without knowing much about nonlinear physics [14]. This fact also indicated
that a biological brain can naturally process nonlinear acoustic signals.

Recently, we suggested that a cluster of oscillating bubbles in water can
operate as an artificial neural network that exhibits complex nonlinear
behaviour and that can be trained to predict highly nonlinear and chaotic time
series that arise in many practical situations [18] such as the analysis of
financial markets, weather forecasting and control of autonomous vehicles [19,
20, 21, 22]. Thus, since the particular kind of the artificial neural networks
that oscillating bubbles can efficiently emulate—the Echo State Network (ESN)
[19] and Liquid State Machine (LSM) [23]—can also reproduce some functions of
a biological brain, it is conceivable that oscillating bubbles may also
reproduce some of the brain’s functions, including those associated with the
perception of music. Hence, in this work we suggest that a highly nonlinear
behaviour of an oscillating bubble could be used to complete some tasks that
require musical creativity.

Musical creativity can be defined as a process of employing existing musical
knowledge to produce novel musical outcomes that may take, for example, the
form of improvisations, compositions and arrangements. The production of
quality musical outcomes remains one of the most challenging tasks for machine
learning systems [24] despite the recent significant progress in AI-powered
musical creativity (see [25, 26, 27, 28] to cite a few works). Subsequently,
the idea that a simple bubble could produce a creative musical output is not
only fundamentally intriguing but can also lead to new knowledge in the field
of AI.

As a representative example, we synthesise a simple version of “In the Hall of
the Mountain King”, a piece of music composed by Edvard Grieg, and use it as
the acoustic signal that drives nonlinear oscillations of a single bubble in
water. By means of rigorous numerical simulations, we demonstrate that the
output signal produced by the bubble is perceived as a “heavy metal” cover on
the original composition decorated with warm and gritty tones typical of an
electric guitar [29].

Figure 1: Notes of the piece of music used as the acoustic signal that drives
the oscillations of the bubble.

This paper is organised as follows. Our main findings are presented in Sect.
II and followed by the discussion in Sect. III. The discussion is supported by
a comprehensive theoretical analysis and numerical modelling of the physical
properties of an acoustically driven oscillating bubble, the results of which
are presented in Sect. A and Sect. B. Since memory is one of the prerequisites
of creativity [30, 31], we employ the ESN algorithm described in Sect. C to
demonstrate in Sect. D that an oscillating bubbles possesses a memory capacity
suitable for applications in the field of AI.

##  II Results

We choose a simple piano version of “In the Hall of the Mountain King” by
Edvard Grieg to be the acoustic signal driving oscillations of the bubble
(Fig. 1). This composition is well-known to the general public and is also
often used by musicians to produce their own recordings. Relying on the
principles of 8-bit computer music arrangement [32], we encode each note of
the melody as a sequence of square pulses repeated at the frequency of the
$n$th key of an idealised acoustic piano:

$f(n)=2^{\frac{n-49}{12}}\times 440\,\text{Hz}\,.$ (1)

A four beats per bar time signature of the melody and its 120 bpm tempo also
enable us to calculate the duration of each bar in seconds. Although this
approach cannot be used reproduce the exact sound of a piano, it suffices to
create an easily recognisable version of the composition (see the
supplementary audio file out.in) in a format suitable for processing by the
numerical model employed in this work.

In the numerical model, we consider a single mm-sized bubble. The fundamental
nonlinear physics underlying the interaction of a mm-sized bubble with a
single square acoustic pressure pulse is discussed in Sect. B. Here we analyse
the response of the bubble to a sequence of identical square pulses that
encode the melody. We also record the response of the bubble as an audio file
(see the supplementary file out.wav) and we discuss the aesthetic
characteristics of the resulting audio record.

While the results presented in this section were obtained using positive
square pressure pulses that increase the ambient pressure of the bubble in a
stepwise manner, similar physical behaviour of the bubble was also observed
using negative square pulses. Pulses of different peak amplitude and temporal
duration were also considered. We established that the choice of the type of
the pulses and of their particular duration and peak amplitude influences the
aesthetic characteristics of the output produced by the bubble. Therefore,
instead of being guided by the physics of interaction between the bubble and
acoustic pressure pulses, our choice of the model parameters is dictated by
the goal of achieving an appealing aesthetic characteristic.

In Fig. 2(a) we plot several input square pulses corresponding to the notes of
the melody (the black curve) and compare them with the respective acoustic
response of the bubble (the red curve). Nonlinear response of oscillating
bubbles has been the subject of many theoretical and experimental works (see
[33, 1, 2, 34, 35] to cite a few), and we establish that the response of the
bubble to the acoustic signature of the melody is also highly nonlinear.
Moreover, we can see that the bubble continues oscillating during the periods
of time between the individual pulses associated with the musical notes. This
result speaks in favour of the ability of the oscillating bubble to have
memory, which is an essential property of a nonlinear processing unit suitable
for application in ESN as well as a prerequisite for artificial creativity
(see Sect. D).

Figure 2: (a) Waveforms corresponding to three notes of the input melody (the
black curve) and the respective acoustic response of the bubble (the red
curve). The green rectangle highlights the time range of a magnified portion
of the signals plotted in the inset located below the main panel. (b) Fourier
power spectra of the waveforms shown in the inset to panel (a).

In particular, we argue that a prolonged oscillation of the bubble excited by
the sound of the composition is equivalent to the sustain effect used in the
music instruments such as electric guitar and piano, where the length of time
a note audibly resonates is deliberately prolonged [29]. This behaviour can
also correspond to the so-called nonlinearity with memory employed in advanced
digital implementations of electric guitar distortion effects [36, 37]. There,
an idealised nonlinear system with memory can be represented analytically as a
Volterra series, where the output of the nonlinear system depends on the input
to the system at all other times, thereby providing the ability to create
fading memory [38].

Indeed, as shown in Fig. 2(b), in the frequency domain the nonlinearity of the
bubble manifests itself as the enrichment of the spectrum with higher-order
harmonics—compare the black curve corresponding to the spectrum of the
acoustic signature of the melody with the red curve corresponding to the
response of the bubble. In electric guitar performances, the appearance of
higher-order harmonics is associated with fuzzy and gritty tones [29, 39, 36].
Subsequently, the recorded output signal (see the supplementary file out.wav)
is aesthetically perceived as an electric guitar cover of the original piece
of music.

To test our perception, we asked people with formal music education to listen
to the output signal and they confirmed that the melody indeed closely
resembles an electric guitar version of the original melody. We also used
Audacity audio processing software, where we applied the standard static
nonlinear audio processing effects to the original melody to simulate the
effect of an electric guitar [39, 36]. The goal of this procedure was to
reproduce the lineshape and spectrum of the bubble response as well as to
recreate the electric guitar effect of the bubble on the original composition.

The result of application of the digital effects is shown in Fig. 3, where we
applied reverberation, which is a process relevant to both memory in
artificial intelligence [40] and to cognitive memory [41], and a guitar
distortion effect that enriches the spectrum with the higher-order harmonics
of the fundamental frequency [39, 29] (the nonlinearity of this distortion
effect is memoryless [36, 37], which justifies the addition of the
reverberation effect to our model). The lineshape and the spectral composition
of the digitally produced signal (the blue curve) resemble those of the
response of the bubble (the red curve). Since the use of distortion is
characteristic of the heavy metal style in music [39], the fact that the
bubbles reproduces this effect serves as an objective confirmation of its
ability to creatively process music.

##  III Discussion

Thus, we show that the ability of a single oscillating bubble to perform
complex nonlinear tasks enables it to arrange existing music pieces similarly
to a human. Creative music composition using the properties of liquids is an
established style of music [42], where it is highly likely that nonlinear
acoustic effects associated with bubbles trapped in liquids [5, 6] have
already been exploited in some form.

However, we look at the nonlinear properties of the bubble at a different
angle. In our previous work we demonstrated the ability of oscillating bubbles
to forecast chaotic time series similarly to an artificial neural network
[18], which is a task that requires not only nonlinearity but also memory.
Most importantly, unlike a bubble in water that produces some sounds that are
then used by an artist to compose music, a bubble employed in an artificial
neural network plays an active role of an analog data processing unit that
mimics the operation of a biological neuron. Although the memory capacity and
the speed of data processing of such a unit are low compared with those of a
typical digital computer, it has been demonstrated that analog computer
systems can be more efficient than digital ones in solving certain classes of
problems pertinent to the field of AI [22, 18, 43, 44]. Given this, we suggest
that a single bubble can be employed as a building block of an analog AI
system that can produce musical outputs with no or little human input.

Unlike the music transcription, which is an exact note for note rendition of a
piece of music written for one instrument and played on another (i.e. piano to
guitar), arrangement is a more creative process, where the style of the music
is changed and new complex tones are added. Consequently, this creative task
is especially challenging for AI system because it requires a machine to have
some of the key features of the human intelligence such as the ability to
associate ideas, perceive, think, search for answers and criticise results of
own work [45]. Yet, creativity relies on cognitive memory [30, 31] and is
closely linked to cultural context and personality, also being influenced by
motivation and emotions of the artist [45]. Interestingly enough, the ability
to appreciate, arrange and compose heavy metal music has also been associated
with high intellectual abilities [46], which means that the production of
heavy metal style music should be a particularly challenging task for AI.

Thinking in terms of machine learning systems, researchers have attempted to
create models, where training inputs for achieving artificial creativity are
represented by poorly defined data sets affected by perturbations and noise
[47, 48]. The studies of so-created models have revealed that achieving
artificial creativity may contradict the standard approach to training an
artificial neural network since perturbations associated with creativity
interfere with the operation of the network, for instance, by altering the
values of its connection weights [47]. Subsequently, it has been suggested
that the organisational principles of conventional neural network should be
changed to enable AI-powered creativity [48].

However, this assessment of the applicability of conventional artificial
neural networks in the field of AI creativity does not take into account the
recent advances in the development of analog (non-digital) counterparts of
neural networks, where hardware and real-life physical systems that exhibit a
nonlinear dynamical behaviour are used as artificial neurons. While such
physical computation systems have thus far mimicked the operation of some
digital neural network architectures [22], it has been demonstrated that they
hold a potential to surpass the abilities of a computer program in operations
intended to simulate the functions of a biological brain [22, 49, 18]. The
findings presented in this work contribute to the endeavour to demonstrate
this potential.

Finally, assuming that an AI system has been able to creatively generate a
musical output comparable with that produced by a human, researchers face yet
another problem: the quality of the AI-generated musical output is difficult
to assess since this process would rely on the appreciation of trained
listeners [25], who may, in turn, hold a cultural bias [50] or a bias against
computer-composed music [51].

Figure 3: (a) Comparison of the temporal response of the bubble (the red
curve) with a signal obtained from the original melody by digitally applying
reverberation and nonlinear acoustic effects (the blue curve). (b) Fourier
spectra of the signals in panel (a). The same times scale as in Fig. 2(a) is
used. The waveform of the original melody is not shown for the sake of
clarity.

Since it is challenging to critically judge the aesthetical quality of the
electric guitar arrangement produced by a bubble, we found several covers on
“In the Hall of the Mountain King” produced by professional electric guitar
players [52, 53]. Even though those compositions sound more appealing than the
version produced by the bubble, we have been able to distinguish the same warm
and gritty tones created by the professional musicians in their performances.
Thus, we leave it up to the readers to listen to the cited compositions and to
comparatively judge the quality of the output produced by the bubble. However,
we note that while it takes years of practice for a human to master an
electric guitar, a single bubble in water appears to have an intrinsic ability
to reproduce the sound of this musical instrument.

##  IV Conclusions

Using a rigorous numerical model of nonlinear oscillations of an acoustically-
driven single bubble in water, we have demonstrated that a bubble can produce
audio outputs that aesthetically sound as creative musical outcomes produced
by humans. Since past research demonstrated that oscillating bubbles can form
a physics-based artificial neural network that can simulate certain functions
of a biological brain, we suggest that either a single oscillating bubble or a
network (cluster) of such bubbles could be used as an apparatus capable of
reproducing some forms of artificial creativity. Achieving creativity in
musics has thus far been a challenging to resolve problem for modern AI
systems. Therefore, we believe that our findings may contribute to further
development in this vital field of fundamental and applied research, also
being of interest to artists, who experiment with the acoustic properties of
liquids.

###### Acknowledgements.

ISM thanks Professor Sergey Suslov and Dr Andrey Pototsky (Swinburne
University of Technology) for valuable discussions, and Professor Mikhail
Kostylev (The University of Western Australia) for help with the calculation
of the memory capacity.

## References

  * Brennen [1995] C. E. Brennen,  _Cavitation and Bubble Dynamics_ (Oxford University Press, New York, 1995).
  * Lauterborn and Kurz [2010] W. Lauterborn and T. Kurz, Physics of bubble oscillations, Rep. Prog. Phys. 73, 106501 (2010).
  * Maksymov  _et al._ [2022a] I. S. Maksymov, B. Q. H. Nguyen, A. Pototsky, and S. A. Suslov, Acoustic, phononic, Brillouin light scattering and Faraday wave-based frequency combs: physical foundations and applications, Sensors 22, 3921 (2022a).
  * Maksymov  _et al._ [2022b] I. S. Maksymov, B. Q. H. Nguyen, and S. A. Suslov, Biomechanical sensing using gas bubbles oscillations in liquids and adjacent technologies: Theory and practical applications, Biosensors 12, 624 (2022b).
  * Minnaert [1933] M. Minnaert, On musical air-bubbles and the sound of running water, Phil. Mag. 16, 235 (1933).
  * Leighton and Walton [1987] T. G. Leighton and A. J. Walton, An experimental study of the sound emitted from gas bubbles in a liquid, Eur. J. Phys. 8, 98 (1987).
  * McKenna  _et al._ [1994] T. M. McKenna, T. A. McMullen, and M. F. Shlesinger, The brain as a dynamic physical system, Neuroscience 60, 587 (1994).
  * Strogatz [2019] S. H. Strogatz,  _Nonlinear Dynamics and Chaos With Applications to Physics, Biology, Chemistry, and Engineering_ (CRC Press, 2019).
  * Heimburg and Jackson [2005] T. Heimburg and A. D. Jackson, On soliton propagation in biomembranes and nerves, PNAS 102, 9790 (2005).
  * Gonzalez-Perez  _et al._ [2014] A. Gonzalez-Perez, R. Budvytyte, L. D. Mosgaard, S. Nissen, and T. Heimburg, Penetration of action potentials during collision in the median and lateral giant axons of invertebrate, Phys. Rev. X 4, 031047 (2014).
  * Hady and Machta [2015] A. E. Hady and B. B. Machta, On soliton propagation in biomembranes and nerves, Nat. Commun. 6, 6697 (2015).
  * Maksymov and Pototsky [2020] I. S. Maksymov and A. Pototsky, Excitation of Faraday-like body waves in vibrated living earthworms, Sci. Rep. 10, 8564 (2020).
  * Maksymov and Greentree [2019] I. S. Maksymov and A. D. Greentree, Coupling light and sound: giant nonlinearities from oscillating bubbles and droplets, Nanophotonics 8, 367 (2019).
  * Levitin [2006] D. J. Levitin,  _This is Your Brain on Music: The Science of Human Obsession_ (Dutton, 2006).
  * Janata [1996] P. Janata,  _Electrophysiological studies of auditory contexts_ (PhD Thesis, The University of Oregon, 1996).
  * Maksymov and Pototsky [2019] I. Maksymov and A. Pototsky, Harmonic and subharmonic waves on the surface of a vibrated liquid drop, Phys. Rev. E 100, 053106 (2019).
  * Fletcher [1990] N. H. Fletcher, Nonlinear theory of musical wind instruments, Appl. Acoust. 30, 85 (1990).
  * Maksymov  _et al._ [2021] I. S. Maksymov, A. Pototsky, and S. A. Suslov, Neural echo state network using oscillations of gas bubbles in water, Phys. Rev. E 105, 044206 (2021).
  * Lukoševičius and Jaeger [2009] M. Lukoševičius and H. Jaeger, Reservoir computing approaches to recurrent neural network training, Comput. Sci. Rev. 3, 127 (2009).
  * Nakajima [2020] K. Nakajima, Physical reservoir computing–an introductory perspective, Jpn. J. Appl. Phys. 59, 060501 (2020).
  * Tanaka  _et al._ [2019] G. Tanaka, T. Yamane, J. B. Héroux, R. Nakane, N. Kanazawa, S. Takeda, H. Numata, D. Nakano, and A. Hirose, Recent advances in physical reservoir computing: A review, Neural Newt. 115, 100 (2019).
  * Nakajima and Fisher [2021] K. Nakajima and I. Fisher,  _Reservoir Computing_ (Springer, Berlin, 2021).
  * Maass  _et al._ [2002] W. Maass, T. Natschläger, and H. Markram, Real-time computing without stable states: a new framework for neural computation based on perturbations, Neural Comput. 14, 2531 (2002).
  * Miller [2019] A. I. Miller,  _The Artist in the Machine: The World of AI-Powered Creativity_ (MIT Press, 2019).
  * Pachet [2012] F. Pachet, Musical virtuosity and creativity, in  _Computers and Creativity_ , edited by J. McCormack and M. d’Inverno (Springer Berlin Heidelberg, Berlin, Heidelberg, 2012) pp. 115–146.
  * Huang and Wu [2016] A. Huang and R. Wu, Deep learning for music, arXiv:1606.04930 (2016).
  * Briot [2021] J.-P. Briot, From artificial neural networks to deep learning for music generation: history, concepts and trends, Neural. Comput. Appl. 33, 39 (2021).
  * Hernandez-Olivan and Beltrán [2023] C. Hernandez-Olivan and J. R. Beltrán, Music composition with deep learning: A review, in  _Advances in Speech and Music Technology: Computational Aspects and Applications_ , edited by A. Biswas, E. Wennekes, A. Wieczorkowska, and R. H. Laskar (Springer International Publishing, Cham, 2023) pp. 25–50.
  * Ross [1998] M. Ross,  _Getting Great Guitar Sounds_ (Hal Leonard Corporation, Milwaukee, 1998).
  * Benedek  _et al._ [2023] M. Benedek, R. E. Beaty, D. L. Schacter, and Y. N. Kenett, The role of memory in creative ideation, Nat. Rev. Psychol. https://doi.org/10.1038/s44159-023-00158-z (2023).
  * Gerver  _et al._ [2022] C. R. Gerver, J. W. Griffin, N. Dennis, and R. Beaty, Memory and creativity: A meta-analytic examination of the relationship between memory systems and creative cognition, PhysArXiv (2022).
  * Waugh [1985] I. Waugh,  _Commodore 64 Music: Making Music with Your Micro_ (Sunshine Books, 1985).
  * Prosperetti [1974] A. Prosperetti, Nonlinear oscillations of gas bubbles in liquids: steady-state solutions, J. Acoust. Soc. Am. 56, 878 (1974).
  * Suslov  _et al._ [2012] S. A. Suslov, A. Ooi, and R. Manasseh, Nonlinear dynamic behavior of microscopic bubbles near a rigid wall, Phys. Rev. E 85, 066309 (2012).
  * Nguyen  _et al._ [2021] B. Q. H. Nguyen, I. S. Maksymov, and S. A. Suslov, Acoustic frequency combs using gas bubble cluster oscillations in liquids: a proof of concept, Sci. Reps. 11, 38 (2021).
  * Yeh  _et al._ [2008] D. T. Yeh, J. S. Abel, A. Vladimirescu, and J. O. Smith, Simulation of guitar distortion circuits, Comput. Music J. 32, 23 (2008).
  * Yeh [2009] D. T. Yeh,  _Digital Implementation of Musical Distortion Circuits by Analysis and Simulation_ (PhD Thesis, Stanford University, 2009).
  * Boyd and Chua [1985] S. Boyd and L. O. Chua, Fading memory and the problem of approximating nonlinear operators with Volterra series, IEEE Trans. Circuits Syst. CAS-32, 1150 (1985).
  * Zölzer [2011] U. Zölzer,  _DAFX: Digital Audio Effects_ (Wiley, 2011).
  * Kirby [1991] K. G. Kirby, Context dynamics in neural sequential learning, Proc. Florida AI Research Symposium (FLAIRS) , 66 (1991).
  * Ribeiro and Nicolelis [2004] S. Ribeiro and M. A. L. Nicolelis, Reverberation, storage, and postsynaptic propagation of memories during sleep, Learn. Mem. 11, 686 (2004).
  * Grant  _et al._ [2021] J. Grant, J. Matthias, and D. Prior,  _The Oxford Handbook of Sound Art_ (Oxford University Press, 2021).
  * Cao  _et al._ [2022] W. Cao, Y. Zhao, A. Boloor, Y. Han, X. Zhang, and L. Jiang, Neural-pim: Efficient processing-in-memory with neural approximation of peripherals, IEEE Trans. Comput. 71, 2142 (2022).
  * Ivanov  _et al._ [2022] D. Ivanov, A. Chezhegov, M. Kiselev, A. Grunin, and D. Larionov, Neuromorphic artificial intelligence systems, Front. Neurosci. 16, 10.3389/fnins.2022.959626 (2022).
  * Boden [1998] M. A. Boden, Creativity and artificial intelligence, Artif. Intell. 103, 347 (1998).
  * Cadwallader [2007] S. M. Cadwallader,  _The Darker Side of Bright Students: Gifted and Talented Heavy Metal Fans_ (The National Academy for Gifted and Talented Youth, University of Warwick, UK, 2007).
  * Thaler [2016] S. L. Thaler, Pattern turnover within synaptically perturbed neural systems, Procedia Comput. Sci. 88, 21 (2016).
  * Oleinik [2019] A. Oleinik, What are neural networks not good at? On artificial creativity, Big Data Soc. 6, 1 (2019).
  * Cucchi  _et al._ [2022] M. Cucchi, S. Abreu, G. Ciccone, D. Brunner, and H. Kleemann, Hands-on reservoir computing: a tutorial for practical implementation, Neuromorph. Comput. Eng. 2, 032002 (2022).
  * Demorest  _et al._ [2016] S. M. Demorest, S. J. Morrison, V. Q. Nguyen, and E. N. Bodnar, The influence of contextual cues on cultural bias in music memory, Music Percept. 33, 590 (2016).
  * Pasquier  _et al._ [2016] P. Pasquier, A. Burnett, and J. B. Maxwell, Investigating listener bias against musical metacreativity, in  _International Conference on Innovative Computing and Cloud Computing_ (2016).
  * [52] A. Parker,  _Hall of the Mountain King invented heavy metal_ , available at https://www.youtube.com/watch?v=l_FuR7rq598.
  * [53] M. Klett,  _Hall of the Mountain King_ , available at https://www.youtube.com/watch?v=G4C9O7HA9os.
  * Keller and Miksis [1980] J. B. Keller and M. Miksis, Bubble oscillations of large amplitude, J. Acoust. Soc. Am. 68, 628 (1980).
  * Mudrov [1990] A. E. Mudrov,  _Numerical Methods for Personal Computers in Basic, Fortran, and Pascal (in Russian)_ (Rasko, Tomsk, 1990).
  * Pelekasis and Tsamopoulos [1993] N. A. Pelekasis and J. A. Tsamopoulos, Bjerknes forces between two bubbles. Part 1. Response to a step change in pressure, J. Fluid Mech. 254, 467 (1993).
  * Akhatov  _et al._ [1997] I. Akhatov, N. Gumerov, C. D. Ohl, U. Parlitz, and W. Lauterborn, The role of surface tension in stable single-bubble sonoluminescence, Phys. Rev. Lett. 78, 227 (1997).
  * Jaeger [2005] H. Jaeger,  _A tutorial on training recurrent neural networks, covering BPPT, RTRL, EKF and the “echo state network” approach_ (GMD Report 159, German National Research Center for Information Technology, 2005).
  * Bertschinger and Natschläger [2004] N. Bertschinger and T. Natschläger, Real-time computation at the edge of chaos in recurrent neural networks, Neural Comput. 16, 1413 (2004).
  * Watt and Kostylev [2020] S. Watt and M. Kostylev, Reservoir computing using a spin-wave delay-line active-ring resonator based on yttrium-iron-garnet film, Phys. Rep. Appl. 13, 034057 (2020).

##  Appendix A Numerical model of bubble oscillations

The accepted model of nonlinear oscillations of a single gas bubble driven by
an acoustic pressure wave is given by the Keller-Miksis (KM) equation [54]
that takes into account the decay of bubble oscillations due to viscous
dissipation and fluid compressibility:

$\displaystyle\left(1-\frac{\dot{R}}{c}\right)R\ddot{R}+\frac{\dot{R}^{2}}{2}\left(3-\frac{\dot{R}}{c}\right)=$
$\displaystyle\frac{1}{\rho}\left[1+\frac{\dot{R}}{c}+\frac{R}{c}\frac{d}{dt}\right]\left[P(R,\dot{R})-P_{\infty}(t)\right]\,,$
(2)

where overdots denote the differentiation with respect to time $t$ and

$P(R,\dot{R})=\left(P_{0}-P_{v}+\frac{2\sigma}{R_{0}}\right)\left(\frac{R_{0}}{R}\right)^{3\kappa}-\frac{4\mu\dot{R}}{R}-\frac{2\sigma}{R}\,.$
(3)

The expression $P_{\infty}(t)=P_{0}-P_{v}+\alpha P_{a}(t)$, where $P_{a}(t)$
is an arbitrary driving acoustic pressure signal, represents the time-
dependent pressure in the liquid far from the bubble. Parameters $R_{0}$,
$R(t)$, $\mu$, $\rho$, $\kappa$, $\sigma$, $c$ and $\alpha$ denote the
equilibrium and instantaneous radii of the bubble, the dynamic viscosity and
the density of the liquid, the polytropic exponent of a gas entrapped in the
bubble, the surface tension of a gas-liquid interface, the speed of sound in
the liquid, and the amplitude of a driving ultrasound wave. Diffusion of the
gas through the bubble surface is neglected.

When bubble oscillations are not affected by fluid compressibility, which is
the case in this work, the acoustic power scattered by the bubble in the far-
field zone is [1]

$P_{scat}(R,t)=\frac{\rho R}{h}\left(R\ddot{R}+2\dot{R}^{2}\right)\,,$ (4)

where $h$ is much larger than the equilibrium radius of the bubble.

Figure 4: Acoustic response of a single mm-sized bubble in water to a (a.i)
positive and (b.i) negative pressure pulse. The respective, normalised to
unity, envelopes of the bubble responses to the step changes in acoustic
pressure are plotted in panels (a.ii) and (b.ii). (c) Spectra of the pressure
scattered by the oscillating bubble driven by the square pulses with different
peak amplitudes $\alpha$. The red (blue) curves denote the spectra of the
bubble oscillations caused by the first (second) step change in the pressure
of the driving square pulse. As a result of the second step change, the bubble
always returns to its equilibrium state and its fundamental oscillation
frequency frequency remains unchanged.

Since oscillations of the the bubble are excited by a signal consisting of
square pulses (see Sect. II), we introduce a pulse repetition frequency
parameter $f_{p}$ and rewrite Eqs. (2)–(3) in the nondimensional form [34,
35], where we use the equilibrium radius of the bubble $R_{0}$ and
${\omega_{p}}^{-1}$ ($\omega_{p}=2\pi f_{p}$) as the length and time scales,
respectively, also introducing the non-dimensional quantities $r={R(t)}/R_{0}$
and $\tau=\omega_{p}t$. We obtain

$\begin{gathered}{r}^{\prime\prime}[(1-\Omega r^{\prime})r+\Omega{\cal
R}]=(\Omega r^{\prime}-3)\frac{{{r}^{\prime}}^{2}}{2}-\frac{{\cal W}+{\cal
R}r^{\prime}}{r}\\\ +({\cal M}+{\cal W})\frac{[1+(1-3\kappa)\Omega
r^{\prime}]}{r^{3\kappa}}\\\ -(1+\Omega r^{\prime})({\cal M}+{\cal
M}_{e}P_{a}(\tau))-{\cal M}_{e}\Omega
r{P_{a}}^{\prime}(\tau)\,,\end{gathered}$ (5)

where primes denote the differentiation with respect to $\tau$,
$\Omega=\dfrac{\omega_{p}R_{0}}{c}$, ${\cal
R}=\dfrac{4\mu}{\rho\omega_{p}R^{2}_{0}}$, ${\cal
W}=\dfrac{2\sigma}{\rho{\omega_{p}}^{2}R^{3}_{0}}$, ${\cal
M}=\dfrac{P_{0}-P_{v}}{\rho{\omega_{p}}^{2}R^{2}_{0}}$, ${\cal
M}_{e}=\dfrac{\alpha}{\rho{\omega_{p}}^{2}R^{2}_{0}}$ and ${\cal K}=3\kappa$.
Parameter $\Omega$ characterises the bubble size relative to the acoustic
wavelength, ${\cal M}$ characterises elastic properties of the gas and its
compressibility, ${\cal W}$ and ${\cal R}$ can be treated as inverse Weber and
Reynolds numbers, representing the surface tension and viscous dissipation
effects, respectively, and ${\cal M}_{e}$ is the measure of the acoustic
forcing [34].

Computations were carried out for the following fluid parameters corresponding
to water at $20^{\circ}$ C: $c=1484$ m/s, $\mu=10^{-3}$ kg m/s,
$\sigma=7.25\times 10^{-2}$ N/m, $\rho=10^{3}$ kg/m3 and $P_{v}=2330$ Pa. We
take the air pressure in a stationary bubble to be $P_{0}=10^{5}$ Pa and the
polytropic exponent of air to be $\kappa=4/3$. In the calculations, the pulse
repetition frequency $f_{p}$ depends on the notes of the piece of musics and
it is always smaller than the frequency of natural oscillations $f_{0}$ of mm-
sized bubbles ($f_{0}R_{0}\approx 3.26$ m s-1 [2] and for $R_{0}=1$ mm
$f_{0}=3260$ Hz). Equation (5) is solved numerically using a fixed-step fourth
order Runge-Kutta method implemented in a customised subroutine rk4 [55]
ported from Pascal to Oberon-07 programming language.

We calculate the typical values of the nondimensional parameters ${\cal M}$,
${\cal W}$, ${\cal R}$ and $\Omega$ setting $R_{0}=1$ mm, $\alpha=0.2P_{0}$
and $f_{p}=100$ Hz:

${\cal R}=\frac{{\cal R}_{0}}{\Omega^{2}},\,{\cal W}=\frac{{\cal
W}_{0}}{\Omega^{3}},\,{\cal M}=\frac{{\cal M}_{0}}{\Omega^{2}},\,{\cal
M}_{e}=\frac{{{\cal M}_{e}}_{0}}{\Omega^{2}}\,,$ (6)

where

$\displaystyle{\cal R}_{0}=\frac{4\mu\omega_{p}}{\rho c^{2}}\approx 1.14\times
10^{-9}\,$ $\displaystyle{\cal W}_{0}=\frac{2\sigma\omega_{p}}{\rho
c^{3}}\approx 2.79\times 10^{-11}\,$ (7) $\displaystyle{\cal
M}_{0}=\frac{P_{0}-P_{v}}{\rho c^{2}}\approx 4.43\times 10^{-5}\,$
$\displaystyle{{\cal M}_{e}}_{0}=\frac{\alpha}{\rho c^{2}}\approx 9.08\times
10^{-5}\,,$

for $\Omega=4.54\times 10^{-6}$. At these parameters the value of ${\cal M}$
exceeds those of ${\cal W}$ and ${\cal R}$ by several orders of magnitude,
which represents the well-known fact that the dynamics of large gas bubbles is
mostly determined by the gas elasticity, while both viscous dissipation and
surface tension play secondary roles [34].

##  Appendix B Bubble forced by a unit step change in acoustic pressure

The response of a single bubble to a unit step change in the driving acoustic
pressure was previously investigated in the context of interaction between two
oscillating bubbles [56]. Here, we investigate it in the context of sound
processing since the piece of music used to excite oscillations of the bubble
is encoded using a series of square pulses (see Sect. II).

We define the driving acoustic signal as $P_{a}(\tau)=\Theta(\tau)$, where
$\Theta(\tau)$ is the Heaviside function

$\Theta(\tau)=\begin{cases}0&\text{for }\,\tau<0\\\ 1&\text{for
}\,\tau>0\,.\end{cases}$ (8)

We assume that the nondimensional driving sound pressure amplitude ${\cal
M}_{e}$ is small and that the bubble oscillates near its equilibrium state so
that its instantaneous nondimensional radius is $r(\tau)=1+r_{1}(\tau)$, where
$r_{1}(\tau)\ll 1$. We linearise Eq. (5) around $r=1$ to obtain the following
equation of a damped linear harmonic oscillator subjected to constant forcing

$(\Omega{\cal R}+1){r_{1}}^{\prime\prime}+({\cal R}+{\cal M}_{e}\Omega+{\cal
A}\Omega){r_{1}}^{\prime}+{\cal A}r_{1}=-{\cal M}_{e}\,,$ (9)

where ${\cal A}\equiv(3{\cal W}+3{\cal M})\kappa-{\cal W}$. Then we denote
$Q=\dfrac{\Omega{\cal R}+1}{{\cal R}+{\cal M}_{e}\Omega+{\cal
A}\Omega}\approx\dfrac{\Omega}{{\cal K}{\cal M}_{0}}$, $\Lambda=\dfrac{{\cal
M}_{e}}{\Omega{\cal R}+1}\approx\dfrac{{\cal M}_{e0}}{\Omega^{2}}$ and
$\omega_{0}=\sqrt{\dfrac{A}{\Omega{\cal R}+1}}\approx\sqrt{{\cal K}{\cal
M}}=\dfrac{\sqrt{{\cal K}{\cal M}_{0}}}{\Omega}$, where we used the fact that
${\cal M}\gg{\cal W},{\cal R}$ established in Sec. A, and we recast Eq. (9) as
an equation of an unforced harmonic oscillator

${r_{1}}^{\prime\prime}+\frac{1}{Q}{r_{1}}^{\prime}+\omega_{0}^{2}(r_{1}+\frac{\Lambda}{\omega_{0}^{2}})=0\,,$
(10)

where parameter $Q$ is the quality factor that describes the resonance
behaviour of the harmonic oscillator and $\omega_{0}$ corresponds to undamped
natural frequency of the bubble. With the initial conditions
$r_{1}(0^{-})={r_{1}}^{\prime}(0^{-})=0$ the solution of Eq. (10) is

$\displaystyle
r_{1}=e^{-\frac{\tau}{\tau_{0}}}\left(\frac{\Lambda\sin{\omega^{\prime}\tau}}{2Q\omega_{0}^{2}\omega^{\prime}}+\frac{\Lambda\cos{\omega^{\prime}\tau}}{\omega_{0}^{2}}\right)-\frac{\Lambda}{\omega_{0}^{2}}\,,$
(11)

where $\omega^{\prime}=\sqrt{\omega_{0}^{2}-\frac{1}{4Q^{2}}}$ is the damped
natural frequency of the bubble and $\tau_{0}=2Q\approx\dfrac{2\Omega}{{\cal
K}{\cal M}_{0}}$ is the characteristic relaxation time over which the
magnitude of oscillations in the transient regime reduces by the factor of
$e$.

Thus, apart from a transient response, the solution also contains a time-
independent response $-\Lambda/\omega_{0}^{2}$. Therefore, one can see that
under constant forcing the bubble oscillates near a changed equilibrium state
$1+r_{1}(\tau\to\infty)=1-\frac{\Lambda}{\omega_{0}^{2}}$, which in the
framework of the adopted model means that the equilibrium radius of the bubble
has decreased. This is consistent with the fact that the constant forcing has
effectively increased the static pressure outside the bubble. As a result, the
oscillation frequency of the bubble is increased since
$\omega_{0}\sim\Omega^{-1}$ but the relaxation time is decreased since
$\tau_{0}\sim\Omega$ thus accounting for the fact that smaller bubbles have a
higher stiffness [57] (recall that parameter $\Omega$ characterises the
equilibrium radius of the bubble).

This behaviour is confirmed by a direct numerical solution of Eq. (5) for a
single square pulse forcing term $P_{a}(\tau)$ defined as

$P_{a}(\tau)=\begin{cases}A&\text{for
}\,\dfrac{-\tau_{p}}{2}\leq\tau\leq\dfrac{\tau_{p}}{2}\\\
0&\text{otherwise}\,,\end{cases}$ (12)

where the duration of the pulse is $\tau_{p}>\tau_{0}$, the unit amplitude of
the pulse $A$ can be either $-1$ or 1 so that the effects of bubble forcing
with both positive and negative square pulses can be accounted for, and the
strength of the forcing is defined by parameter ${\cal M}_{e}$ that is a
function of the dimensional pressure amplitude $\alpha$.

Figure 5: (a) Schematic of the ESN algorithms.

In Fig. 4 we plot the the response of the bubble to a positive square pulse
[panel (a.i)] and a negative square pulse [panel (b.i)] (the response is given
by the acoustic pressure scattered by the bubble according to Eq. (4)). The
red curve denotes the response of the bubbles subjected to a step pressure
change and the blue curve denotes the response of the bubble returned to its
original equilibrium state. The pressure amplitude is $\alpha=0.2P_{0}$ in
panel (a.i) and $\alpha=-0.2P_{0}$ in panel (b.i). Panel (c) shows the spectra
of the bubble oscillations at $\alpha=0.2P_{0}$ (the top curves) and
$\alpha=-0.2P_{0}$ (the bottom curves) alongside the spectra calculated at
several values within the $-0.2P_{0}<\alpha<0.2P_{0}$ range.

The oscillations frequencies of the bubble are given by the frequencies of the
main peaks in the spectra in panel (c). In agreement with the analysis of the
linearised KM equation (9), the frequency of the bubble oscillating near its
original equilibrium state (the blue curves) remains unchanged, but that of
the bubble forced by the positive and negative step changes in the acoustic
pressure (the red curves) increases and decreases, respectively. In panels
(a.ii) and (b.ii), we also plot the envelopes of the transient responses of
the bubble and we observe changes in the relaxation time consistent with those
predicted theoretically. In panel (c) we observe that the numerical
simulations predict the appearance of the second harmonic of the natural
bubble oscillation frequency due to the nonlinearity (the third and fourth
harmonics were also identified; however they are not shown on the figure).
Respective changes in the relaxation time can also be noticed comparing, for
example, the lineshapes of the fundamental and second-harmonic frequency peaks
at $\alpha=\pm 0.2P_{0}$.

Figure 6: Acoustic response of a single oscillating bubble (the red curve) to
a sequence of square pressure pulses that encode a randomly generated binary
time series (the black curve) discussed in the main text. The blue curve
outlines the envelope of the bubble’s response. In the top panel, the green
rectangle highlights the time range of a magnified portion of the signals
plotted in the bottom panel.

##  Appendix C Echo Sate Network

To support our discussion of the ability of the bubble to operate as an
artificial neuron, we use the standard Echo State Network (ESN) algorithm [58,
19]. We choose ESN because, alongside the relevant concept of Liquid State
Machine (LSM) [23], this type of neural network can be used to simulate some
of the functions of a biological brain [59, 49].

In ESN, artificial neurons form an intricate network called the reservoir
(Fig. 5). The dynamics of the reservoir is governed by the nonlinear update
equation

$\displaystyle{\bf x}_{n}=(1-\alpha_{r}){\bf x}_{n-1}+\alpha_{r}\tanh({\bf
W}^{in}{\bf u}_{n}+{\bf W}{\bf x}_{n-1})\,,$ (13)

where $n$ is the index denoting equally-spaced discrete time instances
$t_{n}$, ${\bf u}_{n}$ is the vector of $N_{u}$ input values, ${\bf x}_{n}$ is
a vector of $N_{x}$ neural activations of the reservoir, the operator
$\tanh(\cdot)$ is a sigmoid activation function of a neuron [19], ${\bf
W}^{in}$ is the input matrix containing $N_{x}\times N_{u}$ elements, ${\bf
W}$ is the recurrent weight matrix consisting of $N_{x}\times N_{x}$ elements
and $\alpha_{r}\in(0,1]$ is a parameter that controls the reservoir’s temporal
dynamics [19].

To train the reservoir, one typically calculates the output weights ${\bf
W}^{out}$ by solving a system of linear equations ${\bf Y}^{target}={\bf
W}^{out}{\bf X}$, where ${\bf X}$ and ${\bf Y}^{target}$ are the state matrix
and the target matrix that are constructed using, respectively, ${\bf x}_{n}$
and the vector of target outputs ${\bf y}_{n}^{~{}target}$ as columns for each
discrete time instant $t_{n}$. The solution is often obtained in the form
${\bf W}^{out}={\bf Y}^{target}{\bf X^{\top}}({\bf X}{\bf X^{\top}}+\beta{\bf
I})^{-1}$, where ${\bf I}$ is the identity matrix, $\beta\geq 0$ is a
regularisation coefficient and ${\bf X^{\top}}$ is the transpose of ${\bf X}$
[19]. During the prediction stage, one solves Eq. (13) for new input data
${\bf u}_{n}$ and computes the output vector ${\bf y}_{n}={\bf W}^{out}[1;{\bf
u}_{n};{\bf x}_{n}]$ using a constant bias and the concatenation $[{\bf
u}_{n};{\bf x}_{n}]$.

##  Appendix D Memory capacity of an oscillating bubble

We demonstrate that a nonlinearly oscillating bubble retains memory of the
past acoustic excitation inputs. We adopt the approach used to test the memory
capacity of ESN [59, 58]. We excite oscillations of a single bubble with a
randomly generated time series that contains binary elements that accept
either ’0’ or ’1’ values. An individual ’1’ value is represented by a positive
pressure square pulse of a unit length but a ’0’ value corresponds to a period
of no acoustic excitation that also has the unit length duration. For example,
an input data subset ’10101’ is represented by three square pulses of unit
length separated by two periods of no excitation that also have a unit length
duration. Accordingly, a sequence ’111001111’ corresponds to a triple square
pulse separated from the following quadruple square pulse by two consecutive
periods of no excitation. The actual unit length of an individual square pulse
corresponding to a single ’1’ state is chosen empirically to be of order of
the relaxation time $\tau_{0}$ of the bubble. This choice helps ensure that
the response of the bubble to one pulse does not fully decay until the bubble
is presented to the next pulse of the random time series, thereby enabling the
bubble to remember the past inputs.

In line with the concept of physical reservoir computing, where the nonlinear
dynamical behaviour of the artificial neural network is replaced by the
response of a physical nonlinear-dynamical system [21, 20, 22, 49], we replace
Eq. (13) with Eq. (5), which means that the artificial neural excitations
${\bf x}_{n}$ become a function of the acoustic response of the oscillating
bubble. However, unlike Ref. [18], where ESN was implemented using the
nonlinear dynamical response of a cluster of oscillating bubbles in water and
where the individual bubbles of the cluster were operating as individual
artificial neurons, in this work we employ a single oscillating bubble as a
reservoir and we sample the bubble’s temporal response to obtain 20 virtual
artificial neurons that produce the values of ${\bf x}_{n}$ (for a relevant
discussion see [60]).

We randomly generate a time series that consists of 2000 binary ’0’ and ’1’
values. We encode each binary value as square pulses and no excitation gaps
between them, respectively. The amplitude of the square pulses is
$\alpha=0.1P_{0}$. In the framework of ESN, the so-encoded signal plays the
role of the input vector ${\bf u}_{n}$.

We calculate the response of the bubble to the whole input signal and then we
sample the bubble’s response to obtain the neural activation ${\bf x}_{n}$
corresponding to 20 virtual neurons. Afterwards we use the first half of the
input and the first half of the respective bubble’s response as the training
data, and we calculate ${\bf W}^{out}$ using the procedure described in Sect
C. The second half portions of these data sets are used to conduct the memory
test.

Figure 7: STM and PC task memory capacity of an oscillating bubble expressed
as the square of the correlation coefficient $r^{2}$ calculated for different
discrete time delays.

Figure 6 shows a typical response of the bubble to the input time series
represented by the square pulses and gaps between them. Each square pulse
followed by a no excitation period causes a step change in the pressure of the
driving acoustic wave, thereby triggering two bursts of bubble oscillation:
one at the beginning of the pulse and another one at the end of it. As a
result, the oscillations caused by one pulse do not fully decay until the
bubble is excited by the following pulse, which means that the state of the
system depends on the past inputs. In turn, this indicates that the system
possesses certain memory [58, 60], which is demonstrated in continuation.

We employ two standard approaches to calculate the memory capacity of an
oscillating bubble. The first of them is the $k$-delay task applied to a
random binary time series, where we calculate the correlation coefficient
$r({\bf y}^{target}_{n-k},{\bf y}_{k,n})$ between a delayed target signal
${\bf y}^{target}_{n-k}$ and the predicted output ${\bf y}_{k,n}$ produced by
the oscillating bubble trained using the training data ${\bf u}_{k,n}$ with a
discrete time delay $k$ [58]. The function $r^{2}({\bf y}^{target}_{n-k},{\bf
y}_{k,n})$ can accept any value from 0 to 1, being 0 an indicator of the full
loss of correlation and 1 corresponding to a full correlation between the
correct target data and the prediction made by the bubble. Calculating $r^{2}$
as a function of the discrete delay time $k$, we determine the so-called
short-term (also known as fading) memory capacity (STM) [58, 60] as

$\displaystyle C_{STM}=\sum_{k=1}^{k_{max}}r^{2}({\bf y}^{target}_{n-k},{\bf
y}_{k,n})\,,$ (14)

being $k_{max}$ the maximum delay considered in the analysis.

Then, we task the oscillating bubble with a parity check test [59], where the
bubble predicts a time series defined as $PARITY({\bf u}_{n-k},{\bf
u}_{n-k-1},{\bf u}_{n-k-2})$ for increasing delays $k$. Based on the original
randomly generated binary time series, the so-generated new time series is a
binary sequence itself. The parity function is not linearly separable and its
prediction requires the reservoir to have memory. Similarly to Eq. (14), we
calculate the parity check memory capacity $C_{PC}$ by summation of the parity
check values up to the maximum delay $k_{max}$.

The calculated memory capacities are presented in Fig. 7, where we plot
$r^{2}$ as a function of the discrete delay time. We obtain $C_{STM}=2.83$
bits and $C_{PC}=3.18$ bits. These values are similar to those obtained for
physical reservoir systems of other nature [60] and they confirm that an
oscillating bubble has a decent memory capacity. We also note in Fig. 7 at the
zero delay both STM and PC tests produce the memory of approximately $0.9$ bit
instead of the theoretically expected 1 bit corresponding to 100% correlation.
In the standard ESN approach, this situation originates from long-term
reverberations in the reservoir [40] that deteriorate the recall of
immediately past inputs [58].


# Cleaning Dirty Books: Post-OCR Processing for Previously Scanned Texts

Allen Kim, Charuta Pethe, Naoya Inoue, Steven Skiena
Department of Computer Science,
Stony Brook University, NY, USA
<EMAIL_ADDRESS>
###### Abstract

Substantial amounts of work are required to clean large collections of
digitized books for NLP analysis, both because of the presence of errors in
the scanned text and the presence of duplicate volumes in the corpora. In this
paper, we consider the issue of deduplication in the presence of optical
character recognition (OCR) errors. We present methods to handle these errors,
evaluated on a collection of 19,347 texts from the Project Gutenberg dataset
and 96,635 texts from the HathiTrust Library. We demonstrate that improvements
in language models now enable the detection and correction of OCR errors
without consideration of the scanning image itself. The inconsistencies found
by aligning pairs of scans of the same underlying work provides training data
to build models for detecting and correcting errors. We identify the canonical
version for each of 17,136 repeatedly-scanned books from 58,808 scans.
Finally, we investigate methods to detect and correct errors in single-copy
texts. We show that on average, our method corrects over six times as many
errors as it introduces. We also provide interesting analysis on the relation
between scanning quality and other factors such as location and publication
year.

##  1 Introduction

The HathiTrust and Gutenberg corpora are critical resources for literary
analysis and NLP research, providing legal access to tens of thousands of
texts for research purposes.

Both were constructed from scanned texts, with manual correction in the case
of the Gutenberg corpus. These efforts for the Gutenberg Project have begun as
early as the 1970s when there was a foreseeable need to digitize open-domain
books. Furthermore, the HathiTrust dataset also was constructed from a
compilation of books from multiple libraries from universities and states, and
adds a substantial amount of extra content.

However, when compiling a library of books from multiple sources, many
challenges arise in maintaining a well-structured catalog with minimal
redundant data. Quite often, a popular book will appear in multiple sources of
differing quality.

In this paper, we describe a major effort to clean and organize these texts to
provide a stronger foundation for NLP research in literary texts. Our main
contributions are:

  * •

_OCR correction of previously scanned texts_ – Book scanning technologies are
a mix of vision and language analysis, with language models used to correct
the visual processing errors and ambiguity inherent in the scanning process.
Language models are now substantially more powerful than available at the time
the bulk of the Gutenberg/HathiTrust corpora were collected. We employ these
language models for detecting and correcting scanning errors, yielding much
cleaner texts for downstream analysis. These cleaned texts will be made
available to the research community subject to the limits enforced by Project
Gutenberg and HathiTrust.

With these models, we find errors in hundreds of Gutenberg books. Some
examples are shown in Table 1.

Gutenberg ID | Incorrect Sentence
---|---
3005 | He returned hone
5798 | I dod not smoke.
12773 | Which would he absurd
44223 | …pleaded tie major
53604 | What did he clo?
Table 1: Examples of errors detected in Project Gutenberg books by our method

We do note that it may not be so clear cut at times due to intentional
misspellings in dialogue. For example, "Tat will pe wrong" is a legitimate
sentence (dialogue) in Malcolm by George MacDonald, but is detected as an
error. In general, we find approximately 18.9% of our detected errors in
HathiTrust books to be within quotes, and we see that books with unusually
high error rates in quotes generally stem from OCR errors found on question
marks (’P’ instead of ’?’) or books with heavy vernacular English such as “On
the Plantation” by Joel Chandler Harris (ex. “kaze I’m dat ole dat I ain’t ”).

We show that on average, our model fixes more than six times as many errors as
it introduces. Even among the “errors” the model introduces, much of them may
actually improve downstream NLP tasks even if the new words may be against the
author’s original intentions. This is particularly true in books with heavy
accented English.

  * •

_Alignment analysis of repeatedly-scanned books_ – We leverage the presence of
several thousand books which have been scanned two or more times across the
union of the Gutenberg/HathiTrust, permitting us to pinpoint exactly where
differences exist in each pair of texts. By employing the language-based OCR
correction models described above, we can identify the correct variant of the
text with high confidence, providing training data to improve correction
models. Our alignment procedure permits us to identify the better of the two
versions and construct a single canonical text of higher quality than either
of the input source texts – as well as train models to clean up singleton
texts.

We collect 8,430,587 aligned differences, which were split into a training and
test dataset for our models and provide them for public use, again subject to
limits enforced by Gutenberg and HathiTrust.

  * •

_Analysis of scanning errors_ – Our alignment methodology provides detailed
information about the causes of observed scanning errors in the HathiTrust
corpus. We identify defect levels as a function of library/location,
publication date, and character signatures. We show one such result in Table
2, which shows the quality of a subset of books from different libraries. In
general, we find that location is not as big of a factor as the source that
digitized their books, primarily Google versus the Internet Archive. These
results shed interesting light on the history of printing, and serve to create
prior distributions for improved scanning technologies.

ID | Location | Count | Year | Quality
---|---|---|---|---
nyp | NYPL | 2071 | 1903 | 0.879
miun | Univ. MI | 6 | 1905 | 0.879
mdp | Univ. MI | 1740 | 1904 | 0.866
nnc1 | Columbia | 44 | 1893 | 0.852
uva | Univ. VA | 143 | 1904 | 0.847
pst | PSU | 24 | 1895 | 0.844
njp | Princeton | 437 | 1893 | 0.841
uc1 | UC | 446 | 1898 | 0.837
wu | Univ. WI | 78 | 1999 | 0.824
inu | Univ. IN | 98 | 1897 | 0.819
coo | Cornell | 36 | 1905 | 0.773
umn | Univ. MN | 12 | 1904 | 0.762
ien | NW Univ. | 2 | 1920 | 0.733
nc01 | UNC | 118 | 1894 | 0.715
uc2 | UC | 1290 | 1901 | 0.705
uiuo | Univ. IL | 42 | 1883 | 0.694
loc | Congress | 46 | 1901 | 0.669
dul1 | Duke | 43 | 1891 | 0.649
hvd | Harvard | 23 | 1832 | 0.566
Table 2: Quality of sampled books by location - blue means the books were
digitized by Google, red means the books were digitized by the Internet
Archive, yellow means the books were locally digitized (at the location
specified). The ‘Year’ column shows the average publication year, which
explains the lower quality for books scanned by Harvard, since these are
significantly older.

##  2 Background

###  2.1 Project Gutenberg

Project Gutenberg is one of the oldest online libraries of free eBooks that
currently has more than 60,000 available texts Gutenberg (n.d.). Given the
wide range of languages and topics available, we restrict ourselves to English
fiction, which narrows the scope of text to about 19,347 books. For each book,
in addition to the text, we are given the title, author, and subject as
metadata.

###  2.2 HathiTrust

The HathiTrust digital library is a collaborative effort between academic and
research libraries to provide a unified corpus of books that currently number
over 8 million book titles HathiTrust Digital Library . By filtering down to
English fiction books in this dataset using provided metadata Underwood
(2016), we get 96,635 books along with extensive metadata including title,
author, and publishing date.

###  2.3 Related Work

#### OCR post-analysis.

OCR post-detection and correction has been discussed extensively and can date
back before 2000, when statistical models were applied for OCR correction
Kukich (1992); Tong and Evans (1996). These statistical and lexical methods
were dominant for many years, where people used a combination of approaches
such as statistical machine translation with variants of spell checking Bassil
and Alwani (2012); Evershed and Fitch (2014); Afli et al. (2016); Kissos and
Dershowitz (2016); Schulz and Kuhn (2017); Coustaty et al. (2018). These
approaches were also combined with a human aspect, where an interface could be
presented to a human corrector that provide aligned text. A human corrector
can then efficiently correct mistakes in bulk Taghva and Stofsky (2001); Vobl
et al. (2014).

We also make note of other data cleaning models that have relied on automatas
or generative models Kolak et al. (2003); Pasula et al. (2003); Mayfield et
al. (2009); Llobet et al. (2010); Abedjan et al. (2016); Lew et al. (2021).
Methods such as PClean work off of Bayesian principles and probabilistic
programming to identify likely errors in a specific domain.

In addition to these models, there have been analysis and visualizations on
the OCR errors themselves on digital libraries Chiron et al. (2017b). Jatowt
et al. (2019) show interesting statistical analysis of OCR errors such as most
frequent replacements and errors based on token length over several corpora .
These provide insight into the most common sources of errors and also show how
different sets of documents each present their own individual features. It is
shown that one cannot generalize assumptions about OCR to all domains.

#### ICDAR Competitions.

With growing interest in these fields, the ICDAR Competition on Post-OCR Text
Correction was hosted during both 2017 and 2019 Chiron et al. (2017a); Rigaud
et al. (2019). These competitions called for participants to submit their best
models for both OCR detection and correction with a provided training dataset
that aligned dirty text with ground truth. The difference in the models
submitted between these two years highlight the advancements in natural
language processing.

In ICDAR 2017, the top OCR correction models focused on neural methods. Neural
machine translation had been shown to outperform statistical machine
translation on many tasks, and the top team’s approach explored both these
models and combined results from multiple sources Amrhein and Clematide
(2018). In the 2019 competition, the best performing team was CCC, using BERT
for fine tuning and character-level machine translation for error correction.
Many others have began to build off of this same structure. For example,
Nguyen et al. (2020) present post-OCR approaches based on a contextual
language model (BERT) and neural machine translation (NMT) on aligned text, as
done by CCC. They improve upon them by applying static word embeddings to
improve error detection, and applying length difference heuristics to improve
correction output.

#### Vernacular English.

Another related direction connected to OCR errors is analysis of text with
vernacular English. In general, different dialects in English do not affect
understanding for native English speakers as much as they affect current NLP
systems. This has been considered by Tan et al. Tan et al. (2020), proposing a
new encoding scheme for word tokenization to better capture these variants.
One can also consider applying OCR correction models that work at a token
level to normalize such texts into proper English as well.

#### Language Models.

Separate from OCR errors, we also make use of concepts in language models.
Language models have provided a means to evaluate the likelihood of various
phrases. Traditionally, this was done with n-gram models Bengio et al. (2003),
but this has been replaced with neural language models. With the advent of
transformers in the form of BERT and RoBERTa, language models have progressed
even further Devlin et al. (2019); Liu et al. (2019). In recent years, masked
language model scoring illustrates a way make use of the transformer
architectures to provide scoring of sentences Salazar et al. (2020). There
have also been advances in deeper models such as GPT2 that provide even
stronger results as well Radford et al. (2019).

##  3 Alignment Methods

We focus on a collection of books from the HathiTrust dataset of which we have
96,635. Our first task was to find duplicate books and to align the content
such that we could find the differences.

###  3.1 Deduplication

Given a large collection of text, we first identify which texts should be
grouped together as a “deduplicated” set. We refer to a deduplicated set of
books as a set of texts in which each text corresponds to the same overall
content. There may be variations in the content due to editing or OCR
differences, but the majority of the text should be similar.

To check for similarity, we use the contents of the books with the n-gram
overlap as a metric. In our case, we process the texts into a set of five-
grams and impose at least a 50% overlap between two sets of five-grams for
them to be considered the same. In practice, duplicate books have an overlap
ratio close to 100%, and different books have overlap ratios close to 0%, so
the 50% threshold is insensitive to small changes.

One can consider checking similarity between book titles and authors as a way
to deduplicate books, but this is not a practical approach. Titles of the same
book can vary with different editions; thus, fuzzy matching becomes a
necessity. However, it becomes unclear at what threshold one should consider
it a match. If it is too strict, books that should be clustered might be
missed while if it is too loose, then there may be too many false positives
between books of similar titles. There may also exist annotation errors in the
metadata as well, which requires looking into the actual content of the book.

To avoid comparing each text to every other text, which would be quadratic in
the corpus size, we first group books by author and compute the pairwise
overlap score between each book in each author group. To then deduplicate the
sets, we treat the problem as finding the connected components in a graph,
where the nodes are books and edges exist between books that were found to be
similar.

#### Anthologies

There is one issue regarding books that contain the contents of many other
books (anthologies). We first filter these books out to avoid situations that
break transitivity. For example, if book A includes book B and book C in its
contents, we would get that book A is similar to book B and book C, but book B
and C may not be similar to each other. Thus, to differentiate between
anthologies and books that are legitimate duplicates, we consider the titles
and lengths of the books in common. If there are no common tokens among the
titles and the parent book is longer than the others, we consider the parent
book an anthology. We also filter out books that are of the form "Works, Works
of …, The complete writings of …, The novels of …" and related variants. In
total, we find 11,382 anthologies out of our HathiTrust dataset of 96,634
books and 106 anthologies from our Gutenberg dataset of 19,347 books.

###  3.2 Text Alignment

Given the set of deduplicated books, our task is to now align the text between
books. More concretely, the task is: given two tokenized books of similar text
(high n-gram overlap), create an alignment between the tokens of both books
such that the alignment preserves order and is maximized. At its core, this
problem is simply a longest common subsequence problem done at a token level.
We show an example of such an alignment in Table 3. The only problem is that
the running time of the dynamic programming solution is proportional to
product of the token lengths of both books, which is too slow in practice.

I | kndr | ft | it | isn’t | my | business
---|---|---|---|---|---|---
I | know |  | it | isn’t | my | business
Table 3: Example of text alignment - the words "I" and "it" are aligned and the bold words between them are the differences. Correct |  Incorrect | Baseline | BERT | RoBERTa | GPT2
---|---|---|---|---|---
…had no doubt |  …has no donbt | ✓ | ✓ | ✓ | ✓
…I had laid my head |  …I bad laid my head | ✗ | ✓ | ✓ | ✓
…clinging flakes of froth |  …clinging takes of froth | ✗ | ✗ | ✓ | ✓
…the senor |  …the sefior | ✗ | ✗ | ✗ | ✓
Accuracy of models over 1000 human annotated pairs: | 0.712 | 0.761 | 0.794 | 0.853
Table 4: Examples of extracted pairs with results from different models with
accuracy scores over 1000 pairs(the annotators and models judge the phrase in
the context of the full sentence).

To remedy this problem, we employ the use of “anchor” tokens, which are tokens
that occur only once in a book. Some examples of such tokens are the words
“systematic”, “rampacious”, “affix” in Oliver Twist. They are singleton words
that tend to be more specific in meaning. For an average-length book, there
only exist a few thousand of these tokens, and thus, we can first align the
book according to these tokens. Since the contents of the books are similar,
the anchor tokens for both books should also be similar. Thus, we run the full
dynamic programming solution between the anchor tokens of both books, which
can be done much faster than the book in its entirety. Once we have the
alignment between the anchor tokens, we can then run the dynamic program
between each aligned anchor token. In general, these distances are quite short
and thus, the overall running time improves dramatically. Note that anchor
n-grams would also work if there is not enough anchor tokens.

###  3.3 Rating Sentence Pairs

Given the alignment between a pair of books, we now identify where the
differences lie. For each consecutive aligned token, we check whether there is
a gap in alignment in either of the books. At every point where a gap lies, we
capture those areas as token-wise differences as well as the sentences in
which these differences lie.

The main question now is: given two similar sentences with some small
difference between them, which sentence is “more” correct? Generally, these
differences can be attributed to OCR errors, typically random letters or
punctuation appearing in text. Other times, it may be errors where letters are
replaced such as ‘m’ by ‘in’ or ‘2’ by ‘?’.

#### Baseline.

We first consider a baseline of a dictionary lookup. Given a sentence, we
consider the ratio of tokens that are in a dictionary 111We use the NLTK
English dictionary. to the total number of tokens in the sentence . We
consider the sentence that has a higher ratio to be the better sentence; if
equal, we select randomly.

However, this is quite often not sufficient as the ratio tends to be roughly
equal for both sentences. This can be attributed to the differences in both
sentences being out of dictionary, such as when a name gets misspelled or both
being in the dictionary such as when both are legitimate words (ex. ‘but’
versus ‘nut’ as errors). Additionally, there may be multiple errors in the
same sentence, resulting in skewed ratios. Also, sentences may not always be
of the same length due to OCR errors among sentence-defining punctuation such
as periods. Due to these factors, we turn towards stronger models.

#### Language Models.

Thus, we rely on language models, particularly models based on modern
transformer architectures. In this context, we can apply language models to
compute the likelihood of a given sentence based on the probability of each
token within it. For a given sentence, we compute its likelihood by passing it
through a given language model and compute the log sum of token probabilities
normalized by the number of tokens, to avoid biasing on sentence length. Thus,
given two sentences, we can compute the normalized log likelihood for both and
choose a winner based on the greater value.

#### Evaluation.

For our experiments, we test the baseline along with three language models
based on BERT Devlin et al. (2019), RoBERTa Liu et al. (2019), and GPT2
Radford et al. (2019). For all of these models, we use the pretrained models
without any fine tuning. For the test set, we procure a random set of 1000
pairs of sentences from our corpus, and manually annotate which sentence is
better for each one. We note that there are 93 pairs that were deemed
ambiguous by the human annotators; thus, they were not included in the final
evaluation. Table 4 shows the results for this human annotated set with some
examples.

#### Analysis.

While the baseline performed respectably compared to random guessing (0.5), we
find that GPT2 performs the best out of all the methods. Thus, we apply GPT2
as the main language model for determining the correct sentence. We do note
that it is possible for both sentences to contain errors, but we can still
apply the same methodology to judge which of the two is less severe.

###  3.4 Determining Best Books

Given a pair of duplicate books, we consider the task of identifying the one
that is of better quality from an OCR perspective. By applying the text
alignment and sentence evaluations described in the prior subsections, we
compute a list of aligned sentence pairs between the two books with the
likelihood scores for each one. We can convert these scores into a confidence
by normalizing with softmax.

Formally, given two books $B_{1}$ and $B_{2}$ with $n$ aligned sentences, we
consider $p_{i},q_{i}$ as the respective confidence scores for the $i^{th}$
aligned sentence pair ($p_{i}+q_{i}=1$).

The simplest method to determine the better of the two books then would be to
take the majority count. Whichever book is favored more among all the sentence
pairs can be considered the winner. Concretely, we compute the probability
that book 1 is better than book 2 as:

$\Pr[B_{1}>B_{2}]=\frac{\texttt{count}(p_{i}>q_{i})}{n}$ (1)

If this is greater than 0.5, $B_{1}$ is declared the winner; otherwise,
$B_{2}$ is the winner. Often, this works well but when the number of errors
are relatively balanced between both books, then we need to consider the
confidence scores themselves.

To address this issue, we apply a Bayesian updating approach. Recall that the
posterior probabilities are proportional to the product of the likelihood and
prior. As the prior, we use Equation 1, and we compute the log posterior for
$B_{1}$ ($B_{2}$ is analogous) as:

$\underbrace{\sum_{i=1}^{n}\log{p_{i}}}_{\textrm{log
likelihood}}+\underbrace{\log{\left(\frac{\texttt{count}(p_{i}>q_{i})}{n}\right)}}_{\textrm{log
prior}}$ (2)

The final winner is decided by comparing the final two log posteriors, and
choosing the book corresponding to the larger value.

So far, we have only discussed comparisons between two given books. However, a
general set of duplicates may contain more than two books. To find a winner
among an arbitrary sized set of books, we employ a tournament strategy. We use
our Bayesian approach to find the winner between distinct pairs of books, and
the winner of each pair face off, and so on until there is only one winner. It
is the final winner of the tournament that is marked as the canonical text of
the set.

We apply our method on the full 96,635 HathiTrust texts, and find 58,808 of
them to be a duplicate to another book in the set. Among the duplicates, we
identify 17,136 canonical books.

#### Golden Dataset.

To evaluate our approach, we create a golden dataset based on an alignment
between Gutenberg and HathiTrust. By applying the same deduplication methods
discussed in Section 3, we create a test dataset of 6,694 paired books. In
this set, we use the Gutenberg version as the ground truth since Gutenberg
books are of higher quality due to human editors compared to HathiTrust books.
To evaluate our method for choosing a canonical book, we apply it on our
golden dataset to see how often it selects Gutenberg over HathiTrust as the
better copy. We find that it selects the Gutenberg version 6,059 times out of
the total 6,694 books, showing that our method preferred Gutenberg 90.5% of
the time. This agrees with our understanding that Gutenberg books are of
higher quality.

##  4 OCR Errors in Single-Copy Texts

We now consider OCR errors for single copy texts. In this setting, we cannot
use any alignment technique as the books live in isolation. For this case, we
train models for both OCR error detection and correction using the 17,136 sets
of duplicate books and their alignments. All models were run on a compute
server with 2.30 GHz CPU and TeslaV100 GPU. No hyperparameter tuning was done
on any models; default values were run for all models.

Sentence |  Ground Truth |  Generated | Score | Precision
---|---|---|---|---
… speaking as gently , as if he had been lying in a satin <ocr> eradle </ocr> . |  cradle |  robe | 0.263 | 0.776
… know of your brother ’s <ocr> apphcation n </ocr> to me ? ” |  application |  approbation | 0.398 | 0.829
… was to <ocr> seck </ocr> a home with some friends … |  seek |  find | 0.512 | 0.868
… and <ocr> dryexposition n </ocr> of the glories of the house … |  dry exposition |  dry exposition | 0.658 | 0.905
… in finding <ocr> tlie </ocr> auger holes . |  the |  the | 0.998 | 0.992
Table 5: Examples of generated OCR corrections - score represents the
confidence in the generated text and precision is calculated across the test
set with the corresponding score as a threshold

###  4.1 Detecting OCR Errors

For OCR detection, we want to be able to identify which tokens in a given text
can be marked as an OCR error. This is a classic token classification problem;
thus, we train RoBERTa-large with a token classification head for 3 epochs.

Threshold | Precision | Recall
---|---|---
0.25 | 0.699 | 0.701
0.5 | 0.787 | 0.618
0.75 | 0.853 | 0.506
0.95 | 0.916 | 0.234

Figure 1: ROC and metrics for OCR detection at various thresholds (in general,
we value precision over recall)

The training data is derived from our aligned books from before. For each
sentence pair, we choose the lower-scoring sentence as the sentence with the
OCR error and annotate the tokens as either 0 or 1, where 1 represents an
error. We note that tokenization in RoBERTa further breaks down the tokens to
sub-tokens. In cases where the word that is marked with an OCR error is broken
down into sub-tokens, we label each sub-token as an error.

We perform a train-test split at the book level, and sample a training set of
2,080,328 sentences, half of which have no OCR errors and half of which do.

Figure 1 shows the ROC curve and metrics on the test set. We find that with a
high enough threshold, we can opt for a high precision with relatively few
mistakes. If the goal is to improve the quality of a book, we prefer to
optimize precision over recall as it is more important to be confident in the
changes one makes as opposed to trying to catch all of the errors in a book.
Empirically, we found a threshold of 0.95 to provide a good balance between
prioritizing precision while finding a non-trivial number of errors.

###  4.2 Correcting OCR Errors

For OCR correction, we now assume we have the output of our detection model,
and we now want to generate what the correct phrase should be. We model this
as a sequence-to-sequence problem, where the input is a sentence containing an
OCR error and the output is what the corrected form should be. To do this, we
train a base-T5 seq2seq model Raffel et al. (2019) with a language modeling
head for conditional generation, for 3 epochs.

We use special <ocr> and </ocr> tags to denote the start and end of the OCR
error location within a sentence respectively. For generation, we use greedy
search decoding to generate the most likely sequence of tokens.

We train this model over the same dataset as OCR detection. We note that our
training is performed only on text with errors, annotated with the special
<ocr> tokens. We also score the generated text from a 0 to 1 scale. To do
this, we simply take the minimum probability across the sequence of generated
tokens.

#### Analysis.

Table 5 shows examples of generated OCR predictions along with their score. We
now consider thresholds above which we accept the generated text. The
precision is calculated across the entire test set with the corresponding
score in its row as a threshold. Note that precision increases with higher
thresholds. Empirically, we choose a threshold of 0.95.

One key point to note is that traditionally, many OCR correction models have
been character-based, but with recent advances in transfer learning, we find
that recent token-based models have significant advantages in terms of memory
as well as performance. With access to more context, token-based models have
the advantage that they can make sensible predictions that work as synonyms
even if the edit distance from the original text may be far. This may not be
completely desirable in certain situations where the original words used need
to be preserved (e.g. analyzing an author’s vocabulary), but in many cases,
this may actually be beneficial for NLP analysis/downstream tasks. Quantifying
the improvement on several downstream tasks will be an interesting extension
to consider. We do note that when the model suggests replacements that are
semantically similar (e.g. “seek” to “find”), but not structurally (e.g.
“tlie” to “the”), then it tends to have lower confidence scores.

Figure 2: The top figure shows a histogram for the number of errors
corrected/introduced. The red bars show how many errors we introduce and the
blue bars show how many we correct. The third dark color represents an overlap
of the red and blue bars. The bottom figure shows a scatter plot, where each
point represents a book. The red line is the identity; thus, points below show
books with more fixes than introduced errors, and points above show books with
more errors than fixes.

Figure 2 shows the results of OCR correction on our golden test set. In
general, we show that we introduce far fewer errors in many books (red bars
tend to be more clustered towards the y-axis) compared to how many we correct
(blue bars are spread towards the right, indicating that we are correcting
many errors for many books). We find that on average, we correct more than six
times as many errors as we introduce – about 61.3 OCR error instances
corrected compared to an average 9.6 error instances we introduce. We remark
that this is a pessimistic metric as we are only rewarding ourselves for an
exact match to our silver-standard “ground truth” based on our ranked sentence
pairs.

##  5 Analysis of Scanning Quality

Figure 3: Publication year of books versus quality

#### Quality by Location.

The HathiTrust library is a collection of books from multiple sources, mostly
composed of universities. We explore whether there are differences in the
quality of books depending on location. From Section 1, Table 2 shows the
quality of books on a subset of books from different libraries. We define the
quality of a book to be the percentage of sentences out of the total that do
not contain any OCR error. From a presentation on HathiTrust Data in
Detail222https://www.hathitrust.org/documents/HTRC-UnCamp2012-York-201211.pdf,
we find that some of the books were digitized by Google, others were digitized
by the Internet Archive, and few were digitized locally. Overall, we find that
the quality of books digitized by Google were of higher quality than the
Internet Archive. The exception is Harvard, but this is due to the fact that
their books, on average, were published much earlier than the rest of the
corpus, and consequently, are of lower quality.

#### Quality by Publication Year.

We also look at the quality of scans by publication year. Figure 3 shows this
relation. In general, we see that quality has improved over the years with
many books being of high quality in the early 1900s. Prior to that point, the
quality of books was spread out more uniformly.

#### Top Character Replacements.

Finally, we look at common substitutions for characters. Figure 6 show the top
3 replacements for each character. Each cell is color-coded by a normalized
frequency across all substitutions. We see that some of the most common OCR
errors are ‘j’ with ‘;’ and ‘l’ with ‘!’.

Char | 1 | 2 | 3 | Char | 1 | 2 | 3
---|---|---|---|---|---|---|---
a | the | “ | an | n | – | a | ’
b | by | be | is | o | of | ? | to
c | ’ | “ | * | p | P | – | ?
d | – | a | , | q | a | o | ?
e | – | he | , | r | ? | – | ,
f | ? | l | ! | s | – | ! | ,
g | – | , | ; | t | ? | – | !
h | he | a | it | u | “ | a | up
i | l | ? | 1 | v | " | , | “
j | ; | , | ’ | w | “ | " | –
k | it | a | – | x | " | 1 | X
l | ! | I | 1 | y | – | , | by
m | in | my | – | z | a | ? |
Table 6: Top replacements for each lower case character - darker colors
represent higher frequency of occurrence

##  6 Conclusion

In this paper, we demonstrated how to improve the quality of an important
corpus of digitized books, by correcting transcription errors that generally
occur due to OCR. Our key idea to provide ground truth was to identify
thousands of duplicate books (titles scanned in different locations and of
uncertain quality). We aligned them at the token level to find where the
differences occur, and used modern language models to determine which book
copy is of higher quality. Additionally, we used this alignment as training
data to train a model for correcting OCR errors in singleton books (books
without any duplicates).

We showed that our methods correct over six times as many errors as it
introduces, and also demonstrate that our errors tend to be semantically
sensible. Through our efforts, we produced a substantially better version of
over 50,000 distinct titles from the Hathitrust and Guttenberg as a foundation
for future NLP research as well as show some interesting analysis from post-
OCR processing.

## References

  * Abedjan et al. (2016) Ziawasch Abedjan, Xu Chu, Dong Deng, Raul Castro Fernandez, Ihab F Ilyas, Mourad Ouzzani, Paolo Papotti, Michael Stonebraker, and Nan Tang. 2016.  Detecting data errors: Where are we and what needs to be done?  _Proceedings of the VLDB Endowment_ , 9(12):993–1004.
  * Afli et al. (2016) Haithem Afli, Loïc Barrault, and Holger Schwenk. 2016.  Ocr error correction using statistical machine translation.  _Int. J. Comput. Linguistics Appl._ , 7(1):175–191.
  * Amrhein and Clematide (2018) Chantal Amrhein and Simon Clematide. 2018.  Supervised ocr error detection and correction using statistical and neural machine translation methods.  _Journal for Language Technology and Computational Linguistics (JLCL)_ , 33(1):49–76.
  * Bassil and Alwani (2012) Youssef Bassil and Mohammad Alwani. 2012.  Ocr post-processing error correction algorithm using google online spelling suggestion.  _arXiv preprint arXiv:1204.0191_.
  * Bengio et al. (2003) Yoshua Bengio, Réjean Ducharme, Pascal Vincent, and Christian Janvin. 2003.  A neural probabilistic language model.  _The journal of machine learning research_ , 3:1137–1155.
  * Chiron et al. (2017a) Guillaume Chiron, Antoine Doucet, Mickaël Coustaty, and Jean-Philippe Moreux. 2017a.  Icdar2017 competition on post-ocr text correction.  In _2017 14th IAPR International Conference on Document Analysis and Recognition (ICDAR)_ , volume 1, pages 1423–1428. IEEE.
  * Chiron et al. (2017b) Guillaume Chiron, Antoine Doucet, Mickaël Coustaty, Muriel Visani, and Jean-Philippe Moreux. 2017b.  Impact of ocr errors on the use of digital libraries: towards a better access to information.  In _2017 ACM/IEEE Joint Conference on Digital Libraries (JCDL)_ , pages 1–4. IEEE.
  * Coustaty et al. (2018) Mickaël Coustaty, Antoine Doucet, Adam Jatowt, Nhu-Van Nguyen, et al. 2018.  Adaptive edit-distance and regression approach for post-ocr text correction.  In _International Conference on Asian Digital Libraries_ , pages 278–289. Springer.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Evershed and Fitch (2014) John Evershed and Kent Fitch. 2014.  Correcting noisy ocr: Context beats confusion.  In _Proceedings of the First International Conference on Digital Access to Textual Cultural Heritage_ , pages 45–51.
  * Gutenberg (n.d.) Project Gutenberg. n.d.  www.gutenberg.org.  Accessed: April 2021.
  * (12) HathiTrust Digital Library.  https://www.hathitrust.org/.
  * Jatowt et al. (2019) Adam Jatowt, Mickael Coustaty, Nhu-Van Nguyen, Antoine Doucet, et al. 2019.  Deep statistical analysis of ocr errors for effective post-ocr processing.  In _2019 ACM/IEEE Joint Conference on Digital Libraries (JCDL)_ , pages 29–38. IEEE.
  * Kissos and Dershowitz (2016) Ido Kissos and Nachum Dershowitz. 2016.  Ocr error correction using character correction and feature-based word classification.  In _2016 12th IAPR Workshop on Document Analysis Systems (DAS)_ , pages 198–203. IEEE.
  * Kolak et al. (2003) Okan Kolak, William Byrne, and Philip Resnik. 2003.  A generative probabilistic ocr model for nlp applications.  In _Proceedings of the 2003 Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics_ , pages 134–141.
  * Kukich (1992) Karen Kukich. 1992.  Techniques for automatically correcting words in text.  _Acm Computing Surveys (CSUR)_ , 24(4):377–439.
  * Lew et al. (2021) Alexander Lew, Monica Agrawal, David Sontag, and Vikash Mansinghka. 2021.  Pclean: Bayesian data cleaning at scale with domain-specific probabilistic programming.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1927–1935. PMLR.
  * 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.  _arXiv preprint arXiv:1907.11692_.
  * Llobet et al. (2010) Rafael Llobet, Jose-Ramon Cerdan-Navarro, Juan-Carlos Perez-Cortes, and Joaquim Arlandis. 2010.  Ocr post-processing using weighted finite-state transducers.  In _2010 20th International Conference on Pattern Recognition_ , pages 2021–2024. IEEE.
  * Mayfield et al. (2009) Chris Mayfield, Jennifer Neville, and Sunil Prabhakar. 2009.  A statistical method for integrated data cleaning and imputation.
  * Nguyen et al. (2020) Thi Tuyet Hai Nguyen, Adam Jatowt, Nhu-Van Nguyen, Mickael Coustaty, and Antoine Doucet. 2020.  Neural machine translation with bert for post-ocr error detection and correction.  In _Proceedings of the ACM/IEEE Joint Conference on Digital Libraries in 2020_ , pages 333–336.
  * Pasula et al. (2003) Hanna Pasula, Bhaskara Marthi, Brian Milch, Stuart J Russell, and Ilya Shpitser. 2003.  Identity uncertainty and citation matching.  In _Advances in neural information processing systems_ , pages 1425–1432.
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9.
  * Raffel et al. (2019) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. 2019.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _arXiv preprint arXiv:1910.10683_.
  * Rigaud et al. (2019) Christophe Rigaud, Antoine Doucet, Mickaël Coustaty, and Jean-Philippe Moreux. 2019.  Icdar 2019 competition on post-ocr text correction.  In _2019 International Conference on Document Analysis and Recognition (ICDAR)_ , pages 1588–1593. IEEE.
  * Salazar et al. (2020) Julian Salazar, Davis Liang, Toan Q. Nguyen, and Katrin Kirchhoff. 2020.  Masked language model scoring.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 2699–2712, Online. Association for Computational Linguistics.
  * Schulz and Kuhn (2017) Sarah Schulz and Jonas Kuhn. 2017.  Multi-modular domain-tailored ocr post-correction.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 2716–2726.
  * Taghva and Stofsky (2001) Kazem Taghva and Eric Stofsky. 2001.  Ocrspell: an interactive spelling correction system for ocr errors in text.  _International Journal on Document Analysis and Recognition_ , 3(3):125–137.
  * Tan et al. (2020) Samson Tan, Shafiq Joty, Lav R Varshney, and Min-Yen Kan. 2020.  Mind your inflections! improving nlp for non-standard english with base-inflection encoding.  _arXiv preprint arXiv:2004.14870_.
  * Tong and Evans (1996) Xiang Tong and David A Evans. 1996.  A statistical approach to automatic ocr error correction in context.  In _Fourth Workshop on Very Large Corpora_.
  * Underwood (2016) Ted Underwood. 2016.  Metadata for English-language Literature in HathiTrust Digital Library Beyond 1923.  https://github.com/tedunderwood/hathimetadata.
  * Vobl et al. (2014) Thorsten Vobl, Annette Gotscharek, Uli Reffle, Christoph Ringlstetter, and Klaus U Schulz. 2014.  Pocoto-an open source system for efficient interactive postcorrection of ocred historical texts.  In _Proceedings of the First International Conference on Digital Access to Textual Cultural Heritage_ , pages 57–61.