Concept for a Technical Infrastructure for Management of Predictive Models in Industrial Applications

With the increasing number of created and deployed prediction models and the complexity of machine learning workflows we require so called model management systems to support data scientists in their tasks. In this work we describe our technological concept for such a model management system. This concept includes versioned storage of data, support for different machine learning algorithms, fine tuning of models, subsequent deployment of models and monitoring of model performance after deployment. We describe this concept with a close focus on model lifecycle requirements stemming from our industry application cases, but generalize key features that are relevant for all applications of machine learning.

Motivation
In recent years, applications of machine learning (ML) algorithms grew significantly, leading to an increasing number of created and deployed predictive models. The iterative and experimental nature of ML workflows further increases the number of models created for one particular ML use case. We require so called model management systems to support the full ML workflow and to cover the whole lifecycle of a predictive model. Such a model management system should improve collaboration between data scientist, ensure the replicability of ML pipelines and therefore increase trust in the created predictive models. To highlight the need for model management systems we follow a typical machine learning process and identify shortcomings or problems occurring in practice, that could be mitigated by a model management system. 1 The final publication is available at https://link.springer.com/chapter/10.1007/ 978-3-030-45093-9 32 arXiv:2107.13821v1 [cs.

Model management in the machine learning workflow
A typical ML workflow, as described by the CRISP-DM data mining guide [1] and illustrated in Figure 1, is a highly iterative process. Business Understanding and Data Understanding is gained through assessment of the particular ML use case and the initial gathering and analysis of data. Meticulous Data Preparation, cleaning of data and feature engineering, is an important prerequisite for good modeling results, as selection and data transformation are critical for successful application of ML methods. In the subsequent Modeling task, different ML frameworks and algorithms are applied. Therein, it is necessary to test a variety of algorithm configurations. It is common that the data preparation step and modeling step are repeated and fiddled with, until satisfying results are achieved.  Fig. 1. Visualization of the typical machine learning workflow as described in the CRISP-DM 1.0 Step-by-step data mining guide [1] Finally, when a suitable model is discovered, it is deployed to the target system. Typical ML workflows often end with this step. However, because of changes to the system's environment, i.e. concept drift, the model's predictive accuracy can deteriorate over time. Information about the several ML workflow steps that led to the deployed model might be forgotten, lost, or scattered around different files or knowledge systems. Model management systems should aid by tracking the complete ML workflow and saving every intermediate artefact in order to ensure replicability.

Managing the model lifecycle -industrial applications
Predictive models are increasingly deployed to so-called edge computing devices, which are installed close to the physical systems, e.g. for controlling production machines in industry plants. In such scenarios, predictive models usually need to be tuned for each particular installation and environment, resulting in many different versions of one model. Additionally, models need to be updated or re-tuned to adapt to slowly changing systems or environmental conditions, i.e. concept drift. Once a tuned model is ready for deployment, the model needs to be validated to ensure the functional safety of the plant. The heterogenous landscape of ML frameworks, their different versions and software environments, further increases difficulty of deployment. We argue that model management system need to ML should borrow well established concepts from software development, i.e. continuous integration, continuous delivery, to cope with fast model iterations, and to cover the whole model lifecycle.
In a subsequent phase, the deployed model's prediction performance, during production use, needs to be monitored to detect concept drift or problems in the physical system. Continuous data feedback from the physical system back to the model management system provides additional data for training, and future model validation.

Related work
Kumar et al. [5] have fairly recently published a survey on research on data management for machine learning. Their survey covers different systems, techniques and open challenges in this areas. Each surveyed project is categorized into one of three data centric categorizations: ML in Data Systems cover projects that combine ML frameworks with existing data systems. Projects like Vertica [7], Atlas [9] or Glade [2] integrate ML functionality into existing DBMS system by providing user-defined aggregates that allow the user to start ML algorithms in an SQL like syntax, and provide models as user-defined functions. DB-Inspired ML Systems describe projects that apply DB proven concepts to ML workloads. Most projects apply these techniques in order to speedup or improve ML workloads. This includes techniques like asynchronous execution, query rewrites and operator selection based on data clusters, or application of indices or compression. ML.NET Machine Learning as described by Interlandi et al. [4] introduces the so called DataView abstraction which adapts the idea of views, row cursors or columnar processing to improve learning performance.
ML Lifecycle Systems go beyond simply improving performance or quality of existing ML algorithms. These systems assist the data-scientist in different phases of the ML workflow. In their survey, Kumar et al. [5] further detail the area of ML Lifecycle Systems and introduce so called Model Selection and Management systems. These systems assist not one but many phases of the ML lifecycle.
One representative of Model Selection and Management systems is described by Vartak et al. [8]. Their so called ModelDB, is a model management system for the spark.ml and scikit-learn machine learning frameworks. ModelDB provides instrumented, wrapped APIs replacing the standard Python calls to spark.ml or scikit-learn. The wrapped method calls the ML framework functionality and sends parameters or metadata of the modelling process to the ModelDB-Server. This separation allows ModelDB to be ML framework agnostic, given that the ModelDB API is implemented. Their system provides a graphical user interface (GUI) that compares metrics of different model versions and visualizes the ML pipeline which lead to each model as a graph. However, ModelDB only stores the pipeline comprised of ML instructions that yielded the model. ModelDB does not store the model itself, training data, or metadata about the ML framework version. External changes to the data, for example, are not recognized by the system and could hamper replicability.
Another representative, ProvDB, as described by Miao et al. [6] uses a version control system (e.g. git) to store the data and script files and model files created during the ML lifecycle in a versioned manner. Therein, scripts can be used for either preprocessing or to call ML framework functionalities. Git itself only recognizes changes to the files and therefore treats changes to data, script or model files equally. In order to store semantic connections between e.g. data versions and their respective preprocessing scripts or the connection between data, the ML script and the resulting model, ProvDB uses a graph database (e.g. Neo4j) on top. Provenance of files and metadata about the ML workflow, stored in the graph database, can be recorded through the ProvDB command line or manually defined through the file importer tool or the ProvDB GUI. This design allows ProvDB to support data and model storage of any ML framework given that these artefacts can be stored as files and are committed to git. However, automatic parsing and logging of instructions to the ML framework only works in the ProvDB command line environment. Inside the ProvDB environment, calls to the ML framework and their parameters are first parsed and then forwarded which requires ML frameworks that provide a command line interface.
Similar to ProvDB we aim to store all artefacts created during the ML lifecycle and allow the definition of semantic connections between these artefacts. Our approach differs from ProvDB as we plan to use a relational database for the data persistence and aim to develop a tighter integration to the actual ML framework, comparable to the API approach of ModelDB. Moreover, we aim to support tuning, automated validation and deployment of ML models and provide functionality to monitor performance of deployed models.
In their conclusion Kumar et al. [5] identify the area of "Seamless Feature Engineering and Model Selection", systems that support end-to-end ML workflows, as important open areas in the field of data management for machine learning. They highlight the need for fully integrated systems that support the machine learning lifecycle, even if it only covers a single ML system/framework.

Design and architecture
In the following section we describe our concept of a model management system. This system is designed to be ML framework agnostic. Integration into the open source ML framework HeuristicLab 1 , which is being developed and maintained by our research group, will serve as a prototypical template implementation. Figure 2 serves as illustration of the data-flows and individual components of the model management system described in the following sections. The described system can be used either locally by a single user or as a centralized instance to enables collaboration of different users. The model management system is described by the following key features: -Centralized and versioned data storage for all artefacts of the ML framework.
-Definition of semantic connections between the different artefacts.
-Storage API for ML framework integration.
-Automatic evaluation of models on semantically connected snapshots.
-Bundling of models for deployment and subsequent monitoring.  Fig. 2. Visualization of interaction between the envisioned model management system, a machine learning framework (e.g. HeuristicLab) and an external physical target system.

Data management
The accuracy of prediction models, achievable by different ML algorithms, depends on the quality of the (training) data. Errors in data recording, or wrong assumptions made during business-and data-understanding phase affect data preparation and are therefore carried over to the modeling phase and will subsequently result in bad models. Though, bad models are not solely caused by poor data quality, as a model can become biased if certain information, contained in the dataset, was then not present in the training portion of the ML algorithm. These problems are especially hard to combat or debug if the connection between a specific model version and its training data was not properly documented or if the information is scattered around different knowledge bases and therefore hard to connect and retrieve. A model management system should therefore provide an integrated, versioned data-storage. ML frameworks and supported preprocessing tools need to be able to query specific version of data, i.e. snapshots, from the database. Preprocessing tools also need to be able to store modified data as new snapshots. Additionally, data scientists should be able define semantical relations between snapshots. This connections can be used to mark compatible datasets that stem from similar physical systems or are a more recent data recording of the same system, as also discussed in Section 3.4. In such cases a model management system could automatically evaluate a model's prediction accuracy on compatible snapshots. The same semantic connections can be used to connect base datasets with the specific datasets from physical systems for model tuning. When a new, better model on the base dataset is created the model management system can automatically tune it to all connected specific datasets.

Model management
The section model management loosely encompasses all tasks and system components related to the ML model, this includes the ML training phase and the resulting predictive model, fine tuning the model to fit system specific data sets, evaluation of models (on training sets or physical system data) and the subsequent deployment of validated models.
Model creation or model training In order to conveniently support the ML workflow, a model management system should impose no usability overhead. In case of the Modeling phase this means that necessary instrumentation of ML framework methods, to capture ML artefacts, should not affect usage or require changes in existing pipelines/scripts. Therefore, method signatures of the ML framework must stay the same. Functionally, the model management system has to be able to capture all ML framework artefacts, configurations and metadata necessary to fully reproduce the training step. In our concept for a model management system we intend to provide an easy to use API for capturing artefacts that can be integrated by any ML framework. The resulting knowledge base of tried and tested ML algorithm parameters for a variety of ML problems can serve as a suggestion for suitable configurations for future experiments, or meta-heuristic optimization for problem domains.
Model evaluation Besides ensuring replicability of the ML workflow, a model management system should also aid in the evaluation of models. In practice we require evaluation of a model's prediction accuracy not only on the test section of data, but also on "older" data snapshots, to evaluate whether a new model actually has achieved equal or better predictive quality than it's predecessor.
Similarly, functional safety of the prediction models in their production environments can be ensured by automated validation of models on past production data or on simulations of the physical system. This model evaluation process can be seen as the analogy of unit tests in the continuous development process. Facilitation of the semantic connections between datasets provides the necessary information these evaluation steps.
Model tuning Predictive models often need to be tuned in order to describe a specific target system. Model tuning refers to the task of using ML algorithms to adapt an existing predictive model, or model structure, to fit to a specific previously unknown environment. Model tuning can be used to fit an existing model to its changed environment after a concept drift was detected. Likewise, tuning can improve or speedup the ML workflow by using an existing, proven model as a starting point to describe another representative of a similar physical system. If a model type and ML framework support tuning, the model management system can trigger this tuning process and subsequent evaluation automatically. This process reassembles automated software build processes. If concept drift is detected or automated model tuning is enabled for a physical system, the model management system can take action autonomously.

Model deployment
The model management system should aid in the deployment of prediction models. This means providing the model bundled with all libraries necessary for execution of the model. The heterogenous landscape of ML frameworks and their different versions and software environments can cause compatibility issues on the target system. Crankshaw et al. [3] describe a system called Clipper, that solves this problem by deploying the model and its libraries bundled inside Docker images. This technique could also aid in distribution of the model, as the Docker ecosystem includes image management applications, that host image versions and provide deployment mechanisms. By applying this technique, the model management system can ensure executability and solve delivery of models to the target system.

Data feedback
Our concept for a model management system includes a data gathering component to capture feedback in the form of production data from the edge device.
Monitoring of the model's prediction accuracy during deployment and evaluation of the model on the production data enables the model management system to detect concept drift and to tune and subsequently re-deploy tuned models. The software necessary for monitoring and data gathering can be deployed to the edge device by addition to the bundle created during model deployment.

Summary
In this work we described our technological concept for a model management system. We describe the different features and components that are necessary to fully capture the machine learning lifecycle to ensure replicability of modeling results. Application of predictive models in industrial scenarios provides additional challenges regarding validation, monitoring, tuning and deployment of models that are addressed by the model management system. We argue that advances in model management are necessary to facilitate the transition of machine learning from an expert domain into a widely adopted technology.


Supervised Learning in the Presence of Noise: Application in ICD-10 Code Classification

ICD coding is the international standard for capturing and reporting health conditions and diagnosis for revenue cycle management in healthcare. Manually assigning ICD codes is prone to human error due to the large code vocabulary and the similarities between codes. Since machine learning based approaches require ground truth training data, the inconsistency among human coders is manifested as noise in labeling, which makes the training and evaluation of ICD classifiers difficult in presence of such noise. This paper investigates the characteristics of such noise in manually-assigned ICD-10 codes and furthermore, proposes a method to train robust ICD-10 classifiers in the presence of labeling noise. Our research concluded that the nature of such noise is systematic. Most of the existing methods for handling label noise assume that the noise is completely random and independent of features or labels, which is not the case for ICD data. Therefore, we develop a new method for training robust classifiers in the presence of systematic noise. We first identify ICD-10 codes that human coders tend to misuse or confuse, based on the codes' locations in the ICD-10 hierarchy, the types of the codes, and baseline classifier's prediction behaviors; we then develop a novel training strategy that accounts for such noise. We compared our method with the baseline that does not handle label noise and the baseline methods that assume random noise, and demonstrated that our proposed method outperforms all baselines when evaluated on expert validated labels.

Introduction
International Classification of Diseases (ICD) is a standard classification system for capturing and reporting diagnosis and medical conditions in clinical records for revenue cycle management in healthcare. It includes codes for diagnoses, symptoms, and procedures. The latest version of ICD, ICD-10, has over 70,000 codes. ICD-10 coding system consists of alphanumeric values with up to seven characters (e.g., R91.8), which are structured in a tree-like hierarchy 1. Addition of each character moves a code from one level to another in the hierarchy.
In Radiology, depending on the content, one or multiple ICD codes may be assigned to a single clinical record. Manually assigning ICD codes to health records is time-consuming due to large volume of health records. Furthermore, manual code assignment is a challenging task due to the large code vocabulary and the similarities between codes, which results in inconsistencies among human coders. Previous studies have shown that the inter-assessor agreement rate between human coders is merely 50% (American Hospital Association et al., 2003;Horsky et al., 2017;Stausberg et al., 2008).
Recently, Computer-assisted Coding (CAC) systems have gained popularity as they utilize machine learning for ICD code prediction. Nevertheless, the inconsistency in human-driven labeling poses challenges in training and evaluation of ICD classifiers since the ground truth for training and evaluation may not be reliable.
This paper investigates and categorizes the noise in manually-assigned ICD codes, studies the effect of noisy data in the model training and evaluation, and finally, proposes a method to train robust ICD classifiers in the presence of labeling noise.
In order to study the noise in ICD-10 coding, we used a relatively large dataset of radiology notes with corresponding ICD-10 codes from mul- tiple clinical sites. We discovered systematic noise by analyzing labels assigned by two different human coders. One most prevalent noise pattern is over-using the codes defined for generic symptoms where the codes defined for specific diagnoses should have been used. Since rebuilding training data by expert coders to avoid such errors in labeling is expensive, it is desired to account for such noise in the ICD-10 classifier training that is capable of learning through noisy labels. Most of the existing methods for handling label noise assume that the noise is completely random and is independent of features or labels, which is not the case in ICD-10 data.
In this work, we propose a new method for training robust classifiers in the presence of systematic noise. We first identify ICD-10 codes that human coders tend to misuse or confuse, based on the codes' descriptions, the types of the codes, and baseline classifier's prediction behaviors; we then develop a new training strategy that accounts for such noise. We compared our method with the baseline that does not handle label noise and the baseline methods that assume random and independent noise, and demonstrated that our proposed method outperforms all baselines when evaluated on expert validated labels.
Our contributions are as follows: 1. We identify systematic noise in ICD-10 codes annotated by human coders, and measure its negative impact on machine learning model's performance.
2. We propose a method for detecting systematic noise automatically.
3. We propose a robust training method to train classifiers on noisy labels and gain improvements when evaluated on validated labels.

Analyzing ICD-10 Coding Noise
In order to handle the labeling noise during classifier training, we first analyze the nature of noise by collecting data with both the original noisy labels and validated/corrected labels by expert coders.

Validating annotation
We took a large collection of Radiology notes from multiple clinical sites annotated with ICD-10 codes (the latest version) by several human coders. We randomly sampled notes using stratified sampling to make sure different code sets are represented in the sample, and then asked expert coders to validate existing code annotations and make corrections if necessary. Each radiology note is reviewed by at least two expert coders. If the two expert coders disagree, a third expert coder who is more experienced is asked to make the final judgment. A total of 29,826 Radiology notes were validated through the schema described above. For noisy pattern analysis (section 2), all the validated notes are used. For the model training and evaluations (section 3), we selected one of the clinical sites and used only the notes from the selected site, which has 1,688 notes.
We call the resulting code labels validated labels in contrast to the original labels. Accordingly the corresponding coders would be referred to as validating coders and original coders. In this research, we refer to the original labels as noisy labels and validated labels as clean labels even though the validated labels still may not be 100% accurate.

Condition
Ratio

Noise patterns
During the validation process, each note is assigned to two or more validating coders. We can measure inter-coder agreement rate between the validating coders as well as the agreement rate between the original coders and the validating coders. Given two coders and the set of the notes that are annotated by the both coders, the agreement rate is the rate of the notes that two coders annotated exactly the same code set. The average agreement rate between the original and validating coders is 65%, and the average agreement rate between the two validating coders is 72%. Note that validating coders can see the original annotations, which may have contributed to the higher agreement rate. Second, we categorize the agreement and disagreement between the original code set S o and the validated code set S v as follows: • other: all other cases Table 1 shows an example for each category as well as the percentage of each category in our dataset. We can see that the most common form of disagreement is "replacement". So we focus on notes from this category in which one code is replaced with another, and we want to see how similar or confusing the code pairs are. We leverage the ICD-10 code hierarchy, and check how each pair of codes differ in the hierarchy by computing the length of the common prefixes in the code.
The top level of the hierarchy, indicated by the first letter, is referred to as chapter 1 . The first three characters together are referred to as category.
Each additional character adds more specificity to the code definition. Table 2 shows the breakdown results based on the common characters for the "replacement" type of disagreement. The code pairs under completely different chapters (first character) or different categories (three characters) contribute to 67% of the disagreement, and the disagreement on minor details is only 33%. This is somewhat surprising as one might expect coders tend to disagree with the subtle differences at the lower levels of the hierarchy (characters four, five or six). Further investigations show that among the 40.9% of the cases that have different chapters, 19.4% involve the "R" chapter in one of the codes. The "R" chapter stands for "symptoms, signs, and abnormal clinical and laboratory findings, not elsewhere classified" (DHHS, 2019).  butions. We then average over all the codes and report mean average precision (MAP). Because for each test instance we have both the original labels and the validated labels, we compute two MAP scores treating each of them as ground truth, in order to understand how labeling noise affects classifier evaluation. Note that classifier training is always performed based on the original labels.

Observations
MAP of top 100 ICD-10 codes is measured on the development set. The MAP of the classifiers evaluated against the original labels is 88.5%. The MAP decreases to 48.1% when evaluated against the validated labels. Figure 2 shows the model's average precision on each code evaluated on the original and validated labels. For several ICD-10 codes, scores on the validated labels are much lower than scores on the original labels. Table 3 summarizes the score changes on all ICD-10 codes. While the overall MAP change is about 40%, only 32 ICD-10 codes show significant changes that are larger than 20%. This indicates that score changes are not uniform across all ICD-10 codes, and rather it is concentrated on a few codes.
Previous studies show that if the label noise is random and independent of features or labels, classifier's performance evaluated on cleaned labels should be higher than it's performance evaluated on noisy labels (Patrini et al., 2017;Ma et al., 2018;. Here we observe the opposite trend. This suggests that the noise in our data may not be random and independent, but systematic. We inspected the cases on which validating coders disagree with the original coders and observed that there exists systematic noise in the original labels and is fixed by validating coders. One prevalent noisy pattern is that the original coders often assign symptom ICD-10 codes when diagnosis ICD-10 codes should have been assigned. In ICD-10, there are codes that are used to indicate specific diagnoses (e.g., effusion on knee, spinal stenosis or intervertebral disc displacement), as well as codes that indicate signs or symptoms (e.g., fever, pain in back or cough). The official ICD-10 guideline says that "Codes that describe symptoms and signs, as opposed to diagnoses, are acceptable for reporting purposes when a related definitive diagnosis has not been established (confirmed) by the provider." (DHHS, 2019). Among the 32 ICD-10 codes that have AP score changes above 20%, 16 codes are symptom codes. When the classifier is trained on labels with such systematic noise, it learns to also overpredict symptom codes on cases that should have been assigned diagnosis codes, and therefore, receives low AP when evaluated on validated codes. For example, table 4 shows the top 10 instances ranked by classifier's prediction confidence for the code M54.5 ("Low back pain"). Many instances with false positive M54.5 predictions have in their ground truth specific diagnosis codes that are related to the M54.5 symptom code.  While diagnosis-symptom confusion is most common in this dataset, there are other types of code pairs that may cause confusion. In general, we refer to the code we are trying to predict as the target code and the code that cause confusion as the confusion code. In the noisy dataset, some instances are wrongly annotated with the target codes while their clean labels include the confusion codes. This causes the model to incorrectly predict the target code on instances where confusion codes should have been assigned. In the previous example, the symptom codes are the target codes and the diagnosis codes are the confusion codes.
The opposite scenario where the specific diagnosis is the target code and the symptom codes are confusion codes is also possible but not as com-mon, and therefore, we do not handle such scenario in this paper.

Handling Label Noise in Training
Our proposed training method first identifies which codes are often confused with our target codes based on the validated codes of the development split, and then supervised those codes (confusion codes) along with the target codes so that the model is able to better distinguish them. When the codes for generic symptoms are the target codes, the codes for specific diagnoses work as confusion codes.

Selecting confusion codes
For each of the target codes that are identified to have systematic noise, we select confusion codes based on the code descriptions and the model's behavior on the development set.
First, for each target code, we train an initial binary classifier on original labels as described in the previous section, and we apply it to each instance in development split to generate a label probability, based on which can rank all instances w.r.t. this target code. From the top-k instances, we further select those instances on which the classifier generates false positive predictions w.r.t. the target code. We used k value of 50. Next, we check which other codes are assigned to these selected instances by validating coders and consider them as candidate codes.
Let y (i) be the code set for i th ranked instance. Let p i be the model predicted probability of i th instance containing the target code t. Candidate code set C is given as Then, each candidate code c is scored by the sum of the reciprocal rank of the instances that is annotated with candidate code.
where 1 is the indicator function. We then keep the codes whose scores are larger than 0.1. Next, the selected candidate codes are filtered by their locations in the hierarchy, based on two simple heuristics: 1) accept code if the candidate code is from the same chapter as the target code; 2) accept code if either the candidate code or the target code is from chapter "R" or "S". Our intuition Code Description M54.5 Low back pain M41.86 Other forms of scoliosis, lumbar region M47.816 Spondylosis without myelopathy or radiculopathy, lumbar region 1 M47.817 Spondylosis without myelopathy or radiculopathy, lumbosacral region 2 M48.061 Spinal stenosis, lumbar region without neurogenic claudication M51.26 Other intervertebral disc displacement, lumbar region M51.16 Intervertebral disc disorders with radiculopathy, lumbar region Table 5: ICD code descriptions for M54.5 and codes for specific diagnosis that are related to M54.5. 1 lumbar: relating to the lower part of the back 2 lumbosacral: relating to the lumbar and sacral regions or parts is that the codes from the same chapters are more likely to be confusing. The "R" chapter (symptoms, signs and abnormal clinical and laboratory findings, not elsewhere classified) and the "S" chapter (injury, poisoning and certain other consequences of external causes) could act as wastebasket chapters in the Radiology domain and coding professionals often struggle with these codes (Butler, 2016). This design agrees with the observation in section 2.2 that the most confusing pairs appear in the same or limited chapters. Even though these two heuristics are very simple, we observe them to work well when combined with the first score-based filtering.

Modified supervision
As noted in previous sections, the classifier training data contains only the noisy labels. As a result, we explicitly model the label noise during model training. We map each of the training instances to one of the following three classes based on its original labels.
• class 0: None of the target code or confusion codes is in original labels.
• class 1: The target code is in original labels, and no confusion code is in original labels.
• class 2: At least one confusion code is in original labels.
We separate class 2 from class 1 because instances in class 2 are often mislabeled with the target code. We then train a standard 3-class logistic regression classifier using the mapped classes. During prediction, we use the prediction score for class 1 to determine the target code and ignore scores from class 0 and class 2.

Experiments
We evaluated the proposed training method on the 16 of ICD-10 codes which we identified to have label noise problems (section 2).

Baselines
We compare our method with the following baselines: • Vanilla: standard logistic regression trained on the original noisy labels • Modified label: if a training instance has both target code and confusion codes in the original labels, only keep the confusion codes • Dev set fine-tuned: first train the classifier on training set using original labels, and then fine tune on development set using validated labels • Dev set trained: train a classifier on the small development set using the validated codes • MLP + BR: train a multi-layer perceptron with one hidden layer and (n + 1)-output nodes for one target code and n confusion code. This model does not assume exclusive relations between codes and is expected to capture certain code dependencies as the hidden layer is shared.

Results
A summary of different classifiers' performance on the test set is given in Table 6 using two versions of labels: the original codes and the validated codes. The methods' performance on validated labels and the original labels are negatively correlated, matching our expectation that the noise is systematic -classifiers mimicking human mistakes will match original labels well but not validated labels.  Table 6: MAP for all the methods. The ultimate goal is to get a high score on validated labels. The score on original labels are listed only for reference. Statistical significance for a few pairs are: 9.9% between vanilla and proposed on validated, 12.4% between modified label and proposed on validated and 39.2% between modified label and proposed on original.

Method
When evaluated against validated codes, our proposed method outperforms the rest.
The results also show that the methods which explicitly consider confusion codes (modified label, proposed and MLP+BR) perform better than those who do not. Furthermore, the proposed method, which trains the model with 3-way categorical cross-entropy shows better score over using 2-way cross-entropy loss (modified label). This shows that our method does more than fixing training labels using a simple rule. MLP+BR is better than the vanilla but worse than our model. This shows that simply feeding relevant label information to a neural network without imposing a strong inductive bias based on the noise pattern does not guarantee successful training.
While not listed in table, we have also tried a noise-handling approach such as symmetric crossentropy , which showed worse score (63.3) than the vanilla method (64.8) 2 .
Finally, dev set trained performs poorly due to the limited training data. dev set fine-tuned outperforms vanilla but cannot match the methods that consider confusion codes.

Discussion
Several independent studies have reported that the inter-coder agreement for clinical billing is low. American Health Information Management Association (AHIMA) reported that the regular trained coders have about 42% accuracy evaluated against experts' annotations (American Hospital Associ-ation et al., 2003). In a study on ICD coding for ambulatory visits, it is reported only half of entered codes were actually appropriate and about a quarter codes were missing (Horsky et al., 2017).
The most commonly used datasets for ICD classification are MIMIC-III (Johnson et al., 2016) and CLEF (Névéol et al., 2017). To the best of our knowledge, no subsequent label quality check or cleaning has been performed on these public datasets, and therefore, we did not use these datasets for studying label noise.
Previous studies on ICD code classification tasks mainly focused on exploring different machine learning models for the task. A number of neural methods, including LSTM (Zeng et al., 2019), attention mechanism (Falis et al., 2019), and pretrained language models (Amin et al., 2019) have been proposed for such task. This work concentrates on an orthogonal aspect of ICD classification -label noise. Our modified training strategy is a general method and can be combined with different types of classifiers.
There are many existing works on training noiserobust classifiers (Bucak et al., 2011;Natarajan et al., 2013;Liu and Tao, 2015;Izadinia et al., 2015;Zhao and Guo, 2015;Patrini et al., 2017). Some methods make over-simplified assumptions about the noise and are not suitable for our problem (see section 2.2). For example, several methods assume the noise is completely random and is independent of features or labels ; and several others assume the noise is only in the form of missing labels (Kanehira and Harada, 2016;Jain et al., 2017). There are also methods that leverage samples with both noisy labels and clean labels in order to estimate the noise pattern (Xiao et al., 2015;Vahdat, 2017;Veit et al., 2017). Unlike previous works, our design of the noise handling method is driven both by the data and clinical domain knowledge (i.e., ICD hierarchy).

Conclusion and Future Work
This paper investigates the characteristics of labeling noise in manually-assigned ICD-10 codes and furthermore, proposes a method to train robust ICD-10 classifiers in the presence of labeling noise. Our research concluded that the nature of such noise is systematic. We compared our method with several different baselines including one that does not handle label noise and the baseline methods that assume random noise, and demonstrated that our proposed method outperforms all baselines when evaluated on expert validated labels.
We are currently working on extending our proposed method for data from other service lines besides Radiology, such as Pathology. We are also investigating the impact of including coders from different hospitals that may follow different coding conventions and as a result, may code the same note differently. Explicit modeling of such intersite disagreement during model training will help us generate a more robust and scalable model.


Image Restoration by Solving IVP

Recent research on image restoration have achieved great success with the aid of deep learning technologies, but, many of them are limited to dealing SR with realistic settings. To alleviate this problem, we introduce a new formulation for image super-resolution to solve arbitrary scale image super-resolution methods. Based on the proposed new SR formulation, we can not only super-resolve images with multiple scales, but also find a new way to analyze the performance of super-resolving process. We demonstrate that the proposed method can generate high-quality images unlike conventional SR methods.

Introduction
Super-resolution (SR) task is used to increase the image resolution by estimating its underlying high frequency details. However, SR is a highly ill-posed problem since for any lowresolution input, there are multiple high-resolution solutions, which makes it a challenging problem. Therefore, considerable methods have been studied to solve SR problem. First, interpolation-based methods are simple and efficient, and thus they are widely used in many applications. However, these naive approaches have a clear performance limitation. Deep-learning based methods are being very successful in generating high quality images from lowresolution image, and provide quantitatively promising results. Moreover, several generative SR networks which are composed of a highresolution image generator and discriminator, can generate visually more plausible results with the help of numerous perceptual losses (e.g. VGG and adversarial losses). However, these previous learning-based SR approaches are limited to fixed scaling factors (e.g., x2, x3, and x4) to allow quick inference. Therefore, there has been several researches to solve SR problem with an arbitrary scaling factor. Recently, there has been increasing attempts to model differential equations with neural network. In particular, Neural ordinary differential equations (Neural ODE), allows to formulate a differential path from low-resolution input to highresolution output with a neural network. However, this Neural ODE based SR approach uses the Neural ODE as an intermediate layer of HR generator without clear reasoning in the process of modeling a differential equation. Therefore, in this work, we tackle this problem and present a new SR approach with Neural ODE, and our contributions can be summarized as follows: • We propose a new formulation to perform superresolution on arbitrary scale.
• We find a way to analyze the differential path from lowresolution to high-resolution.
• Our method achieves performance close to existing state-of-the-art methods.
2 Related Works

Image Restoration
Recent works on single image restoration focus on learning mapping functions between degraded image and original image. SRCNN [Dong et al., 2015] proposed to learn the nonlinear mapping from LR image to HR image using a CNN model for the first time. VDSR [Kim et al., 2016b] increased the depth of CNN to model more complex LR-HR mappings. Recent studies have applied different kinds of skip connections to ease the optimization process [Lim et al., 2017;Zhang et al., 2018]. Parallel to devising improved feed-forward CNN architectures, many attempts have been done to develop SISR methods that can be better applied to real-world situations. Re-alSR [Cai et al., 2019] proposed a more realistic degradation model to make more natural training dataset and presented a new method to cope with the given degradation settings. Meta-SR [Hu et al., 2019] proposed Meta-Upscale module to handle arbitrary scale factors for SISR.

Gradual Image Restoration
gradual approaches have been proven to perform well in lowlevel vision tasks. In addition to learning a complex nonlinear mapping of a low-quality image to a high-quality one, these approaches decompose this process into multiple steps and iteratively refine the output images [Kim et al., 2016a;Tai et al., 2017;Haris et al., 2018;Li et al., 2019]. DBPN [Haris et al., 2018] proposed a dedicated neural network design that provides an iterative error correcting mechanism to address mutual dependencies of LR and HR images. SRFBN [Li et al., 2019] proposed an efficient recurrent neural network that employs the feedback mechanism, which iteratively improves the input of the network in each step. However, these methods do not have a clear underlying formulation or theoretical analysis on the gradual image restoration process, which consequently require a large amount of engineering to develop the neural architectures [Li et al., 2019;Haris et al., 2018] and specialized training strategies [Li et al., 2019;Kim et al., 2016a]. LapSRN [Lai et al., 2017] can produce large SR results (e.g., x8) with intermediate SR results (e.g., x2, x4), but it can only handle the pre-determined discrete scale factors such as x2, x4, and x8.

Neural Ordinary Differential Equation
Recently, many attempts have been done to integrate differential formulations and deep learning methodologies. These attempts have led to neural ordinary differential equations (NODE) . NODE is a new family of deep neural network models that parameterizes a differential form using a neural network and produces the output by using an ODE solver. Meanwhile, differential equations have often been involved in image restoration task by modeling nonlinear reaction-diffusion and total variation schemes [Chen and Pock, 2016;Rudin et al., 1992]. Such is also the case in deep-learning-based image restoration methods. [He et al., 2019] designed new neural network architectures inspired by the differential equation solving process, such as Leapfrog and Runge-Kutta approaches. In particular, to solve the SR problem, [Scao, 2020] utilized NODE as a part of neural architecture with an integration. However, the interval of the integral is not fixed (open) and they did not present any concrete formulation on the intermediate images involved in the gradual SR process. Consequently, they need to empirically speculate the optimal neural architecture and the integration interval.

Proposed Method
In this section, we present a new neural approach for the gradual SR reconstruction. We first formulate the SR problem as a gradual SR process with an ODE. We then elaborate how to perform SR with the proposed formulation and how to train it.

gradual Super-Resolution Formulation
Existing SR methods utilizing gradual SR process [Lai et al., 2017;Haris et al., 2018;Li et al., 2019] are based on iterative multi-stage approaches and can be viewed as variants of the following: where n denotes the iteration step, I 0 denotes the given initial input LR image, and I n is the iteratively refined image from its previous state I n−1 . These approaches typically produce multiple intermediate HR images during the refinement, and the rendered image at the last N -th iteration [Tai et al., 2017;Li et al., 2019]  To alleviate these problems, we formulate the gradual SR process with a differential equation. This allows us to implement and train the SR networks in an established way while outperforming the performance of conventional gradual SR process. Assume that (I HR ) ↓ t is a downscaled version of a groundtruth clean image I HR using a traditional SR kernel (e.g., bicubic) with a scaling factor 1 t . We then define I(t) by upscaling (I HR ) ↓ t using that SR kernel with a scaling factor t so that I HR and I(t) have the same spatial resolution (see the illustration of "Generating LR image" in (a). Note that t ≥ 1, and I(1) denotes the ground-truth clean image I HR .
To model a gradual SR process,we first estimate the highfrequency image residual with a neural network. Specifically, when t is a conventional discrete-scaling factor (e.g., x2, x3, and x4), image residual between I(t) and I(t − 1) can be modeled using a neural network f discrete as: (2) Notably, I(t − 1) includes more high-frequency details than I(t) without loss of generality. In our method, we model the slightest image difference to formulate a continuously gradual SR process. Therefore, we take the scale factor t to continuous domain, and reformulate (2) as an ODE with a neural network f as: where θ denotes the trainable parameter of the network f . Using this formulation, we can predict the high-frequency image detail required to slightly enhance I(t) with the network f . (Note that we can obtain I(t) with any rational number t by adding padding to the border of image before resizing and then center cropping the image.) As existing SR neural networks have been proven to be successful at predicting the high-frequency residual image [Kim et al., 2016b], we can use conventional SR architectures as our network f without major changes.

Single Image Super-Resolution with Neural
Ordinary Differential Equation In this section, we explain how to super-resolve a given LR image with a continuous scaling factor using our ODE-based SR formulation. First, we obtain I(t 0 ) by upscaling the given LR input image ("Test time LR image" in (a) using the bicubic SR kernel to a desired output resolution with a scaling factor t 0 . Next, we solve the ODE initial value problem with the initial condition I(t 0 ) by integrating the neural network f from t 0 to 1 to acquire the high-quality image I(1) as follows: As the neural network f is modeled to predict desired highfrequency details, our formulation gradually adds the predicted fine details from the input LR image I(t 0 ) through the integration shown as the solid orange line in (a). Thus, our SR approach becomes a gradual SR process which adds the high-frequency details gradually. To compute the integration with f in the proposed formulation, we use conventional ODE solvers to numerically calculate the output image I(1). Specifically, we approximate the high-quality image I(1) given a fully trained neural network f , network parameter θ, initial condition I(t 0 ), and integral interval [t 0 , 1] using an ODE solver (ODESolve()) as: Thus, our method does not need to consider the stop condition (i.e., the number of feedback iterations) of the gradual SR process unlike conventional approaches [Tai et al., 2017;Li et al., 2019]. Notably, we can use conventional ODE solvers to render the desired outputs for the inference, but the solutions should be differentiable to train the network f through the backpropagation scheme. We compare the SR performance with different ODE solvers (e.g., Runge-Kutta and Euler methods) in our experiments. Our formulation is made upon a continuous context, allows a continuous scale factor t 0 where t 0 ≥ 1. This makes our method able to handle the arbitrary-scale SR problem. But unlike conventional multi-scale SR methods [Kim et al., 2016b;Lim et al., 2017;Hu et al., 2019] that successfully learn multi-scale SR tasks by sharing common features across various scales, we explicitly learn the relationship between images with different scales in image domain itself rather than the feature space.

Training
To train the deep neural network f , and learn the parameter θ in (3), we minimize the loss summed over scale factors t using the L1 loss function as: By minimizing the proposed loss function, our network parameter θ is trained to estimate the image detail to be added into the network input. Notably, during the training phase, we need to employ an ODE solver which allows end-to-end training using backpropagation with other components such as the neural net-

Experimental Results
In this section, we carry out extensive experiments to demonstrate the superiority of the proposed method, and add various quantitative and qualitative comparison results. We also provide detailed analysis of our experimental results. We will release our source code upon acceptance. For each CNN architecture, we change the first layer to feed the scale factor t as an additional input. To be specific, we extend the input channel from 3 to 4, and the pixel locations of the newly concatenated channel (4-th channel) are filled with a scalar value t as shown in (b). In addition, for RDN, we remove the last upsampling layer so that input and output resolutions are the same in our work. Note that, no extra parameters are added except for the first layers of the networks.
To train and infer the proposed SR process, we use the Python torchdiffeq library  to employ Runge-Kutta (RK4) method as our ODE solver in (4), which requires only 6 additional lines of code with PyTorch.
For simplicity, our approaches with VDSR and RDN backbones are called vdsr and RDN in the remaining parts of the experiments, respectively.
Dataset and evaluation. We use the DIV2K [Agustsson and Timofte, 2017] dataset to train our vdsr and RDN. During the training phase, we augment the dataset using random cropping, rotating, and flipping.
During the test phase, we evaluate the SR results in terms of PSNR and SSIM metrics on the standard benchmark datasets (Set14 [Zeyde et al., 2010], B100 (BSD100) [Martin et al., 2001], and Urban100 [Huang et al., 2015]). To be consistent with previous works, quantitative results are evaluated on the Y (luminance) channel in the YCbCr color space.
Training setting. We train the network by minimizing the L1 loss in (4) with the Adam optimizer (β 1 = 0.9, β 2 = 0.999, = 10 −8 ) [Kingma and Ba, 2015]. The initial learning rate is set as 10 −4 , which is then decreased by half every 100k gradient update steps, and trained for 600k iterations in total. The mini-batch size of vdsr is 16 (200x200 patches), but our vdsr takes 8 patches as a mini-batch (130x130 patches) owing to the memory limit of our graphic units. Similar to the training settings in Meta-SR [Hu et al., 2019], we train the network f by randomly changing the scale factor t in (4) from 1 to 4 with a stride of 0.1 (i.e., t ∈ {1.1, 1.2, 1.3, ..., 4}).

Comparison with gradual SR Methods
First, we compare our RDN with several state-of-the-art gradual SR methods: DRCN [Kim et al., 2016a], LapSRN [Lai et al., 2017], DRRN [Tai et al., 2017], D-DPBN [Haris et al., 2018, and SRFBN [Li et al., 2019]. As in [Lim et al., 2017], self-ensemble method is used to further improve RDN (denoted as RDN+). Note that, our RDN and RDN+ can handle multiple scale factors t including non-integer scale factors (e.g., x1.5) using the same network parameter. In contrast, other approaches are required to be trained for certain discrete integer scale factors (x2, x3, and x4) separately, resulting in a distinct parameter set for each scale factor. Nevertheless, quantitative restoration results show that our RDN, RDN+ consistently outperforms conventional gradual SR methods for the discrete integer scaling factors (x2, x3, and x4) in terms of PSNR. We We observe that DRRN and SRFBN fail to gradually refine patches with high-frequency details, while our RDN can gradually improve the intermediate images and render promising results at the final states.

Comparison with Multi-scale SR Methods
Our approach can handle a continuous scale factor for the SR task, thus we compare ours with existing multiscale SR methods that can handle continuous scale factors: VDSR [Kim et al., 2016b] and Meta-SR [Hu et al., 2019]. Notably, Meta-SR implemented using RDN (i.e., Meta-RDN) is the current state-of-the-art SR approach.
In Table 1, we show quantitative results compared to existing SR methods (VDSR, RDN, and Meta-RDN). Note that, VDSR+t and RDN+t are modified versions of VDSR and RDN to take the scale factor t as an additional input of the networks and have the same input and output resolutions as in our network f . We also compare our method with these new baselines (VDSR+t and RDN+t) for fair comparisons.
We evaluate the SR performance on the B100 benchmark dataset by increasing the scaling factor from 1.1 to 4.
Interestingly, we observe that vdsr outperforms VDSR and VDSR+t at every scale by a large margin although VDSR and VDSR+t have similar network architecture to our vdsr. Similarly, RDN shows better performance than Meta-RDN and RDN+t. We also provide qualitative comparison results with Meta-SR in Figure 1, and we see that our RDN recovers much clearer edges than Meta-RDN.

Detailed Analysis
Interpolation and extrapolation. We experiment our method on various scale factors that are not shown during the training phase. In Figure 2, we plot PSNR values from vdsr and RDN by changing the scale factor on the B100 dataset. We see that our method learns an interpolation ability and can successfully deal with unseen scales between 1 and 4 (e.g., 1.15, 1.25, ... 3.95). Moreover, ours also learns an extrapolation ability and handles unseen scale factors larger than 4 (e.g., 4.1, 4.2, ... , 4.5). To sum up, our proposed SR process has a power of generalization (i.e., interpolation and extrapolation abilities), even the network is trained with only a limited number of scale factors. SR performance with different ODE solvers. We experiment our method with different ODE solvers (e.g., Euler and RK4 methods). Note that Euler method is computationally cheaper than RK4, but RK4 provides more accurate approximation results generally. Similarly, in Table 2, we see that vdsr trained with RK4 shows slightly better SR performance than vdsr trained with Euler method on the B100 and Set5 datasets. This result suggests that, we can employ conventional ODE solvers to solve our own SR problem, but the quality of the predicted HR images are relying on the performance of the employed ODE solver. Visual output of the network f . In Figure 3, to see the intermediate results by the network f during the gradual SR   procedure at the test stage, we compute absolute value of f (Î(t), t, θ) where t decreases from 4 to 1, and the initial condition is I(t 0 = 4).
Interestingly, on the sharp patch corresponding to the eye (red box), the absolute values are higher when t is small. While, on the homogeneous patch corresponding to the cheek (green box), the absolute values are higher when t is large. Recall that I(t) becomes close to the groundtruth image when t gets small, and the image difference dI (t) dt (≈ f (Î(t), t, θ)) includes more high-frequency components. Therefore, the absolute values of the network at the eye region which includes high-frequency detail becomes large when t is small, while the absolute values at the homogeneous region which does not require high-frequency detail becomes small when t is small.

Conclusion
In this work, we proposed a novel differential equation for the SR task to gradually enhance a given input LR image, and allow continuous-valued scale factor. Image difference between images over different scale factors is physically modeled with a neural network, and formulated as a NODE. To restore a high-quality image, we solve the ODE initial value problem with the initial condition given as an input LR image. The main difference with existing gradual SR methods is that our formulation is based on the physical modeling of the intermediate images, and adds fine high-frequency details gradually. The analysis on the intermediate states during the SR process gives us more insight on the gradual SR reconstruction. Detailed experimental results show that our method achieves superior performance compared to state-of-the-art SR approaches.


Circuit Design for $k$-coloring Problem and Its Implementation in Any Dimensional Quantum System

With the evolution of quantum computing, researchers now-a-days tend to incline to find solutions to NP-complete problems by using quantum algorithms in order to gain asymptotic advantage. In this paper, we solve $k$-coloring problem (NP-complete problem) using Grover's algorithm in any dimensional quantum system or any $d$-ary quantum system for the first time to the best of our knowledge, where $d \ge 2$. A newly proposed comparator-based approach helps to generalize the implementation of the $k$-coloring problem in any dimensional quantum system. Till date, $k$-coloring problem has been implemented only in binary and ternary quantum system, hence, we abide to $d=2$ or $d=3$, that is for binary and ternary quantum system for comparing our proposed work with the state-of-the-art techniques. This proposed approach makes the reduction of the qubit cost possible, compared to the state-of-the-art binary quantum systems. Further, with the help of newly proposed ternary comparator, a substantial reduction in quantum gate count for the ternary oracle circuit of the $k$-coloring problem than the previous approaches has been obtained. An end-to-end automated framework has been put forward for implementing the $k$-coloring problem for any undirected and unweighted graph on any available Near-term quantum devices or Noisy Intermediate-Scale Quantum (NISQ) devices or multi-valued quantum simulator, which helps in generalizing our approach.

Introduction
Modern day researchers has shown a startling interest for implementing quantum algorithms [1][2][3], which give a potential speedup over many of their classical counterparts as the advancement of quantum computer has achieved a phenomenal success in recent years [4]. There is an immense urge for the implementation of NP-complete problems on quantum computers with the thriving quantum wave [5]. According to the seminal work on computational complexity by Karp [6], if a solution to any of the NP-complete problems can be obtained then any other NP-complete problem can be polynomially reducible to that problem. In this paper, we have focused on one of the well-known NP-complete problems i.e., k-coloring problem. Our main focus is to provide an end-to-end framework that automatically implements an NP-complete problem i.e., k-coloring problem in any dimensional quantum system, so that if anyone can map their computational problem to the k-coloring problem in polynomial time, will be able to implement further, without prior knowledge of gate-based quantum circuit implementation.
An automatic circuit synthesis for k-coloring problem with the help of Grover's algorithm [7] is presented in the context of multi-valued quantum system in this paper. We graduate to multi-valued quantum system or qudits [8], which in the course reduce the circuit complexity and commend the efficiency of quantum algorithms [9] to provide larger state space with simultaneous multiple control operations [10][11][12]. For instance, N qubits can be formulated as N log2d qudits, which immediately gives log 2 d-factor in run-time [13][14][15]. The multi-valued quantum system can be realized on mostly available quantum technologies, as for example, ion trap [16], continuous spin systems [17,18], topological quantum systems [19,20], nuclear magnetic resonance [21], photonic systems [22], superconducting transmon technology [23] and molecular magnets [24].
k-coloring problem is an NP-complete problem that assigns colors to every nodes or vertices of a given graph with the available k colors in such a way that every adjacent vertices connected by an edge having distinct colors. Suppose n is the number of nodes of a given graph, k is the number of colors, then to find an appropriate solution using a classical algorithm requires O(2 n * log d k ) number of steps in d-dimensional system [25,26]. On the other hand, by using oracle and the diffusion operator of multivalued Grover's algorithm [27,28], finding the exact solution needs O √ N number of iterations where N is 2 n * log d k .
Many researchers have already addressed graph coloring problem for binary and ternary quantum system. Earlier in [25,29], graph coloring problem with the help of Grover's algorithm is talked about with respect to the binary quantum systems. Again, in [30], SAT reduction technique, the state-of-the-art approach, is used for solving 3coloring problem and it gives an end-to-end framework for the implementation of it in the IBMQ quantum processor [31]. But, SAT reduction technique generates an immense qubit cost, resulting in inefficient circuit cost. Previously in [32] and [26], circuit synthesis for graph coloring problem using Grover's algorithm has been presented with respect to ternary quantum system with the help of ternary comparators, which have been proposed in [33]. Albeit, in these works, the gate cost remains colossal.
In [34], we proposed a comparator-based approach for implementing the k-coloring problem in binary quantum structure, which has less qubit cost as compared to the state-of-the-art. In this paper, we have generalized the comparator for d-ary quantum system, which helps to overcome the engineering challenge of the implementation of k-coloring problem in d-ary quantum system. We have proposed an automated end-to-end framework for any dimensional quantum system to implement k-coloring problem using newly proposed generalized comparator to map the high level description of proposed circuit to any hardware-level quantum operations with an abstraction with better quantum cost in terms of quantum gate cost relative to the state-of-the-art works. In addition to this, we have claimed the following, for further establishing the novelty of the propose research work: -We propose an automated end-to-end framework for k-coloring problem using quantum search algorithm in any dimensional quantum system for the first time, to the best of our knowledge. -The design of the proposed framework is such that, the quantum solution of kcoloring problem can be mapped into any available near-term quantum devices/multivalued quantum technology, which makes our approach generalized in nature. -We show that our newly proposed comparator helps to implement k-coloring problem with reduced quantum cost with respect to qubits and quantum gates as compared to state-of-the art approaches in binary and ternary quantum domain. -A generalized comparator for d-ary system is elaborated in this paper, which is a first of its kind approach.
The paper is structured as follows. In section 2, the brief description of Grover's algorithm and quantum circuits are described. The proposed methodology is vividly explained in section 3. In section 4, implementation of k-coloring problem has been shown. Concluding remarks are captured in Section 5.

Background
In this section, we have explicitly described quantum circuit and Grover's algorithm.

Quantum circuit
Any quantum algorithm can be expressed or visualized in the form of a quantum circuit. Logical qubits/qudits and quantum gates comprise these quantum circuits [35]. The number of gates present in a circuit is called gate count and the number of qubits/qudits present in a circuit known as qubit/qudit cost.

Qubits/Qudits
Logical qubit/qudit that encodes input/output of a quantum algorithm is referred to as data qubit or qudit. Ancilla qubit/qudit are another type of qubit/qudit used to store temporary results. In d-dimensional quantum system qudit is the unit of quantum information. Qudit states can be manifested as a vector in the d dimensional Hilbert space H d . The span of orthonormal basis vectors {|0 , |1 , |2 , . . . |d − 1 } is the vector space. In qudit system, the general form of quantum state can be expressed as where

Generalized Quantum Gates
In this section, an outline of generalized qudit gates is conferred. The generalisation can be delineated as discrete quantum states of any arity. In a quantum algorithm, for modification of the quamtum state, unitary qudit gates are applied. For logic synthesis of Grover's algorithm in d-dimensional quantum system, it is necessary to take into account one-qudit generalized gates viz. NOT gate (X d ), phase-shift gate (Z d ), Hadamard gate (F d ), two-qudit generalized CNOT gate (C X,d ) and Generalized multi-controlled Toffoli gate (C n X,d ). These gates are expressed in detail for better understanding: Generalized NOT Gate: X d , the generalized NOT or increment gate, for a (d × d) matrix is as follows: Generalized Hadamard Gate: F d , the generalized quantum Fourier transform or generalized Hadamard gate, produces the superposition of the input basis states. The (d × d) matrix representation of it is as shown below : Generalized CNOT Gate: Quantum entanglement is a unparalleled property of quantum mechanics, and can be attained by a controlled NOT (CNOT) gate in a binary quantum system. For d-dimensional quantum systems, the binary 2-qubit CNOT gate is generalised to the IN CREM EN T gate: INCREMENT|x |y = |x |(x + y) mod d , if x = d − 1, and = |x |y , otherwise. The (d 2 ×d 2 ) matrix representation of the generalized CNOT C X,d gate is as follows: where I d and 0 d are both d × d matrices as shown below: Generalized Multi-controlled Toffoli Gate: We extend the generalized CNOT or IN CREM EN T further to operate over n qudits as a generalized Multi-controlled Toffoli Gate or n-qudit Toffoli gate C n X,d . For C n X,d , the target qudit is increased by 1 (mod d) only when all n − 1 control qudits have the value d − 1. The (d n × d n ) matrix representation of generalized Multi-controlled Toffoli (MCT) gate is as follows: Owing to technology constraints, a multi-controlled Toffoli gate can be substituted by an equivalent circuit comprising one-qudit and/ two-qudit gates, although at first the multi-controlled Toffoli must be decomposed into a set of Toffoli gates for any dimensional quantum system.
The binary [36] and ternary circuit [8,37] representation of all the above mentioned generalized gates are described in Figure 1.

Generalized Grover's Algorithm in d-dimensional Quantum System
The generalized Grover's algorithm in d-dimensional quantum system is presented here. There exists two sub-parts of the algorithm viz. oracle and diffusion [28]. As per convention, Grover's algorithm for searching in an unstructured database can be defined as follows: given a collection of unstructured database elements x = 1, 2, . . . , N , and an oracle function f (x) that acts on a marked element s as fol- perceive the marked element with as few calls to f (x) as possible [27,28]. The database is encoded into a superposition of quantum states where each element is assigned to a corresponding basis state. Grover's algorithm searches over every possible outcome, which is put forward as a basis vector |x in an n-dimensional Hilbert space in d-dimensional quantum system. Likewise, the marked element is encoded as |s . Thus, the search can be done in parallel, after application of unitary operations as an oracle function to the superposition of the different possible outcomes. The generalized diffusion operator, also known as inversion about the average operator, amplifies the amplitude of the marked state to increase its measurement probability using constructive interference, with simultaneous enfeeblement of all other amplitudes, and searches the marked element in O( . The circuit diagram for the generalized Grover's algorithm in a d-dimensional quantum system is presented in Figure 2, where at least n + 1 qudits are required. More elaborately, the steps of the Grover's algorithm are as follows: Initialization: The algorithm starts with the uniform superposition of all the basis states on the n input qudits in |0 by assimilating generalized Hadamard or quantum DFT gate. The last ancilla qudit is used as an output qudit which is initialized to Oracle query: The oracle (U f ) of Grover's search marks the marked state |s while keeping all the other states unchanged, and can be expressed as: The oracle block U f as shown in Figure 2 is dependant on the problem instance. The oracle using Unitary transformation is needed to be designed as per requirement.
Diffusion: The diffusion operator of Grover's search is generic, it doesn't depend on specific problem . As shown in Figure 2, the diffusion operator is initially assigned with generalized Hadamard (F ⊗n d ), then by 2|0 n 0 n | − I d n and generalized Hadamard (F ⊗n d ) again. The diffusion operator (D) can be expressed as: The matrix representation of generalized diffusion operator [27] for d-dimensional quantum system is shown below: The combination of the oracle and the diffusion gives generalized Grover operator G, We need to din the Grover's operator O( √ N ) times to get the coefficient of the marked state |s large enough so that it can be obtained from measurement with probability close to 1 and thus round off the Grover's algorithm.

Proposed Methodology of Circuit Synthesis for k-coloring Problem using Grover's Algorithm in any Dimensional Quantum System
The flowchart in Figure 3 depicts the complete flow of our proposed automated endto-end framework. Mainly three algorithms: AutoGenOracle K-color, MCT Realization and Qubit Mapping (Binary) are the basis of our framework. At first, AutoGenOracle K-color algorithm, which is based on the newly designed comparator, is implemented with inputs: graph information i.e, adjacency matrix of the given graph and the number of colors (k) to get the output, quantum circuit netlist in the form QASM. Now, MCT Realization algorithm takes as input, generated circuit netlist and MCT gates to NISQ hardware compatible 1-qubit and 2-qubit gates [38] and multi-valued quantum technology compatible 1-qudit and 2-qudit gates are realised. Due to multivalued quantum technology constraint, implementation of multi-valued circuit netlist on multi-valued quantum hardware is technologically infeasible till date, rather we have simulated and verified the multi-valued circuit netlist on multi-valued simulator. Finally, qubit mapping [39,40] algorithm has been used for mapping generated circuit to the NISQ devices based on the qubit topology.
The proposed methodology for the oracle circuit synthesis of the k-coloring problem in any dimensional quantum system as an application of the Grover's search algorithm is sketched in this section. Figure 4 shows the quantum circuit block of oracle for the k-coloring problem in d-dimensional quantum system. The construction of oracle for k-coloring problem is divided into four parts. It starts with initialization, which is essentially required in Grover's Algorithm.

Initialization
Let there be a graph which has n vertices and e edges, k is the given number of colors, then the total number of data qudits that are required for representing all the colored vertices are n * log d k . The oracle performs a check to find all possible right combination of properly colored vertices with k/fewer colors from a combination of all possible colored vertices. A superposition of m = n * log d k qudits thus generates all possible combination of colored vertices. The initial data qudits in Figure 4 include m qudits prepared in the ground state |ψ = |0 ⊗m , due to the re-usability property of ancilla qudits, r = n ancilla qudits in the exited state |θ = |d−1 ⊗r (These r ancilla qudits are required to prepare Invalid Color detector block and comparator block that are thoroughly explained in the next subsection), one ancilla qudit in the ground state |ζ = |0 (1 ancilla is required if invalid color exists), and one output qudit in the excited state |φ = |d − 1 is required to perform generalized CNOT/Toffoli/MCT operation of the oracle. This entire initialization can be mathematically depicted as:

Generalized Hadamard Transformation
The next step after the initialization is Hadamard transformation. The genralized Hadamard transform F d ⊗m on data qudits and F d on output qudit is performed, hence all possible states are superposed as |ψ 0 ⊗ |θ 0 ⊗ |ζ 0 ⊗ |φ 0 , where 3 Proposed U f Transformation for d dimensional system: The proposed unitary U f transformation is distinctly divided into two parts.
(1)Reduction of Invalid Colors: As color, c = log d k , so maximum d c colors are considered. If d c = k, then all colors are valid colors, else there exists a set of d c − k invalid colors. The valid colors are used to optimize the search space. Using the following steps this can be executed: Qudit Activation: Colors should be numbered sequentially as {0, 1, 2....d c − 1}. After the generalized Hadamard transformation, the input data qudit lines act as the d-dimensional representation of combination of all possible colored vertices. The oracle performs a check for only k, which is the combination of valid colors. All the input qudit lines should be in the excited state |d − 1 for those particular combinations of invalid colors by making input qudit lines suitable as control lines for Generalized CNOT/Toffoli/MCT operation to be assured that the oracle is checking only the k-colored combination of vertices. A number of generalized NOT gates must be imposed on the input qudit lines, that are in the ground state |0 accompanied by the application of 'Invalid Color Detector'. Again after 'Invalid Color Detector', this 'Qudit Activation' is to be applied to roll back to the initial superposed quantum state.
Invalid Color Detector: In any combination of colored vertices if any invalid color is noticed then that combination is rejected with the use of the function ICD (Invalid Color Detector) as: The circuit synthesis of 'Invalid Color Detector', that is functionally depicted in Equation 4 for n vertices, where I 1 , I 2 , .., I n are the data qubits, is described in Figure  5 . The circuit synthesis of 'Invalid Color Detector' for ternary quantum system is described in Figure 6. That is again, functionally shown in Equation 5 for n vertices, where I 1 , I 2 , .., I n are the data qutrits.
(2)Comparator: A newly proposed generalized comparator circuit for d-dimensional quantum system can be defined as: where a and b are the comparing inputs representing the colored vertices of the given graph and the ancilla qudit is f . In Figure 7, circuit synthesis for 2-qubit and 4-qubit comparator is shown, the functional description of which is given in Equation 7. The complete circuit synthesis for the binary comparator is designed using CNOT, NOT, Toffoli/MCT gates.  Induced from the above, a newly proposed ternary comparator can be defined as: Circuit synthesis for 2-qutrit ternary comparator is shown in Figure 8. M-S gate and 1-qutrit permutative gate are used to design the complete circuit synthesis for ternary comparator. Initially, the total number of gate count of our newly proposed comparator is reduced by one as compared to the comparator proposed in [33]. But, gate count can be reduced further at the time of oracular circuit synthesis as one of the outputs of our comparator is 2 instead of 1 [33]. As everything has to be mirrored at the time of circuit synthesis in order to eliminate the cost of wires, there is a need to design an inverse comparator. Our newly proposed 2-qutrit ternary inverse comparator is shown in Figure 9. This newly proposed ternary inverse comparator has a reduced gate count compared to the work in [33].

Generalized MCT Operation
The |φ 0 , output qudit state, is initialized as: Applying a Generalized MCT gate on the output line with ancilla qudits as control, an eigenvalue kickback ω (d−1)(d−1) occurs as a result. This causes a phase shift for the respective input state(s), which in turn helps in finding out all the combinations of properly colored set of vertices. In next subsection, we have elaborately sketched about generalized Grover's diffusion operator.

Generalized Diffusion Operator
The circuit implementing the function of diffusion is the second part of Grover's algorithm. The component along |ψ 0 is kept unchanged when the operation is applied to a superposition state, while inverting the components in dimensions that are perpendicular to |ψ 0 . This can be represented as where, |i Figure 10 shows the generalized circuit for Grover's diffusion operator in ddimensional quantum system. It can be constructed using generalized Hadamard gate, generalized NOT gate and generalized multi-controlled Toffoli gate. The algorithm that causes the gate level synthesis of the proposed method is discussed in the next subsection.

Proposed Algorithm for Oracle Circuit Synthesis in any Dimensional Quantum System
The proposed algorithm Algorithm 1 (AutoGenOracleK-Coloring) of automated oracular circuit synthesis for the k-coloring problem in any dimensional quantum system is illustrated in this subsection. The algorithm accepts the adjacency matrix of the given graph and the number of colors k as input parameters. A circuit netlist in the form of QASM is the output of the algorithm.
The total number of qudit lines that are required for the generation of the oracle circuit can be easily evaluated from the details of the adjacency matrix and the number of given colors. All the input data qudits are initialized with |0 followed by genaralized Hadamard, ancilla lines (A r ) are initialized with |d − 1 , ancilla line A r+1 is initialized with |0 and the output line is initialized with |d − 1 followed by generalized Hadamard. First of all, Invalid Color Detector is applied with suitable Qudit Activation (if invalid color exists) with I r , A r as control and A r+1 as the target. After that, between two adjacent vertices(i, j), a generalized comparator circuit is used with two input lines(i, j) as control and the ancilla line(A r ) as output. They perform the same task for all the adjacent vertices. Following this, a generalized MCT gate is used with all the ancilla lines A r and A r+1 as control and the output line as output for the flip operation of the Grover's oracle. In order to achieve the mirror of the oracle circuit, we have repeated the previous steps as shown in Algorithm 1.

Circuit Cost Estimation
The design of generalized oracle for our proposed algorithm has already been described. Now, in this subsection, we furnish the circuit cost analysis of the oracular circuit in Table 1.
n * log d k data qubits are required for n-vertices graph and k given color. At most n + 1 number of ancilla and at most O(n 2 * log d n) gates are required to design the oracular circuit for n-vertices graph. As for example, for binary quantum system, a graph of three vertices with three connected edges (K 3 ) is shown in Figure 11 and a graph of three vertices with two connected edges for ternary quantum system is shown in Figure 12 which illustrates the gate-optimized circuit synthesis of the 3-coloring problem, r ← f , m ← f 8: for j ← i + 1 to n do 9: if adj(i, j) ← 1 (i and j are connected by an edge(e)) then 10: Use a generalized comparator circuit with the input lines (I i , I j ) corresponding (i, j) as control and the ancilla line Ar as target. 11: r ← r + 1 12: end if 13: end for 14: if r > f + 1 then 15: Use a generalized Toffoli/MCT gate with all ancilla lines Ar as control and A l as target 16: l ← l − 1 17: for m ← i + 1 to n do 18: if adj(i, j) ← 1 (i and j are connected by an edge(e)) then 19: Use a generalized comparator circuit with the input lines (I i , Im) corresponding (i, j) as control and the ancilla line Am as target. 20 Fig. 11 Gate level representation of 3-coloring problem for example graph in binary quantum system The focus of this subsection is the mapping of generated oracle circuit to NISQ devices through MCT realization and qubit mapping algorithm. Due to the constraint of the number of qubits, NISQ Devices are "noisy," thus a certain range of error should be allowed during the estimation of the simulated result of a quantum state [4]. Superconducting quantum circuits, quantum dot, ion trap, neutral atom are the most popular NISQ technologies for implementing the quantum circuit. For mapping the logical synthesized circuit to quantum hardware, each one of the above mentioned technologies has a specific dedicated qubit topology, as in Figure 13. Certain 1-qubit and 2-qubit gates that are supported by most of the quantum hardware are illustrated in Table 2. The logical quantum gates are needed to be realized to hardware specific gates for making it hardware compatible for implementation. id, x, y, z, h, r2, r4, r8, rx, ry, rz, u1, u2, u3, s, t, sdg, tdg 2-qubit gates swap, srswap, iswap, xy, cx, cy, cz, ch, csrn, ms, yy, cr2, cr4, cr8, crx, cry, crz, cu1, cu2, cu3, cs, ct, csdg

Realization of MCT Gate
The process of decomposition of MCT gate to NISQ compatible 1-qubit and 2-qubit gates [38] is shown in Figure 14. At first, the MCT gate is to be decomposed to MCZ gate. After that, MCZ gate is realized to MCR x (π). Lastly, without using any ancilla qubit, MCR x (π) is reduced to 1-qubit and 2-qubit gates.

Qubit Mapping to NISQ Devices
As, our proposed quantum circuit is logical, there is no constraint of qubit connectivity. There is a specific qubit topology or coupling graph for NISQ devices. The interaction between two physical qubits is defined by coupling graph. This is different for different NISQ devices. Hence, obviously mapping the logical circuit to the physical one is challenging. The solution to this problem is to insert SWAP gates between the two qubits to comply to the hardware constraint without compromising on the logic of the quantum circuit. The concept behind a good qubit mapping problem is to minimize the number of SWAP insertion gates as well as the depth of the circuit. Li et. al. proposed SWAP-based BidiREctional heuristic search algorithm (SABRE) in [39], which deals with any arbitrary qubit topology for any NISQ devices. Three main features make SABRE noticeable. Firstly, an exhaustive search is not performed on the entire circuit, but a SWAP-based heuristic search is performed keeping in mind the qubit dependency. Then, initial mapping is optimized with the use of a novel reverse traversal technique. Lastly, the decay effect being introduced to enable the trade-off between the depth and the number of gates of the entire algorithm. Tan et. al. formulated layout synthesis for quantum computing, which is a benchmark, as optimization problems [40]. They handed over two synthesizers: an exact layout synthesizer (OLSQ) and an approximate, transition based synthesizer (TB-OLSQ). OLSQ is the first, that guarantees optimality and efficiency both in time and space for general quantum processors, as compared to previous exact approaches. This approach shows some promises of being beneficial for realistic applications for near-term quantum computers. Our proposed circuit can easily be mapped to any arbitrary qubit topology by using one of these protocols.

Realization of Generalized MCT Gate
In [42], Saha et. al. have shown the decomposition of multi-controlled Toffoli gate in d-dimensional quantum system. A generalized Toffoli decomposition in d-dimensional system using |d state is shown in Figure 15. An akin construction for the Toffoli gate in binary using qutrit is evident from a previous work [43]; Saha et. al. have extended it for d-dimensional quantum system. The idea is to execute an X d operation on the target qudit (third qudit) if and only if the two control qudits, are both |d − 1 . Firstly, a |d − 1 -controlled X +1 d+1 , where +1 and d + 1 are used to denote that the target qudit is incremented by 1 (mod d + 1), is implemented on the first and the second qudits. This eventually upgrades the second qudit to |d as long as the first and the second qudits were both |d − 1 . Then, a |d -controlled X d gate is applied to the target qudit. Therefore, X d is executed only when both the first and the second qudits were |d − 1 , as expected. The controls are rolled back to their original states by a |d − 1 -controlled X −1 d+1 gate, which reverses the effect of the first gate. The most important aspect in this decomposition is that the |d state from d + 1-dimensional quantum system can be used instead of ancilla to store temporary information. Fig. 15 Generalized Toffoli in d-dimensional quantum system [42] For further decomposition of the Toffoli for simulation purpose, the d+1-dimensional Toffoli gate has been decomposed into d+2-dimensional CNOT gates. A generalized CNOT gate for d + 2-dimensional quantum system as C +1 X,d+2 , where +1 and d + 2 denote that the target qudit is incremented by 1 (mod d + 2) only when the control qudit value is d + 1. The ((d + 2) 2 × (d + 2) 2 ) matrix representation of the C +1 X,d+2 gate is as follows: where X +1 d+2 and 0 d+2 are both (d + 2) × (d + 2) matrices as shown below: As an example, a 8-qudit Toffoli gate is shown in Figure 16(a). First, we need to decompose it as in [43] as shown in Figure 16(b). Further, we need to decompose all the d+1-dimensional Toffoli gates into (d+2)-dimensional CNOT gates as shown in Figure 16(c) with the help of the Saha et. al. decomposition of the generalized Toffoli in any dimensional quantum system [42]. All the d − 1-controlled Toffoli gates are decomposed into d − 1-controlled and d-controlled CNOT gates as shown in Figure  16(c). Likewise, all the d-controlled Toffoli gates are decomposed into d-controlled and d + 1-controlled CNOT gates. Consequently, with the help of |d and |d + 1 quantum state of (d + 2)-dimensional system, X d is caried out effectively if all the controlled qudits are in |d − 1 state. In this way, any dimensional multi-controlled Toffoli gate can be decomposed.

Experimental result of k-coloring Problem in NISQ Device
The generated oracle circuit for example graph has been taken as an example case for the simulation of k-coloring problem as shown in Figure 11. The simulation is performed on IBMQ cloud based physical device [18]. The resultant probabilistic output after applying Grover's diffusion operator is shown in Figure 17, where the amplitude of the solution state has been amplified. The location of the solution states are |011000 , |100100 , |000110 , |010010 , |001001 , and |100001 where 00, 01, and 10 are the valid colors as we take 11 as invalid color. These are the properly colored vertex combinations in the given example graph that solves the k-coloring problem with high probability. As we have taken K 3 graph as an example graph and the three valid colors are 00, 01, and 10, solution states must be all possible combination of the valid colors.

Experimental result of k-coloring Problem in Ternary Quantum System
Our ternary circuit instance is verified through simulation with the help of MATLAB simulator [44]. Unfortunately, MATLAB has some limitations of memory constraints. For that, the verification of our circuit needs to be restricted with at most six qutrits. Therefore, a graph of three vertices is taken, where one vertex is connected with other two vertices as an example case for simulating the graph coloring problem. As per the Algorithm 1, as a three vertices graph is taken, three qutrits(n * log 3 n ) are required to represent them. As the example graph having two edges, two ancilla qutrit is required to perform the comparator circuit synthesis and one final qutrit as output. As three colors are given, which are encoded as |0 , |1 and |2 . Generally, a graph with three vertices can be colored with the help of three colors in 3 3 = 27 different ways, that can be represented in the ternary quantum system as |000 . . . |222 . Thus, our database contains 27 elements. In Figure 12, the gate level representation of the Grover's circuit is shown. The simulation steps of Figure 12 are: Step 1: At first, all the qutrits of the 3-qutrit register are initialized with |0 .
Step 4: The output of ternary oracle is acted upon by the ternary diffusion operator. This diffusion operator amplifies the amplitudes of the marked states of step 2.
Step 5: Steps 3 and 4 are repeated for N/M times. (For the multiple solution of Grover's operator having N= number of elements in the database and M= number of marked states).
Step 5 after one iteration is shown in Figure 18 where, the amplitude amplification is performed using diffusion operator to amplify the amplitudes of marked state. It can be verified that the location of the searched states (output of step 2) by subtracting one from the index value of Figure 18 and then converting it to its equivalent ternary value. For example, if index value is taken five form Figure 18, after subtracting one and converting it to ternary we get the string |011 , which is one of the searched state. Analysis of the simulation result confirms that our oracle successfully verifies that any set of vertices of a graph is properly colored by the given set of colors.

Comparative Analysis
Our proposed comparator-based oracle gives better result with respect to data qubit and ancilla qubit as n * log 2 k and O(n) respectively, as compared to [30]. The comparative analysis is shown in Table 3. The new ternary oracle circuit for 3 vetices graph achieved 41% reduction in the quantum gate cost as compared to the most recent related work [26] and 85% reduction in the quantum gate cost as compared to the work [32]. Table 4 shows the comparative analysis for higher vertices graphs as well. We show that for 4-vertices and 5-vertices graph, it can be reached to 43% reduction of gate cost.

Conclusion
Here, in this paper, we have proposed an end-to-end framework, which includes mapping of k-coloring problem to any NISQ devices/multi-valued quantum technology through automatic generation of oracle circuit using Grover's search followed by MCT realization for any dimensional quantum system. This proposed approach for any dimensional quantum system is applicable for any undirected and unweighted given graph, which makes our approach generalized in nature. Our comparator-based approach can reduce qubit cost to n * log 2 k as compared to n * k of reductionbased approach from 3-SAT problem to 3-Color problem. This leads to a reduction of query complexity from O(n * k) to O(n * log 2 k). Further, we have shown that our newly proposed ternary comaparator is a key component in designing the circuit for the k-coloring problem using quantum search algorithm. Our new ternary oracle circuit achieved an at least 41% reduction in the quantum gate cost as compared to the most recent related work [26] and an at least 85% reduction in the quantum gate cost as compared to the work [32]. In future, with the evolution of qudit-supported quantum hardware, we would like to validate our designs.