Test German BERT Named Entity Recognition with Matlab (Updated)

1 Overview

This script illustrates how to use a German BERT model for named entity recognition and compares the predictive performance of such a transformer model to the performance of the addEntityDetails function of Mathwork’s „Text Analytics“ toolbox. As an update to the previous version of this blog, I also conduct a quality test of the new hmmEntityModel function, which was added to the Text Analytics toolbox with Matlab 2023a.
Quite generally, as transformer models have revolutionized NLP over the last years, it is no surprise that the BERT-NER model will be superior to the Matlab functions, as the addEntityDetails function is not based on a neural network and the hmmEntityModel function is based on a purely statistical framwork instead of semantics. This script serves only to illustrate some NER uses of Matlab, as well as the power of transformer models for NLP, which can now be used in Matlab with ease.
Mathwork provides a BERT-base implementation which we rely upon. However, as Mathworks currently does not provide a means to import pre-trained models from Python into Matlab, we rely on the toolbox „exportBERTtoMatlab“ designed by Moritz Scherrmann (from the Institute of Finance & Banking, LMU Munich) for exactly this purpose. As this toolbox basically allows to import all TensorFlow and PyTorch BERT-base models that rely upon the word-piece tokenizer, the expansion by new and more powerful NLP methods directly available in Matlab is in my view just fantastic – I have wished for this for a long time.

2 Using a Pretrained German BERT Model

We use the GermanBERT model trained by deepset.ai and train it ourselve with the GermEval 2014 data. Alternatively, one could have used an already pre-trained model based on these data, but I’d liked to see how the training works in Matlab (though this will not be discussed in this article).
% for replication, adust to your folders
clear; close all;
cd(„c:\Tools\exportBertToMatlab\Matlab\TrainNER\“);

Load German BERT NER Model

Load a pretrained BERT model. The model consists of a tokenizer that encodes text as sequences of integers, and a structure of parameters.
%load model
bertModel = load(„.\TrainedModels\gbert-base2023_02_21_13_16_51.mat“);
bertModel=bertModel.bertModel;
tokenizer = bertModel.Tokenizer;
parameters = bertModel.Parameters;
 
% set parameters
paddingValue = bertModel.Tokenizer.PaddingCode;
seperatorValue = bertModel.Tokenizer.SeparatorCode;
maxSequenceLength = bertModel.Parameters.Hyperparameters.NumContext;

Load Data

Load the example data. The file „dataTokenized.mat“ contains test, train and dev splits of the GermEval2014 competition, the most popular annotated NER data for the German language.
filename = „GermEval2014\dataTokenized.mat“;
data = load(filename);
data=data.tokenizedData;

Set Parameters

tokensTrain = data.train.tokens;
labelsTrain = data.train.label;
% Dev
tokensDev = data.dev.tokens;
labelsDev = data.dev.label;
% Test
tokensTest = data.test.tokens;
labelsTest = data.test.label;
 
% get the BERT tokens as string
tokensBERT=table;
for idx=1:length(tokensTest)
tokensAct = tokenizer.FullTokenizer.decode(tokensTest{idx})‘;
tokensBERT = [tokensBERT;array2table(tokensAct(2:end-1),„VariableNames“,[„Token“])];
end
 

Get all Classes

Show the NER labels, following the IOB coding for categories „person“, „location“, „organization“, and „other“ („O“ is no entity)
classes=unique([horzcat(labelsTrain{:}),horzcat(labelsDev{:}),horzcat(labelsTest{:})])
classes = 1×9 string
„B-LOC“ „B-ORG“ „B-OTH“ „B-PER“ „I-LOC“ „I-ORG“ „I-OTH“ „I-PER“ „O“
numClasses=length(classes);

Setup Datastore

Create an array datastore containing the encoded tokens.
dsXTest = arrayDatastore(tokensTest,„OutputType“,„same“);
miniBatchSize = 128;
%
% Create a mini-batch queue for the data. Preprocess the
% mini-batches using the |preprocessPredictors| function, listed at the end
% of the example.
mbqTest = minibatchqueue(dsXTest,1,…
„MiniBatchSize“,miniBatchSize, …
„MiniBatchFcn“,@(X) preprocessPredictors(X,paddingValue,maxSequenceLength,seperatorValue));

BERT Predict

Make predictions using the modelPredictions function, listed at the end of the example. The data comprise 5,100 test sentences.
startValue=tokenizer.StartCode;
 
tic
YPredTest = modelPredictions(parameters,mbqTest,classes,startValue,seperatorValue,paddingValue);
toc
Elapsed time is 149.184232 seconds.
% Remove labels for start and end tokens in target labels
labelsTest=cellfun(@(x) x(2:end-1),labelsTest,‚UniformOutput‘,false);
% concat labels
YPredTest=horzcat(YPredTest{:})‘;
labelsTest=horzcat(labelsTest{:})‘;

Quality of BERT NER-Model

To test model quality a simple average F1 score across all classes (taking each token separatly into account) is calculated (i.e. Macro-F1).
No suprise, the transformer model achieves Macro-F1 of 82.5% – a decent result.
woT=onehotencode(labelsTest,2,‚ClassNames‘,classes);
woP=onehotencode(YPredTest,2,‚ClassNames‘,classes);
 
% Test for quality (own function)
multiQuality(woT,woP,0.5,true,classes);
microF1score = 0.9660
multiResTbl = 6×1 table
  Mean
1 exact 0.9660
2 hamming 0.9924
3 macroF1 0.8253
4 microF1 0.9660
5 fscore 0.9660
6 acc 0.9660

3 New Sentences

BERT

Iillustration how to test unrelated test senteces using BERT and the Matlab built-in function.
testSentences = [
„Siemens, Linde, BMW, Allianz und Münchner Rück sind DAX-Unternehmen mit Sitz in München.“
„Die Beteiligung an dem Elektroautohersteller Rivian, der im November an die Börse kam, verhalf Amazon außerdem zu einem Rekordgewinn.“
„Internetunternehmen wie Snap und Twitter mussten besonders deutliche Kursverluste hinnehmen.“
„Im Interview kritisiert die Wirtschaftsweise Monika Schnitzer das Vorgehen der EZB.“
];
 
 
% Encode the text data as sequences of tokens using the BERT model
% tokenizer.
tokensNew = encode(tokenizer,testSentences);
Create a mini-batch queue for the new data. Preprocess the mini-batches using the preprocessPredictors function, listed at the end of the example.
dsXNew = arrayDatastore(tokensNew,„OutputType“,„same“);
 
mbqNew = minibatchqueue(dsXNew,1,…
„MiniBatchSize“,miniBatchSize, …
„MiniBatchFcn“,@(X) preprocessPredictors(X,paddingValue,maxSequenceLength,seperatorValue));
Make predictions using the modelPredictions function, listed at the end of the example.
YPredNew = modelPredictions(parameters,mbqNew,classes,startValue,seperatorValue,paddingValue);
 
nerResults=struct();
for idx=1:length(testSentences)
tokensAct=tokenizer.FullTokenizer.decode(tokensNew{idx})‘;
nerResults.(„input“+string(idx))=array2table([tokensAct(2:end-1),YPredNew{idx}‘],„VariableNames“,[„Token“,„Entity“]);
end
 
nerResults.input1
ans = 21×2 table
  Token Entity
1 „Siemens“ „B-ORG“
2 „,“ „O“
3 „Lind“ „B-ORG“
4 „##e“ „B-ORG“
5 „,“ „O“
6 „BMW“ „B-ORG“
7 „,“ „O“
8 „Allianz“ „B-ORG“
9 „und“ „O“
10 „Münchner“ „B-ORG“
11 „Rück“ „I-ORG“
12 „sind“ „O“
13 „DA“ „O“
14 „##X“ „O“
⋮

Compare to Matlab „addEntityDetail“

mTestTokens = tokenizedDocument(testSentences,‚Language‘,‚de‘);
% do not change tokens for entities and compound woprds like (dem <-> der zum)
mTestTokens = addEntityDetails(mTestTokens,‚RetokenizeMethod‘,’none‘);
tdetailsSentences = tokenDetails(mTestTokens);
tdetailsSentences(:,[1,8])
ans = 62×2 table
  Token Entity
1 „Siemens“ organization
2 „,“ non-entity
3 „Linde“ non-entity
4 „,“ non-entity
5 „BMW“ organization
6 „,“ organization
7 „Allianz“ organization
8 „und“ non-entity
9 „Münchner“ organization
10 „Rück“ organization
11 „sind“ non-entity
12 „DAX-Unternehmen“ other
13 „mit“ non-entity
14 „Sitz“ non-entity
⋮

4 Backtest Matlab GermEval 2014

For a more systematic analysis of the improvement due to the transformer model, let’s analyze the performance of the built-in Matlab function on the test data from GermEval 2014. This requires to translate Matlab labels (like „person“ instead of „B-PER“ or „I-PER“) into the IOB coding. We first translate Matlab labels into the „B-“ categories, and determine the true labels.
load(„d:\data\TextAnalysis\NER\dataTestCell.mat“);
testTrue = sentData(:,2);
testText = sentData(:,1);
 
mTokens = tokenizedDocument(testText,‚TokenizeMethod‘,’none‘,‚Language‘,‚de‘);
mTokens = addEntityDetails(mTokens,‚RetokenizeMethod‘,’none‘);
tDetails = tokenDetails(mTokens);
 
tDetails{vertcat(tDetails{:,7})==„non-entity“,8} = „O“;
tDetails{vertcat(tDetails{:,7})==„person“,8} = „B-PER“;
tDetails{vertcat(tDetails{:,7})==„location“,8} = „B-LOC“;
tDetails{vertcat(tDetails{:,7})==„other“,8} = „B-OTH“;
tDetails{vertcat(tDetails{:,7})==„organization“,8} = „B-ORG“;
 
% true labels
mTrue=[];
for ii=1:length(sentData)
mTrue = [mTrue;vertcat(testTrue{ii})‘];
end

Transform Matlab Labels

Here, we add „I-“ lables to the Matlab results in a logically consistent sequence. For example, a sequence error like [„O“,“I-PER“] will be changed to [„O“,“B-PER“], or a sequence [„B-OTH“,“B-OTH“, „B-OTH“, „B-ORG“] will be changed to [„B-OTH“,“I-OTH“, „I-OTH“, „B-ORG“].
Note that this a general correction which can be applied to any NER model. Zöllner et al. (2021) show that even for transformer models this can lead to an improvement of about 4%-points.
 
temp = cleanNER(tDetails.Var8);
mPredict=temp;

Quality Matlab

Macro-F1 measures the quality of the Text Analytics toolbox function „addEntityDetails“. Macro-F1 for the GermEval 2014 test data is 54.26%. Using the BERT model thus leads to an improvement by about 54% or 28%-points!
woT=onehotencode(mTrue,2,‚ClassNames‘,classes);
woP=onehotencode(mPredict,2,‚ClassNames‘,classes);
 
 
multiQuality(woT,woP,0.5,true,classes);
microF1score = 0.9339
multiResTbl = 6×1 table
  Mean
1 exact 0.9339
2 hamming 0.9853
3 macroF1 0.5426
4 microF1 0.9339
5 fscore 0.9339
6 acc 0.9339

5 Testing Quality of the New hmmEntityModel Function

The new hmmEntityModel function was added in Matlab 2023a. HMM stands for Hidden Markov Model, where the model assigns joint probabilities to paired observation and label sequences. Then the model’s parameters are trained to maximize the joint likelihood. The model is thus purely statistical. This has the benefit that it is language and contrext free, i.e. you can use it for all languages supported by the Text Analytics toolbox tokenizer. Since Matlab also provides the training function trainHMMEntityModel, the new NER model also introduces the possibility to train your own model on arbitrary entities, which is not possible with the addEntityDetails function.
%% Load train data (24,000 annotated German sentences)
load(„d:\data\TextAnalysis\NER\dataTrainCell.mat“);
trainTrue = sentData(:,2);
trainText = sentData(:,1);
 
mTokens = tokenizedDocument(trainText,‚TokenizeMethod‘,’none‘,‚Language‘,‚de‘);
mTokens = addEntityDetails(mTokens,‚RetokenizeMethod‘,’none‘);
tDetails = tokenDetails(mTokens);
 
dataTrain =tDetails(:,[„Token“,„DocumentNumber“]);
 
mTrue=[];
for ii=1:length(sentData)
mTrue = [mTrue;vertcat(trainTrue{ii})‘];
end
 

Train hmmEntity Model

%% Train a hmmEntity model
dataTrain.Entity = mTrue;
%% train
mdl = trainHMMEntityModel(dataTrain,NonEntity=„O“);
save(„hmmGermanNER.mat“,‚mdl‘);
 

Test Quality of the hmmEntitiy Model

We now test the quality of the trained German hmm model, using the same test set from GermEval2014 as in the previous analyses.
%% test Matlab HMM function
load(„d:\data\TextAnalysis\NER\dataTestCell.mat“);
testTrue = sentData(:,2);
testText = sentData(:,1);
 
mTrueTest=[];
for ii=1:length(testTrue)
mTrueTest = [mTrueTest;vertcat(testTrue{ii})‘];
end
 
One tricky challenge is that the hmmEntity function retokenizes input text automatically, without the user being able to deactivate this functionality. As the retokenized tokens will be different from the test data, the ground truth labels cannot be matched to the models predictions anymore. For example, for the GermEval test set, this leads to about 96,200 predicted labels instead of 95,542 labels for the test data.
We thus have to align the predicted tokens to the test data tokens and keep the predicted labels. This is a somewhat painful task but it can be achieved by noting that most (but not all) tokenization differences arise from non-alphabetic, numeric, or underscore characters, which can be identified by a regular expression using the „\W“ identifier. Having identified token differences per sentence, one can simply delete as many \W characters as there are length differences between the test and the prediction sentence (\W tokens almost always have an „O“ entity). This requires a sentence-by-sentence cleaning procedure, however (not documented here).
mTokensTest = tokenizedDocument(testText,‚TokenizeMethod‘,’none‘,‚Language‘,‚de‘);
mTokensTest = addEntityDetails(mTokensTest,‚RetokenizeMethod‘,’none‘);
tDetailsTest = tokenDetails(mTokensTest);
 
%% predict sentence by sentence, as hmmEntitiy retokenizes uncontrollably
dataTest =tDetailsTest(:,[„Token“,„DocumentNumber“]);
dataTest.Entity = mTrueTest;
 
% proprietary „balanceTokens“ function to align tokens and labels between
% predictions and test data
resPred = balanceTokens(mTokensTest,mdl);
Starting parallel pool (parpool) using the ‚Processes‘ profile … Connected to parallel pool with 8 workers. ans = 64 ans = 96 ans = 128 ans = 256 ans = 32 ans = 160 ans = 224 ans = 63 ans = 192 ans = 95 ans = 127 ans = 31 ans = 62 ans = 94 ans = 255 ans = 126 ans = 30 ans = 125 ans = 159 ans = 191 ans = 93 ans = 254 ans = 61 ans = 223 ans = 190 ans = 158 ans = 253 ans = 189 ans = 222 ans = 92 ans = 124 ans = 157 ans = 123 ans = 60 ans = 29 ans = 221 ans = 91 ans = 252 ans = 122 ans = 59 ans = 188 ans = 90 ans = 58 ans = 89 ans = 251 ans = 121 ans = 57 ans = 156 ans = 28 ans = 187 ans = 220 ans = 88 ans = 250 ans = 155 ans = 27 ans = 186 ans = 219 ans = 249 ans = 120 ans = 56 ans = 154 ans = 87 ans = 26 ans = 185 ans = 218 ans = 248 ans = 119 ans = 55 ans = 153 ans = 86 ans = 54 ans = 184 ans = 217 ans = 85 ans = 118 ans = 152 ans = 25 ans = 183 ans = 247 ans = 117 ans = 53 ans = 216 ans = 84 ans = 246 ans = 151 ans = 24 ans = 182 ans = 83 ans = 116 ans = 52 ans = 150 ans = 23 ans = 215 ans = 245 ans = 51 ans = 214 ans = 115 ans = 149 ans = 22 ans = 244 ans = 50 ans = 148 ans = 21 ans = 181 ans = 213 ans = 114 ans = 243 ans = 113 ans = 49 ans = 147 ans = 212 ans = 20 ans = 180 ans = 82 ans = 242 ans = 146 ans = 179 ans = 241 ans = 112 ans = 48 ans = 19 ans = 211 ans = 81 ans = 145 ans = 178 ans = 210 ans = 80 ans = 240 ans = 144 ans = 18 ans = 209 ans = 79 ans = 239 ans = 111 ans = 143 ans = 17 ans = 177 ans = 208 ans = 238 ans = 47 ans = 176 ans = 78 ans = 110 ans = 16 ans = 207 ans = 46 ans = 15 ans = 175 ans = 206 ans = 77 ans = 237 ans = 236 ans = 109 ans = 45 ans = 142 ans = 14 ans = 205 ans = 76 ans = 174 ans = 108 ans = 44 ans = 141 ans = 13 ans = 75 ans = 235 ans = 173 ans = 204 ans = 12 ans = 234 ans = 107 ans = 43 ans = 140 ans = 203 ans = 74 ans = 11 ans = 172 ans = 106 ans = 42 ans = 139 ans = 202 ans = 73 ans = 233 ans = 171 ans = 72 ans = 105 ans = 138 ans = 10 ans = 201 ans = 232 ans = 41 ans = 9 ans = 170 ans = 71 ans = 137 ans = 200 ans = 231 ans = 104 ans = 40 ans = 8 ans = 169 ans = 70 ans = 136 ans = 199 ans = 230 ans = 103 ans = 39 ans = 135 ans = 38 ans = 7 ans = 168 ans = 198 ans = 69 ans = 229 ans = 102 ans = 134 ans = 197 ans = 37 ans = 6 ans = 167 ans = 68 ans = 228 ans = 101 ans = 133 ans = 36 ans = 166 ans = 196 ans = 67 ans = 132 ans = 5 ans = 227 ans = 100 ans = 35 ans = 4 ans = 195 ans = 66 ans = 99 ans = 131 ans = 165 ans = 226 ans = 34 ans = 164 ans = 194 ans = 98 ans = 3 ans = 130 ans = 2 ans = 65 ans = 225 ans = 33 ans = 163 ans = 193 ans = 97 ans = 1165 ans = 2680 ans = 129 ans = 1 ans = 162 ans = 2377 ans = 1468 ans = 862 ans = 1164 ans = 2679 ans = 1771 ans = 161 ans = 2376 ans = 1467 ans = 861 ans = 559 ans = 2678 ans = 1770 ans = 2375 ans = 1163 ans = 1466 ans = 860 ans = 558 ans = 2074 ans = 1162 ans = 1769 ans = 2374 ans = 2677 Warning: No supported language detected (based on script or alphabet), setting the language to ‚de‘. For tips showing how to use Text Analytics with languages other than English, German, Japanese, and Korean, see Language Considerations. > In corpusLanguage (line 29) In tokenizedDocument (line 73) In hmmEntityModel/predict (line 20) In parallel_function>make_general_channel/channel_general (line 837) In parallel.internal.parfor.cppRemoteParallelFunction (line 53) ans = 1465 ans = 859 ans = 1768 ans = 557 ans = 2073 ans = 1161 ans = 858 ans = 2676 ans = 1464 ans = 857 ans = 1767 ans = 556 ans = 2072 ans = 2373 ans = 1160 ans = 2675 ans = 1766 ans = 555 ans = 1463 ans = 856 ans = 2071 ans = 2372 ans = 1159 ans = 2674 ans = 1765 ans = 554 ans = 1462 ans = 1764 ans = 2070 ans = 2371 ans = 1158 ans = 2673 ans = 855 ans = 1461 ans = 1763 ans = 553 ans = 2069 ans = 2370 ans = 1460 ans = 854 ans = 1157 ans = 853 ans = 1762 ans = 552 ans = 2068 ans = 2369 ans = 2672 ans = 1459 ans = 852 ans = 1761 ans = 551 ans = 2067 ans = 2368 ans = 1156 ans = 2671 ans = 1458 ans = 2066 ans = 1155 ans = 851 ans = 550 ans = 2367 ans = 2670 ans = 1457 ans = 1760 ans = 2065 ans = 850 ans = 549 ans = 2366 ans = 1154 ans = 2669 ans = 1456 ans = 1759 ans = 2064 ans = 2365 ans = 2668 ans = 548 ans = 1153 ans = 1455 ans = 849 ans = 1758 ans = 2063 ans = 2364 ans = 2667 ans = 547 ans = 1152 ans = 848 ans = 2062 ans = 2666 ans = 1454 ans = 1757 ans = 2363 ans = 1151 ans = 1453 ans = 546 ans = 2061 ans = 2665 ans = 847 ans = 1756 ans = 2362 ans = 1150 ans = 1452 ans = 545 ans = 2060 ans = 2361 ans = 846 ans = 1755 ans = 1149 ans = 2664 ans = 1451 ans = 1754 ans = 544 ans = 2059 ans = 2360 ans = 845 ans = 2663 ans = 543 ans = 2058 ans = 2359 ans = 1148 ans = 1450 ans = 844 ans = 1753 ans = 1147 ans = 2662 ans = 2057 ans = 2358 ans = 1449 ans = 843 ans = 1752 ans = 542 ans = 2661 ans = 541 ans = 2056 ans = 1146 ans = 2660 ans = 1448 ans = 842 ans = 1751 ans = 2357 ans = 540 ans = 2055 ans = 2356 ans = 1145 ans = 1447 ans = 841 ans = 1750 ans = 2659 ans = 1446 ans = 1749 ans = 2054 ans = 2355 ans = 1144 ans = 840 ans = 539 ans = 2658 ans = 1748 ans = 2053 ans = 1143 ans = 1445 ans = 839 ans = 538 ans = 2354 ans = 2657 ans = 1444 ans = 1747 ans = 537 ans = 2052 ans = 2353 ans = 1142 ans = 838 ans = 2656 ans = 1443 ans = 837 ans = 2051 ans = 1141 ans = 2655 ans = 1746 ans = 536 ans = 2352 ans = 1140 ans = 1442 ans = 836 ans = 1745 ans = 2050 ans = 2654 ans = 535 ans = 2351 ans = 1441 ans = 835 ans = 1744 ans = 2049 ans = 1139 ans = 2653 ans = 534 ans = 2350 ans = 1440 ans = 1743 ans = 2048 ans = 1138 ans = 2652 ans = 1439 ans = 834 ans = 533 ans = 2047 ans = 833 ans = 1742 ans = 2349 ans = 1137 ans = 1438 ans = 532 ans = 2651 ans = 832 ans = 1741 ans = 2046 ans = 2348 ans = 1136 ans = 531 ans = 2650 ans = 1437 ans = 831 ans = 1740 ans = 2045 ans = 2347 ans = 1135 ans = 1436 ans = 530 ans = 2649 ans = 1739 ans = 1134 ans = 830 ans = 2044 ans = 2346 ans = 2648 ans = 1435 ans = 529 ans = 1133 ans = 1738 ans = 2043 ans = 2345 ans = 1434 ans = 829 ans = 528 ans = 2042 ans = 1132 ans = 2647 ans = 1737 ans = 1433 ans = 828 ans = 2344 ans = 2646 ans = 1736 ans = 527 ans = 2041 ans = 1131 ans = 1432 ans = 2343 ans = 2645 ans = 827 ans = 526 ans = 1130 ans = 1431 ans = 1735 ans = 2040 ans = 2342 ans = 2644 ans = 525 ans = 1129 ans = 826 ans = 1734 ans = 2039 ans = 2341 ans = 1430 ans = 2038 ans = 2643 ans = 825 ans = 1733 ans = 524 ans = 2340 ans = 1128 ans = 1429 ans = 824 ans = 2037 ans = 2642 ans = 1428 ans = 1732 ans = 523 ans = 2339 ans = 1127 ans = 2036 ans = 2641 ans = 1427 ans = 823 ans = 1731 ans = 2338 ans = 522 ans = 2035 ans = 1126 ans = 2640 ans = 822 ans = 1730 ans = 521 ans = 2337 ans = 1426 ans = 1729 ans = 2034 ans = 2336 ans = 2639 ans = 821 ans = 520 ans = 1125 ans = 1728 ans = 2033 ans = 2638 ans = 1425 ans = 820 ans = 519 ans = 2032 ans = 2335 ans = 1124 ans = 2637 ans = 1424 ans = 1727 ans = 819 ans = 518 ans = 2031 ans = 2334 ans = 1123 ans = 2636 ans = 818 ans = 1726 ans = 1423 ans = 517 ans = 2030 ans = 2333 ans = 1122 ans = 2635 ans = 1422 ans = 1725 ans = 2332 ans = 817 ans = 516 ans = 1121 ans = 2634 ans = 1724 ans = 2029 ans = 2331 ans = 1421 ans = 816 ans = 515 ans = 1120 ans = 2633 ans = 815 ans = 1723 ans = 2028 ans = 2330 ans = 1420 ans = 514 ans = 2027 ans = 1119 ans = 2632 ans = 814 ans = 1722 ans = 2329 ans = 1419 ans = 513 ans = 2026 ans = 1118 ans = 2631 ans = 813 ans = 1721 ans = 2328 ans = 1418 ans = 512 ans = 1117 ans = 2630 ans = 812 ans = 1720 ans = 2025 ans = 1417 ans = 2327 ans = 1116 ans = 811 ans = 511 ans = 2024 ans = 2629 ans = 1719 ans = 2326 ans = 1416 ans = 510 ans = 1115 ans = 2628 ans = 810 ans = 1718 ans = 2023 ans = 1415 ans = 509 ans = 2325 ans = 1114 ans = 809 ans = 2022 ans = 2324 ans = 2627 ans = 1414 ans = 1717 ans = 508 ans = 1113 ans = 808 ans = 1716 ans = 2021 ans = 2323 ans = 2626 ans = 1413 ans = 1112 ans = 807 ans = 1715 ans = 507 ans = 2020 ans = 2322 ans = 2625 ans = 1412 ans = 1111 ans = 806 ans = 506 ans = 2019 ans = 2321 ans = 2624 ans = 1411 ans = 1714 ans = 1110 ans = 805 ans = 1713 ans = 505 ans = 2018 ans = 2320 ans = 2623 ans = 1410 ans = 1109 ans = 804 ans = 504 ans = 2017 ans = 2319 ans = 2622 ans = 1409 ans = 1712 ans = 1108 ans = 503 ans = 2016 ans = 1107 ans = 2621 ans = 1408 ans = 803 ans = 1711 ans = 2318 ans = 1710 ans = 2015 ans = 1106 ans = 2620 ans = 1407 ans = 802 ans = 502 ans = 2317 ans = 2619 ans = 1406 ans = 1709 ans = 501 ans = 2014 ans = 2316 ans = 1105 ans = 801 ans = 2618 ans = 1708 ans = 500 ans = 2013 ans = 2315 ans = 1104 ans = 1405 ans = 800 ans = 2617 ans = 1707 ans = 499 ans = 2012 ans = 1103 ans = 1404 ans = 799 ans = 1706 ans = 2314 ans = 1102 ans = 2616 ans = 1403 ans = 2011 ans = 2313 ans = 798 ans = 498 ans = 2010 ans = 1101 ans = 2615 ans = 1402 ans = 1705 ans = 2312 ans = 797 ans = 497 ans = 2614 ans = 2009 ans = 1100 ans = 1401 ans = 796 ans = 1704 ans = 496 ans = 2311 ans = 2613 ans = 2008 ans = 1099 ans = 795 ans = 1703 ans = 1400 ans = 495 ans = 2007 ans = 2310 ans = 2612 ans = 1702 ans = 1098 ans = 1399 ans = 794 ans = 494 ans = 2006 ans = 2309 ans = 2611 ans = 1701 ans = 1097 ans = 1398 ans = 793 ans = 2308 ans = 2610 ans = 1700 ans = 493 ans = 2005 ans = 2307 ans = 1096 ans = 1397 ans = 792 ans = 2609 ans = 1699 ans = 492 ans = 2004 ans = 1095 ans = 1396 ans = 791 ans = 491 ans = 2306 ans = 2003 ans = 1094 ans = 2608 ans = 790 ans = 1698 ans = 490 ans = 2305 ans = 1093 ans = 1395 ans = 2002 ans = 2304 ans = 2607 ans = 1394 ans = 789 ans = 1697 ans = 489 ans = 2001 ans = 1092 ans = 1696 ans = 2303 ans = 2606 ans = 788 ans = 488 ans = 2000 ans = 2605 ans = 1393 ans = 2302 ans = 1091 ans = 787 ans = 1695 ans = 487 ans = 1090 ans = 1392 ans = 1999 ans = 2301 ans = 2604 ans = 786 ans = 1694 ans = 486 ans = 1089 ans = 1391 ans = 485 ans = 1998 ans = 2300 ans = 785 ans = 2603 ans = 1390 ans = 1693 ans = 484 ans = 1997 ans = 2299 ans = 1088 ans = 784 ans = 2602 ans = 1389 ans = 1692 ans = 1996 ans = 1087 ans = 2298 ans = 783 ans = 1691 ans = 483 ans = 1995 ans = 1086 ans = 2601 ans = 1388 ans = 2297 ans = 782 ans = 1690 ans = 2600 ans = 1387 ans = 482 ans = 1994 ans = 2296 ans = 1085 ans = 481 ans = 1084 ans = 1386 ans = 781 ans = 1689 ans = 1993 ans = 2295 ans = 2599 ans = 1688 ans = 480 ans = 1083 ans = 1385 ans = 780 ans = 1992 ans = 2294 ans = 2598 ans = 479 ans = 1384 ans = 779 ans = 1687 ans = 1991 ans = 1082 ans = 2597 ans = 478 ans = 2293 ans = 1383 ans = 778 ans = 1686 ans = 1990 ans = 1081 ans = 2596 ans = 1382 ans = 2292 ans = 2595 ans = 777 ans = 1685 ans = 477 ans = 2291 ans = 1080 ans = 1381 ans = 1684 ans = 1989 ans = 2594 ans = 776 ans = 476 ans = 2290 ans = 1079 ans = 1380 ans = 775 ans = 1683 ans = 1988 ans = 2593 ans = 1078 ans = 1379 ans = 475 ans = 1987 ans = 2289 ans = 2592 ans = 774 ans = 1682 ans = 1077 ans = 773 ans = 474 ans = 1986 ans = 2288 ans = 1378 ans = 1681 ans = 2591 ans = 473 ans = 1985 ans = 2287 ans = 1076 ans = 1377 ans = 772 ans = 1680 ans = 2590 ans = 472 ans = 1984 ans = 1075 ans = 1376 ans = 771 ans = 1679 ans = 2286 ans = 2589 ans = 1983 ans = 1678 ans = 471 ans = 2285 ans = 1074 ans = 1375 ans = 770 ans = 2588 ans = 470 ans = 1982 ans = 1374 ans = 1677 ans = 1073 ans = 2587 ans = 769 ans = 2284 ans = 469 ans = 1981 ans = 1072 ans = 1373 ans = 768 ans = 1676 ans = 2283 ans = 2586 ans = 468 ans = 1980 ans = 1071 ans = 2585 ans = 1372 ans = 1675 ans = 2282 ans = 1070 ans = 767 ans = 467 ans = 1979 ans = 1371 ans = 1674 ans = 1978 ans = 2281 ans = 2584 ans = 1370 ans = 766 ans = 466 ans = 2280 ans = 1069 ans = 2583 ans = 765 ans = 465 ans = 1977 ans = 1369 ans = 1673 ans = 1976 ans = 2279 ans = 1068 ans = 2582 ans = 764 ans = 464 ans = 1067 ans = 1368 ans = 1672 ans = 1975 ans = 2278 ans = 2581 ans = 763 ans = 1671 ans = 463 ans = 1066 ans = 2580 ans = 1367 ans = 462 ans = 1974 ans = 2277 ans = 1366 ans = 762 ans = 1670 ans = 1973 ans = 1065 ans = 2579 ans = 761 ans = 461 ans = 2276 ans = 2578 ans = 1669 ans = 1972 ans = 1064 ans = 1365 ans = 460 ans = 2275 ans = 2577 ans = 760 ans = 1668 ans = 1971 ans = 1063 ans = 759 ans = 1667 ans = 459 ans = 1970 ans = 2274 ans = 2576 ans = 1364 ans = 458 ans = 1062 ans = 2575 ans = 758 ans = 1666 ans = 1969 ans = 2273 ans = 1061 ans = 1363 ans = 757 ans = 457 ans = 1968 ans = 2574 ans = 1665 ans = 2272 ans = 1060 ans = 1362 ans = 756 ans = 1059 ans = 1664 ans = 456 ans = 1967 ans = 2573 ans = 1966 ans = 2271 ans = 1058 ans = 1361 ans = 755 ans = 1663 ans = 455 ans = 2270 ans = 2572 ans = 1360 ans = 754 ans = 1662 ans = 1965 ans = 1057 ans = 454 ans = 2571 ans = 1359 ans = 753 ans = 1964 ans = 2269 ans = 2570 ans = 1661 ans = 453 ans = 1056 ans = 1358 ans = 752 ans = 2268 ans = 1660 ans = 452 ans = 1963 ans = 2569 ans = 1055 ans = 751 ans = 2267 ans = 1357 ans = 1659 ans = 451 ans = 1962 ans = 2568 ans = 1054 ans = 750 ans = 2266 ans = 1356 ans = 1658 ans = 450 ans = 1961 ans = 1053 ans = 2567 ans = 449 ans = 1355 ans = 749 ans = 1960 ans = 2265 ans = 1052 ans = 2566 ans = 748 ans = 1657 ans = 1354 ans = 448 ans = 1959 ans = 2264 ans = 2565 ans = 1656 ans = 1051 ans = 747 ans = 447 ans = 1353 ans = 746 ans = 1655 ans = 1958 ans = 2263 ans = 1050 ans = 2564 ans = 446 ans = 1957 ans = 1352 ans = 745 ans = 1654 ans = 2262 ans = 1049 ans = 2563 ans = 445 ans = 1956 ans = 1351 ans = 744 ans = 1653 ans = 2261 ans = 1048 ans = 2562 ans = 2561 ans = 1350 ans = 743 ans = 1652 ans = 444 ans = 1955 ans = 1047 ans = 1349 ans = 2260 ans = 1046 ans = 2560 ans = 742 ans = 1651 ans = 443 ans = 1954 ans = 2259 ans = 1348 ans = 1045 ans = 2559 ans = 741 ans = 1650 ans = 442 ans = 1953 ans = 2258 ans = 1347 ans = 1952 ans = 1044 ans = 740 ans = 1649 ans = 441 ans = 2558 ans = 1346 ans = 1951 ans = 2257 ans = 1043 ans = 1345 ans = 739 ans = 1648 ans = 440 ans = 2557 ans = 738 ans = 1647 ans = 1950 ans = 2256 ans = 1042 ans = 1344 ans = 1646 ans = 439 ans = 2255 ans = 1041 ans = 2556 ans = 1343 ans = 438 ans = 2555 ans = 737 ans = 437 ans = 1949 ans = 2254 ans = 1040 ans = 1342 ans = 1645 ans = 1948 ans = 2253 ans = 2554 ans = 736 ans = 436 ans = 1039 ans = 1644 ans = 1947 ans = 2553 ans = 1341 ans = 735 ans = 2252 ans = 1643 ans = 435 ans = 1946 ans = 1038 ans = 2552 ans = 1340 ans = 734 ans = 2251 ans = 1642 ans = 434 ans = 1945 ans = 2250 ans = 2551 ans = 1339 ans = 733 ans = 433 ans = 1037 ans = 2550 ans = 1338 ans = 1944 ans = 2249 ans = 732 ans = 1641 ans = 432 ans = 1036 ans = 2549 ans = 1337 ans = 1943 ans = 2248 ans = 1640 ans = 1035 ans = 2548 ans = 731 ans = 431 ans = 1336 ans = 730 ans = 1639 ans = 1942 ans = 2247 ans = 2547 ans = 1335 ans = 430 ans = 1034 ans = 729 ans = 1638 ans = 1941 ans = 2246 ans = 1334 ans = 429 ans = 1033 ans = 2546 ans = 2245 ans = 728 ans = 1637 ans = 1333 ans = 1940 ans = 2545 ans = 1636 ans = 428 ans = 1032 ans = 727 ans = 2244 ans = 1939 ans = 427 ans = 726 ans = 2544 ans = 1332 ans = 2243 ans = 1031 ans = 1635 ans = 1331 ans = 1938 ans = 2543 ans = 426 ans = 2242 ans = 1030 ans = 725 ans = 1634 ans = 1330 ans = 425 ans = 1029 ans = 2542 ans = 724 ans = 1937 ans = 2241 ans = 1329 ans = 1633 ans = 424 ans = 1028 ans = 2541 ans = 723 ans = 1936 ans = 2240 ans = 1328 ans = 1632 ans = 423 ans = 1027 ans = 2239 ans = 2540 ans = 1327 ans = 722 ans = 1631 ans = 1935 ans = 721 ans = 422 ans = 1026 ans = 2539 ans = 1326 ans = 1934 ans = 2238 ans = 1630 ans = 421 ans = 1025 ans = 720 ans = 1933 ans = 2237 ans = 2538 ans = 1325 ans = 1629 ans = 1024 ans = 1324 ans = 420 ans = 1932 ans = 2236 ans = 2537 ans = 719 ans = 419 ans = 1023 ans = 1323 ans = 1628 ans = 1931 ans = 2235 ans = 2536 ans = 718 ans = 418 ans = 1022 ans = 1322 ans = 1627 ans = 1930 ans = 2234 ans = 2535 ans = 717 ans = 417 ans = 1929 ans = 2233 ans = 1021 ans = 1626 ans = 2534 ans = 1321 ans = 716 ans = 416 ans = 1020 ans = 1320 ans = 1625 ans = 1928 ans = 2232 ans = 1019 ans = 2533 ans = 715 ans = 415 ans = 1319 ans = 1624 ans = 1927 ans = 2231 ans = 1018 ans = 2532 ans = 714 ans = 414 ans = 1926 ans = 1318 ans = 1623 ans = 2230 ans = 1017 ans = 2531 ans = 1622 ans = 413 ans = 1925 ans = 1317 ans = 713 ans = 2229 ans = 2530 ans = 712 ans = 1016 ans = 1316 ans = 1621 ans = 412 ans = 1924 ans = 2228 ans = 1015 ans = 1923 ans = 2529 ans = 711 ans = 1620 ans = 411 ans = 1922 ans = 2227 ans = 1014 ans = 2528 ans = 1315 ans = 710 ans = 1619 ans = 410 ans = 2226 ans = 1013 ans = 1314 ans = 709 ans = 409 ans = 1921 ans = 2225 ans = 2527 ans = 1313 ans = 1618 ans = 708 ans = 1617 ans = 408 ans = 1920 ans = 1012 ans = 2526 ans = 1312 ans = 2224 ans = 2525 ans = 707 ans = 1616 ans = 407 ans = 1919 ans = 2223 ans = 1011 ans = 1311 ans = 706 ans = 2222 ans = 2524 ans = 1615 ans = 406 ans = 1918 ans = 1010 ans = 2523 ans = 1310 ans = 705 ans = 1614 ans = 1917 ans = 2221 ans = 1009 ans = 405 ans = 2522 ans = 1309 ans = 704 ans = 1613 ans = 1916 ans = 1008 ans = 404 ans = 2220 ans = 2521 ans = 703 ans = 1612 ans = 1915 ans = 2219 ans = 1308 ans = 403 ans = 1007 ans = 2520 ans = 702 ans = 1611 ans = 1307 ans = 402 ans = 1914 ans = 2218 ans = 1006 ans = 2519 ans = 701 ans = 1610 ans = 401 ans = 1913 ans = 2217 ans = 1005 ans = 1306 ans = 2518 ans = 700 ans = 1912 ans = 2216 ans = 1609 ans = 400 ans = 1004 ans = 1305 ans = 2517 ans = 699 ans = 1911 ans = 2215 ans = 1608 ans = 399 ans = 1003 ans = 1304 ans = 2516 ans = 698 ans = 1910 ans = 1303 ans = 1607 ans = 398 ans = 2214 ans = 1002 ans = 2515 ans = 697 ans = 397 ans = 1302 ans = 1606 ans = 1909 ans = 2213 ans = 1001 ans = 2514 ans = 696 ans = 1301 ans = 1605 ans = 396 ans = 1908 ans = 2212 ans = 1000 ans = 2513 ans = 695 ans = 1300 ans = 1604 ans = 395 ans = 1907 ans = 2211 ans = 999 ans = 2512 ans = 694 ans = 1299 ans = 1603 ans = 394 ans = 1906 ans = 2210 ans = 998 ans = 2511 ans = 693 ans = 1298 ans = 1602 ans = 393 ans = 1905 ans = 2209 ans = 997 ans = 2510 ans = 692 ans = 2208 ans = 1297 ans = 1601 ans = 392 ans = 1904 ans = 996 ans = 691 ans = 1600 ans = 2207 ans = 2509 ans = 1296 ans = 391 ans = 1903 ans = 995 ans = 690 ans = 1599 ans = 2206 ans = 994 ans = 2508 ans = 1295 ans = 390 ans = 1902 ans = 689 ans = 1598 ans = 389 ans = 2205 ans = 993 ans = 2507 ans = 1294 ans = 1901 ans = 1293 ans = 688 ans = 1597 ans = 388 ans = 1900 ans = 2204 ans = 992 ans = 2506 ans = 1292 ans = 687 ans = 1596 ans = 2203 ans = 2505 ans = 1595 ans = 387 ans = 1899 ans = 991 ans = 1291 ans = 1898 ans = 2202 ans = 2504 ans = 1290 ans = 686 ans = 1594 ans = 386 ans = 2201 ans = 2503 ans = 685 ans = 385 ans = 1897 ans = 990 ans = 1289 ans = 1593 ans = 2502 ans = 684 ans = 384 ans = 2200 ans = 989 ans = 1592 ans = 1896 ans = 2501 ans = 1288 ans = 683 ans = 2199 ans = 988 ans = 1591 ans = 383 ans = 1895 ans = 2500 ans = 1287 ans = 2198 ans = 987 ans = 682 ans = 1590 ans = 382 ans = 1894 ans = 2197 ans = 2499 ans = 1286 ans = 681 ans = 986 ans = 1589 ans = 381 ans = 1893 ans = 2498 ans = 680 ans = 1892 ans = 2196 ans = 985 ans = 2497 ans = 1285 ans = 1588 ans = 380 ans = 679 ans = 1891 ans = 984 ans = 2496 ans = 1587 ans = 2195 ans = 1284 ans = 678 ans = 379 ans = 983 ans = 2495 ans = 1586 ans = 1890 ans = 2194 ans = 378 ans = 982 ans = 2494 ans = 1283 ans = 677 ans = 1585 ans = 1889 ans = 2193 ans = 1282 ans = 981 ans = 2493 ans = 676 ans = 1584 ans = 377 ans = 1888 ans = 2192 ans = 1281 ans = 1887 ans = 980 ans = 2492 ans = 675 ans = 1583 ans = 376 ans = 2191 ans = 1280 ans = 375 ans = 2190 ans = 979 ans = 2491 ans = 674 ans = 1582 ans = 1886 ans = 374 ans = 1885 ans = 2189 ans = 978 ans = 2490 ans = 1279 ans = 673 ans = 1581 ans = 1884 ans = 2188 ans = 977 ans = 2489 ans = 1278 ans = 672 ans = 1580 ans = 373 ans = 1277 ans = 671 ans = 1883 ans = 2488 ans = 1579 ans = 372 ans = 2187 ans = 976 ans = 670 ans = 1882 ans = 2487 ans = 1276 ans = 1578 ans = 371 ans = 2186 ans = 1275 ans = 669 ans = 1881 ans = 2185 ans = 975 ans = 2486 ans = 1577 ans = 974 ans = 1274 ans = 370 ans = 1880 ans = 2184 ans = 2485 ans = 668 ans = 1576 ans = 973 ans = 2484 ans = 1273 ans = 1879 ans = 2183 ans = 667 ans = 369 ans = 1878 ans = 2483 ans = 1272 ans = 666 ans = 1575 ans = 2182 ans = 972 ans = 1574 ans = 368 ans = 1271 ans = 1877 ans = 971 ans = 2482 ans = 665 ans = 2181 ans = 1270 ans = 1573 ans = 367 ans = 1876 ans = 970 ans = 2481 ans = 2180 ans = 1572 ans = 1875 ans = 2480 ans = 1269 ans = 664 ans = 366 ans = 2179 ans = 969 ans = 1874 ans = 2479 ans = 1268 ans = 663 ans = 1571 ans = 365 ans = 2178 ans = 1267 ans = 968 ans = 2478 ans = 662 ans = 1570 ans = 1873 ans = 2177 ans = 967 ans = 364 ans = 2176 ans = 2477 ans = 1266 ans = 661 ans = 1569 ans = 1872 ans = 1568 ans = 363 ans = 2175 ans = 966 ans = 1871 ans = 2476 ans = 1265 ans = 660 ans = 362 ans = 1870 ans = 2475 ans = 1264 ans = 1567 ans = 2174 ans = 965 ans = 659 ans = 361 ans = 1869 ans = 964 ans = 2474 ans = 1566 ans = 2173 ans = 2473 ans = 1263 ans = 658 ans = 360 ans = 1868 ans = 657 ans = 1565 ans = 2172 ans = 963 ans = 1262 ans = 359 ans = 1867 ans = 2472 ans = 656 ans = 1564 ans = 2171 ans = 962 ans = 1261 ans = 358 ans = 2471 ans = 1563 ans = 1866 ans = 2170 ans = 1260 ans = 655 ans = 357 ans = 961 ans = 2470 ans = 1865 ans = 2169 ans = 654 ans = 1562 ans = 1259 ans = 356 ans = 1864 ans = 960 ans = 2469 ans = 1561 ans = 2168 ans = 1258 ans = 653 ans = 1863 ans = 959 ans = 2468 ans = 1560 ans = 2167 ans = 355 ans = 1862 ans = 2467 ans = 1257 ans = 652 ans = 958 ans = 354 ans = 2166 ans = 1256 ans = 651 ans = 1559 ans = 1861 ans = 957 ans = 2466 ans = 353 ans = 2165 ans = 1558 ans = 1860 ans = 2465 ans = 1255 ans = 650 ans = 352 ans = 2164 ans = 956 ans = 1557 ans = 1859 ans = 2464 ans = 1254 ans = 649 ans = 1556 ans = 351 ans = 2163 ans = 955 ans = 1253 ans = 2463 ans = 648 ans = 1858 ans = 954 ans = 1555 ans = 350 ans = 2162 ans = 1252 ans = 2462 ans = 647 ans = 1857 ans = 2161 ans = 953 ans = 1554 ans = 349 ans = 1856 ans = 2461 ans = 1251 ans = 646 ans = 2160 ans = 952 ans = 645 ans = 1553 ans = 348 ans = 1250 ans = 347 ans = 1855 ans = 2159 ans = 1552 ans = 2460 ans = 951 ans = 644 ans = 2158 ans = 1854 ans = 1249 ans = 1551 ans = 2459 ans = 346 ans = 950 ans = 643 ans = 2157 ans = 1248 ans = 1853 ans = 2458 ans = 1550 ans = 345 ans = 949 ans = 642 ans = 1247 ans = 1852 ans = 2156 ans = 2457 ans = 641 ans = 1549 ans = 344 ans = 2155 ans = 948 ans = 1851 ans = 947 ans = 2456 ans = 1246 ans = 640 ans = 1548 ans = 343 ans = 1547 ans = 1850 ans = 2154 ans = 946 ans = 2455 ans = 1245 ans = 342 ans = 639 ans = 1849 ans = 2153 ans = 1244 ans = 1546 ans = 945 ans = 2454 ans = 341 ans = 638 ans = 1848 ans = 2152 ans = 2453 ans = 1243 ans = 1545 ans = 340 ans = 944 ans = 637 ans = 1544 ans = 2151 ans = 943 ans = 2452 ans = 1242 ans = 339 ans = 1847 ans = 636 ans = 1543 ans = 2150 ans = 942 ans = 2451 ans = 1241 ans = 338 ans = 1846 ans = 1240 ans = 635 ans = 2149 ans = 634 ans = 1542 ans = 337 ans = 1845 ans = 941 ans = 2450 ans = 1239 ans = 1844 ans = 2148 ans = 940 ans = 2449 ans = 1541 ans = 336 ans = 1238 ans = 633 ans = 1843 ans = 2147 ans = 632 ans = 1540 ans = 335 ans = 939 ans = 2448 ans = 1237 ans = 1842 ans = 2146 ans = 938 ans = 2447 ans = 631 ans = 334 ans = 1236 ans = 1539 ans = 2145 ans = 937 ans = 2446 ans = 630 ans = 1538 ans = 333 ans = 1841 ans = 2144 ans = 2445 ans = 629 ans = 332 ans = 1840 ans = 936 ans = 1235 ans = 1537 ans = 2143 ans = 2444 ans = 1234 ans = 628 ans = 1839 ans = 935 ans = 1536 ans = 331 ans = 2142 ans = 2443 ans = 627 ans = 1838 ans = 934 ans = 1233 ans = 1535 ans = 330 ans = 1232 ans = 626 ans = 329 ans = 1837 ans = 2141 ans = 933 ans = 2442 ans = 625 ans = 1534 ans = 1836 ans = 1231 ans = 328 ans = 932 ans = 2441 ans = 1533 ans = 2140 ans = 1230 ans = 624 ans = 1835 ans = 931 ans = 327 ans = 1834 ans = 2139 ans = 2440 ans = 623 ans = 1532 ans = 2138 ans = 1229 ans = 326 ans = 1833 ans = 930 ans = 2439 ans = 622 ans = 1531 ans = 2137 ans = 929 ans = 1228 ans = 1530 ans = 325 ans = 1832 ans = 2438 ans = 1831 ans = 2136 ans = 928 ans = 2437 ans = 1227 ans = 621 ans = 1529 ans = 324 ans = 1830 ans = 2135 ans = 927 ans = 2436 ans = 620 ans = 1528 ans = 323 ans = 2134 ans = 1226 ans = 926 ans = 2435 ans = 1527 ans = 322 ans = 1829 ans = 2133 ans = 619 ans = 925 ans = 2434 ans = 1225 ans = 1526 ans = 321 ans = 1828 ans = 2132 ans = 1224 ans = 618 ans = 2131 ans = 924 ans = 2433 ans = 617 ans = 1525 ans = 320 ans = 1827 ans = 1223 ans = 319 ans = 1826 ans = 2130 ans = 923 ans = 2432 ans = 616 ans = 1524 ans = 2431 ans = 1222 ans = 318 ans = 2129 ans = 922 ans = 615 ans = 1523 ans = 1825 ans = 921 ans = 1221 ans = 1522 ans = 317 ans = 1824 ans = 2430 ans = 614 ans = 1823 ans = 2128 ans = 920 ans = 2429 ans = 1220 ans = 613 ans = 1521 ans = 316 ans = 1520 ans = 2127 ans = 919 ans = 1219 ans = 612 ans = 315 ans = 1822 ans = 2428 ans = 1519 ans = 2126 ans = 918 ans = 2427 ans = 1218 ans = 611 ans = 314 ans = 1821 ans = 2125 ans = 917 ans = 2426 ans = 610 ans = 1518 ans = 313 ans = 1820 ans = 2124 ans = 1217 ans = 916 ans = 1517 ans = 312 ans = 1819 ans = 2425 ans = 1216 ans = 609 ans = 2123 ans = 608 ans = 311 ans = 1818 ans = 2122 ans = 915 ans = 1215 ans = 1516 ans = 2424 ans = 607 ans = 310 ans = 1817 ans = 2423 ans = 1214 ans = 1515 ans = 2121 ans = 914 ans = 309 ans = 1816 ans = 2422 ans = 1213 ans = 606 ans = 1514 ans = 913 ans = 308 ans = 1815 ans = 2120 ans = 2421 ans = 1212 ans = 605 ans = 1513 ans = 912 ans = 307 ans = 2119 ans = 1211 ans = 604 ans = 1512 ans = 1814 ans = 911 ans = 2420 ans = 2118 ans = 1210 ans = 603 ans = 1511 ans = 306 ans = 1813 ans = 910 ans = 2419 ans = 305 ans = 2117 ans = 909 ans = 1209 ans = 602 ans = 1510 ans = 2116 ans = 2418 ans = 1208 ans = 601 ans = 1509 ans = 304 ans = 1812 ans = 908 ans = 303 ans = 2115 ans = 1207 ans = 600 ans = 1811 ans = 2417 ans = 1508 ans = 302 ans = 2114 ans = 907 ans = 1206 ans = 599 ans = 1810 ans = 906 ans = 2416 ans = 1507 ans = 301 ans = 1809 ans = 2113 ans = 1205 ans = 598 ans = 2415 ans = 1506 ans = 300 ans = 1808 ans = 2112 ans = 905 ans = 1204 ans = 597 ans = 1505 ans = 2414 ans = 596 ans = 299 ans = 1807 ans = 2111 ans = 904 ans = 1203 ans = 2413 ans = 1504 ans = 298 ans = 1806 ans = 2110 ans = 1202 ans = 595 ans = 1503 ans = 903 ans = 2412 ans = 297 ans = 2109 ans = 594 ans = 1805 ans = 902 ans = 1201 ans = 1502 ans = 1804 ans = 2108 ans = 2411 ans = 593 ans = 1501 ans = 296 ans = 901 ans = 1200 ans = 295 ans = 2107 ans = 2410 ans = 592 ans = 1500 ans = 1803 ans = 900 ans = 1199 ans = 294 ans = 2106 ans = 2409 ans = 591 ans = 1802 ans = 2105 ans = 1198 ans = 1499 ans = 293 ans = 899 ans = 2408 ans = 1197 ans = 1498 ans = 1801 ans = 2104 ans = 590 ans = 292 ans = 898 ans = 2407 ans = 1196 ans = 1800 ans = 1497 ans = 291 ans = 2103 ans = 2406 ans = 589 ans = 1799 ans = 2102 ans = 897 ans = 1195 ans = 290 ans = 896 ans = 2405 ans = 588 ans = 1496 ans = 1798 ans = 1194 ans = 1495 ans = 289 ans = 2101 ans = 895 ans = 2404 ans = 587 ans = 1797 ans = 2403 ans = 1193 ans = 288 ans = 2100 ans = 894 ans = 586 ans = 1494 ans = 1796 ans = 1192 ans = 1493 ans = 287 ans = 2099 ans = 893 ans = 2402 ans = 1191 ans = 585 ans = 286 ans = 1795 ans = 2401 ans = 2098 ans = 892 ans = 1190 ans = 584 ans = 1492 ans = 1794 ans = 1491 ans = 285 ans = 1793 ans = 2400 ans = 1189 ans = 583 ans = 2097 ans = 891 ans = 284 ans = 1792 ans = 890 ans = 2399 ans = 1188 ans = 582 ans = 1490 ans = 2096 ans = 581 ans = 283 ans = 889 ans = 2398 ans = 1489 ans = 1791 ans = 2095 ans = 1187 ans = 580 ans = 282 ans = 2397 ans = 1488 ans = 1790 ans = 888 ans = 579 ans = 281 ans = 2094 ans = 887 ans = 2396 ans = 1186 ans = 1487 ans = 578 ans = 1486 ans = 280 ans = 1789 ans = 2093 ans = 886 ans = 2395 ans = 1185 ans = 577 ans = 1788 ans = 2394 ans = 1184 ans = 1485 ans = 279 ans = 2092 ans = 885 ans = 1484 ans = 2393 ans = 576 ans = 278 ans = 1787 ans = 2091 ans = 884 ans = 1183 ans = 1483 ans = 1786 ans = 575 ans = 277 ans = 2090 ans = 883 ans = 2392 ans = 1785 ans = 1182 ans = 574 ans = 1482 ans = 276 ans = 2089 ans = 882 ans = 2391 ans = 1784 ans = 1181 ans = 573 ans = 1481 ans = 275 ans = 2088 ans = 881 ans = 2390 ans = 1180 ans = 1783 ans = 1480 ans = 274 ans = 2087 ans = 880 ans = 2389 ans = 1179 ans = 572 ans = 1782 ans = 1479 ans = 273 ans = 2086 ans = 879 ans = 2388 ans = 571 ans = 1781 ans = 2387 ans = 1178 ans = 1478 ans = 878 ans = 570 ans = 272 ans = 2085 ans = 2386 ans = 1177 ans = 1477 ans = 1780 ans = 569 ans = 271 ans = 2084 ans = 877 ans = 1176 ans = 1476 ans = 1779 ans = 2385 ans = 270 ans = 1778 ans = 2083 ans = 876 ans = 2384 ans = 1175 ans = 568 ans = 1475 ans = 269 ans = 1777 ans = 875 ans = 2383 ans = 1174 ans = 567 ans = 1474 ans = 2082 ans = 268 ans = 1776 ans = 874 ans = 2382 ans = 1173 ans = 566 ans = 2081 ans = 565 ans = 1473 ans = 267 ans = 2080 ans = 1172 ans = 266 ans = 1775 ans = 873 ans = 2381 ans = 564 ans = 1472 ans = 2079 ans = 1171 ans = 265 ans = 1774 ans = 872 ans = 2380 ans = 563 ans = 1471 ans = 1170 ans = 264 ans = 1773 ans = 2078 ans = 2379 ans = 1470 ans = 871 ans = 562 ans = 1169 ans = 263 ans = 2077 ans = 870 ans = 561 ans = 1168 ans = 262 ans = 2076 ans = 869 ans = 1167 ans = 261 ans = 868 ans = 260 ans = 867 ans = 1469 ans = 1772 ans = 560 ans = 259 ans = 866 ans = 3586 ans = 3888 ans = 258 ans = 3133 ans = 865 ans = 3887 ans = 3585 ans = 3886 ans = 3132 ans = 864 ans = 2378 ans = 3584 ans = 3885 ans = 2982 ans = 3131 ans = 2075 ans = 3583 ans = 3884 ans = 2981 ans = 3130 ans = 3284 ans = 1166 ans = 3129 ans = 3582 ans = 3883 ans = 3581 ans = 3283 ans = 2980 ans = 3435 ans = 3882 ans = 2979 ans = 3128 ans = 3282 ans = 3434 ans = 3127 ans = 3580 ans = 3881 ans = 257 ans = 3281 ans = 2978 ans = 3433 ans = 3126 ans = 3579 ans = 3880 ans = 3578 ans = 3280 ans = 2977 ans = 3432 ans = 3737 ans = 863 ans = 3125 ans = 3879 ans = 2976 ans = 3577 ans = 3736 ans = 3279 ans = 2831 ans = 3431 ans = 3878 ans = 3430 ans = 3124 ans = 2975 ans = 3576 ans = 3735 ans = 3877 ans = 3278 ans = 2830 ans = 3123 ans = 3429 ans = 2974 ans = 3575 ans = 3734 ans = 3876 ans = 3277 ans = 2829 ans = 3122 ans = 3574 ans = 2973 ans = 3428 ans = 3733 ans = 3276 ans = 2828 ans = 2972 ans = 3121 ans = 3875 ans = 3275 ans = 3427 ans = 3573 ans = 3732 ans = 3874 ans = 2827 ans = 3120 ans = 2971 ans = 3426 ans = 3572 ans = 3731 ans = 3274 ans = 2826 ans = 3119 ans = 3873 ans = 2970 ans = 3425 ans = 3571 ans = 3872 ans = 3273 ans = 3118 ans = 3570 ans = 3730 ans = 3272 ans = 2825 ans = 3871 ans = 2969 ans = 3424 ans = 3117 ans = 3569 ans = 3729 ans = 3271 ans = 2824 ans = 2968 ans = 3423 ans = 3116 ans = 3728 ans = 3870 ans = 3270 ans = 2823 ans = 3568 ans = 2967 ans = 3422 ans = 3115 ans = 3727 ans = 3869 ans = 3269 ans = 2822 ans = 3567 ans = 2966 ans = 3421 ans = 3566 ans = 3726 ans = 3868 ans = 3268 ans = 3420 ans = 3114 ans = 2821 ans = 2965 ans = 3113 ans = 3725 ans = 3867 ans = 3267 ans = 2820 ans = 2964 ans = 3419 ans = 3112 ans = 3565 ans = 3724 ans = 3866 ans = 3266 ans = 2819 ans = 2963 ans = 3418 ans = 3111 ans = 3564 ans = 3723 ans = 3865 ans = 2962 ans = 3563 ans = 3864 ans = 3265 ans = 2818 ans = 3417 ans = 3110 ans = 3722 ans = 3264 ans = 2961 ans = 3863 ans = 2817 ans = 2960 ans = 3416 ans = 3109 ans = 3562 ans = 3721 ans = 3415 ans = 3862 ans = 3263 ans = 2816 ans = 2959 ans = 3108 ans = 3561 ans = 3720 ans = 3861 ans = 3414 ans = 3262 ans = 2815 ans = 2958 ans = 3107 ans = 3261 ans = 3560 ans = 3719 ans = 3860 ans = 2957 ans = 3413 ans = 3106 ans = 3260 ans = 2814 ans = 3559 ans = 3718 ans = 3859 ans = 2956 ans = 3412 ans = 3105 ans = 3259 ans = 2813 ans = 3558 ans = 3717 ans = 2955 ans = 3104…
 
%% test
YTest = string(resPred.Entity); % prediction
TTest = dataTest.Entity; % ground truth
 
 
woT=onehotencode(TTest,2,‚ClassNames‘,classes);
woP=onehotencode(YTest,2,‚ClassNames‘,classes);
 
multiQuality(woT,woP,0.5,true,classes);
microF1score = 0.9374
multiResTbl = 6×1 table
  Mean
1 exact 0.9374
2 hamming 0.9861
3 macroF1 0.3921
4 microF1 0.9374
5 fscore 0.9374
6 acc 0.9374
As can be seen from the performace measures, the predictive quality of hmmEntity is actually worse than the addEntityDetail result with Macro-F1 of 39.2%. In return, however, one receives the flexibility to train the model on arbitrary entities.
Overall, using pre-trained BERT models is far more powerful for all NLP applications, and we have seen in this blog that the performance difference for NER is quite significant.

—————– Supporting Functions ————

Mini-batch Preprocessing Function.

The preprocessMiniBatch function preprocess the predictors using the preprocessPredictors function and then encodes the labels as encoded vectors. Use this preprocessing function to preprocess both predictors and labels.
function [X,T] = preprocessMiniBatch(X,T,paddingValue,maxSequenceLength,seperatorValue,classNames)
 
X = preprocessPredictors(X,paddingValue,maxSequenceLength,seperatorValue);
% Add padding to targets
maxLen=size(X,2);
T=cellfun(@(x) addPadLabelsNer(x,maxLen,paddingValue),T,‚UniformOutput‘,false);
T = cat(1,T{:});
T= arrayfun(@(rowIdx) onehotencode(T(rowIdx,:),1,‚ClassNames‘,classNames),1:size(T,1),‚UniformOutput‘,false);
T=cat(3,T{:});
end

Model Function

The function model performs a forward pass of the classification model.
function Y = model(X,parameters,dropout)
 
Y = bertEmbed(X,parameters,„DropoutProbability“,dropout);
 
weights = parameters.Weights.nerclassifier.kernel;
bias = parameters.Weights.nerclassifier.bias;
Y=dlmtimes(weights,Y) + bias;
 
end

Model Gradients Function

The modelGradients function performs a forward pass of the classification model and returns the model loss and gradients of the loss with respect to the learnable parameters.
function [loss,gradients] = modelGradients(X,T,parameters)
 
dropout = 0.1;
Y = model(X,parameters,dropout);
Y = softmax(Y,„DataFormat“,„CTB“);
loss = crossentropy(Y,T,„DataFormat“,„CTB“);
gradients = dlgradient(loss,parameters.Weights);
 
end

Model Predictions Function

The modelPredictions function makes predictions by iterating over mini-batches of data.
function predictions = modelPredictions(parameters,mbq,classes,startCode,separatorCode,paddingCode)
 
predictions = [];
 
dropout = 0;
 
reset(mbq);
 
while hasdata(mbq)
dlX = next(mbq);
dlYPred = model(dlX,parameters,dropout);
dlYPred = softmax(dlYPred,„DataFormat“,„CTB“);
bs=size(dlX,3);
YPred = onehotdecode(dlYPred,classes,1);
YPred=squeeze(YPred)‘;
YPred=string(YPred);
specialTokenMask=(squeeze(dlX)’==startCode)|(squeeze(dlX)’==separatorCode)|(squeeze(dlX)’==paddingCode);
YPred(specialTokenMask)=„“;
YPred=arrayfun(@(rowIdx) YPred(rowIdx,YPred(rowIdx,:)~=„“),1:bs,‚UniformOutput‘,false);
predictions=[predictions;YPred‘];
end
 
end
Schlagwörter: , ,