text:
Protein Crystallization in Microfluidics - Alex Brosseau, Cory Thomas, and Adam Selsman

CHEM-ENG 590E: Microfluidics and Microscale Analysis in Materials and Biology

Introduction

Figure 1: Chemical Structure of polyethylene glycol (PEG)6

Protein crystallization is the process of forming protein crystals. Screening for crystallization conditions is an art. There is no way to predict ahead of time the conditions that produce crystals.3 Since each protein structure is very unique the best combination of protein concentration, pH, temperature, salt concentration, and numerous other variables, varies with each protein. For example, some proteins, like many membrane proteins, do not crystallize well due to their irregular structure. Membrane proteins barely interact with one another, so an unstable crystal lattice is typically formed unless it is crystallized at highly specific conditions unique to each membrane protein. The history of protein crystallization dates back to over 150 years ago. In 1840, the first observations of protein crystallization were recorded, using evaporated worm blood to form hemoglobin crystals.3 With that discovery, protein crystallization became a popular purification method for proteins. Many scientists utilized solely protein precipitation methods, such as salting out, to separate proteins from solution rather than forming crystals. Ammonium sulfate and sodium chloride became popular salts for the protein separation technique of salting out, but other ways of precipitating protein from solution were used as well, such as temperature and pH variation. The use of these precipitation methods were used commonly during that time but were often harsh on the proteins and only the most stable ones survived the treatment. Later on, precipitating reagents like polyethylene glycol (PEG) (shown in Figure 1) became common in protein precipitation because it was found to have little effect on the structure of the protein. However, in 1935 Bernal and Crowfoot created a hydrated protein crystal and observed that the crystal gave a diffraction pattern. This led to the first successful use of protein crystallization to determine the molecular structure of myoglobin in 1958.13 With the advent of microfluidics in 1990's, protein crystallization and precipitation became a common topic to study in microfluidic devices. Originally protein crystallization and precipitation were performed in large batches, but as time went along, liquid handling robots were developed allowing for crystallization in well plates to become common. Both the development of microfluidics and liquid handling robots allowed for crystallization screening at many conditions, without using a lot of protein.

Figure 4: Phase diagram for Protein3

Theory of Protein Crystallization

Phase Diagrams

Protein crystallization largely depends on a variety of factors such as protein structure, protein concentration, precipitating reagent concentration (like PEG), salt concentration, temperature, pH, size of the solution (affects kinetics of crystallization), method of protein crystallization (microbatch, vapour diffusion) and so on. In order to crystallize a protein one must achieve a supersaturated state so that the protein molecules attract to other protein molecules rather than dissolve in the solution. There are two types of protein solids that can form from a supersaturated state: crystals (Figure 2) or precipitates (Figure 3). Similar to how solid water forms, the nature of the protein solid depends on the thermodynamics and the kinetics of solution. Thus the size of the solution can have an effect on crystallization of a protein3,9.

Typically when scientists are looking for crystal hits for a particular protein, they vary only the concentration of protein and one other parameter. A phase diagram for a protein, like in Figure 2, can be developed by varying one parameter and protein concentration independently. The phase diagram consists of 4 distinct regions: undersaturated region, metastable region, labile (nucleation) region, and precipitation region. In the undersaturated region, the adjustable parameter or protein concentration is too low to induce any protein solid formation. The metastable region is a region in which crystals can exist and grow but cannot form. Even when only two variables are varied, like in the phase diagram in Figure 2, there exists many conditions where the protein will be undersaturated. This means there is a great need for microfluidic devices that can screen at many conditions using very little protein. Many scientists put protein solution in the metastable region then add preformed microcrystals of protein to further grow the crystal. The labile, or nucleation, region is where nuclei can form that eventually lead to crystals. When solution is in the nucleation region, but too close to the precipitation region, high amounts of small, low quality crystals form. As a result many scientists limit the amount of nucleation events by shifting solution into the metastable region, where nucleation events cannot occur, by adding protein free buffer to solution.3,9

Over the years many proteins have been identified as model crystallization proteins. These proteins are often used to study crystallization or other crystallization related subjects. These model proteins include hen egg white lysozyme, hemoglobin, xylanase, and many others. Some things these proteins all have in common is that they are relatively small so they form distinct geometric crystals, are globular proteins, and are easily purified from biological sources in massive amounts (one hen egg white yields about 6 g of lysozyme). Another thing to note is that the crystals of a protein are unlike the crystals of molecules, like sodium chloride. A protein crystal is not rigid in structure rather it has a jelly like consistency since it actually contains some water, even though water exclusion is the main driving force behind protein crystal formation.

Common precipitation reagents

Since a lot proteins are unstable outside standard pH (pH 7) and room temperature (27 degrees Celsius), proteins cannot be crystallized by extreme pH variance or temperature variance like other smaller molecules. Thus proteins are largely crystallized by the addition of a precipitating reagent like salt or polyethylene glycol. However, some proteins can be precipitated out of solution by methods such as isoelectric focusing, which involves changing the pH of solution until it is near its pI (isoelectric point). The isoelectric point is the pH at which the amino acid residues of the protein possess no net charge. Since the protein at pI possesses no net charge, it is more likely to interact with other protein molecules via hydrophobic interactions rather than hydrophilic interactions with water. Bound ligands and other chemical modifications, like methylation, acetylation, and phosphorylation, have an effect on the proteins crystallization since they can shift conformation of the oligomer or other levels of structure of proteins.

Polyethylene glycol

The mechanism by which polyethylene glycol leads to formation of protein solids is not fully understood. The current theory suggests that since PEG has little effect on the protein stability, it must work by excluding water from the protein solvation layer (layer of water that surrounds a protein).1 The hydrophilic attraction of PEG pulls water away from this layer leading to protein aggregation. PEG is commonly used in industry to precipitate proteins out of solution. Various molecular weights of PEG have been made because it has been found that higher molecular weights of PEG lead to increased protein precipitation at lower concentrations of the precipitation reagent. This indicates PEG may also work by size exclusion to precipitate protein.1

Salts

Salts are very commonly used in industry to precipitate proteins out of solution. Salting out is the mechanism by which salts cause proteins to come out of solution (salting in also exists and leads to protein go into solution). Sodium chloride and ammonium sulfate are the most common of the salts for protein precipitation. Ammonium sulfate can be rather harsh in its precipitation so it is reserved for the most stable proteins. High amounts of salt shield the proteins charged residues which prevent it from interacting with water, much like isoelectric focusing. Often salts are combined with PEG or other reagents to precipitate a protein out of solution. Particularly, protein solutions at a pH far away from pI of a protein require salt to reduce the protein's charge. Studies have been done that determined the most favorable anions and cations for salting out. The order of the anion and cations are known as the Hofmeister series (shown by Figure 5). Certain salts, like sodium bromide, have to be avoided since they lead to denaturing of the protein.

Figure 5: Hofmeister Series7

Methods of Protein Crystallization

There are many setups to make protein crystals. Microbatch and vapor diffusion are discussed in this section.

Batch Crystallization

Batch crystallization is very simple in concept. A solution of the protein, precipitating reagent, salt, or other additives are mixed together to form a cocktail. A 100% silicon oil or paraffin oil is placed on top of the solution to prevent evaporation. Depending on the kinetics of the crystallization the crystals can form in matter of 15 minutes, or days. Since oil is being added, the oil and solution interface can have an effect on the crystallization, so the use of oil can change whether a crystallization hit is achieved.

Vapor Diffusion Crystallization

Figure 6: Diagram of Sitting Drop Vapor Diffusion Method8

Vapor diffusion crystallization consists of hanging drop and sitting drop methods (Figure 6). In both methods, a drop of protein solution is put onto a surface. As the names imply the drop is either hanging or sitting on the surface. The drop and surface is put into an air tight container with a reservoir solution, typically water. The solution and the drop reach a dynamic equilibrium of vapor pressure so that the drop dehydrates. This technique leads to higher levels of supersaturation than batch crystallization but can also lead to the formation of salt crystals, if salt is used.3

Microdialysis Crystallization

In microdialysis, a protein solution is put in a container. A lid with a semi-permeable dialysis membrane that does not allow protein to escape is put on top. The container is put in a reservoir solution that is comprised of precipitant solution. The precipitant molecules are small enough to diffuse through the membrane to the protein solution, raising the protein solution to multiple supersaturation levels. This method is not commonly done for protein crystallization screening.3

Free Interface and Counter Diffusion Crystallization

In both free interface and counter diffusion crystallization, the protein and precipitant solution are brought into contact in such a manner that no convective mixing occurs but only diffusion (in a wave like manner). Free interface crystallization involves formation of one type of precipitate. Counter diffusion, on the other hand, has multiple precipitation events at different points in the phase diagram. Both methods rely upon the fact proteins do not diffuse quickly (due to their size), so they stay relatively in the same place the precipitant solution diffuses to the protein. These techniques are often done by utilizing a small capillary tube to allow for concentration gradients. Other experiments have been developed using zero gravity conditions. Free interface and counter diffusion crystallization are not as common as microbatch or vapor diffusion, but microfluidic devices for protein crystallization are well suited for them due to diffusion being main driving force of mixing on microscale.3

Techniques to Analyze Protein Crystallization

Quantifying protein precipitation and crystallization can be done by using methods such as UV-Vis (light scattering) or differential scanning fluorimetry (DSF). UV-Vis techniques involve getting an optical density (OD) measurement or turbidity reading for the solution, by having a device scatter light off solution at a wavelength of 562 or 600 nm.3 One could do this measurement for various precipitating reagent concentrations and see what critical concentration leads to a spike in turbidity. The concentrations below this turbidity spike often are best for protein crystallization. DSF is important if one believes their protein solution is causing the protein to denature. In this technique a hydrophobic sensitive dye is put in the protein solution, so that it binds in the core of the protein. The protein is then heating until it unfolds (or melts). Since the dye is fluorescent, as the protein unfolds the fluorescence can be seen and melting temperature can be recorded. A decrease in melting temperature between the protein in the precipitating solution and the protein by itself indicates that the precipitating reagent may affect protein stability. Visual inspection can often be a way to tell if precipitation is occurring as well. Many reagents, like PEG, cause phase separation when mixed with the protein solution (shown by Figure 7). Phase separation is an indication of protein precipitation. Formation of a solid precipitate or a cloudiness to the solution also indicates precipitation. Often the solid precipitate will lie at bottom of the solution and supernatant will become clearer when precipitation occurs.3

Figure 7: Example of Phase Separation and Precipitate formation

Microfluidics and Protein Crystallization

Microfluidic designs for protein crystallization is done often in microfluidics. The nanoliter scale of microfluidics allows little amounts of protein to be tested in a combinatoric fashion for crystallization hits. Microfluidic devices also allow for a lot of crystallization screens to be done on a single chip, simultaneously (high thoroughput screening). However, due to the small scale, a crystallization hit on a nanoliter scale may give a false positive result. This means that when crystallization is scaled up to yield high amount of crystals under the same conditions as the microfluidic device, it will not necessarily yield crystals on the larger scale. This can be avoided by making the scale of microfluidic device large enough to eliminate false positive results. Many designs have been made to crystallize proteins but a lot of them have problems that need to be overcome. One such design was done by Quake et al.(2002) that involved an elastomer chip. In the device crystallization agents are pipetted into 48 wells and an aluminum carrier with a top and bottom plate holds the device. The carrier then uses pneumatic pressure on the wells to pressurize the fluid, forcing them into the chip.4 Protein solution is then added to each well in the device.4 In order to observe the crystallization, windows are created in the device. With this type of device, 6,048 crystallization experiments can be conducted at once using 150 microliters of protein solution. The main problem with this device is that it requires high pressures up to 7 psi, as well as a custom designed aluminum carrier device. However, using a device such as the one created by Quake et al. allows for protein crystallization screening that can not be done on a larger scale very successfully.

Figure 8: Quake et al. Device4

Quick Protein Solubility Chip

Figure 9: Microfluidic device made by Gang Li et al that allows for testing of protein crystallization in 24 wells.12

A centrifugal PDMS-glass derived microfluidic device has been developed by Gang Li et al. for high output protein crystallization. The circular device has 24 wells for precipitants around the outside of the device and a protein inlet in the middle, as seen in Figure 9. The precipitant and protein solutions are metered by the capillary effect of the glass through the channels, and the centrifugal force allows for the mixing of precipitant and protein in the reaction well.12

The device has been experimentally proven and provides an economical way to test different solution's effect on a desired protein. To use the device, a lab would need a centrifugal device to effectively spin the device and a X-ray diffraction machine for analysis.12

Project Progress

The goal of the project is to develop an easy to use microfluidic device that can test for protein precipitation (not crystallization) with 4 precrystallization test solutions (PCT) from Hampton Research.5 The motivation for why this device should be made is that there seems to be no design that can easily test for whether protein precipitates at various conditions. This quick solubility protein test can be used by anyone and would allow for testing of many precipitating solutions in a short amount of time. Although this device will not be designed for testing for crystallization it will be designed for protein precipitation, which gives scientists a lead on what optimal conditions could be close to those necessary for crystallization. The current design has a total of 5 wells: 4 for the PCT solutions and 1 for protein solution. The PCT and protein solutions are driven out from their wells by centrifugal force due to rotation of the chip.10,11 The wells are placed so that fluid flow is in the direction of the centrifugal force. Metering of PCT and protein solutions are done by varying rotation speeds and the distances that the wells are from the center mixing well, as well as using capillary valves. The center well will be mixed by shaking the device. There are some challenges associated with the device design. PDMS, the material being used for the device design, is inherently hydrophobic which prevents PCT solutions from flowing in the channels. The use of a glass base on the device allows for solution to flow, due to glass being hydrophilic. Determining the right dimensions for the capillary valves is also a challenge. The constriction of the valve needs to be small enough to prevent flow of solution through, but large enough to allow for centrifugal force of rotation to push the liquid through. This issue can be described using the Capillary Number, which is a dimensionless number that refers to the ratio of viscous forces to surface tension and described by the equation, $Ca=\mu V/ \sigma$. In order for successful use of the capillary valves, when standing alone, the surface tension must dominate. This means that the liquid will not be able to overcome the surface tension and move through the valve. This surface tension is created due to the capillary pressure created by the valve, which keeps the fluid from flowing through the valve without external force. In order to utilize the capillary valves, centrifugal force is used to overcome the capillary pressure and break the surface tension, allowing for the solution to flow through the valves. A precisely calculated diameter for the tube is key to successfully utilizing these capillary valves.

The 4 PCT solutions provided by Hampton research are made of 0.1 M Tris hydrochloride (pH 8.5), 2.0 M Ammonium sulfate; 0.1 M Tris hydrochloride (pH 8.5), 0.2 M Magnesium chloride hexahydrate, 30% Polyethylene glycol 4,000; 0.1 M Tris hydrochloride (pH 8.5), 1.0 M Ammonium sulfate; and 0.1 M Tris hydrochloride (pH 8.5), 0.2 M Magnesium chloride hexahydrate, 15% Polyethylene glycol 4,000.5 The PCT solutions are designed to evaluate whether a certain protein concentration leads to undersaturation or precipitate formation. The formation of precipitate in at least half of reagents provides a lead for protein concentration that is suitable for crystallization. These PCT solutions are designed for efficient screening which makes them well suited for a microfluidic screening device. Challenges such as non uniform mixing are inherent to larger scale crystallization. Also, larger scale designs do not easily allow for screening at many supersaturation points on the phase diagram without utilizing immense amounts of protein and precipitant materials. Using a microfluidic device would allow for consistent uniform mixing of precipitant solution and protein. Overall, a quick protein solubility chip would easily allow some to screen for protein crystallization in an easy manner while also utilizing small amounts of protein.

File:QuickproteinDesign.jpg
Figure 10: Quick Protein Solubility Design: Image Currently in Progress

References

1-Sim, S.-L.; He, T.; Tscheliessnig, A.; Mueller, M.; Tan, R. B.; Jungbauer, A. Protein precipitation by polyethylene glycol: A generalized model based on hydrodynamic radius. Journal of Biotechnology 2012, 157 (2), 315–319 DOI: 10.1016/j.jbiotec.2011.09.028.

2-Paterová, J.; Rembert, K. B.; Heyda, J.; Kurra, Y.; Okur, H. I.; Liu, W. R.; Hilty, C.; Cremer, P. S.; Jungwirth, P. Reversal of the Hofmeister Series: Specific Ion Effects on Peptides. The Journal of Physical Chemistry B 2013, 117 (27), 8150–8158 DOI: 10.1021/jp405683s.

3-Luft, J. R.; Newman, J.; Snell, E. H. Crystallization screening: the influence of history on current practice. Acta Crystallographica Section F Structural Biology Communications 2014, 70 (7), 835–853 DOI: 10.1107/s2053230x1401262x.

4-Hansen, C. L.; Skordalakes, E.; Berger, J. M.; Quake, S. R. A robust and scalable microfluidic metering method that allows protein crystal growth by free interface diffusion. Proceedings of the National Academy of Sciences 2002, 99 (26), 16531–16536 DOI: 10.1073/pnas.262485199.

5-Hampton Research http://www.hamptonresearch.com/ (accessed Apr 7, 2017).

6-NF Monographs: Polyethylene Glycol http://www.pharmacopeia.cn/v29240/usp29nf24s0_m66430.html (accessed Apr 7, 2017).

7-Darryl, E. Hofmeister Series http://www.chemistry.sjsu.edu/deggers/.

8-Adachi, H.; Takano, K.; Morikawa, M.; Kanaya, S.; Yoshimura, M.; Mori, Y.; Sasaki, T. Application of a two-liquid system to sitting-drop vapour-diffusion protein crystallization http://journals.iucr.org/d/issues/2003/01/00/ts0154/ts0154fig1.html

9-Chayen, N. E.; Saridakis, E. Protein crystallization: from purified protein to diffraction-quality crystal. Nature Methods 2008, 5 (2), 147–153 DOI: 10.1038/nmeth.f.203.

10-Zoval, J.; Jia, G.; Kido, H.; Kim, J.; Kim, N.; Madou, M. Centrifuge-Based Fluidic Platforms. Springer Handbook of Nanotechnology 2007, 549–570 DOI: 10.1007/978-3-540-29857-1_20.

11-Schwemmer, F.; Blanchet, C. E.; Spilotros, A.; Kosse, D.; Zehnle, S.; Mertens, H. D. T.; Graewert, M. A.; Rössle, M.; Paust, N.; Svergun, D. I.; et al. LabDisk for SAXS: a centrifugal microfluidic sample preparation platform for small-angle X-ray scattering. Lab Chip 2016, 16 (7), 1161–1170 DOI: 10.1039/c5lc01580d.

12-Li, G.; Chen, Q.; Li, J.; Hu, X.; Zhao, J. Analytical Chemistry 2010, 82 (11), 4362–4369.

13-Kendrew, J. C.; Bodo, G.; Dintzis, H. M.; Parrish, R. G.; Wyckoff, H.; Phillips, D. C. A Three-Dimensional Model of the Myoglobin Molecule Obtained by X-Ray Analysis. Nature 1958, 181 (4610), 662–666 DOI: 10.1038/181662a0.


text:
## Franklin's Notes

### Mobius transformation

If $\mathbb k$ is a field and $\hat{\mathbb k}=\mathbb k\cup{\infty}$, then a mobius transformation is a function of the form where $ad-bc\ne 0$, defined with domain and codomain $\hat{\mathbb k}$ such that $f(-d/c)=\infty$ and $f(\infty)=a/c$. Most often, mobius transformations are considered in complex projective space $\hat{\mathbb C}$, where they are the simplest kind of rational function (i.e. a rational function of order $1$) and have remarkable geometric properties.

Proposition 1. For any field $\mathbb k$, a mobius transformation is a bijection $\hat{\mathbb k}\to\hat{\mathbb k}$.

Proof. To see why $f$ is bijective, it suffices to express it as a composition of bijections on $\hat{\mathbb k}$. If $c=0$, then $f$ is a linear function, making it bijective. On the other hand, if $c\ne 0$, we may write so that $f$ is the composition of the following three maps: Notice that $b-dac^{-1}\ne 0$, since $ad-bc\ne 0$ as part of the definition of a mobius transformation. This means that $f$ is the composition of two linear functions with leading coefficient $\ne 0$ and an inversion. Linear function with nonzero leading coefficient are bijective in $\hat{\mathbb k}$, since they are bijective on $\mathbb k$ and send $\infty\mapsto\infty$, and inversion is also bijective since it sends each nonzero element of $\mathbb k$ to its multiplicative inverse and $0\leftrightarrow \infty$. Thus, $f$ is bijective. $\blacksquare$

format: plain


text:
# Kerodon

$\Newextarrow{\xRightarrow}{5,5}{0x21D2}$ $\newcommand\empty{}$

Example 2.4.4.6 (The Path Category of a Simplex). Let $n \geq 0$ be a nonnegative integer and let $\operatorname{Path}[n]_{\bullet }$ denote the simplicial category of Notation 2.4.3.1. For any simplicial category $\operatorname{\mathcal{C}}_{\bullet }$, we have canonical bijections

$\operatorname{Hom}_{\operatorname{Cat_{\Delta }}}( \operatorname{Path}[n]_{\bullet }, \operatorname{\mathcal{C}}_{\bullet } ) \simeq \operatorname{N}^{\operatorname{hc}}_{n}(\operatorname{\mathcal{C}}) \simeq \operatorname{Hom}_{\operatorname{Set_{\Delta }}}( \Delta ^ n, \operatorname{N}^{\operatorname{hc}}_{\bullet }(\operatorname{\mathcal{C}}) ).$

It follows that $\operatorname{Path}[n]_{\bullet }$ is a path category for the standard simplex $\Delta ^ n$, in the sense of Definition 2.4.4.1.


text:
# Evaluating machine learning models: How to tackle metrics

Once a model has been trained, it can be evaluated in different ways and with more or less complex and meaningful procedures and metrics. However, the number and possible criteria for evaluating machine learning models can initially be quite confusing to someone who is just starting to deal with the field of machine learning.

For example, it depends on whether the learning is un-supervised or supervised. In the case of supervised learning it also depends on whether we are dealing with a regression or classification, the underlying use case, and so on – to name just a few criteria. I would like to start with supervised learning and classification. In this article I will introduce seven common metrics and methods for evaluating machine learning models using one example throughout this post. However, a detailed discussion would be beyond the scope of this introduction, so I will only touch only briefly on the mathematics underlying the metrics.

## Use case

A manufacturer of drinking glasses wants to identify and sort out defective glasses in his production. A model for image classification is to be trained and used for this purpose. The database consists of images of intact and defective glasses. Intact glasses are represented by 0 in this binary classification; accordingly, defective glasses are represented by 1.

In the following test data (y_true), for example, eight defective and two intact glasses are present and seven of them are correctly classified as defective by the model (y_pred).

# Test data
y_true: [0, 1, 1, 1, 0, 1, 1, 1, 1, 1]

# Forecast/prediction of the model
y_pred: [0, 0, 1, 1, 0, 1, 1, 1, 1, 1]

## Accuracy

Accuracy is probably the most easily understood metric and compares the number of correct classifications to all the classifications to be made.
$$Accuracy=\frac{\#\ correctly\ classified}{\#\ all\ classifications}$$
In the following example, only one value was wrongly predicted and therefore an accuracy of 90% was achieved.

y_true:   [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
y_pred:   [0, 1, 0, 0, 0, 1, 1, 1, 1, 1]
Accuracy: 90%.

If the classes in the data are extremely unevenly distributed, viewing the accuracy alone can unfortunately lead to wrong conclusions. For example, if one class exists nine times more often in the data than the other, simply predicting the more frequent class is enough to achieve 90% accuracy – although the model may not be able to predict the other class. Whether the model is able to distinguish defective glasses from intact glasses is not assessable with this metric and a class distribution, since it always seems to predict a defective glass, as seen in the following example.

y_true:   [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
y_pred:   [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Accuracy: 90%.

In addition to such imponderables, it naturally also depends on the use case which metrics can be used for evaluating machine learning models.

## Binary classification

First, a binary classification [1] can distinguish four cases:

• The class was predicted – which is correct (hit, true positive)
• The class was not predicted – which is correct (reject, true negative)
• The class was predicted – which is wrong (false alarm, false positive)
• The class was not predicted – which is wrong (miss, false negative)

For these four cases, however, different designations are common [2]. Since hit, correct reject, false alarm and miss seem to be most descriptive to me, I will use them here.

## Trade-Off between coverage and precision

If, for example, it is important to recognize a class in the data as comprehensively as possible, the coverage (recall, hit rate, true positive rate) can be used as a quality criterion. Recall represents the number of hit in relation to the sum of hit and miss, i.e. all defective glasses to be detected:
$$Recall=\frac{hit}{hit+miss}$$
If the model as above simply predicts a defective glass, i.e. only one class, the coverage is of course still $$hit=9$$ and $$miss=0$$ and thus $$Recall=\frac{9}{9+0}=1$$.

In contrast to this, precision describes the ratio of the number of hit to the sum of hit and false alarm, i.e. all glasses supposedly detected as defective:
$$Precision=\frac{hit}{hit+false\ alarm}$$
At this point, predicting only one class would of course increase the number of false alarm to 1 and thus result in less precision – $$Precision=\frac{9}{9+1}=0,9$$.

Finally, the coverage describes how many supposed hits there were and the precision how many were correct. Achieving both complete coverage and high precision is desirable. In practice, however, this will not always be possible and the focus will not always be on both. The F-measurement can be evaluated so that the two metrics do not have to be checked and weighed up against each other at the same time.

## F-measurement / F1-Score

The F-measurement describes the harmonic mean between recall and precision and combines the two metrics to one value [3].
$$F1=2*\frac{Recall*Precision}{Recall+Precision}$$
The use of the harmonic mean means that the metric is somewhat more ‘sensitive’ to the smaller of the two values than it would be in the arithmetic mean.
For example, a recall value of $$1,0$$ and a precision value of $$0,1$$ results in an arithmetic mean of $$\frac{1,0+0,1}{2}=0,55$$ – which intuitively does not do justice to the small value of precision. However, the harmonic mean is calculated to $$\frac{2*1,0*0,1}{1,0+0,1}=0,18$$ and points to a worse model.

The F1 score is derived from a more general variant, the F-beta score.
$$F_{\beta}=(1+\beta^2)*\frac{Precision * Recall}{(\beta^2*Precision)+Recall}$$
With the F1 score, $$\beta$$ is set to 1 and thus recall and precision are weighted equally. If the application requires it, Recall and Precision can also be weighted differently. A $$\beta$$ value between 0 and 1 weights the precision more strongly, a value greater than 1 weights the recall more strongly.

However, even in this metric an unequal distribution of the classes in the data can falsify the result. In addition, the case correct recject is not considered in the F measure. A method would be desirable that considers all above mentioned cases of a binary classification, proves to be robust against unbalanced class distributions and is easy to represent.

## Confusion Matrix

The comparison of the model’s predictions and the correct values in the form of a contingency table provides a more detailed insight into the model’s performance. For each case, the number of times it occurred in the result is counted, and the number is entered into a contingency table. The rows describe the predictions and the columns show the correct values. In the binary case this table is also called Confusion Matrix [2].
The four cases can be found in this matrix, for example:

In the following example, the classes are not distributed equally but are in the ratio $$7:3$$.

y_true: [0, 0, 0, 1, 1, 1, 1, 1, 1, 1]
y_pred: [0, 1, 1, 0, 1, 1, 1, 1, 1, 1]

hit = 6, false alarm = 2, miss = 1, correct reject = 1

The model has six defective glasses correctly detected (hit) and one correctly classified as correct reject. However, two intact glasses were detected as defective (false alarm) and one defective glass was not detected (miss). The aim is to achieve the highest possible values in the matrix on the diagonal from top left to bottom right – i.e. high values only for hit and correct reject.

The matrix considers all cases, but keeping track is not always easy, and a statement about the performance of the model is intuitively not possible on the fly. Nevertheless, one gets an impression of how the results relate to each other. For example, the values that influence Recall and Precision can be found directly in the matrix.

## Matthews Correlation Coefficient (MCC)

A metric that summarizes all cases and is considered suitable for application to data sets with unbalanced class distributions is Matthews Correlation Coefficient [4,5,6]. It can be read and calculated from the Confusion Matrix as follows:

$$MCC = \frac{hit*miss-false\ alarm*correct\ reject}{\sqrt{(hit+f.alarm)(hit+miss)(c.rej+f.alarm)(c.rej.+miss)}}$$

The value range of the metric is between -1 and 1. The value 1 is desirable, 0 is random, and negative values indicate a contradictory assessment of the model. However, the MCC is not defined if one of the four sums in the denominator is 0.

## The crux

The values for Accuracy, Precision and Recall in the above example of the Confusion Matrix are:

Accuracy:  0.70
Precision: 0.75
Recall:    0.86

If we compare this model to another only on the basis of accuracy, this could already lead to the exclusion of the model at this point.
A model with good accuracy and bad values for recall and precision could be preferable, but not necessarily the best model for this application. In this case, the metrics Recall and Precision, for example, would be more interesting, since they deal more precisely with the requirements and thus the model can be better assessed and compared.
This means that pure confidence in accuracy can again lead to unfavorable conclusions about the performance of a model, depending on the application. This phenomenon is commonly known as the Accuracy Paradox [7].

In addition, depending on the distribution of classes in the data, some metrics may not represent changes in the predictions or may tend in different directions. The following examples give another small impression of how different the ratings can be.

y_true:   [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
y_pred:   [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Accuracy: 0.90
F1 score: 0.95 (0.9474)
Matthews CC: 0.00

With a value of >= 0.90, F1 and Accuracy already seem to be a quite good model. However, the Matthews Correlation Coefficient clouds the picture of the model and points to randomly correct predictions, since the intact glasses are extremely underrepresented and this one was even wrongly classified.

In the following case, undamaged glasses are more often present in the data and thus allow for a better evaluation.

y_true:   [0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
y_pred:   [1, 0, 1, 1, 1, 1, 1, 1, 1, 1]
Accuracy: 0.90
F1 score: 0.94 (0.9412)
Matthews CC: 0.67 (0.6667)

Matthews Correclation Coefficient now points to a better model with a value of 0.67, since one of the two intact glasses was recognized correctly at least once. Accuracy and F1 do not react at all or only slightly to the change and they are calculated to the same or quite similar values as in the previous example. But will the decisions still be made by chance? After all, the two intact glasses are classified right in one case and once wrong in the other.

In the following example, three good glasses have been predicted twice correctly and once wrongly, so that the performance of the model can be evaluated even better. Matthews Correlation Coefficient acknowledges this with an increase from 0.67 to 0.76 and F1 with a further devaluation from 0.94 to 0.93.

y_true:   [0, 0, 0, 1, 1, 1, 1, 1, 1, 1]
y_pred:   [1, 0, 0, 1, 1, 1, 1, 1, 1, 1]
Accuracy: 0.90
F1 score: 0.93 (0.9333)
Matthews CC: 0.76 (0.7638)

This means that it is advisable to use the values of several metrics when comparing models and especially in case of unbalanced class distributions and to determine in advance which metrics are relevant for the application case.

However, what is the minimum score that we can be satisfied with regarding this model? This, of course, depends on the use case or the requirements and is often difficult to assess if there are no comparative variables such as the reliability of a human decision maker.
Further graphical presentation of the performance of a model can be instructive and help achieve a good trade-off.

## Trade-Off between hit and false alarm rate

While the glass manufacturer’s sales department strives to achieve the highest possible throughput in production, the quality and legal department will be more eager to minimize the number of defective glasses going on sale. This means that the sales department wants to avoid waste consisting of glasses unnecessarily classified as defective (false alarm). The quality assurance department, on the other hand, insists on recognising all defective glasses (hits) – even if this means that a few intact glasses cannot be sold.

The Receiver Operating Characteristic curve (ROC curve) [8] compares the proportion of objects correctly classified as positive, i.e. the hit rate, with the proportion of objects falsely classified as positive, i.e. the false alarm rate, in a diagram. The false alarm rate describes the ratio of the number of glasses falsely detected as defective to the number of glasses detected as intact.
$$False\ Alarm\ Rate = \frac{false\ alarm}{false\ alarm + correct\ reject}$$

This means that the proportion of glasses correctly identified as defective is compared with the proportion of glasses falsely identified as defective.

Additionally it is also a matter of optimizing a threshold value. Depending on the method used, the predictions of a model will not always only output the numbers 0 and 1 for classification. Rather, the values lie between 0 and 1 and thus describe a probability of belonging to a class, which is then to be interpreted. This means at what value do you want to accept that a class has been recognized?

The values of the hit rate are entered on the vertical per threshold value and the values of the false alarm rate on the horizontal. The diagonal from bottom left to top right describes the random limit. That means curves that tend far above this limit and into the upper left corner represent a good evaluation. The hit rate there is as high as possible and the false alarm rate very low at the same time. The result is this typical curve (black in the diagram) on which you can now decide which trade-off to enter, or – if you enter several models – which model can be used with which threshold value, or whether to continue training.

With the model in the following example (orange curve in the diagram), a hit rate of 0.86 could be achieved if a false alarm rate of 0.33 is accepted and a threshold value of 0.3 is applied. The thresholds themselves are not shown in the curve, but are listed in the following table.

y_true: [0    0    0    1    1    1    1    1    1    1   ]
y_pred: [0.22 0.24 0.40 0.23 0.30 0.42 0.70 0.50 0.60 0.80]

Hit rate:         [0.00 0.14 0.71 0.71 0.86 0.86 1.00 1.00]
False alarm rate: [0.00 0.00 0.00 0.33 0.33 0.67 0.67 1.00]
Thresholds:       [1.80 0.80 0.42 0.40 0.30 0.24 0.23 0.22]

If you insist on a false alarm rate of 0, a hit rate of 0.71 is possible. For this purpose, the threshold value must be set to at least 0.42. In practice, of course, there are more data records available and correspondingly much finer gradations from which a threshold value can be selected. In addition, the area under the curve Area Under Curve AUC can be interpreted with a value between 0 and 1. In this case, 1 once again represents the best value and 0.5 represents the coincidence or in this case also the worst value [9]. The AUC values for the curves are listed in the key of the diagram.

## Evaluating machine learning models – Conclusion

In general, you can try to train a model that achieves the best possible values for all metrics. In practice, however, the effort required to achieve the last per mille of improvement often does not justify the actual benefit. A pragmatic, application-oriented approach is more likely to lead to success and provides the necessary leeway to achieve a meaningful trade-off. After all, with the test results and the resulting metric values, the models can only be compared with each other. How good a model really is will then be shown in practice and a justification as to how the model came to its decision has not yet been given, but in some areas it may well be necessary [10].

## References

1] Wikipedia, Evaluation of a binary classifier
[2] Wikipedia, Confusion Matrix
[3] TYutaka Sasaki, 2007, The truth of the F-measure https://www.toyota-ti.ac.jp/Lab/Denshi/COIN/people/yutaka.sasaki/F-measure-YS-26Oct07.pdf
4] Boughorbel S, Jarray F, El-Anbari M (2017) Optimal classifier for imbalanced data using Matthews Correlation Coefficient metric. PLoS ONE 12(6): e0177678. doi.org/10.1371/journal.pone.0177678
[5] Davide Chicco, 2017, Ten quick tips for machine learning in computational biology. doi:10.1186/s13040-017-0155-3
[6] Wikipedia, Matthews correlation coefficient
[8] Tom Fawcett, 2005, An introduction to ROC analysis, doi.org/10.1016/j.patrec.2005.10.010


text:
## FANDOM

74 Pages

The first inaccessible cardinal is the smallest cardinal that is both regular and a limit cardinal, excluding zero and aleph null. This means that it has a cofinality equal to itself, and is not the successor to any other cardinal.


text:
## Monday, January 19, 2015

### Codeforces Round #286 (Div. 1) Problem D - Mr. Kitayuta's Colorful Graph

Problem Statement:
506D - Mr. Kitayuta's Colorful Graph

Solution:
The problem can be divided into (although not mutually exclusive) parts, first one is to effectively build the connectivity information in O(N), and the second part is to manage the queries. I am not so sure about the complexity analysis for the query handling part, but the following works.

First part: building the connectivity information using disjoint set union. Here is a simple yet powerful idea I learnt from the submissions made by clever gods who had solved the problem during the contest. We start out with an empty graph G. Then we incrementally add a new edge e. This edge has a color c and has two end points u and v. Before we add the edge and connect those vertices, we examine first whether each of u and v belong to any edges with color c. Let's say u indeed has such edge, call one of them e'. Since the addition of e to u will lead to e' and e being connected, we can simply represent this connection using a disjoint set union! So upon addition of e to u, e and e' are in the same set. Notice that we only need one of such edge e', since we have the invariant that every other e' incident to u will already be in the same disjoint set as e'! This is a very powerful observation, and this simplify the construction of the disjoint set union structure to O(N) overall.

Second part: handling the queries. For each query, we have a pair of vertices u and v. At this point we will iterate through the edges incident upon u, not all of them, but only one of each color (hence in essence we are iterating through all possible edge colors incident to u): For each such e with color c, we check if v has also an edge e' with color c (any one of them), which can be done in $$O(\lg{N})$$ if we store this information using tree like structure. Then if e and e' belong to the same disjoint union set, we conclude that u is connected to v under color c. Hence the rest of the problem is just a matter of counting the number of such c. We can speed up the whole calculation by storing the computed results for every pair of u and v so far, and to pass the time limit, for each pair u,v being considered, we must only iterate through the vertex which is incident with least number of different colored edges.

I am thinking about the case where N(N+1)/2 = 100,000 = M, where every node has N-1 edges with different colors incident upon it. In this case, in each query (u,v), we must do $$O(N)$$ checking, or $$O(N\lg{N})$$ to be more precise, so for this case, N will be around 450, and the total operations needed will be something around 280 million computations, which is reasonable to be done in less than 4 seconds. In fact this will be the worst case running time, since if there are some nodes which has more than N-1 differently colored edge incident upon it, some nodes are necessarily have less of such edges, hence whenever possible for each (u,v) a query, we will want to choose the one with less number of edges. And I believe that the number of pairs with (u,v) both has more than N-1 number of differently colored edges will be considerably less. A better analysis with stronger observation might be best though..

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <utility>
#include <cstdio>
using namespace std;

int par[100005];
int r[100005];
void init(){for(int i=0;i<=100000;++i)par[i]=i;}
int getpar(int u){return (par[u]==u?u:(par[u]=getpar(par[u])));}
void join(int u, int v){
int x = getpar(u);
int y = getpar(v);
if(x == y) return;
if(r[x] != r[y]){
if(r[x] > r[y])par[y] = x;
else par[x] = y;
} else {
r[x]++;
par[y] = x;
}
}
int N, M, Q;
int u,v,c;
map<int,int> color[100005];
map<pair<int,int>,int> ans;
typedef map<int,int>::iterator mit;
int main(){
scanf("%d%d",&N,&M);
init();
for(int i=1;i<=M;++i){
scanf("%d%d%d",&u,&v,&c);
int a = 0, b = 0;
if(color[u].count(c)) a = color[u][c];
if(color[v].count(c)) b = color[v][c];
color[u][c] = i;
color[v][c] = i;
if(a>0) join(i,a);
if(b>0) join(i,b);
}
scanf("%d",&Q);
while(Q--){
scanf("%d%d",&u,&v);
if(u>v)swap(u,v);
if(ans.count(make_pair(u,v))){
printf("%d\n",ans[make_pair(u,v)]);
continue;
}
int ret = 0;
if(color[u].size() > color[v].size())swap(u,v);
for(mit uit = color[u].begin(); uit != color[u].end(); ++uit){
mit vit = color[v].find(uit->first);
if(vit == color[v].end()) continue;
if(getpar(uit->second) == getpar(vit->second)) ++ret;
}
if(u>v)swap(u,v);
ans[make_pair(u,v)] = ret;
printf("%d\n", ret);
}
return 0;
}


text:
# SNOPT

TOMLAB /SNOPT (hereafter referred to as SNOPT) is a general-purpose system for constrained optimization. It minimizes a linear or nonlinear function subject to bounds on the variables and sparse linear or nonlinear constraints. It is suitable for large-scale linear and quadratic programming and for linearly constrained optimization, as well as for general nonlinear programs of the form (SparseNP)

$\begin{array}{cc} \min_{x} & f_{0}(x)\\ \text{subject to} & l \le \left(\begin{array}{c}x \\ f(x) \\ A_L x \end{array}\right) \le u \end{array}$

where l and u are constant lower and upper bounds, f0 (x) is a smooth scalar objective function, AL is a sparse matrix, and f (x) is a vector of smooth nonlinear constraint functions {fi (x)}. An optional parameter maximize may specify that f0 (x) should be maximized instead of minimized.

Ideally, the first derivatives (gradients) of f0 (x) and fi (x) should be known and coded by the user.

Note that upper and lower bounds are specified for all variables and constraints. This form allows full generality in specifying various types of constraint. Special values are used to indicate absent bounds ($l_j = -\infty$ or $u_j = +\infty$ for appropriate j). Free variables and free constraints ("free rows") are ones that have both bounds infinite. Fixed variables and equality constraints have lj = uj .

## Contents

### Problem types

If f0 (x) is linear and f (x) is absent, SparseNP is a linear program (LP) and SNOPT applies the primal simplex method. Sparse basis factors are maintained by LUSOL as in MINOS.

If only the objective is nonlinear, the problem is linearly constrained (LC) and tends to solve more easily than the general case with nonlinear constraints (NC). For both cases, SNOPT applies a sparse sequential quadratic programming (SQP) method, using limited-memory quasi-Newton approximations to the Hessian of the Lagrangian. The merit function for steplength control is an augmented Lagrangian, as in the dense SQP solver NPSOL.

In general, SNOPT requires less matrix computation than NPSOL and fewer evaluations of the functions than the nonlinear algorithms in MINOS.

It is suitable for nonlinear problems with thousands of constraints and variables, and is efficient if many constraints and bounds are active at a solution. (Thus, ideally there should not be thousands of degrees of freedom.)


text:
# Condition of Constancy of the Function

Fact. Suppose function ${y}={f{{\left({x}\right)}}}$ is defined and continuous on interval ${X}$ and has finite derivative ${f{'}}{\left({x}\right)}$. Function ${y}={f{{\left({x}\right)}}}$ is constant if and only if ${f{'}}{\left({x}\right)}$ for all ${x}$ in ${X}$.

This fact means that if on some interval derivative of function equals 0 then function is constant their, its graph is just horizontal line.

Corollary. Suppose two function ${y}={f{{\left({x}\right)}}}$ and ${y}={g{{\left({x}\right)}}}$ are defined and continuous on interval ${X}$, and have finite derivatives ${f{'}}{\left({x}\right)}$ and ${g{{\left({x}\right)}}}$. Function ${y}={f{{\left({x}\right)}}}$ is constant if and only if ${f{'}}{\left({x}\right)}$ for all ${x}$ in ${X}$. If ${f{'}}{\left({x}\right)}={g{'}}{\left({x}\right)}$ on interval ${X}$ then ${f{{\left({x}\right)}}}={g{{\left({x}\right)}}}+{C}$, where ${C}$ is a constant for all ${x}$ in ${X}$.

This corollary means that if functions have same derivatives on interval ${X}$ then their difference is constant.

Example 1. Consider functions ${f{{\left({x}\right)}}}={\operatorname{arctan}{{\left({x}\right)}}}$ and ${g{{\left({x}\right)}}}={\operatorname{arcsin}{{\left(\frac{{x}}{{\sqrt{{{1}+{{x}}^{{2}}}}}}\right)}}}$.

They are defined and continuous on interval ${\left(-\infty,\infty\right)}$.

Since ${f{'}}{\left({x}\right)}=\frac{{1}}{{{1}+{{x}}^{{2}}}}$ and ${g{'}}{\left({x}\right)}=\frac{{1}}{{{1}-{{\left(\frac{{x}}{\sqrt{{{1}+{{x}}^{{2}}}}}\right)}}^{{2}}}}\cdot\frac{{\sqrt{{{1}+{{x}}^{{2}}}}-\frac{{{{x}}^{{2}}}}{{\sqrt{{{1}+{{x}}^{{2}}}}}}}}{{{1}+{{x}}^{{2}}}}=\frac{{1}}{{{1}+{{x}}^{{2}}}}$ then according to corollary ${\operatorname{arctan}{{\left({x}\right)}}}={\operatorname{arcsin}{{\left(\frac{{x}}{{\sqrt{{{1}+{{x}}^{{2}}}}}}\right)}}}+{C}$ on ${\left(-\infty,\infty\right)}$.

To find constant plug any value of ${x}$, for example, ${x}={0}$: ${\operatorname{arctan}{{\left({0}\right)}}}={\operatorname{arcsin}{{\left(\frac{{0}}{\sqrt{{{1}+{{0}}^{{2}}}}}\right)}}}+{C}$ or ${C}={0}$.

So, we have the following fact: ${\operatorname{arctan}{{\left({x}\right)}}}={\operatorname{arcsin}{{\left(\frac{{x}}{\sqrt{{{1}+{{x}}^{{2}}}}}\right)}}}$ for all ${x}$.

Example 2. Consider functions ${f{{\left({x}\right)}}}={\operatorname{arctan}{{\left({x}\right)}}}$ and ${g{{\left({x}\right)}}}=\frac{{1}}{{2}}{\operatorname{arctan}{{\left(\frac{{{2}{x}}}{{{1}-{{x}}^{{2}}}}\right)}}}$.

It can be easily proven that ${f{'}}{\left({x}\right)}={g{'}}{\left({x}\right)}$. However, function ${g{{\left({x}\right)}}}$ is not defined when ${x}=\pm{1}.$ So, $\frac{{1}}{{2}}{\operatorname{arctan}{{\left(\frac{{{2}{x}}}{{{1}-{{x}}^{{2}}}}\right)}}}={\operatorname{arctan}{{\left({x}\right)}}}+{C}$ on ${\left(-\infty,-{1}\right)},{\left(-{1},{1}\right)},{\left({1},\infty\right)}$.

It is interesting that constant will be different for different intervals.

For interval ${\left(-{1},{1}\right)}$ we plug ${x}={0}$: $\frac{{1}}{{2}}{\operatorname{arctan}{{\left(\frac{{{2}\cdot{0}}}{{{1}-{{0}}^{{2}}}}\right)}}}={\operatorname{arctan}{{\left({0}\right)}}}+{C}$ or ${C}={0}$.

For interval ${\left(-\infty,-{1}\right)}$ we let ${x}\to-\infty$: ${0}=-\frac{\pi}{{2}}+{C}$ or ${C}=\frac{\pi}{{2}}$.

For interval ${\left({1},\infty\right)}$ we let ${x}\to\infty$: ${0}=\frac{\pi}{{2}}+{C}$ or ${C}=-\frac{\pi}{{2}}$.

So,

$\frac{{1}}{{2}}{\operatorname{arctan}{{\left(\frac{{{2}{x}}}{{{1}-{{x}}^{{2}}}}\right)}}}={\operatorname{arctan}{{\left({x}\right)}}}+\frac{\pi}{{2}}$ on ${\left(-\infty,-{1}\right)}$,

$\frac{{1}}{{2}}{\operatorname{arctan}{{\left(\frac{{{2}{x}}}{{{1}-{{x}}^{{2}}}}\right)}}}={\operatorname{arctan}{{\left({x}\right)}}}$ on ${\left(-{1},{1}\right)}$,

$\frac{{1}}{{2}}{\operatorname{arctan}{{\left(\frac{{{2}{x}}}{{{1}-{{x}}^{{2}}}}\right)}}}={\operatorname{arctan}{{\left({x}\right)}}}-\frac{\pi}{{2}}$ on ${\left({1},\infty\right)}$.

Graph confirms these facts.