\section{Introduction}
State of the art machine learning algorithms can achieve high accuracies in classification tasks but misclassify minor perturbations in the data known as as adversarial attacks
\cite{goodfellow2014explaining,papernot2016limitations,kurakin2016adversarial,carlini2017towards,brendel2017decision}. Adversarial examples have been shown to transfer across models which makes it possible to perform transer-based (substitute model) black box attacks \cite{papernot2016transferability}. To counter adversarial attacks many defense methods been proposed with adversarial training being the most popular \cite{szegedy2013intriguing}. This is known to improve  robustness to adversarial examples but also tends to lower accuracy on clean test data that has no perturbations \cite{raghunathan2019adversarial,zhang2019theoretically}. Many previously proposed defenses have also shown to be vulnerable \cite{carlini2017towards,athalye2018obfuscated,ghiasi2020breaking} thus leaving adversarial robustness still an open problem in machine learning.

The 01 loss is known to be more robust to outliers than convex loss models \cite{xie2019,icml13optimize,bartlett04} and gives different boundaries in the presence of outliers. Could the difference in boundaries translate into non-transferability of adversarial examples between convex and 01 loss models? We study this in the setting of white box and substitute model black box attacks.

Computationally 01 loss presents a considerable challenge because it is NP-hard to solve \cite{ben03}. Previous attempts \cite{nips01optimize,mixedint01,approx01,ijcnn01optimize,icml13optimize} lack on-par test accuracy with convex solvers and are slow and impractical for large multiclass image benchmarks. However, a recent stochastic coordinate descent method for linear 01 loss models \cite{xie2019} has shown to attain comparable accuracies to state of the art linear solvers like the support vector machine. We build upon this in our current work.

We propose a 01 loss dual layer neural network with sign activation which to the best of our knowledge is the first such network to be proposed. Since our network weights are real numbers our model is different from binarized neural networks whose weights are constrained to be +1 and -1 or 1 and 0 \cite{galloway2017attacking,courbariaux2016binarized,rastegari2016xnor}. We train our network with stochastic coordinate descent (along the lines of \cite{xie2019} and fully described in our Supplementary Material) and show that it achieves on-par test accuracy to equivalent convex models. We are now in a position to study transferability of adversarial examples between linear 01 loss and convex (hinge) loss models, and between dual layer neural networks with sign activation and 01 loss vs sigmoid activation and logistic loss.

We proceed with white box attacks where the attacker has full knowledge of the model's parameters and  transfer based black box attacks via substitute models where the attacker has access only to label outputs of the model. We study transferability and black box attacks on image benchmarks MNIST \cite{lecun1998gradient}, CIFAR10 \cite{krizhevsky2009learning}, and Mini ImageNet (a ten class subset of the original ImageNet \cite{ILSVRC15}) where we make the following findings.

\begin{itemize}
\item White box adversaries do not transfer effectively between convex and 01 loss on CIFAR10 and ImageNet datasets than they do on MNIST.
\item As a result of this, convex substitute model black box attacks are more effective on convex models than 01 loss ones on CIFAR10 and ImageNet.
\item 01 loss substitute model black box attacks are ineffective on all datasets and on all models due to their non-uniqueness.
\item Discretization of input features does not affect the non-transferability on CIFAR10, in fact it increases it and as a consequence makes 01 loss models even more robust to convex substitute model black box attacks than in the original feature space.
\item Our 01 loss models can attain comparable black box robustness to convolutional models than their convex counterparts.
\end{itemize}

\section{Methods}

\subsection{Background}
The problem of determining the hyperplane with minimum number of misclassifications
in a binary classification problem is known to be NP-hard \cite{ben03}.
In mainstream machine learning literature this is called minimizing the 01 loss
\cite{kernel01} given in Objective~\ref{obj1},

\begin{equation}
\frac{1}{2n}\argmin_{w,w_0} \sum_i (1-sign(y_i(w^Tx_i+w_0)))
\label{obj1}
\end{equation}

where $w \in R^d$, $w_0 \in R$ is our hyperplane, and $x_i \in R^d, y_i\in \{+1,-1\}.\forall i=0...n-1$ are our training data. Popular linear classifiers such as the linear support
vector machine, perceptron, and logistic regression \cite{alpaydin} can be considered
as convex approximations to this problem that yield fast gradient descent solutions \cite{bartlett04}.
However, they are also more sensitive to outliers than the 01 loss \cite{bartlett04,icml13optimize,xie2019}
and more prone to mislabeled data than 01 loss \cite{manwani2013noise,ghosh2015making,lyu2019curriculum}.

\subsection{A dual layer 01 loss neural network}
We extend the 01 loss to a simple two layer neural network with $k$ hidden nodes and sign activation that we call the MLP01 loss. This objective for binary classification can be given as

\begin{equation}
\small
\frac{1}{2n}\argmin_{W, W_0, w,w_0} \sum_i (1-sign(y_i(w^T(sign(W^Tx_i+W_0))+w_0)))
\label{obj2}
\end{equation}

where $W \in R^{d\times k}$, $W_0 \in R^k$ are the hidden layer parameters, $w\in R^k, w_0\in R$ are the final layer node parameters, $x_i \in R^d, y_i\in \{+1,-1\}.\forall i=0...n-1$ are our training data, and $sign(v\in R^k)=(sign(v_0), sign(v_1),...,sign(v_{k-1}))$. While this is a straightforward model to define optimizing it is a different story altogether. Optimizing even a single node is NP-hard which makes optimizing this network much harder. Note that our weights are real numbers as opposed to binarized neural networks whose weights are constrained to be +1 and -1 or 1 and 0 \cite{galloway2017attacking,courbariaux2016binarized,rastegari2016xnor}.

\subsection{Stochastic coordinate descent for 01 loss}
We solve both problems with stochastic coordinate descent based upon earlier work \cite{xie2019}. We initialize all parameters to random values from the Normal distribution with mean 0 and variance 1. We then randomly select a subset of the training data (known as a batch) and perform the coordinate descent analog of a single step gradient update in stochastic gradient descent \cite{bottou2010large}. We first describe this for a linear 01 loss classifier which we obtain if we set the number of hidden nodes to zero. In this case the parameters to optimize are the final weight vector $w$ and the threshold $w_0$.

When the gradient is known we step in its negative direction by a factor of the learning rate: $w=w-\eta\nabla(f)$ where $f$ is the objective. In our case since the gradient does not exist we randomly select $k$ features (set to 64, 128, and 256 for MNIST, CIFAR10, and ImageNet in our experiments), modify the corresponding entries in $w$ by the learning rate (set to 0.17) one at a time, and accept the modification that gives the largest decrease in the objective. Key to our search is a heuristic to determine the optimal threshold each time we modify an entry of $w$. In this heuristic we perform a linear search on a subset of the projection $w^Tx_i$ and select $w_0$ that minimizes the objective.

\begin{figure}[h]
  \centering
  \includegraphics[trim=80 50 0 70, clip, scale=.27]{nrows.png}
  \caption{Train and test accuracy of our stochastic coordinate descent on CIFAR10 class 0 vs 1 with different batch sizes (denoted as nrows). \label{nrows}}
\end{figure}

We repeat the above update step on randomly selected batches for a specified number of iterations given by the user. In Figure~\ref{nrows} we show the effect of the batch size (as a percentage of each class to ensure fair sampling) on a linear 01 loss search on CIFAR10 between classes 0 and 1. We see that a batch size of 75\% reaches a train accuracy of 80\% faster than the other batch sizes. Thus we use this batch size in all our experiments going forward.

We also see that for this batch size the search flattens after 15 iterations (or epochs as given in the figure). We run 1000 iterations to ensure a deep search with an intent to maximize test accuracy. For imbalanced data (that appears in the one-vs-all design) we find that optimizing a balanced version of our objective for half the iterations followed by the default (imbalanced) version gives a lower objective in the end.

In a dual layer network we have to optimize our hidden nodes as well. In each of the 1000 iterations of our search we apply the same coordinate update described above, first to the final output node and then a randomly selected hidden node. In preliminary experiments we find this to be fast and almost as effective as optimizing all hidden nodes and the final node in each iteration.

Our intuition is that by searching on just the sampled data we avoid local minima and across several iterations we can explore a broad portion of the search space. Throughout iterations we keep track of the best parameters that minimize our objective on the full dataset. Below we provide full details of our algorithms.

The problem with our search described above is that it will return different solutions depending upon the initial starting point. To make it more stable we run it 32 times from different random seeds and use the majority vote for prediction.

We extend both our linear and non-linear models to a simple one-vs-all approach for multiclass classification. For a dataset with $k$ classes we create $32$ one-vs-all classifiers for each of the $k$ classes. From the 32 models we can obtain frequency outputs for a test point using simple counting and use them as confidence scores for each class $k$. From this we output the predicted class as the one with the highest confidence. This is similar in spirit to the typical convex softmax objective used in convex neural networks except that there we can optimize to obtain the exact confidences given by sigmoid probabilities.

\subsection{Implementation, experimental platform, and image data}
We implement our 01 loss models in Python and Pytorch \cite{pytorch}, and both MLP and SVM (LinearSVC class) in scikit-learn \cite{scikit}. We optimize MLP with stochastic gradient descent that has a batch size of 200, momentum of 0.9, and learning rate of 0.01 (.001 for ImageNet data). We ran all experiments on Intel Xeon 6142 2.6GHz CPUs and NVIDIA Titan RTX GPU machines (for parallelizing multiple votes). Our SCD01 and MLP01 source codes, supplementary programs, and data are available from \url{https://github.com/zero-one-loss/mlp01}.

We experiment on three popular image benchmarks: MNIST \cite{lecun1998gradient}, CIFAR10 \cite{krizhevsky2009learning}, and ImageNet \cite{ILSVRC15}. Briefly MNIST is composed of grayscale handwritten digits each of size $28\times28$ with 60000 training images and 10000 test and CIFAR10 has $32\times32$ color images with 50000 training and 10000 test. ImageNet is a large benchmark with 1000 classes and color images of size $256\times 256$. We extract images from10 random classes and split them to give a training set of 6144 images and test set of 6369. We normalize each image in each benchmark by dividing each pixel value by 255.

\section{Results}
We refer to our linear (no hidden layer) and non-linear (single hidden layer with 20 nodes) models as SCD01 and MLP01 respectively.
As convex counterparts we select the linear support vector machine (with a cross-validated regularization parameter) denoted as SVM and a dual layer 20 hidden node neural network with logistic loss (MLP). For multiclass we use one-vs-all for all four methods. We use the majority vote of 32 runs for our 01 loss models to improve stability and do the same for SVM and MLP by majority voting on 32 bootstrapped samples.
Our SCD01 and MLP01 source codes, supplementary programs, and data are available from \url{https://github.com/zero-one-loss/mlp01}.

We refer to the accuracy on the test data as clean data test accuracy. An incorrectly classified adversarial example is considered a successful attack whereas a correctly classified adversarial is a failed one. Thus when we refer to accuracy of adversarial examples it is the same as $100-attack success rate$. The lower the accuracy the more effective the attack.

\subsection{Clean accuracy and runtimes}
Before going into robustness we first compare the clean test data accuracies and training runtimes of our 01 loss models to their convex counterparts. In Table~\ref{cleanacc} we see that ensembling SVM and MLP models does not improve the test accuracy over single runs, thus we use a shared weight MLP network with 400 nodes on ImageNet to boost accuracy there.
In fact the SVM boundary depends only upon the support vectors and so each ensemble will be the same as long as the support vectors are included. As a reminder we ensemble by taking the majority vote on multiple bootstrapped samples.

The 01 loss models improve considerably in all three datasets by ensembling. This is not too surprising since 01 loss is non-unique and will give different solutions when ran multiple times from different initializations. As a result of ensembling their accuracy is comparable to their convex peers. This makes it easier to compare their robustness since we don't have to worry about the robustness vs accuracy tradeoff \cite{raghunathan2019adversarial,zhang2019theoretically,tsipras2018robustness}.

\begin{table}[!h]
  \caption{Accuracy of  01 and convex counterparts on clean test data \label{cleanacc}}
  \centering
  \begin{tabular}{lllll} \hline
      &  \multicolumn{4}{c}{Single run}\\
               & SVM  & SCD01 & MLP & MLP01  \\
    MNIST &  91.7  &	83.7 & 97.6 & 91.2\\
    CIFAR10 &  39.9 & 30.7 & 50.2 & 34.3 \\

    Mini ImageNet  &  26 &	25 &  32 & 25.5  \\ \hline
     & \multicolumn{4}{c}{32 votes} \\
     & SVM   & SCD01  & MLP  & MLP01 \\
MNIST  & 91.7 &  90.8 & 97.1 & 96 \\
CIFAR10  & 40.2 & 39.7 & 47.4 & 46.4 \\
    &  MLP400 & SCD01  & & MLP01 \\
     &   single run  & &  & \\
 Mini ImageNet    & 36 &  34.7 & & 41\\ \hline

  \end{tabular}
\end{table}

In Table~\ref{runtimes} we show the runtime of a single run of our 01 loss and convex models on class 0 vs all for each of the three datasets. We don't claim the most optimized implementation but our runtimes are still somewhat comparable to the convex loss models. Interestingly the convex models take much longer on complex and higher dimensional images in ImageNet compared to MNIST. Our 01 loss model runtimes are similar on MNIST and CIFAR10 because their sizes are similar. On Mini ImageNet since it has fewer training samples than MNIST and CIFAR10 the 01 loss runtimes are also lower.

\begin{table}[!h]
  \caption{Runtimes in seconds of single runs on class 0 vs all. Mini ImageNet runtimes for are MLP with 400 hidden nodes. \label{runtimes}}
  \centering
  \begin{tabular}{llllll} \hline
               & SVM  & SCD01 & MLP & MLP01  &  \\
    MNIST &  0.8  &	171 & 64 & 875  \\
    CIFAR10 &  80 & 150 & 267 & 838  \\
    Mini ImageNet  & 659 &	 83 & 8564 & 199 \\ \hline

  \end{tabular}
\end{table}

\subsection{White box attacks}
In this section we study white box attacks just for binary classification on classes 0 and 1 in each of the three datasets. We use single runs of each of the four models to generate adversaries using the model parameters. We use the same white box attack method \cite{papernot2016transferability} for SVM and SCD01 since both are linear classifiers: for a given datapoint $x$ and its label $y$ the adversary is $x' = x + \epsilon(-y)sign(w)$ where $sign(w)=(sign(w_1),sign(w_2),...,sign(w_{d}))$ and  $\epsilon$ is the distortion.

For MLP we use the fast gradient sign method (FGSM) \cite{goodfellow2014explaining}. In this method we generate an adversary using the sign of the model gradient $x_{adv}=x+\epsilon sign(\nabla_x f(x,y)$ where $f$ is the model objective and $\nabla_x f(x,y)$ is the model gradient with respect to the data $x$. We generate white box adversaries for MLP01 with a simple heuristic: for each hidden node $w_k$ we modify the input as $x' = x + \epsilon(-y')sign(w_k)$ (where $y'=sign(w_k^Tx)$ is the output of $x$ from the hidden node $w_k$) and accept the first modification that misclassifies $x$ in the final node output. If $x$ is already misclassified or if none of the hidden node distortions misclassify it we distort with a randomly selected hidden node. We provide the full algorithm in the Supplementary Material. We use $\epsilon$ values on MNIST, CIFAR10, and ImageNet that are typical in the literature.

In Table~\ref{whitebox} we see that the clean accuracies of our 01 loss models are comparable to the convex counterparts. As expected adversaries from the source on the same target are effective except for MLP01. More interestingly, while adversaries from SVM and MLP affect each other considerably they are far less pronounced on SCD01 and MLP01. We see this very clearly on CIFAR10 where both SVM and MLP adversaries have almost 0\% accuracy when attacking each other indicating high transferability \cite{papernot2016transferability}. But SVM and MLP adversaries on SCD01 and MLP01 have a far less effect in this dataset. Adversaries from MLP attain a 63.7\% accuracy on MLP01 and 43.5\% on SCD01. Another interesting observation is that adversaries barely transfer between SCD01 and MLP01. We see similar behavior on Mini ImageNet and to a lesser degree on MNIST.

\begin{table}[!h]
  \caption{Accuracy of adversaries made by source in the first column targeting models in the top row  (class 0 vs 1). \label{whitebox}}
  \centering
  \begin{tabular}{lllll} \hline
               & SVM  & SCD01 & MLP & MLP01 \\ \hline
           & \multicolumn{4}{c}{MNIST $\epsilon=.3$}   \\
    Clean &  100 &	99.9 &	100 & 100 \\
    SVM & 11.9 &	8.1	&40.4	&43.5  \\
    SCD01  &  97 &	0	& 98.5 &  53.2   \\
    MLP   & 25.5	 & 16.1 &	31 & 	42.3  \\
    MLP01   &  99.9	& 99.8 &	99.6 &	69.5  \\ \hline
       & \multicolumn{4}{c}{CIFAR10 $\epsilon=.0625$} \\
   Clean &  82.2 &	81.1	& 88.7 &	84.2 \\
    SVM   &  0	& 41.3&	0.5 & 	70.1	\\
    SCD01 &   76 & 	0.8	& 86 &	84.5 \\
    MLP  &  0	& 43.5 &	0.4 & 	63.7 \\
    MLP01 &  81.7	& 80 & 	88.5 &	66.9 \\ \hline
          &        \multicolumn{4}{c}{Mini ImageNet $\epsilon=.0625$}   \\
    Clean &  60.7 &	67.5 & 	66.1 &	68.7 \\
    SVM & 0	& 54.9 &	21.2 &	53.8 \\
    SCD01     &   58.6 &	1	& 65	& 60.3 \\
    MLP   & 0.5	& 42	& 21.6 &	52.3 \\
    MLP01   &  60.8 & 	65.1 & 	65.8 &	35.7 \\ \hline
  \end{tabular}
\end{table}

We argue that the difference of loss functions (01 vs convex) may be responsible for different boundaries and non-transferability. We illustrate this in two examples. First we see the effect of outliers on 01 loss and hinge loss linear classifiers. Recall that the hinge loss is $max(0,1-yw^Tx)$ where $y$ is the label and $w^Tx$ is the prediction of $x$ given by the classifier $w$. In Figure~\ref{white2}(a) the misclassified outlier forces the hinge loss to give a skewed linear boundary with two misclassifications. This happens because even though the two points are misclassified by the red boundary they are closer to it than the single misclassified one is to the blue one. The 01 loss is unaffected by distances and thus gives the blue boundary with one misclassification. Since the two boundaries have different orientations their adversaries are also likely to be different. In a dataset like MNIST where our accuracies are high we don't expect many misclassified outliers and thus boundaries are unlikely to be different. As a result we see that many adversaries transfer between SVM and SCD01 on MNIST. But on CIFAR10 and Mini ImageNet, which are more complex and likely to contain misclassified outliers, we expect different boundaries which in turn gives fewer adversaries that transfer between the two.

Next we see the difference of convex and 01 loss in simple two hidden node network. In Figure~\ref{white2}(b) we see two hyperplanes $u$ and $v$ on the left whose logistic outputs give the hidden feature space on the right. The two hyperplanes $u$ and $v$ represent two hidden nodes in a two layer network. Recall that the logistic activation $\frac{1}{1+e^{-w^Tx}}$ (where $w^Tx$ is prediction of $x$ given by $w$) is similar to 01 loss: for large values of $|w^Tx|$ it approaches 0 or 1 depending upon the sign of $w^Tx$ and approaches $\frac{1}{2}$ as $|w^Tx|$ approaches 0. Thus if we move the red circle towards the "corner" in the original feature space (as shown in Figure~\ref{white2}(b)) its outputs from $u$ and $v$ approach $\frac{1}{2}$ in the hidden space. Consequently it crosses the linear boundary in the hidden space and becomes adversarial. However if the activation is 01 loss the red point remains unmoved in the hidden space. In fact in 01 loss a datapoint's value in the hidden space changes only if we cross a boundary in the original space.

While both examples are not formal proofs they give some intuition of why fewer adversarial examples  transfer between 01 loss and convex loss compared to between just convex. In particular we see that for 01 loss a datapoint becomes potentially adversarial if and only if it crosses a boundary in the original feature space whereas this is not true for convex losses.

\begin{figure}[h]
  \begin{tabular}{l}
  \includegraphics[trim=125 180 200 80,clip,scale=.4]{"SVM_and_01loss_on_outliers"} \\
  \footnotesize
   (a) Point $B$ is misclassified by the blue line but its hinge loss $max(0,1-yw^Tx)$\\
  \footnotesize   in dotted lines is higher than the combined loss of
  points $A$ and $B$ both\\
  \footnotesize
  \footnotesize misclassified by the red boundary. Thus hinge favors the red skewed line.\\

  \includegraphics[trim=70 220 100 10,clip,scale=.4]{"Distortion_on_logistic_on_XOR"} \\
  \footnotesize
 (b) The logistic activation $\frac{1}{1+e^{-w^Tx}}$ in the original space gives a linear\\
\footnotesize  separation in the hidden space. If the red circle moves towards the "corner"\\
\footnotesize  of the boundaries its distance to $u$ and $v$ decreases. This in turn makes its\\
\footnotesize   activation values approach $1/2$ and it is misclassified in the hidden space.\\
\footnotesize  In 01 loss activation
\footnotesize the red circle does not get  affected in the hidden space.

 \end{tabular}
  \caption{Toy example showing different 01 loss and hinge boundaries, and adversarial examples in simple logistic loss network \label{white2}}
\end{figure}

Interestingly we also see MLP01 adversaries don't transfer to the other three models. When applied to MLP01 the adversaries lower its accuracy relative to clean data but to lesser degree than other models attacking themselves. Thus our white box attack method for MLP01 may not be the most powerful one leaving this an open problem.

\subsection{Substitute model black box attacks}
We see that white box adversaries don't transfer between convex and 01 loss but can we attack a 01 loss model with a convex substitute model \cite{papernot2016transferability}? In this subsection we consider binary and multiclass classification on all three datasets. For all four methods we use 32 votes and one-vs-all multiclass classification. We use adversarial data augmentation \cite{papernot2016transferability} to iteratively train a substitute model trained on label outputs from the target model. In each epoch we generate white box adversaries targeting the substitute model with the FGSM method \cite{goodfellow2014explaining} and evaluate them on the target. Note that our black box attack is untargeted, we are mainly interested in misclassifying the data and not the misclassification label. See  Supplementary Material for the full substitute model learning algorithms but it is essentially the method of Papernot et. al. \cite{papernot2016transferability}.

\subsubsection{Convex substitute model}

\begin{figure}[!h]
  \centering
  \begin{tabular}{c}
  \includegraphics[scale=.33]{"MNIST"} \\
  \footnotesize (a) MNIST $\epsilon=.2$ \\
  \includegraphics[scale=.33]{"CIFAR10binary"} \\
   \footnotesize (b) CIFAR10 binary (class 0 and 1) $\epsilon=.0625$ \\
     \includegraphics[scale=.33]{"CIFAR10"} \\
   \footnotesize (c) CIFAR10 $\epsilon=.0625$ \\
   \includegraphics[scale=.33]{"ImageNet"} \\
  \footnotesize (d) Mini ImageNet $\epsilon=0.0625$ \\
 \end{tabular}
  \caption{Multiclass untargeted black box attack with a dual 200 node hidden layer logistic loss network as the substitute model. In epoch 0 are the clean test accuracies. \label{blackbox}}
\end{figure}

In Figure~\ref{blackbox} we see the accuracy of target models on adversaries generated from a convex substitute model. Specifically we use a dual hidden layer neural network with logistic loss and 200 nodes in each hidden layer as the substitute model. Like in the white box attacks we use $\epsilon$ values commonly used on these datasets. In MNIST (Figure~\ref{blackbox}(a)) we see a rapid drop in accuracy in the first few epochs and somewhat flat after epoch 10. We don't see a considerable difference between the 01 loss and convex sibling models on MNIST although MLP01 has the highest accuracy.

On CIFAR10 and Mini ImageNet we see much more pronounced differences. In CIFAR10 binary classification (Figure~\ref{blackbox}(b)) we see that even though both MLP and MLP01 start off with  clean test accuracies of 88\% and 86\% respectively, at the end of the 20th epoch MLP01 has 58\% accuracy on adversarial examples while MLP has 7\% accuracy. We see similar results on Mini ImageNet binary classification in the Supplementary Material. In CIFAR10 multiclass (Figure~\ref{blackbox}(c)) at the end of the 20th epoch the difference in accuracy between MLP and MLP01 is 24\% even though both methods start off with about the same accuracy on clean test data. Similarly on Mini ImageNet MLP01 is 20.7\% higher in accuracy than MLP in the 20th epoch. This is particularly interesting since MLP01 started off with a higher accuracy on Mini ImageNet and in general we expect more accurate models to be less robust \cite{raghunathan2019adversarial,zhang2019theoretically,tsipras2018robustness}. However that is not the case here. Even if we give MLP the advantage of 400 hidden nodes in a shared weight network instead of one-vs-all, its accuracy in the 20th epoch is 13\% lower than MLP01.

We have already seen earlier in white box attacks that adversaries transfer between SVM and SCD01 on MNIST but not so much on CIFAR10 and Mini ImageNet. The same phenomena can be used to explain the results we see here. On MNIST the convex substitute model can attack SCD01 and MLP01 as effectively as convex models due to better transferability on MNIST. Due to poor transferability on CIFAR10 and Mini ImageNet we see that the attack is less effective on SCD01 and MLP01. In the next subsection we explore what happens if the substitute model is SCD01.

\subsubsection{01 loss substitute model}
\begin{figure}[!h]
  \centering
  \includegraphics[scale=.33]{"SCD01"}  \\
  \caption{We use SCD01 single run as the substitute model to attack single runs of the target models between only classes 0 and 1 in CIFAR10. In epoch 0 are the clean test accuracies. \label{blackbox2}}
\end{figure}

In Figure~\ref{blackbox2} we see the results of a black box attack with SCD01 single run as the substitute model attacking single runs of target models. We see that adversaries produced from this model hardly affect any of the target models in any of the epochs. Even when the target is SCD01 and trained with the same initial seed as the substitute the adversaries are ineffective.

Further investigation reveals that the percentage of test data whose labels match between the 01 loss substitute and its target (known as the label match rate) is high but the label match rate on adversarial examples is much lower (shown in Figure~\ref{01lossattack}).

\begin{figure}[h!]
\begin{tabular}{c}
\includegraphics[scale=.33]{"CIFAR10labelmatchsubst"}\\
\footnotesize (a) Percent of same labels between substitute and target on clean data \\
\includegraphics[scale=.33]{"CIFAR10labelmatchadv"}\\
\footnotesize (b) Percent of same labels between substitute and target on adversarial data \\
\end{tabular}
\caption{In (a) we see that SCD01 substitute model can approximate the target as shown in the label match rates between them. But SCD01 sourced adversaries have a lower match rate which indicates that the direction of the SCD01 boundary is very different from the targets and thus its adversaries have very little effect on the target. \label{01lossattack}}
\end{figure}

Thus even though the SCD01 manages to approximate the target boundary its direction is different which gives ineffective adversaries. This is due to the non-uniqueness of 01 loss which makes single run solutions different from each other. Thus as a substitute model in black box attacks 01 loss is ineffective even in attacking itself.

\subsection{Sensitivity to training data distribution and discretized features}
The pixel distributions on MNIST shows that most pixels are near 0 and 1 whereas CIFAR10 pixel values are normally distributed \cite{weiguang2019sensitivity}. Could this be the cause of transferability between 01 loss and convex on MNIST and non-transferability between them on CIFAR10? To test this we discretize the input features by saturation \cite{weiguang2019sensitivity}: for each pixel x and fixed p we saturate it towards 1 or 0 using the formula $x^p = sign(2x-1)\frac{|2x-1|^{\frac{2}{p}}}{2} + \frac{1}{2}$. In Table~\ref{binarize} we compare white box adversary transferability between our four models on the original CIFAR10 dataset between classes 0 vs 1 and a fully binarized one with saturation parameter $p=\infty$. Even after binarizing CIFAR10 adversarial examples do not transfer effectively between 01 loss and convex models, in fact the transferability becomes harder. Thus it is likely that different boundaries caused my outliers are the cause of non-transferability on CIFAR10.

\begin{table}[!h]
  \caption{Accuracy of adversaries made by source in the first column targeting models in the top row  (class 0 vs 1). \label{binarize}}
  \centering
  \begin{tabular}{lllll} \hline
               & SVM  & SCD01 & MLP & MLP01 \\ \hline
       & \multicolumn{4}{c}{CIFAR10 original $\epsilon=.0625$} \\
   Clean &  82.2 &	81.1	& 88.7 &	84.2 \\
    SVM   &  0	& 41.3&	0.5 & 	70.1	\\
    SCD01 &   76 & 	0.8	& 86 &	84.5 \\
    MLP  &  0	& 43.5 &	0.4 & 	63.7 \\
    MLP01 &  81.7	& 80 & 	88.5 &	66.9 \\ \hline
       & \multicolumn{4}{c}{CIFAR10 fully binarized $\epsilon=.0625$} \\
   Clean &  76.6 &	79.1	& 81.2 &	78.6 \\
    SVM   &  0	&  73.9 &	6.5 & 	76.7	\\
    SCD01 &   71.1 & 	62.4	& 78.1 &	78.5 \\
    MLP  &  0.3	& 74.2 &	3 & 	76.3 \\
    MLP01 &  76.7	& 79.4 & 	81 &	73.8 \\ \hline
   \end{tabular}
\end{table}

In fact discretizing the input features increased robustness of convex and 01 loss models (as also seen previously for convex models \cite{panda2019discretization}). Below in Figure~\ref{discrete} we see the accuracy of adversarial examples when we attack models trained on the original input features and binarized ones. The clean test accuracy is slightly lower in the binarized feature space but the robustness is better (particularly for our 01 loss models). In MNIST we see 100\% robustness after binarizing input features.

\begin{figure}[!h]
  \centering
  \begin{tabular}{c}
  \includegraphics[scale=.33]{"mnist-binarize"} \\
  \includegraphics[scale=.33]{"cifar10-binarized"} \\

 \end{tabular}
  \caption{Black box attacks with a dual 200 node hidden layer logistic loss network as the substitute model. In epoch 0 are the clean test accuracies. All models are more robust on the binarized features than the original space. \label{discrete}}
\end{figure}

\subsection{Comparison to convolutional neural networks}
We finally compare black box robustness of our 01 loss models to simple convolutional neural networks. We find the pair of CIFAR10 classes where MLP01 achieves the highest test accuracy (this turns out to be classes 6 vs 8). We then train MLP01 and MLP each with 400 hidden nodes and two convolutional neural networks. We take LeNet \cite{lecun1998gradient} and SimpleNet80 that has the convolutional layers from LeNet followed by a single hidden layer of 80 nodes. The latter is a watered down version of LeNet with fewer hidden layers.

We use a convolutional neural network with four convolutional blocks as the substitute model. In each convolutional block we have a $3\times3$ convolutional kernel followed by max pool and batch normalization. In the first, second, third, and fourth layer we have 32, 64, 128, and 256 kernels and a final layer for the output. Thus the substitute model here is much more sophisticated and powerful than the one used in our experiments above.

In Figure~\ref{cnn} we see that MLP01 has lower but comparable clean test accuracies than all the convex models including its convex counterpart MLP. However, its robustness is much higher than MLP and even surpasses that of SimpleNet80 after the tenth epoch of the substitute model training.

\begin{figure}[!h]
  \centering
  \begin{tabular}{c}
  \includegraphics[scale=.33]{"cnn"} \\
  \includegraphics[scale=.33]{"cnn2"} \\

 \end{tabular}
  \caption{Black box attacks with a convolutional neural network of four convolutional blocks. In epoch 0 are the clean test accuracies. We see that MLP01 is on-par with convolutional networks but MLP has much lower robustness. \label{cnn}}
\end{figure}

\section{Discussion and Conclusion}
Binarized neural networks \cite{galloway2017attacking,courbariaux2016binarized,rastegari2016xnor} have weights and activations constrained to be near +1 and -1 (or 1 and 0) whereas our model weights are real numbers. The purpose of those networks is efficiency as opposed to robustness. Indeed we see in recent work that binarized networks offer marginal improvements in robustness to substitute model black box robustness on MNIST and none in CIFAR10 (see Tables 4 and 5 in \cite{galloway2017attacking} and Table 8 in \cite{panda2019discretization}). In our case we see large improvements over convex (non-binarized) models on CIFAR10 as well as on ImageNet.

There is nothing to indicate that 01 loss models are robust to black box attacks that do not require substitute model training \cite{brendel2017decision,chen2019hopskipjumpattack}. These attacks are, however, computationally more expensive and require separate computations for each example. A transfer based model can be more effective (and dangerous) once it has approximated the target model boundary.

Our work shows a lack of transferability between 01 loss and convex models on datasets like CIFAR10 and ImageNet. As a result they are more robust to substitute model black box attacks than convex models on those datasets. Interestingly the robustness is on-par with simple convolutional models that have the powerful advantage of convolutions which our 01 loss models lack. As future work 01 loss convolutions may be a promising avenue for models with high clean test accuracy and high adversarial accuracy as well.


\subsubsection{%
    \@startsection
    {subsubsection}
    {3}
    {0ex}
    {2.5ex}
    {2.5ex}
    {\normalfont\normalsize\bfseries}
}
\makeatother

\usepackage{graphicx}
\usepackage{marvosym}
\usepackage{amsmath,amssymb,amsfonts}
\usepackage{algorithmic}
\usepackage{graphicx}
\usepackage{textcomp}
\usepackage[T5]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{pifont}
\usepackage{float}
\usepackage{caption}
\usepackage{placeins}
\usepackage{array}
\newcolumntype{P}[1]{>{\centering\arraybackslash}p{#1}}
\newcolumntype{M}[1]{>{\centering\arraybackslash}m{#1}}
\usepackage{multirow}
\usepackage[bookmarks,bookmarksopen,bookmarksdepth=3, bookmarksnumbered]{hyperref}
\hypersetup{colorlinks, citecolor=blue, linkcolor=blue, urlcolor=blue}

\addtolength{\textfloatsep}{-8pt}
\addtolength{\intextsep}{-8pt}

\begin{document}
\title{Vietnamese Word Segmentation\\with SVM: Ambiguity Reduction\\and Suffix Capture}

\titlerunning{Vietnamese Word Segmentation with SVM}

\author{Duc-Vu Nguyen\inst{1,3}\textsuperscript{(\Letter)}\and
Dang Van Thin\inst{1,3} \and \\Kiet Van Nguyen\inst{2,3} \and Ngan Luu-Thuy Nguyen\inst{2,3}}

\authorrunning{D.-V. Nguyen et al.}

\institute{Multimedia Communications Laboratory, University of Information Technology,\\Ho Chi Minh City, Vietnam \\
\email{\{vund,thindv\}@uit.edu.vn}\\ \and
University of Information Technology, Ho Chi Minh City, Vietnam\\
\email{\{kietnv,ngannlt\}@uit.edu.vn} \and Vietnam National University, Ho Chi Minh City, Vietnam}

\maketitle

\begin{abstract}

In this paper, we approach Vietnamese word segmentation as a binary classification by using the Support Vector Machine classifier. We inherit features from prior works such as n-gram of syllables, n-gram of syllable types, and checking conjunction of adjacent syllables in the dictionary. We propose two novel ways to feature extraction, one to reduce the overlap ambiguity and the other to increase the ability to predict unknown words containing suffixes. Different from UETsegmenter and RDRsegmenter, two state-of-the-art Vietnamese word segmentation methods, we do not employ the longest matching algorithm as an initial processing step or any post-processing technique. According to experimental results on benchmark Vietnamese datasets, our proposed method obtained a better $\text{F}_\text{1}\text{-score}$ than the prior state-of-the-art methods UETsegmenter, and RDRsegmenter.

\keywords{Vietnamese Natural Language Processing \and Word Segmentation \and POS Tagging.}
\end{abstract}
\input{sections/1-introduction.tex}
\input{sections/2-method.tex}
\input{sections/3-experiments.tex}
\input{sections/4-conclusion.tex}

\section*{Acknowledgment}
This research is funded by University of Information Technology-Vietnam \mbox{National} University HoChiMinh City under grant number D1-2019-16.

\addcontentsline{toc}{section}{References}
\bibliographystyle{splncs04}

\section{Introduction} \label{introduction}
Word segmentation is an essential task in Vietnamese natural language processing, which has a significant impact on higher processing levels \cite{diend1,ha2003,nguyenetal2006}. Unlike English, white spaces in Vietnamese written text can function as a syllable separator or a word separator. For example, the Vietnamese string ``hiện đại hóa đất nước'' ($\text{modernize}_\text{hiện\_đại\_hoá}$ $\text{country}_\text{đất\_nước}$), which consists of five syllables, is segmented into ``hiện\_đại\_hoá đất\_nước''. Underscores denote the white spaces which function as syllable separator, and white spaces are used for word separation. Vietnamese word segmentation can be considered as a binary classification problem with two classes: underscore and white-space \cite{thainp1}.

Vietnamese is an isolated language and every Vietnamese word has exactly one form \cite{hongphuong08}. Vietnamese words are constituted by one or more syllables. According to the statistics reported in \cite{hongphuong08}, and \cite{phongnt1}, about 16\% of Vietnamese words are single-syllable words and 71\% are two-syllable words. Single-syllable words account for about 81\% of Vietnamese syllables, which means 19\% syllables are not meaningful when standing alone. The string ``loại hình phạt'' (3 syllables) can be segmented as ``loại\_hình phạt'' ($\text{type}_\text{loại\_hình}$ $\text{penalize}_\text{phạt}$) or ``loại hình\_phạt'' ($\text{type}_\text{loại}$ $\text{penalty}_\text{hình\_phạt}$). This phenomenon is called ``overlap ambiguity involving three consecutive syllables'' by the authors in \cite{hongphuong08}. All of the above have created challenges in Vietnamese word segmentation \cite{quynt1}.

We have an observation that solving overlap ambiguity is essential for the Vietnamese word segmentation task. The authors in \cite{hongphuong08} proposed the ambiguity resolver, which uses a bi-gram language model. Their proposal has slightly improved the Vietnamese word segmentation result. Additionally, the binary classifier for the Vietnamese word segmentation trained by the authors in \cite{phongnt1} still causes overlap ambiguity cases. They used rules based on the dictionary and threshold for the classifier in the post-processing phase to handle overlap ambiguities. Experimental results on the benchmark Vietnamese treebank show that the approach of the authors in \cite{phongnt1} outperforms the previous state-of-the-art method of the authors in \cite{hongphuong08}. Therefore, we decided to inspire the idea from the authors in \cite{phongnt1} in handling overlap ambiguities. However, we have assumed how the performance of our method changes when using feature templates to reduce overlap ambiguity cases without post-processing.

From a different point of view, the authors in \cite{nghiem2008} proposed affixes features as a part of the rich feature set in their Vietnamese POS tagging method. Additionally, the authors in \cite{lehongtag10} utilized potential affixes to improve the performance of unknown words (accuracy of 80.69\% on Vietnamese POS tagging task of Vietnamese treebank \cite{thainp1}). In practice, we can not perform part-of-speech (POS) tagging for unknown words if these unknown words can not be constituted by machine annotated word segmentation. Therefore, we decide to study the impact of affixes on the performance of word segmentation. We approach Vietnamese word segmentation with a uni-directional model in which labels are predicted from left to right of a sentence based on a syllable window. Because those labels from the left hand have been predicted, we can utilize information of suffixes to improve Vietnamese word segmentation.

In this paper, we propose a feature-based method using SVM classifier to solve the Vietnamese word segmentation task. Our method considers Vietnamese word segmentation as a binary classification with two classes: underscore and white-space \cite{phongnt1}, in which a majority of feature templates are inherited from the research of the authors in \cite{nguyenetal2006,phongnt1}. Two novel feature templates in our method are to reduce ambiguity cases and capture unknown words containing suffixes. Our proposed method obtained better $\text{F}_\text{1}\text{-score}$ than the previous state-of-the-art methods JVnSegmenter \cite{nguyenetal2006}, vnTokenizer \cite{hongphuong08}, DongDu \cite{luu2012}, UETsegmenter \cite{phongnt1}, and RDRsegmenter \cite{datnq1} measured on the Vietnamese treebank \cite{thainp1} for Vietnamese word segmentation task. Additionally, we used VnMarMoT \cite{nguyenetal2017word} on the result of our word segmentation method. On the benchmark Vietnamese treebank \cite{thainp1}, we achieved result better $\text{F}_\text{1}\text{-score}$ than previous state-of-the-art result \cite{nguyenetal2017word} on Vietnamese POS Tagging task when using predicted segmentation instead of gold segmentation.
\section{Our Approach} \label{wsmethod}
In this section, we first model the word segmentation task. Next, we concentrate on the most critical part of our paper, which is the features extraction phase for the SVM classifier.

\subsection{Problem Representation}
\label{wsprorep}
In the early days of the research on Vietnamese word segmentation, the authors in \cite{diend1} considered Vietnamese word segmentation as a stochastic transduction problem. They represented the input sentence as an unweighted Finite-State Acceptor (FSA). Recently, the syllable-based and white-space-based $\text{representation}$ have been two typical ways of modeling the Vietnamese word segmentation task. The authors in \cite{nguyenetal2006} presented the syllable-based representation. In syllable-based representation, three labels B\_W, I\_W, and O\_W are used to indicate syllables that begin a word, syllables inside a word, and syllables outside a word, respectively. Syllables outside a word are punctuation marks such as full stops, commas, question marks, semicolons, and brackets. The authors  in \cite{thainp1} presented the white-space-based representation. In this representation, computers are expected to differentiate two types of white space: one appears in between two syllables of the same word, denoted by an underscore; the other separates two different words, denoted by a white space.

\begin{figure}[htb]
\centering
\includegraphics[scale=1.14]{images/diagram_1.pdf}
\caption{Example of five-syllable window. In this diagram, the string ``hiện đại hóa đất nước'' ($\text{modernize}_\text{hiện\_đại\_hoá}$ $\text{country}_\text{đất\_nước}$) consisting of five syllables.}
\label{fig:1}
\end{figure}

We decided to use white-space-based representation for our Vietnamese word segmentation method because of its clarity. In our approach, we assign underscore or white space labels for each syllable from left to right of the input sentence by utilizing features in the window of five syllables from the current syllable. An example is given in Fig.~\ref{fig:1}, in which the current syllable is $\text{syllable}_\text{i}$ (``hoá''), and it needs to be classified. The gold label of $\text{syllable}_\text{i}$ is $\text{y}_\text{i}$ (white space). The five-syllable window of the current syllable contains $\text{syllable}_\text{i-2}$ (``hiện''), $\text{syllable}_\text{i-1}$ (``đại''), $\text{syllable}_\text{i}$ (``hoá''),     $\text{syllable}_\text{i+1}$ (``đất''), and $\text{syllable}_\text{i+2}$ (``nước''). Additionally, we can utilize previous labels $\text{y}_\text{i-1}$, $\text{y}_\text{i-2}$ and so on, for feature extraction of the current syllable.

\subsection{Feature Extraction}
\label{feaext}
To represent information of each syllable of the input sentence, we use the count vectorization technique. We divide the extracted features into four groups (four-vectors), which are baseline, more-than-four-syllable word, ambiguity reduction, and suffix feature. To obtain only one vector for the current syllable, we concatenated these four vectors.

We would like to introduce some utility operators and functions that we use to present feature templates for Vietnamese word segmentation. Firstly, the $\text{f}_\text{i}$ symbol represents a function that returns the lowercase-simplified form of $\text{syllable}_\text{i}$. Secondly, $\text{f}_\text{i:i+k+1}$ returns the concatenation of lowercase-simplified forms of adjacent syllables from $\text{syllable}_\text{i}$ to $\text{syllable}_\text{i+k}$ with white-space characters between them. For example given five-syllable window in Fig.~\ref{fig:1}, the value of $\text{f}_\text{i}$ symbol is ``hoá'' and value of $\text{f}_\text{i-1:i+2}$ symbol is ``đại hoá đất''. Besides, we should take syllable types into account for feature extraction. In our research, we inherit from \cite{phongnt1} four syllable types: ``lower'', ``upper'', ``all upper'', and ``other'', which correspond to the following cases: the syllable has all lowercase letters; the syllable has an upper-case initial letter; the syllable has all upper-case letters; and the syllable is a number or other things. In a similar manner as $\text{f}_\text{i}$ and $\text{f}_\text{i:i+k+1}$, we use $\text{t}_\text{i}$ and $\text{t}_\text{i:i+k+1}$ symbols for types of syllables. Lastly, range(i, i+k+1) returns the list of integers ranging $\text{from i to i+k}$ : ($\text{i, i+1, ..., i+k}$).

\subsubsection{Baseline Features}
\begin{table}[htb]
\centering
\caption{Baseline feature templates for word segmentation.}
\label{tab:1}
\begin{tabular}{|@{\hspace{0.2em}}c@{\hspace{0.2em}}|@{\hspace{0.2em}}l@{\hspace{0.2em}}|}
\hline
\textbf{No.} & \multicolumn{1}{c|}{\textbf{Templates}} \\ \hline\hline
1 & \{$\text{f}_\text{j}$ \textbf{for} j \textbf{in} \textbf{range}(i-2, i+3)\} \\ \hline
2 & \{$\text{f}_\text{j:j+2}$ \textbf{for} j \textbf{in} \textbf{range}(i-2, i+2)\} \\ \hline\hline

3 & \{(i-j) \textbf{for} j \textbf{in} \textbf{range}(i-2, i+2) \textbf{if} \textbf{inVNDict}($\text{f}_\text{j:j+2}$)\} \\ \hline
4 & \{(i-j) \textbf{for} j \textbf{in} \textbf{range}(i-2, i+1) \textbf{if} \textbf{inVNDict}($\text{f}_\text{j:j+3}$)\} \\ \hline
5 & \{(i-j) \textbf{for} j \textbf{in} \textbf{range}(i-3, i+1) \textbf{if} \textbf{inVNDict}($\text{f}_\text{j:j+4}$)\} \\ \hline\hline

6 & \{$\text{t}_\text{j:j+2}$ \textbf{for} j \textbf{in} \textbf{range}(i-2, i+2) \textbf{if} ($\text{t}_\text{j}$ \textbf{$\neq$} `LOWER' \textbf{and} $\neg$\textbf{inVNDict}($\text{f}_\text{j:j+2}$))\} \\ \hline
7 & \{$\text{t}_\text{j:j+3}$ \textbf{for} j \textbf{in} \textbf{range}(i-2, i+1) \textbf{if}  ($\text{t}_\text{j}$ \textbf{$\neq$} `LOWER' \textbf{and} $\neg$\textbf{inVNDict}($\text{f}_\text{j:j+3}$))\} \\ \hline\hline
8 & ($\text{t}_\text{i}$ \textbf{=} $\text{t}_\text{i+1}$ \textbf{=} `LOWER' \textbf{and} $\text{f}_\text{i}$ \textbf{=} $\text{f}_\text{i+1}$)? \\ \hline
9 & ($\text{t}_\text{i}$ \textbf{=} $\text{t}_\text{i+1}$ \textbf{=} `UPPER' \textbf{and} \textbf{isVNFamilyName}($\text{f}_\text{i}$))? \\ \hline
10 & ($\text{t}_\text{i}$ \textbf{=} $\text{t}_\text{i+1}$ \textbf{=} `UPPER' \textbf{and} \textbf{isVNMiddleName}($\text{f}_\text{i}$))? \\ \hline
\end{tabular}
\end{table}
\FloatBarrier

\noindent Table~\ref{tab:1} shows all feature templates of the baseline feature group. We have introduced $\text{f}_\text{i}$, $\text{f}_\text{i:i+k+1}$, $\text{t}_\text{i}$, $\text{t}_\text{i:i+k+1}$ symbols, and range(i, i+k+1) function in the last paragraph of subsection~\ref{feaext}, for convenience. \sloppy
In Table~\ref{tab:1}, inVNDict($\text{f}_\text{i:i+k+1}$) returns true if and only if $\text{f}_\text{i:i+k+1}$ is in Vietnamese word dictionary; isVNFamilyName($\text{f}_\text{i}$) returns true if and only if $\text{f}_\text{i}$ is a Vietnamese family name; isVNMiddleName($\text{f}_\text{i}$) returns true if and only if $\text{f}_\text{i}$ is a Vietnamese middle name. Notably, we used the Vietnamese words dictionary\footnote{https://github.com/datquocnguyen/RDRsegmenter/blob/master/VnVocab}, list of Vietnamese family and middle names from research of the authors in \cite{datnq1}.

In this baseline feature group, we inherit two ways of extracting feature with five-syllable window for current syllable from \cite{phongnt1}, which are the lowercase form of syllables (the first and second templates in Table~\ref{tab:1}) and syllable types (the sixth and seventh templates in Table~\ref{tab:1}). We also inherit from \cite{phongnt1} the following features: full-reduplicative word (the eighth template), Vietnamese family name (the ninth template), Vietnamese middle name (the tenth template). Additionally, we check if a conjunction of two up to four adjacent syllables in a window of seven syllables exists in the dictionary (the third, fourth, and fifth templates). These feature templates are inherited from the research of the authors in \cite{nguyenetal2006} except the fifth template.

\subsubsection{More-than-four-syllable Word Features}
\noindent We proposed this feature template based on the research of the authors in \cite{nguyenetal2006} to capture the signal of whether the center syllable is a unit of a more-than-four-syllable word. We expect the classifier can predict more-than-four-syllable words although they are rare in Vietnamese.

\begin{table}[htb]
\centering
\caption{Feature templates for capturing five up to nine syllables words.}
\label{tab:2}
\begin{tabular}{|@{\hspace{0.3em}}c@{\hspace{0.3em}}|@{\hspace{0.3em}}l@{\hspace{0.3em}}|}
\hline
\textbf{No.} & \multicolumn{1}{c|}{\textbf{Templates}} \\ \hline\hline
1 & \{(i-j) \textbf{for} j \textbf{in} \textbf{range}(i-4, i+1) \textbf{if} \textbf{inVNDict}($\text{f}_\text{j:j+5}$)\} \\ \hline
2 & \{(i-j) \textbf{for} j \textbf{in} \textbf{range}(i-5, i+1) \textbf{if} \textbf{inVNDict}($\text{f}_\text{j:j+6}$)\} \\ \hline
3 & \{(i-j) \textbf{for} j \textbf{in} \textbf{range}(i-6, i+1) \textbf{if} \textbf{inVNDict}($\text{f}_\text{j:j+7}$)\} \\ \hline
4 & \{(i-j) \textbf{for} j \textbf{in} \textbf{range}(i-7, i+1) \textbf{if} \textbf{inVNDict}($\text{f}_\text{j:j+8}$)\} \\ \hline
5 & \{(i-j) \textbf{for} j \textbf{in} \textbf{range}(i-8, i+1) \textbf{if} \textbf{inVNDict}($\text{f}_\text{j:j+9}$)\} \\ \hline
\end{tabular}
\end{table}

We recognize that words are containing up to five to nine syllables (we have shown the distribution of unique words according to lengths in Table~\ref{tab:4} of subsection~\ref{corpora}). Thus, we only take into account the concatenation of adjacent syllables with length ranging from five to nine. Lastly, we check all concatenations in the dictionary (the first, second, third, fourth, and fifth templates in Table~\ref{tab:2}).

\subsubsection{Ambiguity Reduction Features}
\label{sepsyl}

\noindent We assume that some syllables tend not to combine with other syllables in constituting a two-syllable word. For the convenience of presentation, we call the syllable with such a tendency ``a separable syllable''. We define a separable syllable as a syllable where the number of occurrences $a_i$ of one-syllable words constituted by that syllable is higher than the number of occurrences $b_i$ of more-than-one-syllable words beginning with that syllable.

\begin{figure}[htb]
\centering
\includegraphics[scale=1.16]{images/diagram_2.pdf}
\caption{Four situations were used in designing ambiguity reduction feature templates.}
\label{fig:2}
\end{figure}

However, we do not consider a syllable as a separable syllable if $a_i + b_i$ is not higher than the average of $a_j + b_j$ of all possible separable syllables because of we want to get rid of an uncertain separable syllable. In Vietnamese, there are some conspicuous separable syllables such as ``những'' (these), ``nhưng'' (but), ``cũng'' (also), ``đây'' (here), and ``với'' (with). The syllable ``văn'' (literature) is a non-separable syllable. For example, syllable ``văn'' usually is the first syllable of many two-syllable words such as ``văn\_bản'' (document), ``văn\_hoá'' (culture), ``văn\_sĩ'' (writer), and ``văn\_kiện'' (documentation).

\begin{table}[htb]
\centering
\caption{Feature templates in case of a current syllable is a separable syllable, and the first previous label is SPACE.}
\label{tab:3}
\begin{tabular}{|@{\hspace{0.3em}}c@{\hspace{0.3em}}|@{\hspace{0.3em}}l@{\hspace{0.3em}}|}
\hline
\textbf{No.} & \multicolumn{1}{c|}{\textbf{Templates}} \\ \hline\hline
1 & \{\textbf{inVNDict}($\text{f}_\text{j:j+2}$) \textbf{for} j \textbf{in} \textbf{range}(i, i+4)\} \\ \hline
2 & \{\textbf{inVNDict}($\text{f}_\text{j:j+3}$) \textbf{for} j \textbf{in} \textbf{range}(i, i+3)\} \\ \hline
3 & \{\textbf{inVNDict}($\text{f}_\text{j:j+4}$) \textbf{for} j \textbf{in} \textbf{range}(i, i+2)\} \\ \hline
4 & \{\textbf{inVNDict}($\text{f}_\text{j:j+5}$) \textbf{for} j \textbf{in} \textbf{range}(i, i+1)\} \\ \hline
\end{tabular}
\end{table}

The noticeable difference between our method from research of \cite{phongnt1} is that we do not use post-processing for dealing with overlap ambiguities.
We proposed a novel way of feature extraction, in which we used boolean variables to record signals of overlap ambiguity cases. In case of the current syllable is a separable syllable and the first-previous label is SPACE (as we can see in Fig.~\ref{fig:2}), we check the concatenations of lowercase-simplified forms of adjacent syllables in Vietnamese dictionary: \{$\text{f}_\text{i:i+2}$, $\text{f}_\text{i+1:i+3}$, $\text{f}_\text{i+2:i+4}$, $\text{f}_\text{i+3:i+5}$\} (the first template in Table~\ref{tab:3}); \{$\text{f}_\text{i:i+3}$, $\text{f}_\text{i+1:i+4}$, $\text{f}_\text{i+2:i+5}$\} (the second template in Table~\ref{tab:3}), \{$\text{f}_\text{i:i+4}$, $\text{f}_\text{i+1:i+5}$\} (the third template in Table~\ref{tab:3}); \{$\text{f}_\text{i:i+5}$\} (the fourth template in Table~\ref{tab:3}. In other words, we check all combinations of every two, three, four, and five adjacent syllables in a five-syllable window (as we can see in Fig.~\ref{fig:2}) in Vietnamese dictionary. This manipulation records all signals of overlap ambiguity cases, which are considered as features. We perform the same manipulation in case of $\text{syllable}_\text{i-1:i+2}$, $\text{syllable}_\text{i-2:i+2}$, and $\text{syllable}_\text{i-3:i+2}$ can be a word (described in Fig.~\ref{fig:2}).

\subsubsection{Suffix Features}

\noindent In Vietnamese, suffixes are tail-affixes (syllables or one-syllable words) that are placed after a word to create larger words \cite{nguyen1997vietnamese}. In our research, we obtain potential suffixes by statistics instead of linguistic knowledge. To obtain potential suffixes, we counted the number of occurrences of the last lower syllables in an out-of-vocabulary three-syllable or four-syllable words. However, we do not consider a syllable as a suffix if its number of occurrences is not higher than the average number of occurrences of all possible suffixes because we want to get rid of uncertain suffixes.

\begin{figure}[htb]
\centering
\includegraphics[scale=1.17]{images/diagram_3.pdf}
\caption{Diagram of suffix case describes whether we choose ``underscore'' or ``space'' for current syllable.}
\label{fig:3}
\end{figure}

We design suffix features with the expectation that the classifier can predict three-syllable or four-syllable words more accurate in case of next syllable is a suffix (as we can see in Fig.~\ref{fig:3}). In other words, we want the classifier to pay special attention to the case where the next syllable is a suffix. In case the next syllable is a suffix, we derive current lowercase-simplified forms of conjunction of adjacent syllables $\text{f}_\text{i-1-off\_set:i+1}$ (the value of ``off\_set'' follows Fig.~\ref{fig:3}) as a feature for classifier. The next syllable $\text{f}_\text{i+1}$ is also treated as a feature. Finally, we derive left and right contexts of the current suffix which are $\text{f}_\text{i-2-off\_set}$, $\text{f}_\text{i-3-off\_set}$, $\text{f}_\text{i+2}$, and $\text{f}_\text{i+3}$ as features. For example, we assume that in the training set we have the string ``xây\_dựng cơ\_sở vật\_chất theo hướng \textbf{hiện\_đại\_hoá}, hoàn\_thành việc xoá lớp\_học tạm\_bợ'' (build facilities towards modernization, finish eradicating unsettled classrooms) and in the test set there is the string ``xây\_dựng nhà dân theo hướng \textbf{kiên\_cố\_hoá} để phòng\_chống lụt\_bão'' (build residential houses following solidified methods to protect against storms and floods). We also assume that in this example  ``\textbf{kiên\_cố\_hoá}'' (solidified) is out-of-vocabulary. The syllable ``\textbf{hoá}'' is a suffix in Vietnamese. In this case, the classifier can not predict the word ``\textbf{kiên\_cố\_hoá}'' in the test set because it is out-of-vocabulary. However, if we leverage the context of this suffix when training, we may predict the word ``\textbf{kiên\_cố\_hoá}''. Because it has the same the left context, uni-gram ``hướng'' and bi-gram ``theo\_hướng'', as the word ``\textbf{hiện\_đại\_hoá}'' (modernized).
\section{Conclusion and Future Work} \label{conclusion}
In this paper, we propose a novel feature-based method using the SVM classifier for Vietnamese word segmentation. Overlap ambiguity and unknown words containing suffixes phenomena are real challenges in Vietnamese word segmentation. We prove that our proposed features, ambiguity reduction and suffix-capturing features, help to improve the performance of word segmentation. Experiments on the benchmark Vietnamese datasets show that our method obtains a higher $\text{F}_\text{1}\text{-score}$ score than state-of-the-art approaches. Finally, according to the experimental results, our Vietnamese word segmentation method has a positive impact on Vietnamese POS tagging. However, the greatest weakness of our ambiguity reduction and suffix features is that we do not care about parts-of-speech information. Therefore, we are planning to refer to the ambiguity solving method of the authors in \cite{ducpd1} for our further research. Our code is open-source and available at {\tt https://github.com/ngannlt/UITws-v1}.
\section{Experiment And Result} \label{experiment}
\subsection{Corpora}
\label{corpora}

\begin{table}[htb]
\centering
\caption{Distribution of unique words according to number of syllables in a word (\%).}
\label{tab:4}
\setlength\tabcolsep{2.7pt}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
\multirow{2}{*}{\textbf{Corpus}} & \multicolumn{6}{c|}{\textbf{Number of syllables in a word}} \\ \cline{2-7}
 & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5-9} & \textbf{$>$9} \\ \hline\hline
VNWordSeg & 38.21 & 53.59 & 07.57 & 00.52 & 00.11 & 00.00 \\ \hline
\begin{tabular}[c]{@{}c@{}}Training dataset\\ of VLSP 2013\\ POSTag\end{tabular} & 31.66 & 58.51 & 07.33 & 02.03 & 00.45 & 00.02 \\ \hline
\begin{tabular}[c]{@{}c@{}}Training dataset\\ of VLSP 2013\\ WordSeg\end{tabular} & 36.49 & 48.92 & 11.54 & 02.63 & 00.41 & 00.01 \\ \hline
\end{tabular}
\end{table}

In our research, we compared the performance of our Vietnamese word segmentation method with published results of other well-known state-of-the-art approaches. Additionally, we studied the impact of our word segmentation method on the performance of the POS tagging task. For these purposes, we evaluated our methods on the VLSP 2013 WordSeg and VLSP 2013 POSTag corpus\footnote{http://vlsp.org.vn/vlsp2013/eval/ws-pos}, which was released for competition. Both of the two corpora are provided for research or educational purpose by the national project on Vietnamese language and speech processing VLSP\footnote{http://vlsp.org.vn}. The training dataset of VLSP 2013 WordSeg consists of 75,389 manually word-segmented sentences (approximately 23 words per sentence on average), which is part of Vietnamese treebank corpora \cite{thainp1}. The test dataset of VLSP 2013 WordSeg consists of 2,120 sentences (approximately 31 words per sentence). The training dataset of VLSP 2013 POSTag consists of 26,999 manually word-segmented sentences (about 22.5 words per sentence on average), which was collected from two sources of the national VLSP project \cite{thainp1} and the Vietnam Lexicography Center\footnote{https://www.vietlex.com}. The test dataset of VLSP 2013 POSTag consists of 2,120 sentences. Specially, we also experimented with the Vietnamese word segmentation corpus, which was provided by the authors in \cite{nguyenetal2006}. In this paper, we temporarily call this corpus ``VNWordSeg''\footnote{{https://www.jaist.ac.jp/\char`\~hieuxuan/vnwordseg/data}}. VNWordSeg consists of 7,807 manually word-segmented sentences (about 19 words per sentence on average), which was divided into 5 folds for later research \cite{nguyenetal2006}.

Table~\ref{tab:4} shows the distribution of unique words according to the number of syllables in a word in VNWordSeg, Training dataset of VLSP 2013 POSTag, and Training dataset of VLSP 2013 WordSeg. The majority of the three datasets are one- and two- syllables words. More-than-four-syllable words are rare in the three datasets. However, words containing from five to nine syllables account for the notable small ratios (0.11\%, 0.45\%, and 0.41\% in VNWordSeg, Training dataset of VLSP 2013 POSTag, and Training dataset of VLSP 2013 WordSeg, respectively). For more detail, there are 136, 305, and 321 separable syllables (described in subsection~\ref{sepsyl}) in VNWordSeg, Training dataset of VLSP 2013 POSTag, and Training dataset of VLSP 2013 WordSeg, respectively.

\subsection{Experimental Setup}
Vietnamese word segmentation has to solve the large-scale classification problem \cite{nguyenetal2006}. Therefore, we decided to use the Linear Support Vector Classification (LinearSVC) \cite{scikit11} as a tool for SVM classifier implementation. The LinearSVC on Python 3 programming language was based on LIBLINEAR  written on C programming language \cite{linearsvc}. By using LinearSVC, we tuned only one parameter, which is the penalty parameter $C$ of the error term in the SVM classifier. We chose the best value of $C$ based on the main evaluation metric $\text{F}_\text{1}\text{}$ score by using gird search experiments, in which value of $C$ can be $0.001$, $0.01$, $0.1$, $1$, $10$, or $100$.
\subsection{Feature Selection Results}

\begin{table}[H]
\centering
\caption{Our word segmentation results using 5-fold cross-validation with all combinations of features (\%). We also re-trained UETsegmenter \cite{phongnt1} and RDRsegmenter \cite{datnq1} methods with the same training datasets and testing datasets with the aim of reference.}
\label{tab:5}
\begin{tabular}{|@{\hspace{0.5em}}l@{\hspace{0.5em}}|c|c|c|c|c|c|}

\hline
\multicolumn{1}{|c|}{\multirow{5}{*}{\textbf{Prior Methods/Features}}} & \multicolumn{6}{c|}{\textbf{Corpus}} \\ \cline{2-7}
\multicolumn{1}{|c|}{} & \multicolumn{2}{c|}{\textbf{VNWordSeg}} & \multicolumn{2}{c|}{\textbf{\begin{tabular}[c]{@{}c@{}}Training Set\\of VLSP 2013\\ POSTag\end{tabular}}} & \multicolumn{2}{c|}{\textbf{\begin{tabular}[c]{@{}c@{}}Training Set\\of VLSP 2013\\ WordSeg\end{tabular}}} \\ \cline{2-7}
\multicolumn{1}{|c|}{}                   & \multicolumn{1}{c|}{\textbf{$C$}} & \multicolumn{1}{c|}{\textbf{$\text{F}_\text{1}\text{-score}$}} & \multicolumn{1}{c|}{\textbf{$C$}} & \multicolumn{1}{c|}{\textbf{$\text{F}_\text{1}\text{-score}$}} & \multicolumn{1}{c|}{\textbf{$C$}} & \multicolumn{1}{c|}{\textbf{$\text{F}_\text{1}\text{-score}$}} \\ \hline\hline
UETsegmenter \cite{phongnt1} &        - &    92.0986 &        - &    97.9820 &        - &    98.7954\\\hline
RDRsegmenter \cite{datnq1} &        - &  93.7811   &        - &   98.3069  &        - &  99.0726  \\\hline\hline
base &        1.0 &    94.4866 &        0.1 &    98.5080 &        0.1 &    99.2630\\ \hline\hline
base + long &        1.0 &    94.4858 &        0.1 &    98.5371 &        0.1 &    99.2762\\ \hline
base + sep &        1.0 &    94.5686 &        0.1 &    98.5647 &        0.1 &    99.2963\\ \hline
base + sfx &        1.0 &    94.4881 &        0.1 &    98.5104 &        0.1 &    99.2669\\ \hline\hline
base + long + sep &        1.0 &    94.5686 &        0.1 &    98.5848 &        0.1 &    99.3024\\ \hline
base + long + sfx &        1.0 &    94.4910 &        0.1 &    98.5434 &        0.1 &    99.2811\\ \hline
base + sep + sfx &        1.0 &    \textbf{94.5752} &        0.1 &    98.5666 &        0.1 &    99.2979\\ \hline\hline
base + long + sep + sfx &        1.0 &    94.5743 &        0.1 &    \textbf{98.5870} &        0.1 &    \textbf{99.3032}\\ \hline
\end{tabular}
\end{table}

To explore the impacts of feature groups on the performance, we conducted feature selection experiments with all combinations of features on three datasets VNWordSeg, Training dataset of VLSP 2013 POSTag, and Training dataset of VLSP 2013 WordSeg. We denoted ``base'', ``long'', ``sep'', and ``sfx'' for baseline, more-than-four-syllable word, ambiguity reduction, and suffixes feature groups, respectively.

Table~\ref{tab:5} presents feature selection results with all combinations of feature groups. More-than-four-syllable word features have impacts on the Training dataset of VLSP 2013 POSTag (0.02+\%) slightly, and Training dataset of VLSP 2013 WordSeg (0.03+\%) in comparison with the baseline groups. The ambiguity reduction features have the most substantial impacts on VNWordSeg (0.08+\%). We can also observe that the suffixes features, which have minimal impacts on three corpora (according to our experiments, there are 2, 4, and 3 suffixes on VNWordSeg, Training dataset of VLSP 2013 POSTag, and Training dataset of VLSP 2013 WordSeg, respectively).

\subsection{Main Results}

Table~\ref{tab:6} compares the Vietnamese word segmentation results of our method with results published in previous research works, using the same training and test datasets. Table~\ref{tab:6} shows that our method achieved the highest precision, recall, and $\text{F}_\text{1}\text{-score}$. Our method obtains 0.29+\% higher $\text{F}_\text{1}\text{-score}$ than RDRsegmenter \cite{datnq1}, which is the recent state-of-the-art approach. It should be noted that the results of vnTokenizer \cite{hongphuong08}, JVnSegmenter \cite{nguyenetal2006} and DongDu \cite{luu2012} were reported by the authors in \cite{phongnt1}.

\begin{table}[htb]
\centering
\caption{Word segmentation results on test dataset of VLSP 2013 WordSeg (\%).}
\label{tab:6}
\begin{tabular}{|l|c|c|c|}
\hline
\multicolumn{1}{|c|}{\textbf{Method}} & \textbf{Precision} & \textbf{Recall} & \textbf{$\text{F}_\text{1}\text{-score}$} \\ \hline\hline
vnTokenizer \cite{hongphuong08} & 96.98 &  97.69 &  97.33 \\ \hline
JVnSegmenter-Maxent \cite{nguyenetal2006} & 96.60 &  97.40 &  97.00 \\ \hline
JVnSegmenter-CRFs \cite{nguyenetal2006} &  96.63 &  97.49 & 97.06 \\ \hline
DongDu \cite{luu2012} & 96.35 & 97.46 & 96.90 \\ \hline
UETsegmenter \cite{phongnt1}  & 97.51 & 98.23 & 97.87 \\ \hline
RDRsegmenter \cite{datnq1} & 97.46 & 98.35 & 97.90 \\ \hline
Our WordSeg \{all features\} & \textbf{97.81} & \textbf{98.57} & \textbf{98.19} \\ \hline
\end{tabular}
\end{table}

Table~\ref{tab:7} shows the Vietnamese word segmentation 5-fold cross-validation results of our method with results published in previous research on the VNWordSeg corpus. Method of the authors in \cite{oanhtran10ws} had been holding the highest $\text{F}_\text{1}\text{-score}$ on VNWordSeg. However, our method obtains the highest recall score on the VNWordSeg corpus.

\begin{table}[H]
\centering
\caption{Word segmentation results using 5-fold cross-validation on VNWordSeg corpus (\%).}
\label{tab:7}
\begin{tabular}{|l|c|c|c|}
\hline
\multicolumn{1}{|c|}{\textbf{Method}} & \textbf{Precision} & \textbf{Recall} & \textbf{$\text{F}_\text{1}\text{-score}$} \\ \hline\hline
Method of the authors in \cite{nguyenetal2006} & 94.00 &  94.45 &  94.23 \\ \hline
Method of the authors in \cite{oanhtran10ws} & \textbf{96.71} &  93.89 &  \textbf{95.30} \\ \hline
Our WordSeg \{base + sep + sfx\} & 94.24 & \textbf{94.92} & 94.58 \\ \hline
\end{tabular}
\end{table}

\subsection{Analyses}

In order to analyze the word segmentation results in more detail, we computed $\text{F}_\text{1}$ score according to number of syllables in a word and three and four syllables words containing suffixes. Additionally, we also re-trained UETsegmenter \cite{phongnt1} with the Vietnamese words dictionary of RDRsegmenter \cite{datnq1} and vice versa. As we can see in Table~\ref{tab:8}, our method obtains higher $\text{F}_\text{1}$ scores than UETSegmener \cite{phongnt1}, and RDRsegmenter \cite{datnq1} on one and two syllables words (1 \& 2). On three-syllable words ($\text{3}^\text{a}$), RDRsegmenter \cite{datnq1} achieves the highest $\text{F}_\text{1}$ score. On four-syllable words ($\text{4}^\text{a}$), UETsegmenter \cite{phongnt1} achieves the highest $\text{F}_\text{1}$ score. Notably, UETsegmenter \cite{phongnt1} used another Vietnamese words dictionary\footnote{https://github.com/phongnt570/UETsegmenter/blob/master/dictionary} which contains all 7 three-and-four-syllable unknown words that they predict correctly. Besides, UETSegmener \cite{phongnt1} can not predict three syllables words containing suffixes ($\text{3}^\text{b}$) when training with the Vietnamese words dictionary of RDRsegmenter \cite{datnq1}. Therefore, we can conclude that RDRsegmenter \cite{datnq1} and our word segmentation method have not solved unknown words containing suffixes badly ($\text{3}^\text{b}$). Lastly, different from the result of UETsegmenter \cite{phongnt1} on three-syllable words ($\text{3}^\text{a}$) and RDRsegmenter \cite{datnq1} on four-syllable words ($\text{4}^\text{a}$), our result on three-syllable and words four-syllable words are not left far away by the highest result.

\begin{table}[H]
\centering
\caption{Word segmentation results ($\text{F}_\text{1}$ score) on \textbf{test dataset of VLSP 2013 WordSeg} according to number of syllables in a word (\%). For convenience, we denote three and four syllables unknown words containing suffixes by \textbf{$\text{3}^\text{b}$} and \textbf{$\text{4}^\text{b}$} (unknown words are detected by checking in the Vietnamese words dictionary of RDRsegmenter \cite{datnq1}). And conversely, we use \textbf{$\text{3}^\text{a}$} and \textbf{$\text{4}^\text{a}$}, indicating three and four syllables words which are not \textbf{$\text{3}^\text{b}$} or \textbf{$\text{4}^\text{b}$}. Notably, we temporarily use \textbf{UETws}, \textbf{RDRws}, and \textbf{UITws} as abbreviations for \textbf{UETsegmenter} \cite{phongnt1}, \textbf{RDRsegmenter} \cite{datnq1}, and \textbf{our word segmentation method using all features}. We also provide proportions of words (\%) in parentheses.}
\label{tab:8}
\resizebox{\textwidth}{!}{%
\begin{tabular}{|c|l|c|c|c|c|c|c|c|c|}
\hline
\multirow{3}{*}{\textbf{\begin{tabular}[c]{@{}c@{}}Vietnamese\\ Dictionary\\ Resource\end{tabular}}} & \multicolumn{1}{c|}{\multirow{3}{*}{\textbf{Method}}} & \multicolumn{7}{c|}{\textbf{Number of syllables in a word}} & \multirow{3}{*}{\textbf{Total}} \\ \cline{3-9}
 & \multicolumn{1}{c|}{} & \textbf{\begin{tabular}[c]{@{}c@{}}1\\ (57.75)\end{tabular}} & \textbf{\begin{tabular}[c]{@{}c@{}}2\\ (40.42)\end{tabular}} & \textbf{\begin{tabular}[c]{@{}c@{}}$\text{3}^\text{a}$\\ (00.74)\end{tabular}} & \textbf{\begin{tabular}[c]{@{}c@{}}$\text{3}^\text{b}$\\ (00.13)\end{tabular}} & \textbf{\begin{tabular}[c]{@{}c@{}}$\text{4}^\text{a}$\\ (00.68)\end{tabular}} & \textbf{\begin{tabular}[c]{@{}c@{}}$\text{4}^\text{b}$\\ (00.05)\end{tabular}} & \textbf{\begin{tabular}[c]{@{}c@{}}5-9\\ (00.22)\end{tabular}} & \\ \hline\hline
\multirow{3}{*}{\begin{tabular}[c]{@{}c@{}}UETws\\ \cite{phongnt1}\end{tabular}} & UETws \cite{phongnt1} & 98.46 & \textbf{97.97} & 79.96 & \textbf{89.74} & \textbf{78.62} & \textbf{100.00} & 21.30 & 97.87 \\ \cline{2-10}
 & RDRws \cite{datnq1} & 98.37 & 97.68 & 85.41 & 89.03 & 74.23 & \textbf{100.00} & 23.60 & 97.74 \\ \cline{2-10}
 & UITws & \textbf{98.59} & 97.96 & \textbf{85.77} & \textbf{89.74} & 77.26 & \textbf{100.00} & \textbf{34.02} & \textbf{98.01} \\ \hline\hline
\multirow{3}{*}{\begin{tabular}[c]{@{}c@{}}RDRws\\ \cite{datnq1}\end{tabular}} & UETws \cite{phongnt1} & 98.47 & 97.90 & 80.40 & 0.00 & \textbf{79.51} & \textbf{26.32} & 34.97 & 97.79 \\ \cline{2-10}
 & RDRws \cite{datnq1} & 98.57 & 97.85 & \textbf{86.30} & 79.19 & 75.74 & 0.00 & 23.60 & 97.90 \\ \cline{2-10}
 & UITws & \textbf{98.82} & \textbf{98.14} & 85.23 & \textbf{80.20} & 78.60 & 0.00 & \textbf{46.83} & \textbf{98.19} \\ \hline
\end{tabular}%
}
\end{table}

Lastly, Table~\ref{tab:9} shows POS tagging performance on the test dataset of VLSP 2013 POSTag with the predicted word segmentation. We re-trained the UETsegmenter tool on VLSP 2013 POSTag. Our Vietnamese word segmentation method has helped VnMarMot \cite{nguyenetal2017word} of increase in performance on VLSP 2013 POSTag with 0.3+\% improvement of $\text{F}_\text{1}$ score by comparing with (VnMarMoT \cite{nguyenetal2017word} using RDRsegmenter \cite{datnq1}) approach.

\begin{table}[H]
\centering
\caption{POS Tagging performance with predicted word segmentation on test dataset of VLSP 2013 POSTag (\%).}
\label{tab:9}
\begin{tabular}{|@{\hspace{0.25em}}l@{\hspace{0.25em}}|c|c|}
\hline
\multicolumn{1}{|c|}{\multirow{2}{*}{\textbf{Method}}} & \multicolumn{2}{c|}{\textbf{$\text{F}_\text{1}\text{-score}$}} \\ \cline{2-3}
\multicolumn{1}{|c|}{} & \textbf{WordSeg} & \multicolumn{1}{l|}{\textbf{POSTag}} \\ \hline\hline
RDRPOSTagger with RDRsegmenter \cite{nguyenetal2017word} & 97.75 & 93.39 \\ \hline
(BiLSTM-CRF + CNN-char) with RDRsegmenter \cite{nguyenetal2017word} & 97.75 & 93.55 \\ \hline
VnMarMoT with RDRsegmenter \cite{nguyenetal2017word} & 97.75 & 93.96 \\ \hline
VnMarMoT \cite{nguyenetal2017word} with Our WordSeg \{all features\} & \textbf{98.06} & \textbf{94.27} \\ \hline
\end{tabular}
\end{table}