2023

These authors contributed equally to this work.

[1]Francesco Guatieri These authors contributed equally to this work.

[1]Research Neutron Source Heinz Maier-Leibnitz (FRM II), Technical University
of Munich , Lichtenbergstr. 1, Garching bei München, 85748, Bayern, Germany

# Imaging low-energy positron beams in real-time with unprecedented resolution

Michael Berghold<EMAIL_ADDRESS>Vassily Vadimovitch Burwitz
<EMAIL_ADDRESS>Lucian Mathes<EMAIL_ADDRESS>Christoph
Hugenschmidt<EMAIL_ADDRESS><EMAIL_ADDRESS>*

###### Abstract

Particle beams focused to micrometer-sized spots play a crucial role in
forefront research using low-energy positrons. Their expedient and wide
application, however, requires highly-resolved, fast beam diagnostics. We have
developed two different methods to modify a commercial imaging sensor to make
it sensitive to low-energy positrons. The first method consists in removing
the micro-lens array and Bayer filter from the sensor surface and depositing a
phosphor layer in their place. This procedure results in a detector capable of
imaging positron beams with energies down to a few tens of eV, or an intensity
as low as
$35\text{\,}\mathrm{e}^{+}\mathrm{/}\mathrm{s}\mathrm{/}\mathrm{m}\mathrm{m}^{2}$
when the beam energy exceeds $10\text{\,}\mathrm{k}\mathrm{e}\mathrm{V}$. The
second approach omits the phosphor deposition; with the resulting device we
succeeded in detecting single positrons with energies upwards of
$6\text{\,}\mathrm{k}\mathrm{e}\mathrm{V}$ and efficiency up to 93%. The
achieved spatial resolution of
$0.97\text{\,}\mathrm{\SIUnitSymbolMicro}\mathrm{m}$ is unprecedented for
real-time positron detectors.

###### keywords:

Positrons, Imaging, Detectors, Semiconductors

##  1 Introduction

Low-energy positron beams are an essential tool of investigation in modern
material science Mills_PositronSurfaceSciences ; Schultz_Surfaces , enabling a
variety of spectroscopic techniques which can be used to study material
defects Dupasquier_PALSFoundational ; Siegel_PALSFoundational , elemental
compositions KumarLynn_ElementslDBS , crystalline surface structures
Fukaya_THREPD  and Fermi surfaces West_ACARFoundation . The current frontier
in the development of positron annihilation spectroscopy technologies is the
production and the expedient deployment of micrometer-sized beams, which would
allow probing and resolving the properties of a sample to micro-metric scale
Uedono_Microbeam ; Mittender_Microbeam ; Gigl_Microbeam . Furthermore,
positron microbeams are an enabling technology for fundamental physics
experiments, such as gravitational tests with positronium atoms Mills_FreeFall
or interferometry with antimatter Sala_Interferometry .

Due to fundamental technological limitations current low-energy positron beams
possess very low brightness. The difficulty of performing on-line monitoring
of a low-energy low-brightness particle beam is a hindrance to the widespread
practical application of microscale positron beams. The two most prominently
employed techniques to determine a positron beam position and size are the
knife-edge method (KEM) Platinum  and imaging through the use of micro-channel
plates (MCPs) Wiza_MCP . The KEM achieves high transversal resolution but
requires long measurement times, since a target has to be moved step-wise
through the beam cross-section and data acquisitions performed at each step;
furthermore, the resulting measurement is fundamentally uni-dimensional. An
MCP, in contrast, allows for fast imaging of the impinging positron beam. Each
individual micro-channel in an MCP acts as an amplifier: A charged particle
that enters it can trigger the production of a cascade of electrons, which are
then converted to visible light by luminescence in a phosphor screen placed in
the backplane of the MCP. On the downside, the resolution of MCPs is
substantially lower than what is achievable by KEM Tresmin_MCP ; furthermore,
their installation imposes stringent geometric constraints, such as the
availability of a view-port for imaging of the phosphor screen via a digital
acquisition camera Vinelli1 .

A possibility hitherto unexplored is to skip the amplification stage of the
MCP and instead directly impinge a continuous positron beam onto a phosphor-
coated image sensor. Belief in the potential of this configuration is in part
motivated by the experimental observation that a phosphor screen impacted by a
positron beam emits significantly more light than when it is hit by an
electron beam of similar energy and intensity; effect that is more pronounced
at lower energies Stenson_Luminescence . On top of that, this new approach to
beam imaging would exploit the huge progress made in the image sensor
technology in the last 30 years: spurred by the popularization of digital
cameras and smartphones, the industry has achieved orders of magnitudes of
improvements in terms of pixel count, resolution, sensitivity, noise and cost
Boukhayma_CMOS ; Gouveia_CMOS . The sensitivity of modern image sensors might
realistically be sufficient to detect positron-induced luminescence without
the need for an electron-cascade amplification stage. Moreover, current image
sensors have pixel sizes in the order of $1\text{\,}\mathrm{\SIUnitSymbolMicro
m}$ or smaller, a resolution surpassing that of the best MCPs and comparable
to what can be achieved with KEM.

Even more ambitiously, one could attempt to directly use an image sensor
without phosphor coating to image and impinging positron beam. The idea of
using image sensors for beam detection is in itself not completely new, as the
phenomenon of electron beam-induced current (EBIC) can be employed for imaging
of electron beams Hanoka_EBIC ; Mecklenburg_EBIC . The main challenge here is
that the intensity of a positron beam is typically between $7$ and $14$ orders
of magnitude smaller than that of an electron beam. A priori, we would have
expected that necessary requirements to directly image a positron beam with an
image sensor would be the use of a custom built sensor, long integration times
and a high intensity positron beam, such as that produced at the NEPOMUC
facility NEPOMUC .

In this work we report that a consumer-grade image sensor, based on
complementary metal-oxide substrate (CMOS) technology can, instead, resolve
individual impinging positrons with almost unit efficiency and micrometric
accuracy if the positron kinetic energy exceeds $6\text{\,}\mathrm{keV}$. This
result far surpasses our expectations in terms of sensitivity and resolution.
Furthermore, we determined that it is possible to image the beam also by
coating the image sensor with phosphors; our results indicate that, in this
configuration, it is possible to detect a positron beam with a kinetic energy
down to a few $\text{\,}\mathrm{e}\mathrm{V}$ and with a resolution that is
only limited by the thickness and granularity of the phosphor coating.

##  2 Results

###  2.1 Phosphor-aided detection

We have imaged a low-energy positron beam by means of detectors realized by
modifying commercial CMOS image sensors (Sony IMX219). The sensors were
modified by first removing the Bayer filter and microlens array from their
surface and then depositing a
$70\text{\,}\mathrm{\SIUnitSymbolMicro}\mathrm{m}$ coating of EJ-600 ZnS:Ag
phosphor powder (see Fig. 1 and section 4.1).

The beam was produced by moderating the positrons emitted by a radioactive
22Na $\beta^{+}$-emitter through a
$1\text{\,}\mathrm{\SIUnitSymbolMicro}\mathrm{m}$ thick mono-crystalline (110)
tungsten foil. This beam can be focused onto the target in a
$2-$3\text{\,}\mathrm{m}\mathrm{m}$$ spot with an energy that can be varied
between 2 and $25\text{\,}\mathrm{k}\mathrm{e}\mathrm{V}$; positron rate at
the target is in the order of $6\cdot 10^{4}$ positrons/s LabBeam . A variety
of coils is used to adiabatically transport the beam, including several pairs
of steering coils which allow us to move the spot laterally with respect to
the target. The image sensor was installed in the focusing point of the
positron beam with its surface orthogonal to the beam direction. Beam focusing
is achieved by the combined action of electrostatic lenses and by pinching the
magnetic field in the proximity of the target by means of a ferromagnetic rod
installed underneath the sensor (see Fig. 1b).

Figure 1: a) Section of the microscopic structure of the sensor according to
Matthews et al. ReverseEngineering  b) Main assembly used to hold and test the
sensor; for clarity the front cover of the copper encasing holding the readout
electronics is omitted. c) Schematic representation of the processes of layer
removal (1), phosphor-mediated imaging (2) and direct imaging (3).

The particle beam is recorded by the sensor as a bright spot (see Fig. 2). We
have verified the nature of the signal to be the positron beam with three
independent methods. Firstly, by observing the disappearance of the signal
when a shutter located $3\text{\,}\mathrm{m}$ upstream of the sample holder is
closed. Secondly, by observing that a tungsten wire with a diameter of
$125\text{\,}\mathrm{\SIUnitSymbolMicro}\mathrm{m}$ installed
$1\text{\,}\mathrm{m}\mathrm{m}$ in front of the sensor surface will cast a
shadow onto the sensor and, thirdly, by observing that the spot recorded by
the sensor moves in accordance with the variation of the current in the
correction coils used to steer the beam (see Fig. 2). In the image recorded by
the sensor it is possible to discern the outline of single phosphor grains, as
well as the presence of curly white streaks with lengths ranging from $5$ to
$70\text{\,}\mathrm{\SIUnitSymbolMicro}\mathrm{m}$. These white streaks are
tracks produced by high energy electrons resulting from Compton scattering
with high energy $\gamma$ quanta, which themselves are the result of positron
annihilation (see Fig. 2c.2). The process has a low enough cross section to
not interfere significantly with the measurement. Based on the blurring of the
shadow projected by the wire we can determine an upper limit to the standard
deviation of the optical transfer function (OTF) of the sensor
Reichenbach_Resolution  finding it to be less than
$19\text{\,}\mathrm{\SIUnitSymbolMicro}\mathrm{m}$, which is similar to the
resolution given by an MCP and substantially better than what a typical MCP-
phosphor-camera system can provide Tresmin_MCP .

Figure 2: a-e) Imaging of the positron beam using the phosphor-coated CMOS
sensor with different steering coils settings. The black shadow is produced by
a tungsten wire, the dark area below is a region with thicker phosphor
coating. c.2) The magnification shows the outline of single phosphor grains
and white tracks left by Compton electrons. f) The portion of image e) marked
by the yellow rectangle has been projected and fitted with the error function
to provide a lower limit to the sensor’s OTF; in practice, factors other than
the sensor resolution contribute to the blurring, such as beam divergence and
scattering over the wire edges.

The beam intensity required to produce an image depends on the exposure time
and on the beam energy, as expected from Stenson et al.Stenson_Luminescence .
We have computed the ratio between the signal recorded by the sensor’s analog
to digital converter (ADC) and the positron flux in two steps. First we
measured the total beam intensity with two high purity Germanium (HPGe)
detectors in anti-collinear geometry. We then determined the positron flux
impinging on different regions of the sensor by performing a Gaussian fit of
the spot (see section 4.3). Fitting the beam is necessary to prevent the
clipping due to the limited sensor area from biasing the calibration of the
beam intensity. The relationship between positron flux and recorded signal
intensity is shown in Fig. 3. When operating the beam with a kinetic energy of
$10\text{\,}\mathrm{k}\mathrm{e}\mathrm{V}$ a positron flux greater than
${35\pm
11\,$\text{\,}\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{c}\mathrm{l}\mathrm{e}\mathrm{s}\mathrm{/}\mathrm{s}\mathrm{/}\mathrm{m}\mathrm{m}^{2}$}$
is detectable with a signal to noise (S/N) ratio greater than 1; to achieve
this S/N ratio an exposure time of $167\text{\,}\mathrm{s}$ and
$16\\!\times\\!16$ pixel sub-sampling are required. Alternatively, a
$19\text{\,}\mathrm{s}$ exposure time combined with $4\\!\times\\!4$ pixel
sub-sampling will still be able to detect a flux as low as $730\pm 360\
$\text{\,}\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{c}\mathrm{l}\mathrm{e}\mathrm{s}\mathrm{/}\mathrm{s}\mathrm{/}\mathrm{m}\mathrm{m}^{2}$$
allowing for a faster and spatially more resolved measurement. In general, the
operational parameters of the sensor should be adjusted depending on the flux
to be detected to achieve optimal performance or a specific S/N ratio. With
the beam intensity available to us we are still able to detect the beam when a
$2\text{\,}\mathrm{k}\mathrm{e}\mathrm{V}$ implantation energy is employed.
According to literature Stenson_Luminescence , this positron flux should be
visible down to an implantation energy of a few
$\text{\,}\mathrm{e}\mathrm{V}$.

Figure 3: Top: the amount of photons emitted by the phosphor coating
determined from the sensor as a function of the beam energy of the signal
produced into the image sensor. The sensor was operated with variable gain and
exposure time in order to keep the signal within the sensor’s dynamic range.
Bottom: the minimum beam intensity necessary to produce a detectable signal
with a S/N ratio larger than $1$ using an exposure time of
$167\text{\,}\mathrm{s}$ and employing $16\\!\times\\!16$ pixel sub-sampling.

###  2.2 Direct positron detection

We tested whether the CMOS sensor itself is sensitive to low-energy positrons.
We prepared the sensor by removing the Bayer filter and microlens array from
its surface, but applied no coating (see section 4.1). The sample was
installed in the same setup employed in 2.1 and tested with the same beam.
Acquisition was performed with an exposure of $4.9\text{\,}\mathrm{s}$ and a
gain value of $5.3$ while the beam energy was varied between
$3\text{\,}\mathrm{k}\mathrm{e}\mathrm{V}$ and
$15\text{\,}\mathrm{k}\mathrm{e}\mathrm{V}$. We found the sensor to be, in
this configuration, capable of detecting single positrons with kinetic energy
larger than of $6\text{\,}\mathrm{k}\mathrm{e}\mathrm{V}$. Single positrons
appear in the image as clusters of one to four pixels whose brightness greatly
exceeds the background noise (see Fig. 4).

Figure 4: a) High resolution imaging of a wedge of aluminum foil obtained with
$10\text{\,}\mathrm{k}\mathrm{e}\mathrm{V}$ positrons impinging on an uncoated
CMOS sensor. b) A detail showing instances of the signal produced by single
positrons impinging on the surface of the sensor, which results in the
activation of one to four pixels. The dark shadows near the tip of the
aluminum foil are caused by impurities that were present in the drop of
isopropyl alcohol used to deposit the aluminum foil onto the sensor. c)
Criteria used to identify positrons in the images.

Computing the detection efficiency of the sensor requires knowledge of the
positron flux impinging over the sensor surface. This cannot be determined
solely from the counts of the HPGe detectors installed around the sample
chamber since, as can be seen in Fig. 2, the beam spot is not completely
contained in the sensor area. We have determined the local positron flux over
the surface of the sensor by fitting the beam shape to determine the portion
of beam hitting the sensor surface. To produce a suitable image to perform the
beam fit an exposure time of $4.9\text{\,}\mathrm{s}$ and gain of 5.3 were
employed, as these parameters produce negligible pile-up and keep the signal
within the dynamic range of the pixels. We observed the detection efficiency
to depend strongly on the beam energy, ranging from being close to zero for
energies below $6\text{\,}\mathrm{k}\mathrm{e}\mathrm{V}$ to approaching unity
for energies above $15\text{\,}\mathrm{k}\mathrm{e}\mathrm{V}$ (see Fig. 5,
top). We interpret this result as an indication that the photodiodes built
into the CMOS sensor are indeed extremely sensitive to positrons, but that a
kinetic energy of $6\text{\,}\mathrm{k}\mathrm{e}\mathrm{V}$ is required for
the positron to penetrate deep enough to reach them. This interpretation is
coherent with the available information about the geometric structure of the
sensor ReverseEngineering , which indicates the presence of additional layers
on top of the sensitive volume, specifically an anti-reflection coating, a
wire grid layer and possibly a passivation layer (made of silicon oxide,
silicon nitride or both Gouveia_CMOS ); we present in section 2.4 a
quantitative discussion of the effects of these layers.

It is reasonable to assume that the removal of additional layers would allow
the detection of positrons of even lower kinetic energy. We have attempted to
scrape away the wire grid from the surface of the sensor, but found the
process to be too unrealiable to be employed in any practical sense as
removing large portions of it almost inevitably leads to the destruction of
the device. We were nonetheless able to scrape away a small portion of the
wire grid without damaging the sensor. As the scraped area is too small to
allow for a beam fit, it is not possible to compute its absolute detection
efficiency; instead we computed, as a function of the implantation energy, the
ratio between the signal intensity recorded in this area and in an adjacent
area still coated by the grid (see Fig. 5, bottom). We removed the fixed-
pattern noise (see section 4.2) from the measurements before computing the
ratio, but not the constant pedestal that arises naturally when applying the
positron beam. This is needed, as its presence keeps the ratio finite at all
energies; for consistency the same pedestal was included in our simulations of
this metric (see section 2.4). The ratio shows a peak located around
$5\text{\,}\mathrm{k}\mathrm{e}\mathrm{V}$ with a half width of about
$1\text{\,}\mathrm{k}\mathrm{e}\mathrm{V}$, indicating a decrease of the
energy threshold for positron detection by about
$2\text{\,}\mathrm{k}\mathrm{e}\mathrm{V}$ in the exposed areas.

Figure 5: Top: Positron detection efficiency of an uncoated CMOS sensor with
the Bayer filter and microlens array removed as a function of the impinging
positron energy. The detection efficiency is close to unity at
$15\text{\,}\mathrm{k}\mathrm{e}\mathrm{V}$ and drops to zero below
$6\text{\,}\mathrm{k}\mathrm{e}\mathrm{V}$ due to the positron kinetic energy
being insufficient for them to reach the sensitive volume of the sensor. The
electron-hole pair creation in the sensitive volume of the sensor as predicted
by Monte Carlo simulation is shown as orange line. Bottom: the ratio of the
signal recorded by a small area of the sensor in which the wire grid was
removed and by an adjacent area with the wire grid intact. In solid orange the
same ratio as predicted by Monte Carlo simulation.

We have determined the resolution of the sensor by imaging the shadow
projected by a single strand of tungsten wire,
$4\text{\,}\mathrm{\SIUnitSymbolMicro}\mathrm{m}$ in diameter placed directly
onto the sensor surface. The imaging was performed by acquiring 7096 frames
with a $4.9\text{\,}\mathrm{s}$ exposure, which is low enough to distinguish
individual positrons in the images. Positrons were identified in each of the
acquired images as instances of a $2\\!\times\\!2$ squares of pixels
containing at least one whose brightness exceeded the background noise, and
surrounded by a 1-pixel thick frame containing no pixels excited beyond the
background noise; the positron was then assigned to the brightest pixel among
the four (see Fig. 4c for a visual representation of the criteria). We present
in Fig. 6 the result of the reconstruction in which we determined the OTF
width by projecting a portion of the wire shadow and fitting it with an error
function Reichenbach_Resolution  with standard deviation
$0.97\text{\,}\mathrm{\SIUnitSymbolMicro}\mathrm{m}$.

Figure 6: Shadow of a $4\text{\,}\mathrm{\SIUnitSymbolMicro}\mathrm{m}$
tungsten wire laid directly onto the sensor surface. The image was produced by
tallying together 7096 images shot with a $4.9\text{\,}\mathrm{s}$ exposure;
positrons were identified and their position assigned to one of the image
pixels. The gray level in the image indicates the amount of positrons
collected within each specific pixel. On the right, fit of the projection of
the wire shadow with the error function indicating an OTF with a standard
deviation of $0.97\text{\,}\mathrm{\SIUnitSymbolMicro}\mathrm{m}$

###  2.3 Durability of the sensor

In our most extensive testing we have implanted a total of $1.2\cdot 10^{10}$
positrons into one of our detectors; as we did so we observed two ways in
which damage to the sensor did manifest. Around $12$ pixels per million
behaved as dead pixels and always read out at the upper limit of their dynamic
range. An additional $0.28\%$ of the pixels manifest an increase of their dark
current; modest in most cases (less than 8% of the full dynamic range in 75%
of cases) but dramatic in a few instances. By comparing data recorded over the
course of 45 hours we observed a slight upwards trend in the dark current of
these few pixels, with typical rates in the order of $0.17\%$ of the dynamic
range per day. The slow rate at which the dark current increases and the
absence of abrupt changes in any pixel’s dark current indicates that these
pixels were most likely damaged during the sample preparation; furthermore,
that the dead pixels were most likely produced in a similar fashion, albeit
with a baseline shift severe enough to cause them to saturate at all times.
Within the 705 cases of pixels with an anomalous dark current that we have
analyzed, less than 10% displayed a dark current greater than one third of the
ADC dynamic range, and as such the anomaly can be in most cases corrected
algorithmically; this leaves about 300 pixels per million which are unusable
or barely usable. Due to their limited number, we do not expect this kind of
damage to be an issue for the vast majority of applications.

###  2.4 Monte Carlo simulation

The physical mechanism allowing the direct detection of positrons impinging on
a CMOS sensor is the creation of electron-hole pairs inside the depletion zone
of the photodiodes built into the device Hanoka_EBIC ; this creation occurs
through a combination of bremsstrahlung and elastic scattering as the
positrons are stopped by the material. We have adapted the code base from a
previous work NCPImplantation  and employed the available information on the
geometric structure of the Sony IMX219 sensor ReverseEngineering  to simulate
the generation of electron-hole pairs in the sensitive portion of the image
sensor. The core of our code simulates the process of positron scattering in
silicon as a series of discrete interactions. Silicon is the most abundant
element in a CMOS sensor and a suitable stand-in for the other materials that
we expect to be present (aluminum, silicon, silicon oxide and silicon nitride)
on account of having a similar density. We compute the expected amount of
electron-hole pairs created in each discrete interaction as proportional to
the energy lost by the positron, weighted depending on the positron energy
according to the data presented by Funsten et al.Funsten1 . The positron
detection efficiency is determined as proportional to the expected amount of
electron-hole pairs generated in the sensitive region. Placing the sensitive
region at the depths presented by Matthews et al. ReverseEngineering
($0.57-3$\text{\,}\mathrm{\SIUnitSymbolMicro}\mathrm{m}$$) yields a detector
efficiency in excellent agreement with the experimental data (see Fig. 5).

We used the same simulation process to predict the signal ratio between areas
covered by the wire grid and areas not covered by the wire grid, where the
sensitive volume lays $250\text{\,}\mathrm{n}\mathrm{m}$ below the surface.
The resulting curve resembles the experimental data, albeit with a shift in
energy of about $800\text{\,}\mathrm{e}\mathrm{V}$ which cannot be resolved by
modifying the depth of the sensitive volume. There are several possible causes
for this shift. Firstly, in our simulation we are using silicon as a stand-in
for every material present in the sensor: this approximation works best when
the sensitive area is deeper and coated by different layers, as the deviations
from the silicon model tend to average out. After removing the wire grid only
the anti-reflection layer remains, which makes the simulation result more
sensitive to its modeling. In addition, it is known that energy deposited in
layers adjacent to a p-n junction can result in the creation of electron-hole
pairs in the junction itself Funsten1 ; we can expect this phenomenon to
become more prominent in the case of a shallower implantation as it causes the
density of deposited energy to increase.

As positrons enter the material and lose energy they also spread transversely
and produce a signal that can be picked up by other nearby pixels. We have
determined via Monte Carlo sampling that the lateral spread in the active
region previously quoted is a distribution with
$340\text{\,}\mathrm{n}\mathrm{m}$ standard deviation. The discretization to
pixel coordinates intrinsically introduces an OTF having
$323\text{\,}\mathrm{n}\mathrm{m}$ width. Combining these two yields an OTF
with a standard deviation of $470\text{\,}\mathrm{n}\mathrm{m}$, which
indicates that the resolution found in subsection 2.2 is likely overestimating
the sensor’s actual OTF by about a factor of $2$. On top of that,
reconstruction algorithms capable of circumventing the pixel discretization
might have the potential of reaching the resolution of the best positron
detectors ever built Anzi_2020 .

##  3 Discussion

We have established that modern commercial CMOS sensors achieve, with minimal
modifications, exceptional detection performance of low-energy positron beams:
they can provide high readout frequency, high resolution and two-dimensional
imaging. The imaging can be achieved via conversion of the positrons to
visible light in a phosphor coating layer applied onto the sensor; the
resulting light is intense enough to be detected without amplification even
for weak, radioisotope-based beams. Alternatively, detection can be achieved
by implanting positrons with sufficient kinetic energy directly into the
sensor.

As an outlook, the use of CMOS technology could usher in the development of a
new class of custom detectors that are very precise, sensitive and affordable.
Furthermore, they could be designed to integrate the readout electronics
within the silicon die, reducing the amount of additional vacuum-installed
components and thus lowering the level of contamination during operations in
ultra-high vacuum. In the development of bespoke positron image sensors,
several features could be fine-tuned to further improve the performance in
specific applications. Firstly, increasing the dimensions of the image sensor
can ease its use as a device for the detection and optimization of positron
beams. Secondly, high-precision temporal tagging can be achieved with an
integrated front-end that transmits only the locations of individual
positrons, rather than the entire image, following designs that are common for
larger particle detectors NIMFACT . Thirdly, a decrease in pixel size would
increase the precision of position measurements. The minimum size of pixels is
constrained by the need of including support electronics and electrical
connections in the die; this can be circumvented by employing pixels with a
high aspect ratio when exceptional measurement precision is required in a
specific direction at the cost of lowering the resolution in the orthogonal.
Finally, bringing the active area closer to the surface, by reducing or
omitting the passivation layer, would allow the detection of positrons at
considerably lower energies and further compress the OTF of the sensor. This
last improvement might prove challenging as handling a sensor with a shallow
or no passivation layer necessitates particular care due to its sensitivity to
atmospheric oxidants.

Positron detection via CMOS image sensors is a valuable technique that has the
potential to impact a wide range of applications, from beam diagnostics,
aiding the optimization of beam position, size and shape, to the enabling of
fundamental physics experiments that are based upon the extremely accurate
determination of positron positions. In particular, the precise readout of the
positron impacting coordinates is crucial for high-precision diffractometry,
which could allow the measurement of free-fall of antimatter Mills_FreeFall ,
or interferometric measurements, to test the quantum behaviour of positrons
Sala_Interferometry . As a last example, this technology could enable the
miniaturization and integration of transmission positron microscopes, as
firstly demonstrated by Mills et al. Mills_Transmission , into experimental
setups not specifically designed for this purpose.

##  4 Methods

###  4.1 Sample preparation

To allow the Sony IMX219 image sensor to work with positrons, its color filter
and microlens array need to be removed. Prior to the removal procedure we
prepared the sensors by sealing the bonding wires connecting the silicon die
to the supporting PCB: we encased them in a protective layer of two component
epoxy (UHU Plus Endfest 300) to shield them against accidental acid spills or
mechanical impacts. We then weakened the polymer layers by repeatedly
dispensing small amounts of fuming nitric acid onto the sensor surface with a
pipette and subsequently rinsing the device with deionized water and isopropyl
alcohol. After repeatedly exposing the sensor to the acid, we mechanically
removed the weakened layers by carefully scraping the surface using a custom-
made tool, consisting of an aluminum scalpel with a flat tip,
$3\text{\,}\mathrm{m}\mathrm{m}$ in width, sharpened at a $25^{\circ}$ angle.
After the scraping, we rinsed the sensor once again with isopropyl alcohol and
tested it to verify that its imaging capabilities were not damaged during the
procedure.

At this point, the sensor can either be used as is – exposing the bare silicon
structure to the particle beam – or be coated by a thin layer of high-
efficiency phosphor, thus enabling the detection of very low energy positron
beams. We employed silver-doped zinc sulfide, denoted as ZnS:Ag (EJ-600) as
our phosphor of choice. To obtain a uniform coating of the sensor, we
suspended the powdered phosphor, $8\text{\,}\mathrm{\SIUnitSymbolMicro m}$ in
nominal particle size, in ethanol and then drop-wise deposited the suspension
onto the sensor using a pipette. After the solvent has evaporated, the
phosphor particles form an even coating of constant thickness on the sensor.
We assessed the thickness of the coating by means of depth-of-focus
measurements with an optical microscope. We then varied the amount and
concentration of suspension used until we obtained a coating with a thickness
of $70\text{\,}\mathrm{\SIUnitSymbolMicro m}$, chosen to mirror the thickness
employed in literature for this type of phosphor Stenson_Luminescence .

###  4.2 Readout electronics frontend

The sensor readout system consists primarily of a single-board computer (SBC,
Raspberry 3B+) installed in the vacuum chamber. The SBC is powered via two HV
feedthroughs which provide the acceleration bias voltage, which is connected
to the SBC ground plane, and a high current $5\text{\,}\mathrm{V}$ rail on top
of the bias voltage which is used to power the SBC. The camera is installed
onto a small daughter board and powered through the dedicated zero insertion
force (ZIF) connector of the SBC. Data is transmitted to and from the SBC
through an ad-hoc WiFi bridge.

All of the electronics installed in vacuum were encased in a
$1.5\text{\,}\mathrm{m}\mathrm{m}$ thick nonsealed copper shell which serves
both as Faraday cage to capture potential arcs and as pathway to transfer heat
to the passthroughs. We employed passthroughs with a copper core
$10\text{\,}\mathrm{m}\mathrm{m}$ in diameter so that they could serve as the
main heat transfer from the SBC to the environment. An additional copper brace
was installed contacting the surface of the CPU with the copper casing to aid
heat transfer from the system. Active air cooling had to be applied to the
flange hosting the HV passthroughs and the $5\text{\,}\mathrm{V}$ power supply
to allow continuous operation of the board and sensor below $47^{\circ}$C.

The number of electronic components in vacuum was minimized and as many
components as possible were removed from the SBC, including all of the
connectors with the exception of the camera-dedicated ZIF. No electronic
component containing liquids was installed in vacuum. Prior to the
installation in vacuum all electronics were repeatedly washed with a
cyclohexane-based cleaning agent (Electrolube Fluxclene FLU400DB) and rinsed
with isopropyl alcohol before the evaporation of the cleaning agent to ensure
the removal of any flux residuals. The resulting assembly was able to be kept
at a pressure of $2\cdot
10^{-7}$\text{\,}\mathrm{m}\mathrm{b}\mathrm{a}\mathrm{r}$$ by the operation
of a turbomolecular pump (Leybold TurboVac 300).

During the measurements, the sensitivity of the CMOS sensor was adjusted based
on the intensity of the positron flux to minimize pile-ups, keep the signal
within the dynamic range and maximize the S/N ratio. We controlled the
sensitivity of the CMOS by manipulating the sensor gain and exposure time
which are determined by the values written in a variety of control registers.
When needed we have allowed the values of these registers to be set outside of
the manufacturer’s specifications BergholdThesis .

As the sensor sensitivity is proportional to the product of gain and exposure
time, multiple configurations can result in the same sensitivity. We
prioritized configurations that avoid using extreme gain or exposure values as
we observed them to lead to increased fixed-pattern noise BergholdThesis ;
then determined the optimal configuration by dynamically adjusting the sensor
parameters during the course of our measurements while monitoring the quality
of the recorded images. We provide a table in the supplementary materials,
listing all of the register configurations used to acquire the data employed
in this work.

###  4.3 Beam fitting

Total and coincidence particle counts from the HPGe detectors allow us to
measure the total positron flux impinging on the target. To compute from this
the positron flux impinging on the detector we need to first determine the
beam shape and position relative to the detector surface, this is due to the
fact that the beam is typically not entirely contained inside the sensitive
area of the sensor. To this end we model the beam profile with a two-
dimensional Gaussian distribution which we write as

$\displaystyle
f_{\xi}(x,y)=A\cdot\exp\\!\left[\frac{\vec{v}^{\,t}\cdot\Sigma\cdot\vec{v}}{2\,(S_{xx}S_{yy}-S_{xy}^{2})}\right]\text{,}$
(1)

where

$\displaystyle\vec{v}$ $\displaystyle=\begin{bmatrix}x-C_{x}\\\
y-C_{y}\end{bmatrix}\text{,}~{}~{}~{}~{}\Sigma=\begin{bmatrix}S_{xx}&S_{xy}\\\
S_{xy}&S_{yy}\end{bmatrix}\text{,}$ $\displaystyle\text{and}~{}~{}~{}~{}\xi$
$\displaystyle=(A,C_{x},C_{y},S_{xx},S_{xy},S_{yy}).$

We fit the beam by performing a least squares minimization combined with
iterative reweighting (IRLS) IRLS  and graduated optimization
GraduatedOptimization . The use of IRLS reduces the likelihood of the
minimization to be confounded by dead pixels or bright spots created by
Compton processes, while graduated optimization prevents the fit from
converging to a local minimum. We start the fit by subtracting the fixed-
pattern noise, which is determined by acquiring a frame with the same setting
used in the measurement but no positron beam.

The IRLS fit is performed via minimization for $k\in\\{0,1,2\\}$ of

$\chi^{2}(\xi_{k})=\sum_{x,y}\frac{[f_{\xi_{k}}(x,y)-I(x,y)]^{2}}{w_{k}(x,y)}~{}\text{,}$
(2)

where $I(x,y)$ is the intensity of the measured image at the coordinates
$(x,y)$ and $w_{k}(x,y)$ is recursively defined as

$\displaystyle w_{0}(x,y)$ $\displaystyle=1~{}\text{,}$ $\displaystyle
w_{k+1}(x,y)$ $\displaystyle=\min(\delta,\lvert
f_{\xi_{k}}(x,y)-I(x,y)\rvert)~{}\text{,}$ (3)

where $\delta$ is set to the value of an ADC unit. For each value of $k$ the
minimization over the six free parameters $\xi$ is done by performing six
iterations of the Newton method, with the gradient and Hessian matrix being
computed analytically. The output of the IRLS fit is the value $\xi_{2}$.

Graduated optimization is used to fit each image, whereby Gaussian blurring is
used to make the function to be optimized convex. The threefold IRLS
minimization is repeated a total of $\left\lfloor\log_{4}(W))\right\rfloor$
times, where $W$ is the width of the image in pixels. During the last
iteration the original image is fitted; during the previous iterations a
Gaussian blur with radius equal to $4^{i-1}$ pixels is applied to the image
before the fit, with $i$ being the number of iterations left in the procedure.
At each step the result of the previous fit is used to initialize the next
one, which decreases the probability of the fit converging to a local minimum.
The procedure here described yields a function whose residuals, with reference
to our experimental data, are observed to follow for the most part a normal
distribution, with the dead pixels as outliers. The residual image has a
uniform distribution both in the real and in the frequency domain and no
distinguishable patterns, which brings confidence in the correctness of the
fit model and technique.

## Acknowledgments

We would like to thank Dr. Davide Orsucci for insightful discussions and for
reviewing the preliminary drafts of this paper.

## References

  *   * (1) Mills Jr, A.P.: Surface analysis and atomic physics with slow positron beams. Science 218(4570), 335–340 (1982). https://doi.org/10.1126/science.218.4570.335
  * (2) Schultz, P.J., Lynn, K.G.: Interaction of positron beams with surfaces, thin films, and interfaces. Reviews of Modern Physics 60(3), 701 (1988). https://doi.org/10.1103/RevModPhys.60.701
  * (3) Dupasquier, A., Ottaviani, G.: Defect profiling by positron beams and other techniques. In: Positron Spectroscopy of Solids, pp. 581–657. IOS Press, Amsterdam (1995). https://doi.org/10.3254/978-1-61499-211-0-581
  * (4) Siegel, R.: Positron annihilation spectroscopy. Annual Review of Materials Science 10(1), 393–425 (1980). https://doi.org/10.1146/annurev.ms.10.080180.002141
  * (5) Asoka-Kumar, P., Alatalo, M., Ghosh, V., Kruseman, A., Nielsen, B., Lynn, K.: Increased elemental specificity of positron annihilation spectra. Physical Review Letters 77(10), 2097 (1996). https://doi.org/10.1103/physrevlett.77.2097
  * (6) Fukaya, Y., Kawasuso, A., Ichimiya, A., Hyodo, T.: Total-reflection high-energy positron diffraction (trhepd) for structure determination of the topmost and immediate sub-surface atomic layers. Journal of Physics D: Applied Physics 52(1), 013002 (2018). https://doi.org/10.1088/1361-6463/aadf14
  * (7) Lock, D., Crisp, V., West, R.: Positron annihilation and Fermi surface studies: a new approach. Journal of Physics F: Metal Physics 3(3), 561 (1973). https://doi.org/10.1088/0305-4608/3/3/014
  * (8) Oshima, N., Suzuki, R., Ohdaira, T., Kinomura, A., Narumi, T., Uedono, A., Fujinami, M.: Development of positron microbeam in AIST. In: Materials Science Forum, vol. 607, pp. 238–242 (2009). https://doi.org/10.4028/www.scientific.net/MSF.607.238. Trans Tech Publ
  * (9) Mitteneder, J., Dickmann, M., Kögel, G., Egger, W., Dollinger, G.: Recent developments of the scanning positron microscope SPM for depth-and position-resolved positron lifetime measurement. In: AIP Conference Proceedings, vol. 2182, p. 040002 (2019). https://doi.org/10.1063/1.5135834. AIP Publishing LLC
  * (10) Gigl, T., Beddrich, L., Dickmann, M., Rienäcker, B., Thalmayr, M., Vohburger, S., Hugenschmidt, C.: Defect imaging and detection of precipitates using a new scanning positron microbeam. New Journal of Physics 19(12), 123007 (2017). https://doi.org/10.1088/1367-2630/aa915b
  * (11) Mills Jr, A., Leventhal, M.: Can we measure the gravitational free fall of cold Rydberg state positronium? Nuclear Instruments and Methods in Physics Research Section B: Beam Interactions with Materials and Atoms 192(1-2), 102–106 (2002). https://doi.org/10.1016/S0168-583X(02)00789-9
  * (12) Sala, S., Ariga, A., Ereditato, A., Ferragut, R., Giammarchi, M., Leone, M., Pistillo, C., Scampoli, P.: First demonstration of antimatter wave interferometry. Science advances 5(5), 7610 (2019). https://doi.org/10.1126/sciadv.aav7610
  * (13) Hugenschmidt, C., Kögel, G., Repper, R., Schreckenbach, K., Sperr, P., Triftshäuser, W.: First platinum moderated positron beam based on neutron capture. Nuclear Instruments and Methods in Physics Research Section B: Beam Interactions with Materials and Atoms 198(3), 220–229 (2002). https://doi.org/10.1016/S0168-583X(02)01527-6
  * (14) Ladislas Wiza, J.: Microchannel plate detectors. Nuclear Instruments and Methods 162(1), 587–601 (1979). https://doi.org/10.1016/0029-554X(79)90734-1
  * (15) Tremsin, A.S., Vallerga, J.V., Siegmund, O.H.W.: Overview of spatial and timing resolution of event counting detectors with microchannel plates. Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment 949, 162768 (2020). https://doi.org/10.1016/j.nima.2019.162768
  * (16) Vinelli, G., Ferragut, R., Giammarchi, M., Maero, G., Romé, M., Toso, V.: Real-time monitoring of a positron beam using a microchannel plate in single-particle mode. Journal of Instrumentation 15(11), 11030 (2020). https://doi.org/10.1088/1748-0221/15/11/P11030
  * (17) Stenson, E., Hergenhahn, U., Stoneking, M., Pedersen, T.S.: Positron-induced luminescence. Physical Review Letters 120(14), 147401 (2018). https://doi.org/10.1103/PhysRevLett.120.147401
  * (18) Boukhayma, A.: Low-Noise CMOS Image Sensors, pp. 13–34. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-68774-2_2. https://doi.org/10.1007/978-3-319-68774-2_2
  * (19) Gouveia, L.C.P., Choubey, B.: Advances on CMOS image sensors. Sensor review 36(3), 231–239 (2016). https://doi.org/10.1108/SR-11-2015-0189
  * (20) Hanoka, J., Bell, R.: Electron-beam-induced currents in semiconductors. Annual review of materials science 11(1), 353–380 (1981). https://doi.org/10.1146/annurev.ms.11.080181.002033
  * (21) Mecklenburg, M., Hubbard, W.A., Lodico, J.J., Regan, B.: Electron beam-induced current imaging with two-angstrom resolution. Ultramicroscopy 207, 112852 (2019). https://doi.org/10.1016/j.ultramic.2019.112852
  * (22) Hugenschmidt, C., Kögel, G., Repper, R., Schreckenbach, K., Sperr, P., Straßer, B., Triftshäuser, W.: The neutron induced positron source at Munich – NEPOMUC. Nuclear Instruments and Methods in Physics Research Section B: Beam Interactions with Materials and Atoms 221, 160–164 (2004). https://doi.org/10.1016/j.nimb.2004.03.048. Proceedings of the XII International Workshop on Positron and Positronium Physics
  * (23) Mathes, L., et al.: Low-energy positron beam for coincidence doppler-broadening spectroscopy of near-surface defects. Nuclear Instruments and Methods in Physics Research Section B: Beam Interactions with Materials and Atoms (in preparation) (2023)
  * (24) Matthews, R., Falkner, N., Sorell, M.: Reverse engineering the Raspberry Pi Camera v2: A study of pixel non-uniformity using a scanning electron microscope. Forensic Science International: Digital Investigation 32, 200900 (2020). https://doi.org/10.1016/j.fsidi.2019.200900
  * (25) Reichenbach, S.E., Park, S.K., Narayanswamy, R.: Characterizing digital image acquisition devices. Optical Engineering 30(2), 170–177 (1991). https://doi.org/10.1117/12.55783
  * (26) Guatieri, F., Mariazzi, S., Brusa, R.S.: Monte Carlo simulation of the implantation profile of e+ in nanochanneled silicon. Eur. Phys. J. D 72(11), 198 (2018). https://doi.org/10.1140/epjd/e2018-90344-y
  * (27) Funsten, H.O., Suszcynsky, D.M., Ritzau, S.M., Korde, R.: Response of 100% internal quantum efficiency silicon photodiodes to 200 eV-40 keV electrons. IEEE Transactions on Nuclear Science 44(6), 2561–2565 (1997). https://doi.org/10.1109/23.650863
  * (28) Anzi, L., Ariga, A., Ereditato, A., Ferragut, R., Giammarchi, M., Maero, G., Pistillo, C., Romé, M., Scampoli, P., Toso, V.: Sensitivity of emulsion detectors to low energy positrons. Journal of Instrumentation 15(03), 03027 (2020). https://doi.org/10.1088/1748-0221/15/03/P03027
  * (29) Amsler, C., Antonello, M., Belov, A., Bonomi, G., Brusa, R.S., Caccia, M., Camper, A., Caravita, R., Castelli, F., Comparat, D., Consolati, G., Demetrio, A., Di Noto, L., Doser, M., Ekman, P.A., Fanì, M., Ferragut, R., Gerber, S., Giammarchi, M., Gligorova, A., Guatieri, F., Hackstock, P., Haider, D., Haider, S., Hinterberger, A., Kellerbauer, A., Khalidova, O., Krasnický, D., Lagomarsino, V., Malbrunot, C., Mariazzi, S., Matveev, V., Müller, S.R., Nebbia, G., Nedelec, P., Nowak, L., Oberthaler, M., Oswald, E., Pagano, D., Penasa, L., Petracek, V., Prelz, F., Prevedelli, M., Rienaecker, B., Robert, J., Røhne, O.M., Rotondi, A., Sandaker, H., Santoro, R., Storey, J., Testera, G., Tietje, I.C., Toso, V., Wolz, T., Wuethrich, J., Yzombard, P., Zimmer, C., Zurlo, N.: A cryogenic tracking detector for antihydrogen detection in the AEgIS experiment. Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment 960, 163637 (2020). https://doi.org/10.1016/j.nima.2020.163637
  * (30) Mills, A.P., Wilson, R.J.: Transmission of 1 - 6-keV positrons through thin metal films. Phys. Rev. A 26, 490–500 (1982). https://doi.org/10.1103/PhysRevA.26.490
  * (31) Berghold, M.: Direct imaging of high-intensity positron beams with CMOS sensors. Bachelor’s thesis, Technische Universität München, Garching bei München (2022)
  * (32) Holland, P.W., Welsch, R.E.: Robust regression using iteratively reweighted least-squares. Communications in Statistics - Theory and Methods 6(9), 813–827 (1977) https://doi.org/10.1080/03610927708827533. https://doi.org/10.1080/03610927708827533
  * (33) Blake, A., Zisserman, A.: The graduated non-convexity algorithm. In: Visual Reconstruction. The MIT Press, Cambridge (1987). https://doi.org/10.7551/mitpress/7132.003.0009. https://doi.org/10.7551/mitpress/7132.003.0009


# NeuralFastLAS: Fast Logic-Based Learning from Raw Data

Theo Charalambous  Yaniv Aspis  Alessandra Russo Imperial College London
{theo.charalambous18, yaniv.aspis17<EMAIL_ADDRESS>
###### Abstract

Symbolic rule learners generate interpretable solutions, however they require
the input to be encoded symbolically. Neuro-symbolic approaches overcome this
issue by mapping raw data to latent symbolic concepts using a neural network.
Training the neural and symbolic components jointly is difficult, due to slow
and unstable learning, hence many existing systems rely on hand-engineered
rules to train the network. We introduce NeuralFastLAS, a scalable and fast
end-to-end approach that trains a neural network jointly with a symbolic
learner. For a given task, NeuralFastLAS computes a relevant set of rules,
proved to contain an optimal symbolic solution, trains a neural network using
these rules, and finally finds an optimal symbolic solution to the task while
taking network predictions into account. A key novelty of our approach is
learning a posterior distribution on rules while training the neural network
to improve stability during training. We provide theoretical results for a
sufficient condition on network training to guarantee correctness of the final
solution. Experimental results demonstrate that NeuralFastLAS is able to
achieve state-of-the-art accuracy in arithmetic and logical tasks, with a
training time that is up to two orders of magnitude faster than other jointly
trained neuro-symbolic methods.

##  1 Introduction

Inductive Logic Programming (ILP) Systems Cropper and Muggleton (2016); Law et
al. (2015) induce a set of first-order logical rules that can be used to
explain observations. The solutions generated by ILP systems are naturally
interpretable by humans, generalizable, and require very little data. However,
ILP systems are limited to only learning from symbolic inputs. In many
settings, data is instead presented in a raw form, such as a set of images or
natural text. To overcome this issue, neuro-symbolic methods have been
proposed in recent years. A promising approach involves separating the system
into two different components: a neural component, which is responsible for
mapping raw data to latent symbolic concepts, and a symbolic component which
reasons over these latent concepts and produces a final answer. However,
training the neural and symbolic components jointly is a difficult task. On
the one hand, when the neural component is untrained, the symbolic component
receives highly noisy input. On the other hand, the neural component does not
have a reliable training signal before the symbolic component can induce the
correct rules. For this reason, many neuro-symbolic systems use hand-
engineered rules to train the neural network Manhaeve et al. (2018); Yang et
al. (2020).

To our knowledge, three approaches have been proposed that jointly train a
neural network and use an ILP system to induce first-order rules. $Meta_{ABD}$
Dai and Muggleton (2021) builds on top of Meta-Interpretive Learning Muggleton
et al. (2015) and uses a process of abduction to derive the most likely rules
and labels for use in backpropagation. However, it cannot learn rules
involving default negation. NSIL uses ILASP Law et al. (2015) or FastLAS Law
et al. (2021) to learn answer set programs. At each iteration, it induces a
hypothesis and trains the neural network using NeurASP Yang et al. (2020). It
uses a process of exploration/exploitation of examples to improve learning.
However, its dependence on the repeated search for an optimal hypothesis
results in a slow training process and scalability issues. The Apperception
Engine Evans (2022) is another method that trains two components together,
however the perception component is a binary neural network whose weights can
be 0 or 1, hence it is unlikely to be able to scale to complex perception
tasks.

In this paper, we introduce NeuralFastLAS, a neuro-symbolic learning system
built on top of FastLAS. NeuralFastLAS receives examples in the form of raw
data inputs together with a final label. From these examples, the system
trains a neural network to recognise latent symbolic concepts from the raw
data and induces an answer set program that can explain the final label given
these latent concepts. Similarly to FastLAS, NeuralFastLAS first constructs an
opt-sufficient subset of the hypothesis space that is guaranteed to contain an
optimal hypothesis. Using this smaller set of rules, NeuralFastLAS trains a
neural network to recognise the latent concepts using a semantic loss function
Xu et al. (2018), greatly speeding up training. To help guide the training,
NeuralFastLAS uses a novel technique of learning a posterior distribution over
the rules in the opt-sufficient subset. Once the neural network is trained,
the final hypothesis is constructed by finding a set of rules of the shortest
length that maximise the prediction scores of the network over the raw data.

We prove theoretical results for the correctness of the opt-sufficient subset
produced by NeuralFastLAS and show a sufficient condition on the convergence
of the neural network to guarantee that the correct rules are learnt.
Furthermore, we evaluate NeuralFastLAS on arithmetic and logical tasks and
show that it consistently achieves state-of-the-art accuracy while having
training times that are orders of magnitude faster than other neuro-symbolic
systems that learn rules.

The paper is structured as follows. Section 2 provides background knowledge on
answer set programming and the FastLAS system for learning such programs.
Section 3 formalises the neuro-symbolic learning task that NeuralFastLAS
solves. Section 4 covers each stage of the NeuralFastLAS algorithm in detail.
Section 5 presents the results of a systematic evaluation of the
NeuralFastLAS. Section 6 concludes the paper.

##  2 Background

In this section we introduce the concepts needed throughout the paper. Let
$\mathtt{h}$, $\mathtt{b_{1},\ldots,b_{n}}$, $\mathtt{c_{1},\ldots,c_{m}}$ be
any atoms. A _normal rule_ $r$ has the form
$\mathtt{h\operatorname{\mathtt{:-}}b_{1},\ldots,b_{n},}$
${\operatorname{\;\mathtt{not}\;}c_{1},\ldots,\operatorname{\;\mathtt{not}\;}c_{m}}$,
where $\mathtt{h}$ is the head of the rule (head(r)),
$\mathtt{b_{1},\ldots,b_{n},\operatorname{\;\mathtt{not}\;}c_{1},\ldots,\operatorname{\;\mathtt{not}\;}c_{m}}$
is (collectively) the body of the rule (body(r)), and
“$\operatorname{\;\mathtt{not}\;}$” represents negation as failure. A rule
$r^{\prime}$ is said to be a subrule of $r$ (denoted $r^{\prime}\leq r$) if
$\operatorname{head}(r)=\operatorname{head}(r^{\prime})$ and
$\operatorname{body}(r^{\prime})\subseteq\operatorname{body}(r)$. $r^{\prime}$
is a strict subrule if $r^{\prime}\leq r$ and $r^{\prime}\neq r$. Constraints
are rules of the form
$\mathtt{\operatorname{\mathtt{:-}}b_{1},...,b_{n},c_{1},...,c_{m}}$, whereas
choice rules have the form
$\mathtt{l\\{h_{1},\ldots,h_{k}\\}u\operatorname{\mathtt{:-}}}$
$\mathtt{b_{1},\ldots,b_{n},\operatorname{\;\mathtt{not}\;}c_{1},\ldots,\operatorname{\;\mathtt{not}\;}c_{m}}$.
The head $\mathtt{l\\{h_{1}\ldots,h_{k}\\}u}$ of a choice rule is called
aggregate, with $\mathtt{l}$ and $\mathtt{u}$ as (positive) integers and
$\mathtt{h_{1},\ldots,h_{k}}$ as any atoms. An ASP program is a set of normal
rules, choice rules and constraints. The Herbrand Base of an ASP program
$\Pi$, denoted $HB_{\Pi}$, is the set of all ground (with no variables) atoms
formed using the predicates and constants that appear in $\Pi$. Subsets of
$HB_{\Pi}$ are called interpretations of $\Pi$. A ground (with no variables)
aggregate $\mathtt{l\\{h_{1},\ldots,h_{k}\\}u}$ is satisfied by an
interpretation $I$, if
$\mbox{$\mathtt{l}$}\leq|I\cap\\{\mbox{$\mathtt{h_{1}\ldots,h_{k}}$}\\}|\leq\mbox{$\mathtt{u}$}$.
The semantics of an ASP program $\Pi$ is defined with respect to the reduct of
$\Pi$. Specifically, given an interpretation $I$ of $\Pi$, the reduct of
$\Pi$, denoted $\Pi^{I}$, is constructed from the grounding of $\Pi$ in four
steps. The first two steps deal with the negation as failure
“$\operatorname{\;\mathtt{not}\;}$” by i) removing all ground rules in $\Pi$
whose bodies contain the negation of an atom in $I$ and ii) removing all the
negative literals from the remaining rules. The third step deals with the
constraints and choice rules whose head is not satisfied by $I$ by replacing
their respective (empty) head with $\bot$ (where $\bot\not\in HB_{\Pi}$). The
final step deals with the remaining choice rules $\mathtt{\\{h_{1},\ldots
h_{m}\\}\operatorname{\mathtt{:-}}b_{1},\ldots b_{n}}$ by replacing each of
them with the set of rules
$\mathtt{\\{h_{i}\operatorname{\mathtt{:-}}b_{1},\ldots b_{n}\mid h_{i}\in
I\cap\\{h_{1},\ldots h_{m}\\}\\}}$. Any interpretation $I\subseteq HB_{\Pi}$
is an answer set of $\Pi$ if it is the minimal model of the reduct $\Pi^{I}$.
We denote with $AS(\Pi)$ the set of answer sets of $\Pi$.

Since the NeuralFastLAS algorithm that we propose in this paper is built on
top of the FastLAS algorithm Law et al. (2020), we briefly describe its main
steps. FastLAS is a logic-based system for learning answer set programs
capable of solving observational predicate learning (OPL) tasks over large
search spaces. OPL tasks aim to learn concepts that are directly observable
from given examples, and their solutions are ASP programs, called hypotheses,
that define such concepts. As is common in ILP systems, FastLAS uses mode
declarations as language bias to define the search space (also called
hypothesis space) of a learning task. A mode bias $M$ specifies two sets,
$M_{h}$ and $M_{b}$, of a mode head and body declarations, respectively.
Informally, a mode declaration is an atom whose arguments are either
$\mathtt{var(t)}$ or $\mathtt{const(t)}$, where $\mathtt{t}$ is a constant
called a type. An atom is compatible with a mode declaration $m$ if it uses
the predicate of $m$ and replaces every argument $\mathtt{var(t)}$ in $m$ with
a variable of type $\mathtt{t}$, and every $\mathtt{const(t)}$ in $m$ with a
constant of type $\mathtt{t}$. Body declarations can be negated atoms using
negation as failure.

######  Definition 1 (Hypothesis space).

Let $M=\langle M_{h},M_{b}\rangle$ be a mode bias. The hypothesis space
$S_{M}=\\{r_{i}|i\geq 1\\}$ is the set of rules $r_{i}$ such that
head($r_{i}$) is compatible with a mode head declaration, and each literal in
body($r_{i}$) is compatible with a mode body declaration.

FastLAS learns ASP programs from a given set of examples, within the context
of a (possibly empty) background knowledge. Examples are context-dependent
partial interpretation (CDPI). A CDPI $e=\langle
e_{id},e_{pi},e_{ctx}\rangle$, where $e_{id}$ is the example identifier,
$e_{pi}$ is a partial interpretation composed of a pair of disjoint sets of
atoms $e_{pi}=\langle e^{inc},e^{exc}\rangle$ called the inclusions and
exclusions respectively, and $e_{ctx}$ is an ASP program consisting of normal
rules, called a context. A program $\Pi$ accepts a CDPI example $e$, if and
only if there is an answer set $A$ of $\Pi\cup e_{ctx}$ such that
$e^{inc}\subseteq A$ and $A\cap e^{exc}=\emptyset$. We now recall the
definition of a Learning from Answer Sets (LAS) task Law et al. (2020).

######  Definition 2 (LAS task).

A Learning from Answer Set (LAS) task is a tuple $T=\langle B,M,E\rangle$
where $B$ is an ASP program, called background knowledge, $E$ is a finite set
of CDPIs, and $M$ is a mode bias. For any hypothesis $H\subseteq S_{M}$:

  * •

For any $e\in E$, $H$ covers $e$ iff $B\cup H$ accepts $e$.

  * •

$\mathcal{S}_{len}(H)$ is the number of literals in $H$, written $|H|$.

  * •

$H$ is a solution of $T$ if $H$ covers all $e\in E$. $H$ is optimal if there
is no solution $H^{{}^{\prime}}$ such that
$\mathcal{S}_{len}(H^{{}^{\prime}})<\mathcal{S}_{len}(H)$.

FastLAS is restricted to solving non-recursive, OPL tasks. A task is non-
recursive if no predicate in $M_{h}$ occurs in $M_{b}$ or the body of any rule
in $B\cup e_{ctx}$ for any $e\in E$.

To compute an optimal solution for a given LAS task $T$, FastLAS algorithm
uses four main steps. Informally, in the first step it constructs a SAT-
sufficient space which is comprised of two sets $C^{+}(T)$ and $C^{-}(T)$; in
the second step, called generalisation, it constructs $G(T)$ as a set of rules
that generalise $C^{+}(T)$ without covering any rules in $C^{-}(T)$. It then
optimises $G(T)$, in its third step, into an OPT-sufficient hypothesis space.
The final solving step, uses the OPT-sufficient hypothesis space to compute an
optimal solution.

##  3 Neural-Symbolic Learning

Many neural-symbolic architectures Dai and Muggleton (2021); Yang et al.
(2020) consist of distinct perception and reasoning components. The perception
component maps the raw data to (latent) symbolic concepts while the reasoning
component finds a final label using symbolic background knowledge. To train
both components, a dataset $\mathcal{D}$ is available, composed of pairs
$(x,y)\in\mathcal{X}\times\mathcal{Y}$ where $\mathcal{X}$ is the set of all
possible raw inputs, $\mathcal{Y}$ the set of final labels, and the latent
symbolic concepts are unlabelled. We denote the space of latent symbolic
concepts as $\mathcal{Z}$.

Formally, the perception model is parameterised by $\theta$. For a given raw
data input, the perception model outputs a probability
$P_{\theta}(z|x)=P(z|\theta,x)$ for each $z\in\mathcal{Z}$. The symbolic
component consists of background knowledge $B$ and a hypothesis $H$, which are
used together to map the symbolic concepts in $z$ to the labels $y$. To
optimise both $\theta$ and $H$ jointly, we use the following objective
function Dai and Muggleton (2021):

$(H^{*},\theta^{*})=\operatorname*{argmax}_{H,\theta}\prod_{(x,y)\in\mathcal{D}}\sum_{z\in\mathcal{Z}}P(y,z|B,x,H,\theta)$
(1)

Note that this can be rewritten as

$P(y,z|B,x,H,\theta)=P(y|B,H,z)P_{\sigma^{*}}(H|B)P_{\theta}(z|x)$ (2)

where $P_{\sigma^{*}}$ is the Bayesian prior distribution on first-order logic
hypothesis Hocquette and Muggleton (2018). To solve for the objective function
above in the context of FastLAS, we propose the NeuralFastLAS algorithm.

###  3.1 NeuralFastLAS Learning Tasks

This section formulates the learning tasks used within the NeuralFastLAS
architecture. It differs from the learning tasks in FastLAS as the context of
an example is not symbolically given, but consists of raw data.

######  Definition 3.

A raw-data example is of the form $e=\langle e_{\text{id}},\langle
e_{\text{pi}}^{\text{inc}},e_{\text{pi}}^{\text{exc}}\rangle,e_{\text{raw}}\rangle$.
$e_{\text{id}}$ is the identifier for the example,
$e_{\text{pi}}^{\text{inc}}$ and $e_{\text{pi}}^{\text{exc}}$ are the
inclusion and exclusion set, respectively, and $e_{\text{raw}}$ is the set of
raw data for that example.

An example of raw data may be a set of images, the corresponding latent
symbolic labels may be object names or numbers that appear in the image. For
any data point $d=(x,y)\in\mathcal{D}$, we generate the example $e_{d}=\langle
d_{id},\langle\\{y\\},\mathcal{Y}\setminus\\{y\\}\rangle,x\rangle$ where
$d_{id}$ is any unique identifier.

######  Definition 4.

A NeuralFastLAS task is of the form $T=\langle
B,M,E,\mathcal{Z},\Theta\rangle$ where $B$ is the background knowledge in the
form of an ASP program, $M$ is the mode bias, $\mathcal{Z}$ is the latent
space and $E$ is a set of raw-data examples. $\Theta$ is the space of neural
network parameters such that $\theta\in\Theta$ maps $x\in\mathcal{X}$ to
$\mathcal{Z}$.

A solution for a NeuralFastLAS task is a pair $(H,\theta)$ where $H\subset
S_{M}$ and $\theta\in\Theta$ is the neural network’s parameters. An optimal
solution of the task is a solution of equation 1. As NeuralFastLAS is built on
top of the FastLAS algorithm, it inherits the restriction to non-recursive,
OPL tasks.

##  4 NeuralFastLAS Algorithm

This section presents the NeuralFastLAS algorithm. It is built on top of the
FastLAS system Law et al. (2021). There are six steps to the NeuralFastLAS
system: (1) Abduction; (2) Construction of the SAT-sufficient subset; (3)
Generalisation; (4) Optimisation; (5) Neural training; (6) Solving.

Steps (1) to (4) construct the opt-sufficient subset of the task, that is the
set of rules that cover at least one example for some valid combination of
latent labels, and does not violate any example. The opt-sufficient subset is
then used to train the neural network using the semantic loss function Xu et
al. (2018) in step (5). Finally, using predictions from the neural network, we
find the optimal solution with respect to Equation 2 in step (6).

###  4.1 Abduction

The abduction stage computes the set of valid network outputs for each $e\in
E$ while taking into account any constraints given by $B$. To do so, a
symbolic program $P_{\mathcal{Z}}$ is constructed whose answer sets correspond
to all possible neural network choices. $\mathcal{Z}$ is of the form
$\mathcal{Z}=\mathcal{Z}_{1}\times\mathcal{Z}_{2}\times...\times\mathcal{Z}_{n}$
where the pipeline takes $n$ raw data inputs per data point. For each
$\mathcal{Z}_{i}$, we add the choice rule

$\mathtt{1\\{nn(i,\mathcal{Z}_{i,1}),...,nn(i,\mathcal{Z}_{i,m})\\}1.}$ (3)

to $P_{\mathcal{Z}}$. The answer sets of $P_{\mathcal{Z}}$ correspond to every
combination of latent labels. The predicate nn/2 is a reserved name in
NeuralFastLAS. It maps a raw data identifier to the corresponding symbolic
label of the raw data. For example, if the first raw data input is an image of
a cat, then the final ASP program will contain the atom nn(1, cat).

The set of valid neural network outputs for each example corresponds to the
answer sets $AS(B\cup P_{\mathcal{Z}})$. We refer to each such answer set as a
possibility and denote $\text{poss}(e)=AS(B\cup P_{\mathcal{Z}})$. With this,
we can define coverage in the context of NeuralFastLAS:

######  Definition 5.

We say that a hypothesis $H$ covers a NeuralFastLAS example $e$ if there
exists a possibility $A\in AS(B\cup P_{\mathcal{Z}})$ such that $A\cup H$
accepts $e$.

The set of neural networks outputs that can be used by $H$ to cover an example
$e$ is denoted $\operatorname{cov}(H,e)$. Formally,
$\operatorname{cov}(H,e)=\\{A\cap\mathcal{Z}:A\in AS(B\cup
P_{\mathcal{Z}}),A\cup H\text{ accepts }e\\}$.

###  4.2 Computing the SAT-Sufficient Subset and Generalisation

After computing the symbolic possibilities, NeuralFastLAS produces a SAT-
sufficient space by first constructing the sets $C^{+}(T,p)$ and $C^{-}(T,p)$
of maximal rules that prove at least one literal in the inclusion or exclusion
sets of a possibility $p$, respectively. $C^{+}(T)=\cup_{e\in
E}\cup_{p\in\text{poss}(e)}C^{+}(T,p)$ is the set of all SAT-sufficient rules.
$C^{-}(T)$ is defined analogously.

The abduction stage of NeuralFastLAS can produce a large number of
possibilities. With many examples, the number of possibilities can make the
task computationally intensive. To explore the search space intelligently,
NeuralFastLAS prunes $S_{M}$ by taking into account constraints over the mode
bias. Two key constraints of NeuralFastLAS are:

  1. 1.

Symmetry of Predicate Arguments: If the arguments A and B are marked as
symmetric in the predicate h(A, B, C), then rules that differ only in the
order of A and B are considered the same and only appear once in the SAT-
sufficient subset.

  2. 2.

Capture and Release Arguments: Every argument in every literal is referred to
as either a “capture” argument (denoted with -) or a “release” argument
(denoted with +). Intuitively, a rule conforms to capture and release
conditions if: (1) For any body literal with a capture argument, the variable
in that argument must also be present in a release argument of another body
literal or the head literal. (2) For variables in the capture arguments in the
head literal, that variable must also be present as a release argument of a
body literal. (3) Every variable present in the release argument of a literal
must be unique. Consider $M_{h}=\\{f(var(t^{+}),var(t^{-})\\}$ and
$M_{b}=\\{g(var(t^{-}),var(t^{+})),h(var(t^{-}),var(t^{+}))\\}$, then the rule
$f(A,B)\operatorname{\mathtt{:-}}g(A,C),h(C,B)$ conforms to the capture and
release variables, whereas the rule
$f(A,B)\operatorname{\mathtt{:-}}g(A,C),h(D,C)$ does not as the release
arguments of $g$ and $h$ are not unique.

A formal description of symmetry of predicate arguments and capture and
release variables is given in the supplementary material.

The generalisation step is identical to that in the original FastLAS system.
Each rule from the SAT-sufficient subset is generalised and added to the new
set $G(T)$.

###  4.3 Optimisation

At this stage, we have the set of generalised rules $G(T)$. We proceed by
defining the following notion of neural optimality, which aims to find the
most relevant subrules of $G(T)$ that do not violate all of the possibilities
of any example. Note that in NeuralFastLAS, every example must be covered by
making an appropriate choice for the latent labels.

######  Definition 6 (Neural Optimisations).

Given a rule $r$, we define the optimisations of $r$, denoted
$\operatorname{neural\\_opt}(r)$, to be the set of rules $r^{\prime}$ that
satisfy the following conditions:

  1. 1.

$r^{\prime}$ is a subrule of $r$.

  2. 2.

There does not exist a rule $r^{\prime\prime}$ such that
$r^{\prime\prime}<r^{\prime}$ and $r^{\prime}$ and $r^{\prime\prime}$ cover
the exact same possibilities.

  3. 3.

There does not exist any example $e\in E$ such that for every
$p\in\text{poss}(e)$, $r^{\prime}$ is a subrule of a rule in $C^{-}(T,p)$.

  4. 4.

$r^{\prime}$ is a smallest such rule satisfying (1), (2) and (3).

The opt-sufficient subset is then defined as $S_{M}^{\text{opt}}$ where

$S_{M}^{\text{opt}}=\bigcup_{r\in G(T)}\operatorname{neural\\_opt}(r)$

Item 3 is a pruning criterion introduced in NeuralFastLAS. Intuitively, item 3
says that if a rule violates every possibility of an example, then it is
guaranteed to not be included in the final solution so we can prune it at the
optimisation stage.

###  4.4 Neural Training

The optimisation stage produces the opt-sufficient subset of the task $T$.
With this, we can train the neural network. The neural network training stage
of NeuralFastLAS consists of:

  1. 1.

Training the Perception Component: The raw data is fed into a neural network
which outputs probability vectors predicting the corresponding latent label
for each raw data input. During the gradient descent step, NeuralFastLAS
optimises the parameters to improve the accuracy of the network.

  2. 2.

Learning a Posterior Distribution on the Rules: NeuralFastLAS also uses an
extra parameter $\theta_{R}$ to represent a score for the rules in
$S_{M}^{\text{opt}}$. This is used to improve stability when training the
network.

The neural network has two heads: the first is the perception component, and
the second is the rule probability predictor. The output of the neural network
is $\theta_{R}$ concatenated with all of the $P_{\theta}(z_{i}|x_{i})$ for
$x_{i}\in e_{\text{raw}}$.

Input $x\in\mathcal{X}$ Neural Network Latent Predictions $P_{\theta}(z|x)$
$\vdots$ $p$ $P(S_{M}^{\text{opt}}|\theta_{R})$ $\theta_{R}$ Semantic Loss
Function $L^{s}(y,p)$ $\operatorname{AS}_{y}$ ASP Solver Label
$y\in\mathcal{Y}$ Figure 1: Schematic of the Neural Component of
NeuralFastLAS. Gray sections show where gradient descent steps occur. The
dashed line show how gradients are propagated. The two boxes denote the neural
component (left) and semantic component (right).

The semantic loss function is intended to capture how close a neural network’s
predictions are to satisfying some symbolic constraints. NeuralFastLAS uses
the semantic loss function to find the latent label predictions and rules in
$S_{M}^{\text{opt}}$ can be used to prove the downstream label and propagate
this information back to the neural network during gradient descent. To
compute the semantic loss for an example $e$, the answer set program
$P_{e}=B\cup P_{\mathcal{Z}}\cup
S_{M}^{\text{opt}}\cup\\{\mbox{$\mathtt{\operatorname{\mathtt{:-}}\operatorname{\;\mathtt{not}\;}y.}$}\\}\cup\mbox{$\mathtt{1\\{use(0..N)\\}1.}$}$
is constructed. Each rule $r_{i}\in S_{M}^{\text{opt}}$ is augmented with a
literal $\mathtt{use(i)}$ to indicate if it is used in an answer set when
proving the downstream label. This way, each answer set of $P_{e}$ corresponds
to a choice of the neural network labels and the rule that entails $y$.

######  Definition 7 (Semantic Loss in ASP).

Let $P_{e}$ be the program for which we are computing the semantic loss. For a
final label $y$, let $\operatorname{AS}_{y}$ denote the set of answer sets of
$P_{e}$ that contain $y$ and $X$ be the set of all possible ground
$\mathtt{nn}$ and $\mathtt{use}$ facts. We define the semantic loss as

$L^{s}(y,p)=-\log\sum_{A\in\operatorname{AS}_{y}}\
\prod_{\begin{subarray}{c}i\in\\{0,...,n\\}\\\ X_{i}\in A\cap
X\end{subarray}}p_{i}\prod_{\begin{subarray}{c}i\in\\{0,...,n\\}\\\ X_{i}\in
A^{c}\cap X\end{subarray}}(1-p_{i})$ (4)

where $p$ is a posterior probability vector given as output by the neural
network and $p_{i}$ denotes the predicted probability of atom $X_{i}$.

Previous symbolic reasoners Tsamoura et al. (2021) used the semantic loss
function with handwritten rules. NeuralFastLAS is different in that it learns
rules and the network is trained before the final hypothesis is found. This
introduces a new problem: during training, the many incorrect rules produce a
lot of noise in the loss computation. To compensate for this noisy signal, we
learn a probability distribution on the rules in $S_{M}^{\text{opt}}$. We do
this by introducing the parameter
$\theta_{R}\in\mathbb{R}^{\left|S_{M}^{\text{opt}}\right|}$ such that
$P(r_{i}|\theta_{R})=\operatorname{softmax}(\theta_{R})$ gives a probability
vector. Intuitively, we can see $P(r_{i}|\theta_{R})$ as a learnt probability
score that rule $r_{i}$ from $S_{M}^{\text{opt}}$ will cover a data point.

###  4.5 Solving

After the network has been trained, the solving stage constructs the program
$P_{\text{solve}}$ to compute an optimal hypothesis thus solving the symbolic
task. In NeuralFastLAS, the following prior is introduced

$P_{\sigma^{*}}(H|B)=(e-1)e^{-\lvert H\rvert}$ (5)

in order to perform a $\log$ transformation

$\displaystyle\operatorname*{argmax}_{H,\theta}P(y|B,H,z)P_{\sigma^{*}}(H|B)P_{\theta}(z|x)$
(6) $\displaystyle=\operatorname*{argmin}_{H,\theta}\left[\lvert E\rvert\lvert
H\rvert+\sum_{e\in E}\min_{z\in\operatorname{cov}(H,e)}-\log
P_{\theta}(z|e_{\text{raw}})\right]$ (7)

A solution $(H^{*},\theta^{*})$ is optimal if it satisfies Equation 7. There
are two distinct parts of the equation: the first is a value that scores the
hypothesis based on its length, the second is a value that scores the best
network choice $z$ out of all possible network choices that can be used to
cover $e$ with $H$.

The solving stage involves constructing a program $P_{\text{solve}}$ that
includes an ASP representation of equation 7 in terms of weak constraints
(details of the construction of $P_{\text{solve}}$ can be found in the
supplementary material). An optimal answer set of $P_{\text{solve}}$
corresponds to an optimal hypothesis with respect to a given $\theta$. We
denote this solution by $H=\operatorname{neural\\_solve}_{s}olve(T,\theta)$.

###  4.6 Optimality of NeuralFastLAS

We prove two key theoretical properties of the NeuralFastLAS algorithm. Let
$\theta^{*}$ represent the perfect neural network, then we define the notion
of a correct hypothesis $H^{*}$ to be an optimal hypothesis with respect to
$\theta^{*}$, $H^{*}=\operatorname{neural\\_solve}_{s}olve(T,\theta^{*})$.
First, we show that the opt-sufficient subset contains a correct hypothesis
for a task $T$. Second, we prove a sufficient condition on the convergence of
the neural network to guarantee that the solving stage returns a correct
hypothesis.

######  Theorem 1.

Let $T$ be a NeuralFastLAS task, then there exists a hypothesis $H\subseteq
S_{M}^{\text{opt}}$ in the opt-sufficient subset such that $(H,\theta^{*})$ is
a solution to $T$ and for any other hypothesis $H^{\prime}$ such that
$(H^{\prime},\theta^{*})$ is also a solution of $T$,
$\mathcal{S}_{len}(H)\leq\mathcal{S}_{len}(H^{\prime})$.

Since the solving stage follows the training of the neural network, the
results from the solving stage are dependent on the convergence of the
network. We prove that if the network trains “almost perfectly”, then
NeuralFastLAS returns a correct solution. It is important to emphasise that
the condition of the network training “almost perfectly” is a sufficient, but
not a necessary condition for returning a correct hypothesis. The neural
network can achieve suboptimal results but NeuralFastLAS may still find the
optimal hypothesis.

######  Definition 8 (Almost Perfectly Trained Networks).

A network with parameters $\theta$ is said to have trained almost perfectly
for a NeuralFastLAS task $T$ if the following bound is satisfied: Let $H^{*}$
be a correct hypothesis for $T$, then for any input $x$ with ground truth
latent label $z^{\text{gt}}$, we have

$P_{\theta}(z^{\text{gt}}|x)\geq\frac{e^{\lvert E\rvert\lvert
H^{*}\rvert}}{1+e^{\lvert E\rvert\lvert H^{*}\rvert}}$ (8)

The following theorem states that in the case of an almost perfectly trained
network, NeuralFastLAS always returns a correct solution.

######  Theorem 2.

Let $\theta$ be the parameters of an almost perfectly trained network, then
$H=\operatorname{neural\\_solve}_{s}olve(T,\theta)$ is a correct solution of
$T$.

##  5 Experiments

In this section, we discuss the empirical evaluation of NeuralFastLAS. We
evaluate NeuralFastLAS on tasks involving arithmetic computations and logical
reasoning111Code to be made available if the paper is accepted.. The
experiments conducted aim to answer the following questions: (1) Can
NeuralFastLAS learn a correct hypothesis and train the neural network jointly
with high accuracy? (2) How does NeuralFastLAS compare to fully neural and
other neuro-symbolic learning methods in terms of accuracy and training time?
(3) Does the posterior distribution learnt over the rules accurately reflect
the correct hypothesis? (4) Is NeuralFastLAS able to scale up with a larger
hypothesis space?

|  | End-to-End Accuracy
---|---|---
| Task Type | $a+b+c$ | $a\times b+c$ | $a\times b\times c$ | E9P
CNN |  | 40.76 $\pm$ 1.71 % | 52.16 $\pm$ 1.51 % | 68.68 $\pm$ 1.14 % | 95.13 $\pm$ 0.43 %
CBM |  | 90.66 $\pm$ 1.03 % | 93.52 $\pm$ 0.62 % | 95.65 $\pm$ 0.43 % | 97.69 $\pm$ 0.38 %
NALU |  | 0.03 $\pm$ 0.02 % | 0.00 $\pm$ 0.00% | 0.19 $\pm$ 0.09% | -
MetaABD | Small | 33.03 $\pm$ 25.98 % | 93.82 $\pm$ 0.62 % | 94.45 $\pm$ 0.44 % | -
NSIL | 8.02 $\pm$ 0.47 % | 86.44 $\pm$ 27.25 % | 96.22 $\pm$ 0.43 % | 79.93 $\pm$ 33.88 %
NeuralFastLAS | 96.33 $\pm$ 0.75 % | 96.48 $\pm$ 0.23 % | 96.81 $\pm$ 0.23 % | 97.72 $\pm$ 0.26 %
MetaABD | Large | ————————- Training Timeout (24 hours) ——— | -
NSIL | ————————- Training Timeout (24 hours) ———————————-
NeuralFastLAS | 96.14 $\pm$ 0.45 % | 96.47 $\pm$ 0.29 % | 96.62 $\pm$ 0.21 % | 97.39 $\pm$ 0.61 %
Table 1: Benchmark results for the four tasks. For each result, we show the
mean and standard deviation of the final accuracy on the test set. A dash
indicates that the experiment was not run for that model.

#### Experiments:

We answer these questions with four experiments: The first three tasks involve
learning arithmetic formulae, specifically the formulae $a+b+c$, $a\times
b\times c$ and $a\times b+c$, where $a$, $b$ and $c$ are given as MNIST images
representing single-digit integers. The final labels for each task appear in
the background knowledge and are in the ranges 0-27, 0-90 and 0-729,
respectively. These tasks are challenging due to the large number of neural
possibilities and the large hypothesis space; previous neuro-symbolic methods
that learn rules have only performed arithmetic experiments on two digits or
with only addition and multiplication in the search space.

| Small | Large
---|---|---
Arithmetic |  $+$, $\times$ |  $+$, $\times$, $-$, $\wedge$, $//$
E9P |  even, $+9$ |  even, $+1$, $+2$, …, $+9$
Table 2:  Search space for each category of task. $//$ represents integer
division.

The last task is Even9Plus (E9P) Cunnington et al. (2022). In this task, the
input is two images representing single-digit integers. If the first digit is
even, the result is the value of the second digit plus nine. Otherwise, the
result is the value of the second digit. This task requires learning a rule
with negation as failure.

To investigate how each method scales with the size of the search space, we
create two versions of each task. Table 2 shows the body predicates that form
the search space for each category of task.

#### Baselines:

We compare NeuralFastLAS against a variety of other methods. First, we compare
NeuralFastLAS to fully neural methods: a CNN baseline, Concept Bottleneck
Models (CBM) Koh et al. (2020) and Neural Arithmetic Logic Units (NALU) Trask
et al. (2018). The NALU is excluded from the E9P task as it is not designed
for logical reasoning. We also compare to two other neuro-symbolic learning
models that jointly train the neural and symbolic components:
$Meta_{ABD}$222We use the $Meta_{ABD}$ code available at
https://github.com/AbductiveLearning/Meta_Abd Dai and Muggleton (2021) and
NSIL333The code is not publicly available, but we were given access after
contacting the authors of Cunnington et al. (2022). Cunnington et al. (2022).
The same CNN network was used for the neural component of each of the neuro-
symbolic methods. Note that $Meta_{ABD}$ cannot learn negation as failure and
hence is unable to solve the E9P task.

#### Experiment Setup:

Each experiment was run 10 times. Hyper-parameter tuning was carried out for
each model using a held-out validation set. For the neuro-symbolic models, we
test against both forms of the mode bias. All experiments were performed on a
machine with the following specification: Ubuntu 22.04.1 LTS with an Intel®
Xeon® W-2145 CPU @ 3.70GHz, an NVIDIA GeForce RTX 2080 Ti GPU and 64GB of RAM.

###  5.1 Learning Arithmetic Formulae

|  | Training Time (minutes)
---|---|---
| Task Type | $a+b+c$ | $a\times b+c$ | $a\times b\times c$ | E9P
$Meta_{ABD}$ | Small | 245.4 | 31.7 | 52.5 | -
NSIL | 18.2 | 46.8 | 25.0 | 13.7
NeuralFastLAS | 0.8 | 1.7 | 7.2 | 0.3
$Meta_{ABD}$ | Large | – Training Timeout ( $>$ 24 hours) – | -
NSIL | – Training Timeout ( $>$ 24 hours) ———-
NeuralFastLAS | 5.9 | 10.5 | 27.6 | 3.3
Table 3: Mean training time of the neuro-symbolic systems

The results of this experiment are summarised in Table 1. First, we discuss
the answer to questions (1) and (2). NeuralFastLAS was able to correctly solve
all the given tasks and achieve high accuracy. It was able to do so even
though the neural network was not trained “almost perfectly”, showing that the
condition in Definition 8 is not a necessary one.

The fully neural models consistently perform worse than their neuro-symbolic
counterparts. This is likely because the fully neural models are unable to
utilise any background knowledge. In particular, NALU struggles to learn. RNNs
generally require many more training samples due to problems propagating
gradients Pascanu et al. (2012).

$Meta_{ABD}$ is less consistent than NeuralFastLAS in its learning, as seen in
the large standard deviation of accuracy. In the $a+b+c$ task, the minimum
accuracy $Meta_{ABD}$ achieves is 2.6% while the highest is 82.0%. On the
other hand, NeuralFastLAS consistently achieves over 95.0%. This demonstrates
that NeuralFastLAS is less sensitive to its initial conditions. $Meta_{ABD}$
utilises a process of abduction to train the neural network, choosing the
latent label with the highest probability. Hence, during the backpropagation
stage of each example, only the information of one label is used to train the
network. In the case that the wrong label is chosen, $Meta_{ABD}$ can get
stuck in a local minimum, which explains the sensitivity to initial
conditions. On the other hand, NeuralFastLAS’ use of the semantic loss allows
it to take into account every possible latent labelling during
backpropagation, avoiding this problem.

The $Meta_{ABD}$ tasks are formulated in such a way that the equations it can
learn are of the form $(a\circ_{1}b)\circ_{2}c$ where $\circ$ represents an
operator, so the search space is small. However, $Meta_{ABD}$ cannot solve the
large arithmetic task within a reasonable amount of time. This is because it
has to recompute the abduced labels every epoch, whereas NeuralFastLAS
computes the opt-sufficient subset once during the whole training pipeline.

NSIL fails to solve the $a+b+c$ task. This is because it must commit to a
hypothesis before training the neural network. The range of $a+b+c$ is a
subset of the ranges of many other formulae (e.g. $a\times a+b$) and so if the
wrong hypothesis is chosen in the first iteration, the network will train
incorrectly and become stuck in a local minimum.

| Latent Label Accuracy
---|---
| $a+b+c$ | $a\times b+c$ | $a\times b\times c$
$Meta_{ABD}$ | 54.0% | 97.3% | 97.4%
NSIL | 12.2% | 96.8% | 88.6%
NeuralFastLAS | 98.8% | 98.7% | 98.5%
Table 4:  The latent label accuracy for the neuro-symbolic systems

Table 4 shows the latent accuracy achieved by both methods \- despite the
training of the network being weakly supervised through the use of semantic
loss, NeuralFastLAS achieves an accuracy comparable to that of a supervised
network training on MNIST labels.

###  5.2 Learning with Negation-as-Failure

In the E9P task, which requires learning rules with negation-as-failure,
NeuralFastLAS outperforms NSIL. NSIL can become trapped in a local minimum if
it chooses the wrong hypothesis in the first iteration, but in most cases,
both method achieve similar a final accuracy. This similarity is due to both
utilising the semantic loss to train the network. NeuralFastLAS uses it
explicitly in its training stage, while NSIL uses it implicitly through its
use of NeurASP Yang et al. (2020).

However, NSIL fails to train within the time limit in the larger task. The
exploration/exploitation mechanism produces many noisy examples which creates
an incredibly complex optimisation task that is passed to FastLAS. The large
number of examples in combination with the large search space create a task
that FastLAS struggles to solve quickly.

###  5.3 The Posterior Rule Distribution

To answer question (3), we present an example of how the posterior
distribution of a NeuralFastLAS changes during the training of the network for
the $a\times b+c$ task. From Figure 2, we see that the algorithm successfully
learns the correct rule. The intuitive reason is that a ground truth rule
(that is, a rule used to generate the dataset) will be present in at least one
answer set when computing the answer sets for the semantic loss. In turn, the
backpropagation will favour this rule over rules that appear less frequently
in answer sets.

Figure 2: The learnt posterior distribution of the rules during the first
quarter of the first training epoch for the task learning $a\times b+c$. The
blue line represents the correct rule $a\times b+c$, the black lines represent
rules that are “close” (namely $a\times c+b$ and $b\times c+b$.)

By the end of this epoch, the answer sets that use the correct rule from the
opt-sufficient subset will contribute to most of the semantic loss’ value.
Hence the noise from the other answer sets is reduced and learning is much
more stable. NeuralFastLAS is able to fine-tune on the correct rule before
even reaching the solving stage, learning to better predicted probabilities to
use in solving.

###  5.4 Training Time

We turn our attention to question (4). Table 3 shows the training time for
each of the models. We look at the $a+b+c$ task as an example, NeuralFastLAS
is 22$\times$ faster than NSIL and 306$\times$ faster than $Meta_{ABD}$.
NeuralFastLAS performs each of its symbolic stages exactly once by utlising
the opt-sufficient subset for network training. On the other hand, NSIL must
perform the FastLAS solving stage once per epoch. Similarly, $Meta_{ABD}$ must
recompute the abduced labels for every epoch. Furthermore, $Meta_{ABD}$ needs
many epochs to learn in the $a+b+c$ task, as it struggles to converge, hence
the significantly higher training time. The results show that NeuralFastLAS
scales to larger search spaces without extreme penalties to training time.

##  6 Conclusion

This paper presents NeuralFastLAS, a neuro-symbolic approach that jointly
trains both components. NeuralFastLAS computes an opt-sufficient subset of
rules to train a neural network and then solves for the final hypothesis using
the network predictions. The experiments show that NeuralFastLAS achieves
state-of-the-art accuracy in various tasks while being orders of magnitude
faster than other neuro-symbolic methods. It is restricted to solving tasks
with non-recursive solutions, a limitation imposed by FastLAS. Future work
will be aimed at lifting this restriction to expand the scope of tasks that
can be solved.

## References

  * Cropper and Muggleton [2016] Andrew Cropper and Stephen H. Muggleton.  Metagol system.  https://github.com/metagol/metagol, 2016.
  * Cunnington et al. [2022] Daniel Cunnington, Mark Law, Jorge Lobo, and Alessandra Russo.  Inductive learning of complex knowledge from raw data.  arXiv, abs/2205.12735, 2022.
  * Dai and Muggleton [2021] Wang-Zhou Dai and Stephen Muggleton.  Abductive knowledge induction from raw data.  In Zhi-Hua Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pages 1845–1851. International Joint Conferences on Artificial Intelligence Organization, 8 2021.  Main Track.
  * Evans [2022] Richard Evans.  The apperception engine.  In Hyeongjoo Kim and Dieter Schönecker, editors, Kant and Artificial Intelligence, pages 39–104. De Gruyter, 2022.
  * Hocquette and Muggleton [2018] Céline Hocquette and Stephen Muggleton.  How much can experimental cost be reduced in active learning of agent strategies?  In Fabrizio Riguzzi, Elena Bellodi, and Riccardo Zese, editors, Inductive Logic Programming, pages 38–53, Cham, 2018. Springer International Publishing.
  * Koh et al. [2020] Pang Wei Koh, Thao Nguyen, Yew Siang Tang, Stephen Mussmann, Emma Pierson, Been Kim, and Percy Liang.  Concept bottleneck models.  In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 5338–5348. PMLR, 13–18 Jul 2020\.
  * Law et al. [2015] Mark Law, Alessandra Russo, and Krysia Broda.  The ILASP system for learning answer set programs.  www.ilasp.com, 2015.
  * Law et al. [2020] Mark Law, Alessandra Russo, Elisa Bertino, Krysia Broda, and Jorge Lobo.  Fastlas: Scalable inductive logic programming incorporating domain-specific optimisation criteria.  Proceedings of the AAAI Conference on Artificial Intelligence, 34(03):2877–2885, Apr. 2020.
  * Law et al. [2021] Mark Law, Alessandra Russo, Krysia Broda, and Elisa Bertino.  Scalable non-observational predicate learning in asp.  In Zhi-Hua Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pages 1936–1943. International Joint Conferences on Artificial Intelligence Organization, 8 2021.  Main Track.
  * Manhaeve et al. [2018] Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt.  Deepproblog: Neural probabilistic logic programming.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
  * Muggleton et al. [2015] Stephen H. Muggleton, Dianhuan Lin, and Alireza Tamaddoni-Nezhad.  Meta-interpretive learning of higher-order dyadic datalog: predicate invention revisited.  Machine Learning, 100(1):49–73, Jul 2015.
  * Pascanu et al. [2012] Razvan Pascanu, Tomás Mikolov, and Yoshua Bengio.  Understanding the exploding gradient problem.  CoRR, abs/1211.5063, 2012.
  * Trask et al. [2018] Andrew Trask, Felix Hill, Scott E Reed, Jack Rae, Chris Dyer, and Phil Blunsom.  Neural arithmetic logic units.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
  * Tsamoura et al. [2021] Efthymia Tsamoura, Timothy Hospedales, and Loizos Michael.  Neural-symbolic integration: A compositional perspective.  Proceedings of the AAAI Conference on Artificial Intelligence, 35(6):5051–5060, 2021.
  * Xu et al. [2018] Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Van den Broeck.  A semantic loss function for deep learning with symbolic knowledge.  In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 5502–5511. PMLR, 10–15 Jul 2018\.
  * Yang et al. [2020] Zhun Yang, Adam Ishay, and Joohyung Lee.  Neurasp: Embracing neural networks into answer set programming.  In Christian Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pages 1755–1762. International Joint Conferences on Artificial Intelligence Organization, 7 2020.  Main track.