[a]Jonathan Kriewald

# A combined explanation of the $B$-meson decay anomalies with a single vector
leptoquark

Chandan Hati  Jean Orloff  Ana M. Teixeira

###### Abstract

Motivated by the recent experimental progress on the $R_{D^{(\ast)}}$ and
$R_{K^{(\ast)}}$ anomalies in $B$-decays, we consider an extension of the
Standard Model by a single vector leptoquark field. We study how one can
achieve the required lepton flavour non-universality, starting from a priori
universal gauge couplings. While the unitary coupling flavour structure,
induced by the mass misalignment of quarks and leptons after $SU(2)_{L}$
breaking, does not allow to comply with stringent bounds from lepton flavour
violating processes, we find that effectively non-unitary couplings, due to
mixings with heavy vector-like fermions, hold the key to simultaneously
address the $R_{K^{(\ast)}}$ and $R_{D^{(\ast)}}$ anomalies. Furthermore, in
the near future, the expected progress in the sensitivity on charged lepton
flavour violating observables should allow to probe a large region of the
preferred parameter space in this class of vector leptoquark models.

##  1 Introduction and Motivation

Despite the discovery of the Higgs boson at the LHC, direct signals for new
particles have so far eluded experimental observation. However, in recent
years, indirect hints of new physics (NP) in flavour observables have begun to
manifest: in particular, precise measurements of semi-leptonic charged and
neutral current decays of $B$-mesons appear to show deviations from the SM
predictions. The ratios $\boldsymbol{R_{D^{(\ast)}}}=\mathrm{BR}(B\to
D^{(\ast)}\tau\nu)/\mathrm{BR}(B\to D^{(\ast)}\ell\nu)$ [1] and
$\boldsymbol{R_{K^{(\ast)}}}=\mathrm{BR}(B\to
K^{(\ast)}\mu\mu)/\mathrm{BR}(B\to K^{(\ast)}ee)$ [2, 3] are, up to
kinematical factors, expected to be unity in the SM. Both processes currently
exhibit a discrepancy of around $\sim 3\>\sigma$, hinting indirectly at the
presence of $\mathrm{TeV}$-scale NP with lepton flavour universality violating
(LFUV) interactions. Moreover, angular observables in $B\to K^{\ast}\mu\mu$
decays also exhibit a pattern of deviations with local discrepancies around
$3\>\sigma$ as well [4, 5]. Due to their ability to generate sizeable
contributions to semileptonic flavour changing neutral currents (FCNC) at
tree-level, leptoquark (LQ) models are currently under extensive scrutiny.

##  2 A vector leptoquark model

Notably, the $SU(2)_{L}$-singlet vector LQ $V_{1}$ (transforming as
$(\mathbf{3},\mathbf{1},2/3)$ under the SM gauge group) is among the “last
standing” viable single mediator explanations of both charged and neutral
current “$B$-meson decay anomalies”. The couplings of such a (gauge) field to
SM fermions can be cast as

$\mathcal{L}\supset\sum_{i,j,k=1}^{3}V_{1}^{\mu}\left(\bar{d}_{L}^{i}\,\gamma_{\mu}\,K_{L}^{ik}\,\ell_{L}^{k}+\bar{u}_{L}^{j}\,V_{ji}^{\dagger}\,\gamma_{\mu}\,K_{L}^{ik}\,U_{kj}^{\mathrm{P}}\,\nu_{L}^{j}\right)+\mathrm{H.c.}\>\text{,}$
(1)

in which $K_{L}^{ij}$ are the (effective) LQ couplings to left-handed SM
fermions111For simplicity, and due to the absence of strong hints in the data
suggesting otherwise, we restrict the couplings to be only left-handed and
real., $V$ denotes the Cabibbo-Kobayashi-Maskawa (CKM) quark mixing matrix and
$U^{\mathrm{P}}\equiv U_{L}^{\ell\dagger}U_{L}^{\nu}$ is the Pontecorvo-Maki-
Nakagawa-Sakata (PMNS) leptonic mixing matrix. The leading neutral and charged
current Wilson coefficients which generate sizeable contributions to $b\to
s\ell\ell$ and $b\to c\ell\nu$ can then be conveniently expressed as

$\displaystyle C^{ij;\ell\ell^{\prime}}_{9,10}$ $\displaystyle=$
$\displaystyle\mp\frac{\pi}{\sqrt{2}G_{F}\,\alpha_{\text{em}}\,V_{3j}\,V_{3i}^{\ast}\,m_{V_{1}}^{2}}\left(K_{L}^{i\ell^{\prime}}\,K_{L}^{j\ell\ast}\right)\,,$
$\displaystyle C_{jk,\ell i}^{V_{L}}$ $\displaystyle=$
$\displaystyle\frac{\sqrt{2}}{4\,G_{F}\,m_{V_{1}}^{2}}\,\frac{1}{V_{jk}}\,(V\,K_{L}\,U^{P})_{ji}\,K_{L}^{k\ell\ast}\,\text{.}$
(2)

Remarkably, $V_{1}$ closely connects the charged current with the neutral
current anomalies; while an enhancement in $b\to c\tau\nu$ transitions
requires sizeable $b\tau$ and $c\nu_{\tau}$ couplings, the same couplings also
generate sizeable $b\to s\tau\tau$ operators which feed under renormalisation
group (RG) running (from the LQ mass scale to the observable scale) into $b\to
s\mu\mu$ and $b\to see$ operators, as pointed out in [6]. While this behaviour
naturally occurs in $V_{1}$ models attempting at a combined explanation, it is
also preferred by the data on $b\to s\ell\ell$ processes on its own. In the
left plot of Figure 1 we present a model independent fit under the hypothesis
of (lepton flavour) universal NP contributions to $\Delta
C_{9}^{bs\ell\ell}=\Delta C_{9}^{\text{univ.}}$ in addition to the
“$(V-A)$-current” $\Delta C_{9}^{bs\mu\mu}=-\Delta C_{10}^{bs\mu\mu}$. To
evaluate the impact of the most recent data on the angular observables in
$B\to K^{\ast}\mu\mu$ decays provided by the LHCb collaboration [5], we first
establish a baseline by fitting the described NP hypothesis to all available
data, excluding the latest measurements. In a second fit we then include the
most recent data into the likelihood. In the left panel of Figure 1 we present
both fits in the plane of the $(V-A)$ NP contributions vs. the additional
universal contribution in $C_{9}$. While the best-fit point is only slightly
affected, the new data-improved precision has a strong impact on the
likelihood contour levels. It can be seen that a non-vanishing universal
contribution to $C_{9}$ is now preferred by around $3\>\sigma$ compared to
formerly $2\>\sigma$. The resulting correlation between charged and neutral
current transitions can further be visually verified in Figure 1 where we show
in the right plot a fit of the most dominant LQ coupling combinations relevant
to to $b\to s\ell\ell$ and $b\to c\tau\nu$ data.

Figure 1: Left: Likelihood contours resulting from a fit to all available
$b\to s\mu\mu$ data in the plane of ($V-A$) NP contributions vs. an additional
universal contribution. The filled contours include the recent LHCb
measurement [5], while the likelihood contours depicted by dashed lines
exclude this data. The pentagon denotes the SM prediction, while the star
(diamond) denotes the new (old) best fit point. Right: Likelihood contours
resulting from a fit of the dominant LQ coupling products to both $b\to
s\ell\ell$ and $b\to c\tau\nu$ data.

##  3 Non-unitary couplings

Being a gauge boson222Vector LQs can also appear as composite fields; for
simplicity we here assume it to arise from an extension of $SU(3)_{c}$., the
couplings of $V_{1}$ to SM fermions are a priori universal. The universality
is however in general broken by a possible mass misalignment of quarks and
leptons, such that, analogous to the CKM mechanism, a unitary flavour
structure is generated. In order to accommodate the anomalous data in
$B$-meson decays, the LQ couplings $K_{L}^{ij}$ are required to exhibit a
particular flavour pattern, which in turn leads to sizeable charged lepton
flavour violation (cLFV) rates. As it turns out, the experimental bounds on
cLFV processes can be respected if the ($3\times 3$) coupling matrix
$K_{L}^{ij}$ is non-unitary [7]. Non-unitary couplings (to SM fermions) can be
achieved by mixings of SM fermions with additional vector-like fermions.
Inspired from neutrino physics [8], the effects of these mixings, specifically
with leptons, can be parametrised in an effective way, using a product of
unitary rotation matrices. Should a specific model encompass additional
vector-like leptons, one must also consider the impact of the new states for
electroweak precision observables, as for instance the constraints on the $Z$
boson LFU ratios and cLFV decay modes. In particular, only vector-like
$SU(2)_{L}$ doublets allow to circumvent otherwise excessive corrections to
the $Z-\ell\ell^{(\prime)}$ tree-level couplings, as emphasised in [7].

##  4 Results and Outlook

In a specific construction333Contrary to many other attempts in the
literature, we do not neglect any coupling in order to comply with cLFV
bounds; all couplings are a priori assumed to be non-vanishing. including 3
generations of vector-like doublet leptons, we explored the model’s parameter
space by randomly scanning over 12 (of 15 total) relevant mixing angles at a
mass benchmark point of $m_{V_{1}}=1.5\>\mathrm{TeV}$. Our phenomenological
analysis includes, besides a large set of $b\to s\ell\ell$ and $b\to c\ell\nu$
observables, numerous constraints from cLFV decay modes of light and heavy
mesons as well as purely leptonic cLFV processes. The results of this scan are
shown in the left panel of Figure 2, where we present a large number of sample
points in the plane of the dominant combinations of LQ couplings: these allow
reconciling the anomalous data at the $1\>\sigma$ level, agreeing with the
parametrisation independent fit shown in the right panel of Figure 1. Although
a significant number of additional parameters is introduced, solid predictions
can be made. In the right panel of Figure 2 we show the sample points in the
plane of the most constraining observables $K_{L}\to\mu^{\pm}e^{\mp}$ and
neutrinoless $\mu-e$ conversion. It can be seen that a large portion of the
parameter space is already excluded (blue points), while the remaining
(preferred) region (orange points) is well within the reach of the upcoming
cLFV-dedicated experiments COMET [9] and Mu2e [10].

Figure 2: Left: Sample points reconciling the $B$-meson decay anomalies at
$1\>\sigma$ while being consistent with current experimental bounds on cLFV
processes. Right: Sample points (of the model) in the plane of the most
constraining cLFV observables. Points in blue accommodate both anomalies at
the $3\>\sigma$-level, points in orange are in addition complying with all
cLFV bounds. Dashed lines denote current experimental bounds, while the dotted
line indicates the future sensitivity of COMET [9] and Mu2e [10].

Besides the excellent experimental prospects from cLFV-dedicated experiments
(COMET/Mu2e and Mu3e [11]), Belle II recently started its first data-taking
run. Being a $B$-factory, it aims not only to scrutinise the $B$-anomalies,
but also to produce copious amounts of charmed mesons and $\tau$ leptons,
allowing to reach an unprecedented precision and sensitivity on related
flavour processes in the near future. Going beyond a random scan, and to a
comprehensive statistical analysis (a global fit of the LQ couplings) allows
to explore the experimental prospects on how vector LQ models can be further
probed in the near future [12]. By means of Monte-Carlo techniques we thus
estimate ranges for numerous observables to be investigated by Belle II [13],
for three LQ mass benchmark points
$m_{V_{1}}\in\\{1.5,2.5,3.5\\}\>\mathrm{TeV}$.

Figure 3: Predicted ranges for several $b\to s\tau\tau$ and cLFV observables
to be investigated at Belle II [13], COMET [9]/Mu2e [10] and Mu3e [11]. The
blue, orange and green lines respectively denote the $90\%$-range around the
respective best-fit points, for leptoquark masses of $1.5,\,2.5\text{ and
}3.5\>\mathrm{TeV}$. The horizontal red (purple) lines denote the current
(future) bound at $90\,\%$ C.L.; stars denote SM predictions when appropriate.
All Belle II sensitivities correspond to an integrated luminosity of
$50\>\mathrm{ab}^{-1}$.

As previously mentioned, due to the $SU(2)_{L}$ representation of $V_{1}$, the
LQ couplings responsible for sizeable NP contributions in $b\to c\tau\nu$
operators, as required by $R_{D^{(\ast)}}$ data, also generate large NP
contributions in $b\to s\tau\tau$ operators. Consequently, significant
enhancements in related meson decays, with respect to the SM prediction, are
expected. Additionally, a successful accommodation of the anomalous $b\to
s\ell\ell$ data necessitates large $b\mu$ and $s\mu$ LQ couplings. This
combination induces $\tau-\mu$ flavour violating processes at the tree-level,
in many cases at testable rates. In Figure 3 we present (preliminary)
predictions for several $b\to s\tau\tau$ and $\tau-\mu$ flavour violating
observables together with current experimental bounds and future
sensitivities. In addition to neutrinoless $\mu-e$ conversion in nuclei, $b\to
s\tau\tau$ and $b\to s\tau\mu$ related meson decays, as well as the cLFV decay
$\tau\to\phi\mu$ can be singled out as “golden modes”. Especially
$\tau\to\phi\mu$ decays have excellent chances of being observed by Belle II.
Conversely, should future searches for the decays yield negative results, the
related LQ couplings would be tightly constrained. It then might prove very
challenging to accommodate the $B$-meson decay anomalies with a single vector
LQ.

##  5 Summary and Conclusion

In recent years, numerous observables hint at the presence of LFUV in charged
and neutral current semileptonic $B$-meson decays. $SU(2)_{L}$-singlet vector
leptoquarks are excellent candidates for a combined explanation, but are
subject to stringent constraints from cLFV observables. We have shown that, in
order to comply with data on a large number of flavour observables, the
flavour structure of the LQ couplings to SM matter are required to be non-
unitary, which can be generated by mixings of SM leptons with heavy vector-
like doublet states. Furthermore, we have made predictions for many $b\to
s\tau\tau$ and cLFV observables, out of which we have identified several
“golden modes”, that have excellent chances to be observed by upcoming
experiments in the near future.

## References

  * [1] G. Caria et al. [Belle], Phys. Rev. Lett. 124 (2020) no.16, 161803 [arXiv:1910.05864 [hep-ex]].
  * [2] R. Aaij et al. [LHCb], Phys. Rev. Lett. 122 (2019) no.19, 191801 [arXiv:1903.09252 [hep-ex]].
  * [3] R. Aaij et al. [LHCb], JHEP 08 (2017), 055 [arXiv:1705.05802 [hep-ex]].
  * [4] R. Aaij et al. [LHCb], JHEP 02 (2016), 104 [arXiv:1512.04442 [hep-ex]].
  * [5] R. Aaij et al. [LHCb], Phys. Rev. Lett. 125 (2020) no.1, 011802 [arXiv:2003.04831 [hep-ex]].
  * [6] A. Crivellin, C. Greub, D. Müller and F. Saturnino, Phys. Rev. Lett. 122 (2019) no.1, 011805 [arXiv:1807.02068 [hep-ph]].
  * [7] C. Hati, J. Kriewald, J. Orloff and A. M. Teixeira, JHEP 12 (2019), 006 [arXiv:1907.05511 [hep-ph]].
  * [8] Z. z. Xing, Phys. Lett. B 660 (2008), 515-521 [arXiv:0709.2220 [hep-ph]].
  * [9] R. Abramishvili et al. [COMET], PTEP 2020 (2020) no.3, 033C01 [arXiv:1812.09018 [physics.ins-det]].
  * [10] L. Bartoszek et al. [Mu2e], “Mu2e Technical Design Report,” arXiv:1501.05241 [physics.ins-det].
  * [11] A. Blondel, A. Bravar, M. Pohl, S. Bachmann, N. Berger, M. Kiehn, A. Schoning, D. Wiedner, B. Windelband and P. Eckert, et al. “Research Proposal for an Experiment to Search for the Decay $\mu\to eee$,” arXiv:1301.6113 [physics.ins-det].
  * [12] C. Hati, J. Kriewald, J. Orloff, A. M. Teixeira, “The fate of vector leptoquarks: impact of future flavour data,” arXiv:2012.05883 [hep-ph].
  * [13] E. Kou et al. [Belle-II], PTEP 2019 (2019) no.12, 123C01 [erratum: PTEP 2020 (2020) no.2, 029201] [arXiv:1808.10567 [hep-ex]].


11institutetext: UIET, South Campus Panjab University, Sector 25, Chandigarh,
160014, India. 22institutetext: School of Science and Technology, Nottingham
Trent University,
50 Shakespear Street, Nottingham, NG1 4FQ, United Kingdom.

# Taguchi based Design of Sequential Convolution Neural Network for
Classification of Defective Fasteners††thanks: NTU-PU Collaborative Research
Grant

Manjeet Kaur 11 Krishan Kumar Chauhan 11 Tanya Aggarwal 11 Pushkar Bharadwaj
11 Renu Vig 11 Isibor Kennedy Ihianle 22 Garima Joshi 11 Kay Owa
22

###### Abstract

Fasteners play a critical role in securing various parts of machinery.
Deformations such as dents, cracks, and scratches on the surface of fasteners
are caused by material properties and incorrect handling of equipment during
production processes. As a result, quality control is required to ensure safe
and reliable operations. The existing defect inspection method relies on
manual examination, which consumes a significant amount of time, money, and
other resources; also, accuracy cannot be guaranteed due to human error.
Automatic defect detection systems have proven impactful over the manual
inspection technique for defect analysis. However, computational techniques
such as convolutional neural networks (CNN) and deep learning-based approaches
are evolutionary methods. By carefully selecting the design parameter values,
the full potential of CNN can be realised. Using Taguchi based design of
experiments and analysis, an attempt has been made to develop a robust
automatic system in this study. The dataset used to train the system has been
created manually for M14 size nuts having two labeled classes: Defective and
Non-defective. There are a total of 264 images in the dataset. The proposed
sequential CNN comes up with a 96.3% validation accuracy, 0.277 validation
loss at 0.001 learning rate.

###### Keywords:

Fasteners Sequential Convolution Neural Network Defects Taguchi analysis.

##  1 Introduction

Bolts and nuts are common fasteners in the mechanical and automotive
industries. Cold forming, hot forming, thread production, machining, hardening
and tempering are the procedures that fasteners go through throughout
production [3]. Changes in the material’s intrinsic characteristics, effect of
vibrations, tool damage, and improper process management can result in flaws
in the end products as fasteners because of the processes they go through [5].
Fastener raw materials might often develop cracks. Wrinkles are a form of
imperfection on fasteners caused by material displacement during the forging
process of nuts in particular. Deformation, dents, wrinkles, scratches,
fractures, rough surface, missing and misaligned threads on the fastener
surface are all faults generated by processing [20]. Small and medium-sized
industries are the largest manufacturers of these fasteners but the process of
inspection is done manually, which requires a lot of people, money, and time.
Even with all of that work, the potential for errors still exists, and
defective products may reach clients. As a result of the vibration, these
defective fasteners may lose up, or even break in long-term [21]. The
development of automation technologies to detect bad steel fasteners could
help in overcoming this challenge. The machine learning defect detection
system reduced human error and effort, it makes the procedure more accurate by
detecting defects that might otherwise go unnoticed by humans [4]. The process
involved calculating a collection of hand-crafted textural characteristics,
which were afterward trained on a classifier [14]. Although the automated
detection process based on image processing and machine learning techniques
offered great benefits it has some major drawbacks. One of the most
significant is that the appearance of abnormalities changes in terms of form,
size, colour, geometry, and other factors even within the same inspection work
[15]. Due to these reasons computer vision applications and deep learning
based convolution neural network (CNN) can be used for better efficiency and
precise detection rate.

##  2 Related Work

Computer vision-based applications for object detection and classification
using transfer learning and traditional CNNs are emerging and have become very
popular in software, mechanical and electrical industrial sectors. The amount
of speed, efficiency, and robustness provided by these applications has made
day-to-day work simple [11]. There are a lot of examples where the use of such
deep learning models for the detection and classification of industrial
fasteners has proved to be successful in achieving the goal of high accuracy
in less time. Some of the examples where computer vision has exceptional
contributions are taken into consideration before proposing the model. Several
algorithms have been used for metal crack detection and texture feature
extraction. Different edge detection operators have been used to obtain thin
edge features on defective samples [19]. Similarly several machine learning
based techniques,have been explored for classification of surface defects on
rolled steel [3]. Sharifzadeh et al. applied Gaussian functions and histogram
approaches to detect various flaws on steel components, with a detection rate
of 88.4% for holes, 78% for scratches, 90.4% for coil breaks, and 90.3% for
rust problems [16]. Ashour et al. applied support vector machine to inspect
the visual texture feature from the sample data, also different kernel
functions has been investigated for best performance classifier [1]. Park et
al. proposed machine learning based imaging based system for defect detection
for dirt, scratches, and wears on surface. CNN has been applied to check the
existence of defect in the target region on an input sample image. The
proposed method has been proven to be advantageous in terms of time, cost and
performance as compared to manual inspection techniques [13]. Bhandari and
Deshpande proposed a modified scheme based on heuristics algorithm used by
human inspectors for identifying surface imperfections to compute the
features, then used SVM to classify surface images into two classes: defective
and defect-free. The system was tested on a surface texture database and
achieved a classification accuracy of 94.19% [2]. Zhao et al. investigated
computer vision to detect pin missing problems in transmission lines that
employed bolts to link different components. Defects in these bolts can cause
major problems, such as grid breakdown. To solve this problem, a CNN model was
proposed, which included three key improvements for extracting small-scale
bolt features and achieved a 71.4% accuracy [22]. A version of CNN
architecture was used by Liu et al. to detect catenary support components
(CSCs). It involved the integration of a detection network for CSCs utilising
large scale optimized and improved Faster R-CNN with a cascade network for the
detection of CSCs with small scales. The model has a good accuracy of 92.8%
[9]. Taheritanjani et al. created a system that automatically recorded,
preprocessed data and compared it to a variety of supervised and unsupervised
machine learning models for detecting damage in 12 different fasteners. The
method also helped in determining the type of fastener used. The supervised
model achieved 99%, whereas the unsupervised model achieves 84% [18]. Giben et
al. proposed a visual inspection method for semantic segmentation and
classification of material using deep convolution neural network (DCNN). In
this approach they identified ten kinds of materials in total using this
method, and the proposed model had a classification accuracy of 93.35%. The
detection rate for chipped and crumbling ties was 92.11% and 86.06%,
respectively [7]. To extract rich feature information, Kou et al. used
specifically built dense convolution blocks in their defect detection model,
which significantly increases feature reuse, feature propagation, and the
network’s characterization ability. The suggested model generated 71.3% mean
Average Precision (mAP) on the GC10-DET dataset, which is publicly available,
and 72.2% mAP on the NEUDET dataset [8]. Song et al. presented a CNN based
technique in which they consider damage screw, surface dirt and stripped screw
as defective classes, images has been taken up with industrial camera.
Proposed model achieve 98% accuracy with 1.2s of average time taken to process
per image [17]. Gai et al. proposed a CNN technique for detecting defects on
steel surfaces in industrial parts. An industrial camera was used to collect
and pre-process the data, and then the VGG architecture was used to improve
network features, classification, and defect recognition capability. The
proposed model was then compared to other traditional strategies and found to
be more effective [6]. Computer vision-based applications such as object
identification and classification using transfer learning or traditional CNNs
have grown increasingly popular in all industries. The speed, efficiency, and
robustness provided by these approaches have simplified day-to-day tasks.
Researchers have employed the transfer learning approach in defect
categorization but these models were trained on datasets for object detection
and have no resemblance to the defect detection domain. Due to the fundamental
difference between the object detection and defect detection domains, CNN
models must be built from the scratch and trained on good quality dataset.
Furthermore, the lack of standard datasets leads to erroneous and inconclusive
findings, and there is currently no model that can be right away used for
transfer learning. This work proposes a dataset of defects on the nuts and a
design of sequential CNN model to handle these two key difficulties. This
study also demonstrates the efficacy of the Taguchi strategy, which is a
simple yet effective method for handling parameter optimization problems. The
proposed method aids in determining the sequential CNN parameter value for
defect classification in fasteners, according to the results.

Figure 1: Proposed Workflow for Taguchi based Design of Sequential Convolution
Neural Network (CNN).

##  3 Proposed Framework for Taguchi based Design of Sequential Convolution
Neural Network (CNN)

Fig. 1 shows the proposed framework for designing an optimized sequential CNN
model. The details of each step are as presented below:

###  3.1 Dataset Preparation

In order prepare a practical dataset, samples of M14 size nuts with six side
faces have been collected from the fastener industries. The images of size
1844*4000 pixels were captured by mobile phone camera in variable light
conditions by varying the level of illumination. Image of each face of nut is
captured. The real world captured dataset had the problem of class imbalance,
as the number of non-defective sides of nut were more than the defective
samples. To enhance the number of defective images in the dataset,
augmentation in terms of scaling and brightness variation was applied. This
resulted in 132 images each in ‘Defective’ and ‘Non-Defective’ class. 80% of
images were used for the training set and 20% for the test set. Fig. 2 shows
the sample images from dataset. The most common types of defects are crack,
dent, patches, scratches and wrinkles [6]. Here, all the defects are
considered as a single class as ’Defective’.

Figure 2: Sample Images M14 Size Nuts in Dataset.

###  3.2 Sequential CNN Design Parameters

The architecture of a basic sequential CNN is as depicted in Fig. 3. These
architectures can be created from scratch. To create a CNN model for a given
application, early layers learn low-level characteristics, while the end-layer
conducts classification based on the feature map.

Figure 3: Structure of Sequential CNN.

####  3.2.1 Number of CNN Layers

The CNN structures are motivated by the fact that increase in number of layers
help in better approximation of target function and enhances the capability to
learn from more detailed feature set. This makes, the number of layer as one
of the essential dimension in regulating learning ability of the sequential
architecture.

####  3.2.2 Input Image Size

Image size is chosen such that the fine defects such as cracks and scratches
are clearly visible but larger input image size leads to more number of input
is visible. However, having larger size input image leads to increase in
complexity of CNN. Therefore, [100x100] and [200x200] are selected for the
study. If a coloured image of 100 pixels in height and width is supplied, each
pixel has one single channel, and the input layer has the form (100, 100, 3).

####  3.2.3 Optimizer

An optimizer updates the model with respect to the loss function and help in
minimizing it by calculating partial derivative of the loss corresponding to
weights and updating the weights in the direction opposite of the obtained
gradient. This process is repeated until the loss function’s minima is
reached. Gradient descent takes into account the learning rate and takes
larger steps if the loss is large and a smaller steps if loss is decreasing.
The purpose of small learning rate is to come close to minimum value. The
objective function is optimised using Stochastic Gradient Descent (SGD). It
replaces the gradient with a value computed from a randomly picked data
subset, this can be considered a probabilistic estimate to steepest descent.
As a result, specific samples are chosen rather than the entire dataset. The
global minimum can be readily attained, but when dealing with a large dataset
becomes more difficult, hence SGD takes approximation of gradient descent by
selecting a subset of samples. It can be particularly helpful in the case of
large dataset. Adaptive Moment Estimation (ADAM) scales the learning rate
using an exponentially weighted gradient. It is one of the most popular
gradient descent optimizer algorithms. It keeps the record of the average of
earlier gradients that are decreasing. It is a very effective optimizer that
requires very little memory and has a low training cost.

####  3.2.4 Loss Function

Hinge rank loss aims to reduce the spread between the output of the model and
the target vector while isolating it from all the other vectors, thus
penalizing equally all the errors. Squared hinge loss computes the square of
hinge loss, resulting in flat error function’s surface and also making it
numerically simple to handle. If a hinge loss improves performance on a binary
classification issue, most probably a squared hinge loss will improve
performance even more.

####  3.2.5 Activation Function

Rectified Linear Unit (ReLU) is a non-linear activation function to calculate
activations of convolved feature map. ReLU response maximizes beyond a certain
point away from zero and has a V-shape, whereas the response is capped to the
maximum value of 6 giving it a Z-shape.

####  3.2.6 Filter Size

The purpose of implementing CNN is to extract key features from the input
images that can characterize a class. Convolutional operation considers the
local subset of pixels, therefore different levels of subsets can be explored
in the image by using different filter sizes and variation in filter size
capture different details. A small size filters find fine details by exploring
the small regions in the image. While, large size filter finds coarse
information and the model tries to find features in a large area of the input
at each computation. Hence, spatial filters can be explored to improve
performance with regard to learning aspect of the network. By carefully
adjusting the filters, CNN can perform well both on coarse and fine details.
In this research, an attempt is made to experiment with these basic building
elements of sequential CNN in order to identify the best combination that will
allow the model to perform well. The influence of each parameter adjustment
and its combinations can be better understood by carefully designing the
experiments.

###  3.3 Taguchi based Grid search for CNN design Parameters

####  3.3.1 Taguchi based grid search

approach is relevant to all the real-world design problems which depends on
number of control factors or hyperparameters. Taguchi’s orthogonal array has
been used in the design of experiments [10]. It is found out to be proficient
when paralleled to many other statistical designs [13]. Value of control
factors must be determined in order to achieve the optimal results. Taguchi
analysis aims to enhance quality as a way to deliver resilient configurations
and design. The term ”signal” refers to improved performance with little
variance, which is referred to as ”noise.” The consistency of performance is a
metric of robustness, which is achieved by making the design immune to the
effects of uncontrollable characteristics. A two-step optimization procedure
is used in Taguchi grid search. Selection of hyper parameters and desired
modifications is the initial stage. Next, the orthogonal array is chosen to
ensure that these control components participate equally and in a planned
manner [12]. The best potential performance is produced in the second stage by
identifying the best arrangement of hyperparameters.

####  3.3.2 Selection of Hyperparameters

Variations in object size, and distance from the camera are sources of
variation (noise) in the defect categorization domain. The aim is to find the
optimum hyperparameter combination that delivers high performance when
subjected to fluctuations. Table 1 lists the description, value of parameters
variation while performing trials. Since there is one component with four
levels and five factors with two levels, L16 is the best choice among the
Taguchi mixed level design possibilities for six parameters. A total of 36
trials will be required if the complete factorial design with all possible
cmbinations is used. However, utilising Taguchi’s orthogonal array to properly
design trials, the total number of trials that must be examined for testing is
reduced to 16 as indicated in Table 2.

Table 1: Parameters and variations. Factors (6) | Name of parameter | Variations/Levels
---|---|---
A | No. of CNN Layers | 6, 8, 10, 12
B | Image Size | [100x100], [200x200]
C | Optimizer | adam, sgd
D | Loss Function | Hinge, Squared Hinge
E | Activation Function | ReLU, ReLU6
F | Filter Size | [2x2], [3x3]

####  3.3.3 Selection of Response Parameters

In this work, the response parameters or performance metrics that are used to
assess performance are test accuracy, validation accuracy, test loss and
validation loss. The purpose is to maximize accuracy and minimize loss.

##  4 Analysis of Results

The model is implemented with Python software, and the DOE analysis is done
with Minitab. The recommended set of parameters has been fine-tuned for the
fastener dataset.The outcome of experiments for the possible set of
combinations are recorded, each training is conducted for 500 epochs and the
best result are recorded. Table 2 is analysed using Taguchi’s analysis in a
Minitab tool. The highlighted text indicates the best results in Table 2.

Table 2: Experimental Outcome as per Taguchi’s L16 Orthogonal Array.

Exp. | Parameter Variation | Response Values
---|---|---
Run | A | B | C | D | E | F | Train | Train | Val. | Val.
|  |  |  |  |  |  | Loss | Accuracy | Loss | Accuracy
1. | 6 | [100x100] | adam | Hinge | ReLU | [2x2] | 0.3885 | 0.9251 | 0.9303 | 0.9145
2. | 6 | [100x100] | adam | Hinge | ReLU | [3x3] | 0.6127 | 0.8508 | 0.7954 | 0.8629
3. | 6 | [200x200] | sgd | Sqd. Hinge | ReLU6 | [2x2] | 0.3539 | 0.7552 | 0.6096 | 0.6721
4. | 6 | [200x200] | sgd | Sqd. Hinge | ReLU6 | [3x3] | 0.5114 | 0.9091 | 0.8036 | 0.8966
5. | 8 | [100x100] | adam | Sqd. Hinge | ReLU6 | [2x2] | 0.1441 | 0.8449 | 1.6285 | 0.8497
6. | 8 | [100x100] | adam | Sqd. Hinge | ReLU6 | [3x3] | 0.5757 | 0.8545 | 0.7945 | 0.8397
7. | 8 | [200x200] | sgd | Hinge | ReLU | [2x2] | 0.275 | 0.1983 | 0.579 | 0.1883
8. | 8 | [200x200] | sgd | Hinge | ReLU | [3x3] | 0.2206 | 0.9027 | 0.4843 | 0.9151
9. | 10 | [100x100] | sgd | Hinge | ReLU6 | [2x2] | 0.3332 | 0.9455 | 0.6477 | 0.9433
10. | 10 | [100x100] | sgd | Hinge | ReLU6 | [3x3] | 0.2258 | 0.9273 | 0.5374 | 0.9201
11. | 10 | [200x200] | adam | Sqd. Hinge | ReLU | [2x2] | 0.0762 | 0.8949 | 0.3033 | 0.9021
12. | 10 | [200x200] | adam | Sqd. Hinge | ReLU | [3x3] | 0.3889 | 0.9536 | 0.7223 | 0.9433
13. | 12 | [100x100] | sgd | Sqd. Hinge | ReLU | [2x2] | 0.3889 | 0.9455 | 0.6691 | 0.9433
14. | 12 | [100x100] | sgd | Sqd. Hinge | ReLU | [3x3] | 0.3626 | 0.9455 | 0.4624 | 0.9433
15. | 12 | [200x200] | adam | Hinge | ReLU6 | [2x2] | 0.1161 | 0.8545 | 0.5709 | 0.8528
16. | 12 | [200x200] | adam | Hinge | ReLU6 | [3x3] | 0.1911 | 0.9159 | 0.3713 | 0.9216

##### Interval Plot

for variation in values in train loss, train accuracy, validation loss and
validation accuracy is shown in Fig. 4. It is used to evaluate and compare
confidence intervals for result means. An interval plot depicts a 95%
confidence interval for each group’s mean. The plot indicates that the mean
value of train and validation accuracy is almost equal with similar
variability, while the loss values show clear displacement in terms of mean
average value. The validation loss has a lot of variability and is
considerably larger. Further, by analysis of outcome, efforts are undertaken
to reduce loss and enhance accuracy.

Figure 4: Interval Plot.

##### Main Effect Plot:

Fig. 5 shows the Main Effect Plot for the adjustment of six hyperparameters.
The main effect graphs show how each factor affects the system’s overall
performance. ’Main effect’ is defined as when different degrees of a parameter
ave varying effects on performance. When the line is horizontal, it signifies
that the characteristic average is the same across all variants of that
hyperparameter. If the plot is not horizontal, and changes in the factor’s
values affect the characteristic differently, there is a significant influence
[12]. The major effect plot of test and validation accuracy in Fig. 5 is used
to determine the best set of values for each factor. The element with the
greatest fluctuation has the greatest effect on the system response, and hence
has Rank 1 and so on, according to the ranks of main effect analysis. The
optimizer and loss function have the largest impact on system performance,
while the type of activation function has the least.

Figure 5: Main Effect Plot and Main Effect Analysis from Minitab Tool.

###  4.1 Optimized Sequential CNN Model

Taking into account the hyperparameters listed in Table 1, the proposed values
of parameters on the basis of Taguchi analysis are selected as shown in main
effect plot to maximize accuracy in Fig. 5. The number of CNN layers is 10,
image size is [100x100], Activation function is Relu6, loss function is
squared hinge, optimizer is adam, filter size [3x3], filters in each layer are
[32, 32, 32, 64, 64, 64, 128, 128, 256, 256]. Proposed sequential CNN
architecture is designed and confirmation run is performed taking into
consideration these parameter and summarized in Table 3.

Table 3: Proposed Sequential CNN Architecture.

Layer | Type | Output Shape | No. of Parameters
---|---|---|---
conv_1 | 2D, Conv | (100, 100, 32) | 416
conv_2 | 2D, Conv | (100, 100, 32) | 4128
conv_3 | 2D, Conv | (100, 100, 32) | 4128
max_pooling_1 | Pooling, max | (50, 50, 32) | 0
conv_4 | 2D, Conv | (50, 50, 64) | 18496
conv_5 | 2D, Conv | (50, 50, 64) | 36928
conv_6 | 2D,Conv | (50, 50, 64) | 36928
max_pooling_1 | Pooling, max | (25, 25, 64) | 0
conv2d_7 | 2D, Conv | (25, 25, 128) | 73856
conv2d_8 | 2D, Conv | (25, 25, 128) | 147584
max_pooling_3 | Pooling | (12, 12, 128) | 0
conv2d_9 | 2D, Conv | (12, 12, 256) | 295168
conv2d_10 | 2D, Conv | (12, 12, 256) | 590080
max_pooling_4 | Pooling, max | (6, 6, 256) | 0
flatten_1 | Flatten | (9216) | 0
dense_1 | Dense | (1) | 9217
Total parameters: 1,216,929 |
Trainable parameters: 1,216,929 |
Non-trainable parameters: 0 |
No. of CNN Layers: 10 |
No. of Filters in each Layer: [32, 32, 32, 64, 64, 64, 128, 128, 256, 256] |
Activation Function: ReLU6 |
Loss Function: Squared Hinge |
Optimizer: Adaptive Moment Optimizer (adam) |
Batch Size: 32 |
Filter size in each layer: [3x3] |
Classifier: Binary Support Vector Machine |

Figure 6: Comparison of Results for Proposed Design.

##  5 Conclusion

Automatic defect detection systems have proven to be more effective than
manual inspection procedures in quality control. The goal of this work is to
use Taguchi-based design of trials and analysis to create a robust autonomous
system for visual inspection. A dataset of pictures of nut surface defects is
developed and used. A sequential CNN architecture is created using Taguchi
design of experiments and analysis. The findings suggest that choosing the
right hyperparameters is crucial for attaining low loss values and higher
accuracy in a specific application. Training accuracy is 98.69%, training loss
is 0.0449, validation loss is 0.2794, and validation accuracy is 96.3% in this
study. System resilience is seen with consistent training and validation
outcomes, that is low loss and high accuracy are achieved.
In future work, more comprehensive study will be carried out taking into
various categories of defects.

## References

  * [1] Ashour, M.W., Halin, A.A., Khalid, F., Abdullah, L.N., Darwish, S.H.: Texture-based classification of workpiece surface images using the support vector machine. International Journal of Software Engineering and Its Applications 9(10), 147–160 (2015)
  * [2] Bhandari, S.H., Deshpande, S., Deshpande, S.: A simple approach to surface defect detection. 2008 IEEE Region 10, 8–10 (2008)
  * [3] Caleb, P., Steuer, M.: Classification of surface defects on hot rolled steel using adaptive learning methods. In: KES’2000. Fourth International Conference on Knowledge-Based Intelligent Engineering Systems and Allied Technologies. Proceedings (Cat. No. 00TH8516). vol. 1, pp. 103–108. IEEE (2000)
  * [4] Chen, J., Liu, Z., Wang, H., Núñez, A., Han, Z.: Automatic defect detection of fasteners on the catenary support device using deep convolutional neural network. IEEE Transactions on Instrumentation and Measurement 67(2), 257–269 (2017)
  * [5] Elangovan, S., Boopathy, T., Kannan, R.: Fabrication and analysis of polymer bolt and nut assembly by additive manufacturing system. Journal of Emerging Technologies and Innovative Research (JETIR) 6(6) (2019)
  * [6] Gai, X., Ye, P., Wang, J., Wang, B.: Research on defect detection method for steel metal surface based on deep learning. In: 2020 IEEE 5th Information Technology and Mechatronics Engineering Conference (ITOEC). pp. 637–641. IEEE (2020)
  * [7] Giben, X., Patel, V.M., Chellappa, R.: Material classification and semantic segmentation of railway track images with deep convolutional neural networks. In: 2015 IEEE International Conference on Image Processing (ICIP). pp. 621–625. IEEE (2015)
  * [8] Kou, X., Liu, S., Cheng, K., Qian, Y.: Development of a yolo-v3-based model for detecting defects on steel strip surface. Measurement 182, 109454 (2021)
  * [9] Liu, W., Liu, Z., Nunez, A., Han, Z.: Unified deep learning architecture for the detection of all catenary support components. IEEE Access 8, 17049–17059 (2020)
  * [10] Montgomery, D.C.: Design and analysis of experiments. John wiley & sons (2017)
  * [11] Neogi, N., Mohanta, D.K., Dutta, P.K.: Review of vision-based steel surface inspection systems. EURASIP Journal on Image and Video Processing 2014(1), 1–19 (2014)
  * [12] Oehlert, G.W.: A first course in design and analysis of experiments. Kluwer Academic Publishers (2010)
  * [13] Park, J.K., Kwon, B.K., Park, J.H., Kang, D.J.: Machine learning-based imaging system for surface defect inspection. International Journal of Precision Engineering and Manufacturing-Green Technology 3(3), 303–310 (2016)
  * [14] Saiz, F.A., Serrano, I., Barandiarán, I., Sánchez, J.R.: A robust and fast deep learning-based method for defect classification in steel surfaces. In: 2018 International Conference on Intelligent Systems (IS). pp. 455–460. IEEE (2018)
  * [15] Shaheen, M.A., Foster, A.S., Cunningham, L.S., Afshan, S.: Behaviour of stainless and high strength steel bolt assemblies at elevated temperatures—a review. Fire Safety Journal 113, 102975 (2020)
  * [16] Sharifzadeh, M., Amirfattahi, R., Sadri, S., Alirezaee, S., Ahmadi, M.: Detection of steel defect using the image processing algorithms. In: The International Conference on Electrical Engineering. pp. 1–7. Military Technical College (2008)
  * [17] Song, L., Li, X., Yang, Y., Zhu, X., Guo, Q., Yang, H.: Detection of micro-defects on metal screw surfaces based on deep convolutional neural networks. Sensors 18(11), 3709 (2018)
  * [18] Taheritanjani, S., Schoenfeld, R., Bruegge, B.: Automatic damage detection of fasteners in overhaul processes. In: 2019 IEEE 15th International Conference on Automation Science and Engineering (CASE). pp. 1289–1295. IEEE (2019)
  * [19] Xue, B., Wu, Z.: Key technologies of steel plate surface defect detection system based on artificial intelligence machine vision. Wireless Communications and Mobile Computing 2021 (2021)
  * [20] Xue, P., Jiang, C., Pang, H.: Detection of various types of metal surface defects based on image processing. Traitement du Signal 38(4) (2021)
  * [21] Yun, J.P., Choi, S., Kim, J.W., Kim, S.W.: Automatic detection of cracks in raw steel block using gabor filter optimized by univariate dynamic encoding algorithm for searches (udeas). NDT and E International 42(5), 389–397 (2009). https://doi.org/10.1016/j.ndteint.2009.01.007
  * [22] Zhao, Z., Qi, H., Qi, Y., Zhang, K., Zhai, Y., Zhao, W.: Detection method based on automatic visual shape clustering for pin-missing defect in transmission lines. IEEE Transactions on Instrumentation and Measurement 69(9), 6080–6091 (2020)


11institutetext: State Key Laboratory of Computer Science, Institute of
Software, Chinese Academy of Sciences
University of Chinese Academy of Sciences
11email<EMAIL_ADDRESS>
# Discovering an Algorithm Actually Learning Restricted Single Occurrence
Regular Expression with Interleaving

Xiaofan Wang  Xiaolan Zhang

###### Abstract

A recent paper [3, 4] proposed an algorithm $i$SOIRE, which combines single-
occurrence automaton (SOA) [1, 2] and maximum independent set (MIS) to learn a
subclass single-occurrence regular expressions with interleaving (SOIREs) and
claims the learnt expression is SOIRE, which has unrestricted usage for
interleaving. However, in reality, the learnt expression still has many
restrictions for using interleaving, even does for Kleene-star or interation,
i.e, the learnt expression is not an SOIRE, we prove that by examples. In this
paper, for the algorithm $i$SOIRE, we first give the basic notions, then
provide analyses about incorrectness, finally present the correct result
learnt by $i$SOIRE. Our theoretical analyses demonstrate that the result
derived by $i$SOIRE belongs to a subclass of SOIREs.

##  1 Basic Notions

We give the notions about single-occurrence regular expressions with
interleaving (SOIRE), single-occurrence automaton (SOA).

######  Definition 1 (regular expression with interleaving)

Let $\Sigma$ denote a finite set of alphabet symbols. The regular expression
with interleaving are defined as follows. $\varepsilon$, $a\in\Sigma$ are
regular expressions. For the regular expressions $r_{1}$ and $r_{2}$, the
concatenation $r_{1}\cdot r_{2}$, the kleene-star $r_{1}^{*}$, the disjunction
$r_{1}|r_{2}$, the interleaving $r_{1}\&r_{2}$ are also regular expressions.
Note that iteration $r_{1}^{+}$, optional $r?$ are used as abbreviations of
$r_{1}r_{1}^{*}$, $r|\varepsilon$. Usually, we omit concatenation operators in
examples.
$\mathcal{L}(r_{1}\&r_{2})\\!=\\!\mathcal{L}(r_{1})\&\mathcal{L}(r_{2})=\bigcup_{s_{1}\in\mathcal{L}(r_{1}),s_{2}\in\mathcal{L}(r_{2})}s_{1}\&s_{2}$.
For $u,v\in\Sigma^{*}$ and $a,b\in\Sigma$,
$u\&\varepsilon=\varepsilon\&u=\\{u\\}$, and
$(au)\&(bv)=\\{a(u\&bv)\\}\cup\\{b(au\&v)\\}$.

######  Definition 2 (single-occurrence regular expression with interleaving
(SOIRE))

Let $\Sigma$ be a finite alphabet. A single-occurrence regular expression with
interleaving (SOIRE) is a regular expression with interleaving over $\Sigma$
in which every terminal symbol occurs at most once.

According to the definition, SOIREs have unrestricted usage for interleaving
and other operators.

######  Definition 3 (single-occurrence automaton (SOA) [1, 2])

Let $\Sigma$ be a finite alphabet, and let $q_{0}$, $q_{f}$ be distinct
symbols that do not occur in $\Sigma$. A single-occurrence automaton (SOA)
over $\Sigma$ is a finite directed graph $\mathscr{A}\\!=\\!(V,E)$ such that
(1) $\\{q_{0},q_{f}\\}\in V$, and $V\subseteq\Sigma\cup\\{q_{0},q_{f}\\}$. (2)
$q_{0}$ has only outgoing edges, $q_{f}$ has only incoming edges, and every
$v\in V\setminus\\{q_{0},q_{f}\\}$ is visited during a walk from $q_{0}$ to
$q_{f}$.

A string $a_{1}\cdots a_{n}$ ($n\geq 0$) is accepted by an SOA $\mathscr{A}$,
if and only if there is a path $q_{0}\rightarrow
a_{1}\rightarrow\cdots\rightarrow a_{n}\rightarrow q_{f}$ in $\mathscr{A}$.

##  2 Analyses about the algorithm $i$SOIRE

First, we present analyses about the algorithm $i$SOIRE. Then, in term of the
expression learnt by the algorithm $i$SOIRE, we obtain two conclusions and
provide the corresponding proofs. The two conclusions reveal the expression
learnt by the algorithm $i$SOIRE is not an SOIRE.

For any given finite sample, SOA is constructed by using algorithm 2T-INF [1],
the algorithm $i$SOIRE [3, 4] combines SOA and MIS to infer an expression
called SOIRE. The main procedure $Soa2Soire$ [3, 4] (see Figure 2(a)) is
designed by revising only few steps of the algorithm $Soa2Sore$ [2] (see
Figure 1), which is used to infer a single-occurrence regular expression
(SORE) [1, 2]. The main differences between algorithms $Soa2Soire$ and
$Soa2Sore$ are in line 5 $\sim$ line 8.

In algorithm $Soa2Sore$, in line 5 $\sim$ line 8, if the input SOA built form
given finite sample contains a strongly connected component ($U$), $U$ is used
to infer an expression ($r$) and then is added an iteration operator (+),
i.e., $r^{+}$. The strongly connected component ($U$) is contracted to a
vertex labelled with $r^{+}$. However, in algorithm $Soa2Soire$, only for the
strongly connected component ($U$) where $|U|\\!=\\!1$, $U$ is used to
generate an expression ($a\\!\in\\!\Sigma,U\\!=\\!\\{a\\}$) and then is added
an iteration operator (+), i.e., $a^{+}$. For $|U|\\!>\\!1$, $U$ is used to
introduce interleaving $\&$ into inferred expression by calling subroutine
$Merge$ (see Figure 2(b)).

Subroutine $Merge$ is used to return an expression, where the interleaving
$\&$ is introduced. $filter(U,S)$ [3, 4] denotes that, for each string $s\in
S$, $filter$ extracts the substring consisting of symbols in $U$, where the
order of the alphabetic symbols maintains the relative order of that in $s$.
The input of the subroutine $Merge$ is the set of the strings extracted by
$filter$. In $Merge$, first, in line 1 $\sim$ line 8, $all\\_mis$ [5] (the set
of the distinct maximum independent set) is computed. Then, in line 9 $\sim$
line 13, for each obtained maximum independent set $mis\in all\\_mis$, $mis$
is used to generate an expression by recursively calling $Soa2Soire$, where
the input is the set of the strings extracted by $filter(mis,S)$. Each
generated expression is input in $U^{\prime}$. Finally, in line 14, subroutine
$combine$ connects all expressions in $U^{\prime}$ by using interleaving $\&$.
For example $U^{\prime}\\!=\\!\\{r_{1},r_{2},r_{3}\\}$,
$combine(U^{\prime})\\!=\\!r_{1}\&r_{2}\&r_{3}$. The result returned by
$Merge$ is the result of $combine$.

Since the algorithm $Soa2Soire$ presented in [3, 4] does not provide the proof
about the correctness, for any learnt expression, we check whether the learnt
expression is SOIRE, which has unrestricted usage for interleaving and other
operators. However, we discover that the learnt expression still has many
restrictions for using interleaving, even does for Kleene-Star or iteration,
the learnt result is not an SOIRE. For better understanding, we provide the
proofs by examples, which specify the learnt result is not an SOIRE.

Figure 1: The algorithm $Soa2Sore$.

(a) $Soa2Soire$

(b) $Merge$

Figure 2: The algorithm $i$SOIRE.

For the given algorithm $Soa2Soire$, there are two conclusions:

  1. 1.

For the learnt expression, Kleene-star ∗ or iteration + is just on a single
alphabet symbol.

###### Proof

In algorithm $Soa2Soire$, in line 6 $\sim$ line 7, $plus()$ [2], which should
have used to add an iteration + on an expression, but only works on a single
alphabet symbol. In the whole process of the recursion of the algorithm,
$plus()$ does not occur in other cases. Since the initially obtained strongly
connected components have been merge into a vertex (see subroutine $Contract$
[2]), and the corresponding edges, which can form loops in SOA, have been
removed (see subroutine $bend$ [2]), even though for a node $v$: $v.label()$
is an expression consisting of multiple alphabet symbols, $v$ does not
possible occur in a strongly connected component. Hence, we can assert that a
class of expressions cannot be learnt, such as $(ab)^{+}$, $(a|b)^{+}$,
$(a|b\&c)^{+}$, $(a\&b)^{+}$ and $((a|b)\&(c|d)\&(e|f))^{*}$.

  2. 2.

The expressions of form $a\&(b(c\&d))$ cannot be learnt.

###### Proof

Assume that the expression $a\&(b(c\&d))$ can be correctly learnt by
induction. In $merge$, the interleaving $\&$ is introduced by the subroutine
$combine$, in line 9 $\sim$ line 13, any obtained maximum independent set
$mis\in all\\_mis$ can form a sample $S^{\prime}$
$(S^{\prime}\\!=\\!filter(mis,S))$. And SOA $A$=2T-INF$(S^{\prime})$. Sample
$S^{\prime}$ and SOA $A$ are as inputs of the algorithm $Soa2Soire$, let
$delta$ denote the derived expression. According to the computation of
$filter$, the alphabet symbols in $\delta$ are in the same maximum independent
set $mis$.

Then in line 9, for each $mis_{i}\\!\in\\!all\\_mis$, the corresponding
expression $\delta_{i}$ is generated.
($S^{\prime}_{i}\\!=\\!filter(mis_{i},S)$; SOA
$A_{i}$=2T-INF$(S^{\prime}_{i})$;
$\delta_{i}\\!=\\!Soa2Soire(S^{\prime}_{i},A_{i})$;) $\delta_{i}$ is put into
$U$, then $combine(U)=\delta_{1}\&\delta_{2}\&\cdots\&_{i}$.

For expression $a\&(b(c\&d))$, $mis_{1}\\!=\\!\\{a\\}$,
$mis_{2}\\!=\\!\\{b,c,d\\}$, $mis_{3}\\!=\\!\\{c\\}$ and
$mis_{4}\\!=\\!\\{d\\}$. Then for the initially constructed SOA, since $b,c,d$
can form a maximum independent set $mis_{2}$, then for $mis_{3}\\!=\\!\\{c\\}$
and $mis_{4}\\!=\\!\\{d\\}$ are not maximum independent sets, respectively.
There is a contradiction, the initial assumption does not hold. The
expressions of form $a\&(b(c\&d))$ cannot be learnt by $Soa2Soire$.

Conclusion 1 and conclusion 2 have revealed that the expression learnt by
$Soa2Soire$ still has many restrictions for using interleaving. Such as the
expressions of form $(a|b\&c)^{+}$, $(a\&b)^{+}$, $((a|b)\&(c|d)\&(e|f))^{*}$
and $a\&(b(c\&d))$. Meanwhile, the learnt expression has restrictions for
using Kleene-star or iteration, even does for the expressions of form
$(ab)^{+}$ and $(a|b)^{+}$. Actually, for conclusion 2, if $a$, $b$, $c$ and
$d$ are replaced with regular expressions, respectively. The same conclusions
can be obtained. This implies that the expression learnt by $Soa2Soire$ is not
an SOIRE.

##  3 The correct result learnt by $i$SOIRE

In Section 2, we have proved that the expression learnt by $Soa2Soire$ is not
an SOIRE. However, we should check whether the expression returned by $i$SOIRE
belongs to a subclass of SOIREs or not. Here, by analyzing the algorithm
$Soa2Soire$, we propose a subclass of SOIREs called RSOIREs (see definition 3)
and prove that the expression learnt by $Soa2Soire$ is a RSOIRE.

######  Definition 4 (restricted SOIREs)

A restricted SOIRE (RSOIRE) is a regular expression with interleaving over
$\Sigma$ by the following grammar, and where every terminal symbol occurs at
most once.

$P:=SP\Big{|}PS\Big{|}S\Big{|}T\Big{|}P|S$ (1) $S:=S\&S\Big{|}T$ (2)
$T:=T|T\Big{|}TT\Big{|}\varepsilon\Big{|}a\Big{|}a^{*}(a\in\Sigma)$ (3)

###### Example 1

$(a^{+}|b)(c\&d)$, $ad\&(b|c^{*})$, and $a^{+}|b^{+}\&c^{*}$ are RSOIREs.
However, $(ab)\&(c|d)^{+}$, $((a|b\&c)d?)^{*}$, and $a\&(b(c\&d))$ are SOIREs,
not RSOIREs.

###### Theorem 3.1

For any given finite sample $S$, let SOA $A$=2T-INF$(S)$, and
$r=Soa2Soire(S,A)$. Then $r$ is a RSOIRE, and for any RSOIRE $r^{\prime}$,
$r^{\prime}$ can be learnt by $Soa2Soire$.

###### Proof

  1. 1.

$r$ is a RSOIRE.

(1) For regular expressions $\varepsilon,a,a^{*}$, in algorithm $Soa2Soire$,
in line 2, line 11 $\sim$ line 16 and line 7, they can be derived, the
correctness can be ensured by the corresponding correctness of algorithm
$Soa2Sore$.

(2) For regular expressions $r_{1}r_{2}$ and $r_{1}|r_{2}$, assume that
$r_{1}$ and $r_{2}$ can be correctly derived by $Soa2Soire$ by induction. In
line 11 $\sim$ line 16 and line 22 $\sim$ line 23, $r_{1}r_{2}$ and
$r_{1}|r_{2}$ can be derived, the correctness can also be ensured by the
corresponding correctness of algorithm $Soa2Sore$.

(3) For regular expression $r_{1}\&r_{2}\&\cdots\&r_{k}$ $(k\geq 2)$, assume
that $r_{i}$ $(1\leq i\leq k)$ can be correctly derived by $Soa2Soire$ by
induction. According to the conclusion 2 and the corresponding proof in
Section 2, $r_{i}$ cannot be possible to contain the interleaving $\&$. The
expression $r_{1}\&r_{2}\&\cdots\&r_{k}$ is computed by $combine$ in $Merge$,
$r_{i}$ is derived by computing the corresponding maximum independent set
$mis_{i}$. And for any two distinct maximum independent sets $mis_{i}$ and
$mis_{j}$ $(i\\!\neq\\!j)$, the symbols in $mis_{i}$ and the symbols in
$mis_{j}$ can be interleaved. Thus, the expression
$r_{1}\&r_{2}\&\cdots\&r_{k}$ can be correctly derived by $Soa2Soire$.

The expressions discussing in (1), (2) and (3), which are connected by using
concatenation or disjunction, can form complexity expressions, and certainly
they can be decomposed into the above discussed basic expressions. The grammar
(3) and grammar (2) presented in definition 3 can generated the expressions
discussing in (1) and (2), respectively. And the complexity expressions formed
by the expressions discussing in (1), (2) and (3) can be generated by the
grammar (1). This implies that any expression $r$ learnt by $Soa2Soire$ is a
RSOIRE.

  2. 2.

For any RSOIRE $r^{\prime}$, $r^{\prime}$ can be learnt by $Soa2Soire$.

(1) For grammar (3), the corresponding generated regular expressions can be
derived by $Soa2Soire$, the correctness can be ensured by the corresponding
correctness of algorithm $Soa2Sore$.

(2) For grammar (2), according to the proofs in 1, the corresponding generated
regular expressions with interleaving can also be derived by $Soa2Soire$.

(3) For grammar (1), the generated complexity expressions can be decomposed
into the expressions produced by grammar (2) or grammar (3), then the
complexity expressions can also be derived by $Soa2Soire$.

This implies that, for an expression $r^{\prime}$ generated by the defined
grammars, $r^{\prime}$ can be learnt by $Soa2Soire$.

We give a correct class of expression that can be learnt by $Soa2Soire$, and
present the corresponding proofs of correctness. Theorem 3.1 demonstrate that
the expression learnt by $Soa2Soire$ belongs to a subclass of SOIREs.

##  4 Conclusion

In this paper, we mainly provide analyses about the incorrectness about
algorithm $i$SOIRE, and then present the correct a class of expressions can be
learnt by algorithm $i$SOIRE, the corresponding proofs illustrate that the
learnt expression belongs to a subclass of SOIREs. Since the algorithm
$i$SOIRE can be used to learn other classes of expressions, such as
$k$-occurrence regular expression with interleaving, the corresponding
correctness depends on the correctness of the algorithm $i$SOIRE. The comments
in this paper can be provided as a reference.

## References

  * [1] Bex, G.J., Neven, F., Schwentick, T., Vansummeren, S.: Inference of concise regular expressions and DTDs. ACM Transactions on Database Systems 35(2), 1–47 (2010)
  * [2] Freydenberger, D.D., Kötzing, T.: Fast learning of restricted regular expressions and DTDs. Theory of Computing Systems 57(4), 1114–1158 (2015)
  * [3] Chen, H., Zhang, X., Zhang, L.: An effective algorithm for learning single occurrence regular expressions with interleaving. In: Proceedings of the 23rd International Database Applications & Engineering Symposium, IDEAS 2019, Athens, Greece, June 10-12, 2019. pp. 24:1–24:10 (2019), https://doi.org/10.1145/3331076.3331100
  * [4] Chen, H., Zhang, X., Zhang, L.: An effective algorithm for learning single occurrence regular expressions with interleaving. arXiv preprint arXiv:1906.02074 (2019)
  * [5] Peng, F., Chen, H.: Discovering restricted regular expressions with interleaving. In: Asia-Pacific Web Conference. pp. 104–115. Springer (2015)