text:
Fairness (machine learning)

Fairness in machine learning refers to the various attempts at correcting algorithmic bias in automated decision processes based on machine learning models. Decisions made by computers after a machine-learning process may be considered unfair if they were based on variables considered sensitive. Examples of these kinds of variable include gender, ethnicity, sexual orientation, disability and more. As it is the case with many ethical concepts, definitions of fairness and bias are always controversial. In general, fairness and bias are considered relevant when the decision process impacts people's lives. In machine learning, the problem of algorithmic bias is well known and well studied. Outcomes may be skewed by a range of factors and thus might be considered unfair with respect to certain groups or individuals. An example would be the way social media sites deliver personalized news to consumers.

Context

Research about fairness in machine learning is a relatively recent topic. In 2018, a majority of papers on the topic had been published in the preceding three years.[1] That same year, IBM introduced AI Fairness 360, a Python library with several algorithms to reduce software bias and increase its fairness[2][3] and Facebook made public their use of a tool, Fairness Flow, to detect bias in their AI. However, the source code of the tool is not accessible.[4] In 2019, Google published a set of tools in GitHub to study the effects of fairness in the long run.[5]

Controversies

The use of algorithmic decision making in the legal system has been a notable area of use under scrutiny. In 2014, then U.S. Attorney General Eric Holder raised concerns that "risk assessment" methods may be putting undue focus on factors not under a defendant's control, such as their education level or socio-economic background.[6] An investigative report published by ProPublica in 2016 claimed that the COMPAS software, widely used in US courts to predict recidivism, was racially biased. The report claimed that black defendants were almost twice as likely to be incorrectly labelled as higher risk than white defendants, while making the opposite mistake with white defendants.[7] Racial and gender bias has also been noted in image recognition algorithms. Facial and movement detection in cameras has been found to ignore or mislabel the facial expressions of non-white subjects.[8] In 2015, the automatic tagging feature in both Flickr and Google Photos was found to label black people with tags such as "animal" and "gorilla".[9] A 2016 international beauty contest judged by an AI algorithm was found to be biased towards individuals with lighter skin, likely due to bias in training data.[10] A study of three commercial gender classification algorithms in 2018 found that all three algorithms were generally most accurate when classifying light-skinned males and worst when classifying dark-skinned females.[11]

Group Fairness criteria

In classification problems, an algorithm learns a function to predict a discrete characteristic ${\textstyle Y}$, the target variable, from known characteristics ${\textstyle X}$. We model ${\textstyle A}$ as a discrete random variable which encodes some characteristics contained or implicitly encoded in ${\textstyle X}$ that we consider as sensitive characteristics (gender, ethnicity, sexual orientation, etc.). We finally denote by ${\textstyle R}$ the prediction of the classifier. Now let us define three main criteria to evaluate if a given classifier is fair, that is if its predictions are not influenced by some of these sensitive variables.[12]

Independence

We say the random variables ${\textstyle (R,A)}$ satisfy independence if the sensitive characteristics ${\textstyle A}$ are statistically independent of the prediction ${\textstyle R}$, and we write

${\displaystyle R\bot A.}$
We can also express this notion with the following formula:
${\displaystyle P(R=r\ |\ A=a)=P(R=r\ |\ A=b)\quad \forall r\in R\quad \forall a,b\in A}$
This means that the classification rate for each target classes is equal for people belonging to different groups with respect to sensitive characteristics ${\displaystyle A}$.

Yet another equivalent expression for independence can be given using the concept of mutual information between random variables, defined as

${\displaystyle I(X,Y)=H(X)+H(Y)-H(X,Y)}$
In this formula, ${\textstyle H(X)}$ is the entropy of the random variable ${\displaystyle X}$. Then ${\textstyle (R,A)}$ satisfy independence if ${\textstyle I(R,A)=0}$.

A possible relaxation of the independence definition include introducing a positive slack ${\textstyle \epsilon >0}$ and is given by the formula:

${\displaystyle P(R=r\ |\ A=a)\geq P(R=r\ |\ A=b)-\epsilon \quad \forall r\in R\quad \forall a,b\in A}$

Finally, another possible relaxation is to require ${\textstyle I(R,A)\leq \epsilon }$.

Separation

We say the random variables ${\textstyle (R,A,Y)}$ satisfy separation if the sensitive characteristics ${\textstyle A}$ are statistically independent of the prediction ${\textstyle R}$ given the target value ${\textstyle Y}$, and we write

${\displaystyle R\bot A\ |\ Y.}$
We can also express this notion with the following formula:
${\displaystyle P(R=r\ |\ Y=q,A=a)=P(R=r\ |\ Y=q,A=b)\quad \forall r\in R\quad q\in Y\quad \forall a,b\in A}$
This means that all the dependence of the decision ${\displaystyle R}$ on the sensitive attribute ${\displaystyle A}$ must be justified by the actual dependence of the true target variable ${\displaystyle Y}$.

Another equivalent expression, in the case of a binary target rate, is that the true positive rate and the false positive rate are equal (and therefore the false negative rate and the true negative rate are equal) for every value of the sensitive characteristics:

${\displaystyle P(R=1\ |\ Y=1,A=a)=P(R=1\ |\ Y=1,A=b)\quad \forall a,b\in A}$
${\displaystyle P(R=1\ |\ Y=0,A=a)=P(R=1\ |\ Y=0,A=b)\quad \forall a,b\in A}$

A possible relaxation of the given definitions is to allow the value for the difference between rates to be a positive number lower than a given slack ${\textstyle \epsilon >0}$, rather than equal to zero.

In some fields separation (separation coefficient) in a confusion matrix is a measure of the distance (at a given level of the probability score) between the predicted cumulative percent negative and predicted cumulative percent positive.

The greater this separation coefficient is at a given score value, the more effective the model is at differentiating between the set of positives and negatives at a particular probability cut-off. According to Mayes:[13] "It is often observed in the credit industry that the selection of validation measures depends on the modeling approach. For example, if modeling procedure is parametric or semi-parametric, the two-sample K-S test is often used. If the model is derived by heuristic or iterative search methods, the measure of model performance is usually divergence. A third option is the coefficient of separation...The coefficient of separation, compared to the other two methods, seems to be most reasonable as a measure for model performance because it reflects the separation pattern of a model."

Sufficiency

We say the random variables ${\textstyle (R,A,Y)}$ satisfy sufficiency if the sensitive characteristics ${\textstyle A}$ are statistically independent of the target value ${\textstyle Y}$ given the prediction ${\textstyle R}$, and we write

${\displaystyle Y\bot A\ |\ R.}$
We can also express this notion with the following formula:
${\displaystyle P(Y=q\ |\ R=r,A=a)=P(Y=q\ |\ R=r,A=b)\quad \forall q\in Y\quad r\in R\quad \forall a,b\in A}$
This means that the probability of actually being in each of the groups is equal for two individuals with different sensitive characteristics given that they were predicted to belong to the same group.

Relationships between definitions

Finally, we sum up some of the main results that relate the three definitions given above:

• Assuming ${\textstyle Y}$ is binary, if ${\textstyle A}$ and ${\textstyle Y}$ are not statistically independent, and ${\textstyle R}$ and ${\textstyle Y}$ are not statistically independent either, then independence and separation cannot both hold.
• If ${\textstyle (R,A,Y)}$ as a joint distribution has positive probability for all its possible values and ${\textstyle A}$ and ${\textstyle Y}$ are not statistically independent, then separation and sufficiency cannot both hold.

Mathematical formulation of group fairness definitions

Preliminary definitions

Most statistical measures of fairness rely on different metrics, so we will start by defining them. When working with a binary classifier, both the predicted and the actual classes can take two values: positive and negative. Now let us start explaining the different possible relations between predicted and actual outcome:[14]

Confusion matrix
• True positive (TP): The case where both the predicted and the actual outcome are in a positive class.
• True negative (TN): The case where both the predicted outcome and the actual outcome are assigned to the negative class.
• False positive (FP): A case predicted to befall into a positive class assigned in the actual outcome is to the negative one.
• False negative (FN): A case predicted to be in the negative class with an actual outcome is in the positive one.

These relations can be easily represented with a confusion matrix, a table that describes the accuracy of a classification model. In this matrix, columns and rows represent instances of the predicted and the actual cases, respectively.

By using these relations, we can define multiple metrics which can be later used to measure the fairness of an algorithm:

• Positive predicted value (PPV): the fraction of positive cases which were correctly predicted out of all the positive predictions. It is usually referred to as precision, and represents the probability of a correct positive prediction. It is given by the following formula:

${\displaystyle PPV=P(actual=+\ |\ prediction=+)={\frac {TP}{TP+FP}}}$

• False discovery rate (FDR): the fraction of positive predictions which were actually negative out of all the positive predictions. It represents the probability of an erroneous positive prediction, and it is given by the following formula:

${\displaystyle FDR=P(actual=-\ |\ prediction=+)={\frac {FP}{TP+FP}}}$

• Negative predicted value (NPV): the fraction of negative cases which were correctly predicted out of all the negative predictions. It represents the probability of a correct negative prediction, and it is given by the following formula:

${\displaystyle NPV=P(actual=-\ |\ prediction=-)={\frac {TN}{TN+FN}}}$

• False omission rate (FOR): the fraction of negative predictions which were actually positive out of all the negative predictions. It represents the probability of an erroneous negative prediction, and it is given by the following formula:

${\displaystyle FOR=P(actual=+\ |\ prediction=-)={\frac {FN}{TN+FN}}}$

• True positive rate (TPR): the fraction of positive cases which were correctly predicted out of all the positive cases. It is usually referred to as sensitivity or recall, and it represents the probability of the positive subjects to be classified correctly as such. It is given by the formula:

${\displaystyle TPR=P(prediction=+\ |\ actual=+)={\frac {TP}{TP+FN}}}$

• False negative rate (FNR): the fraction of positive cases which were incorrectly predicted to be negative out of all the positive cases. It represents the probability of the positive subjects to be classified incorrectly as negative ones, and it is given by the formula:

${\displaystyle FNR=P(prediction=-\ |\ actual=+)={\frac {FN}{TP+FN}}}$

• True negative rate (TNR): the fraction of negative cases which were correctly predicted out of all the negative cases. It represents the probability of the negative subjects to be classified correctly as such, and it is given by the formula:

${\displaystyle TNR=P(prediction=-\ |\ actual=-)={\frac {TN}{TN+FP}}}$

• False positive rate (FPR): the fraction of negative cases which were incorrectly predicted to be positive out of all the negative cases. It represents the probability of the negative subjects to be classified incorrectly as positive ones, and it is given by the formula:

${\displaystyle FPR=P(prediction=+\ |\ actual=-)={\frac {FP}{TN+FP}}}$

Relationship between fairness criteria as shown in Barocas et al.[12]

The following criteria can be understood as measures of the three general definitions given at the beginning of this section, namely Independence, Separation and Sufficiency. In the table[12] to the right, we can see the relationships between them.

To define these measures specifically, we will divide them into three big groups as done in Verma et al.:[14] definitions based on a predicted outcome, on predicted and actual outcomes, and definitions based on predicted probabilities and the actual outcome.

We will be working with a binary classifier and the following notation: ${\textstyle S}$ refers to the score given by the classifier, which is the probability of a certain subject to be in the positive or the negative class. ${\textstyle R}$ represents the final classification predicted by the algorithm, and its value is usually derived from ${\textstyle S}$, for example will be positive when ${\textstyle S}$ is above a certain threshold. ${\textstyle Y}$ represents the actual outcome, that is, the real classification of the individual and, finally, ${\textstyle A}$ denotes the sensitive attributes of the subjects.

Definitions based on predicted outcome

The definitions in this section focus on a predicted outcome ${\textstyle R}$ for various distributions of subjects. They are the simplest and most intuitive notions of fairness.

• Demographic parity, also referred to as statistical parity, acceptance rate parity and benchmarking. A classifier satisfies this definition if the subjects in the protected and unprotected groups have equal probability of being assigned to the positive predicted class. This is, if the following formula is satisfied:

${\displaystyle P(R=+\ |\ A=a)=P(R=+\ |\ A=b)\quad \forall a,b\in A}$

• Conditional statistical parity. Basically consists in the definition above, but restricted only to a subset of the instances. In mathematical notation this would be:

${\displaystyle P(R=+\ |\ L=l,A=a)=P(R=+\ |\ L=l,A=b)\quad \forall a,b\in A\quad \forall l\in L}$

Definitions based on predicted and actual outcomes

These definitions not only considers the predicted outcome ${\textstyle R}$ but also compare it to the actual outcome ${\textstyle Y}$.

• Predictive parity, also referred to as outcome test. A classifier satisfies this definition if the subjects in the protected and unprotected groups have equal PPV. This is, if the following formula is satisfied:

${\displaystyle P(Y=+\ |\ R=+,A=a)=P(Y=+\ |\ R=+,A=b)\quad \forall a,b\in A}$

Mathematically, if a classifier has equal PPV for both groups, it will also have equal FDR, satisfying the formula:

${\displaystyle P(Y=-\ |\ R=+,A=a)=P(Y=-\ |\ R=+,A=b)\quad \forall a,b\in A}$

• False positive error rate balance, also referred to as predictive equality. A classifier satisfies this definition if the subjects in the protected and unprotected groups have aqual FPR. This is, if the following formula is satisfied:

${\displaystyle P(R=+\ |\ Y=-,A=a)=P(R=+\ |\ Y=-,A=b)\quad \forall a,b\in A}$

Mathematically, if a classifier has equal FPR for both groups, it will also have equal TNR, satisfying the formula:

${\displaystyle P(R=-\ |\ Y=-,A=a)=P(R=-\ |\ Y=-,A=b)\quad \forall a,b\in A}$

• False negative error rate balance, also referred to as equal opportunity. A classifier satisfies this definition if the subjects in the protected and unprotected groups have equal FNR. This is, if the following formula is satisfied:

${\displaystyle P(R=-\ |\ Y=+,A=a)=P(R=-\ |\ Y=+,A=b)\quad \forall a,b\in A}$

Mathematically, if a classifier has equal FNR for both groups, it will also have equal TPR, satisfying the formula:

${\displaystyle P(R=+\ |\ Y=+,A=a)=P(R=+\ |\ Y=+,A=b)\quad \forall a,b\in A}$

• Equalized odds, also referred to as conditional procedure accuracy equality and disparate mistreatment. A classifier satisfies this definition if the subjects in the protected and unprotected groups have equal TPR and equal FPR, satisfying the formula:

${\displaystyle P(R=+\ |\ Y=y,A=a)=P(R=+\ |\ Y=y,A=b)\quad y\in \{+,-\}\quad \forall a,b\in A}$

• Conditional use accuracy equality. A classifier satisfies this definition if the subjects in the protected and unprotected groups have equal PPV and equal NPV, satisfying the formula:

${\displaystyle P(Y=y\ |\ R=y,A=a)=P(Y=y\ |\ R=y,A=b)\quad y\in \{+,-\}\quad \forall a,b\in A}$

• Overall accuracy equality. A classifier satisfies this definition if the subject in the protected and unprotected groups have equal prediction accuracy, that is, the probability of a subject from one class to be assigned to it. This is, if it satisfies the following formula:

${\displaystyle P(R=Y,A=a)=P(R=Y\ |\ A=b)\quad \forall a,b\in A}$

• Treatment equality. A classifier satisfies this definition if the subjects in the protected and unprotected groups have an equal ratio of FN and FP, satisfying the formula:

${\displaystyle {\frac {FN_{A=a}}{FP_{A=a}}}={\frac {FN_{A=b}}{FP_{A=b}}}}$

Definitions based on predicted probabilities and actual outcome

These definitions are based in the actual outcome ${\textstyle Y}$ and the predicted probability score ${\textstyle S}$.

• Test-fairness, also known as calibration or matching conditional frequencies. A classifier satisfies this definition if individuals with the same predicted probability score ${\textstyle S}$ have the same probability of being classified in the positive class when they belong to either the protected or the unprotected group:

${\displaystyle P(Y=+\ |\ S=s,A=a)=P(Y=+\ |\ S=s,A=b)\quad \forall s\in S\quad \forall a,b\in A}$

• Well-calibration is an extension of the previous definition. It states that when individuals inside or outside the protected group have the same predicted probability score ${\textstyle S}$ they must have the same probability of being classified in the positive class, and this probability must be equal to ${\textstyle S}$:

${\displaystyle P(Y=+\ |\ S=s,A=a)=P(Y=+\ |\ S=s,A=b)=s\quad \forall s\in S\quad \forall a,b\in A}$

• Balance for positive class. A classifier satisfies this definition if the subjects constituting the positive class from both protected and unprotected groups have equal average predicted probability score ${\textstyle S}$. This means that the expected value of probability score for the protected and unprotected groups with positive actual outcome ${\textstyle Y}$ is the same, satisfying the formula:

${\displaystyle E(S\ |\ Y=+,A=a)=E(S\ |\ Y=+,A=b)\quad \forall a,b\in A}$

• Balance for negative class. A classifier satisfies this definition if the subjects constituting the negative class from both protected and unprotected groups have equal average predicted probability score ${\textstyle S}$. This means that the expected value of probability score for the protected and unprotected groups with negative actual outcome ${\textstyle Y}$ is the same, satisfying the formula:

${\displaystyle E(S\ |\ Y=-,A=a)=E(S\ |\ Y=-,A=b)\quad \forall a,b\in A}$

Social welfare function

Some scholars have proposed defining algorithmic fairness in terms of a social welfare function. They argue that using a social welfare function enables an algorithm designer to consider fairness and predictive accuracy in terms of their benefits to the people affected by the algorithm. It also allows the designer to trade off efficiency and equity in a principled way.[15] Sendhil Mullainathan has stated that algorithm designers should use social welfare functions in order to recognize absolute gains for disadvantaged groups. For example, a study found that using a decision-making algorithm in pretrial detention rather than pure human judgment reduced the detention rates for Blacks, Hispanics, and racial minorities overall, even while keeping the crime rate constant.[16]

Individual Fairness criteria

An important distinction among fairness definitions is the one between group and individual notions.[17][18][14][19] Roughly speaking, while group fairness criteria compare quantities at a group level, typically identified by sensitive attributes (e.g. gender, ethnicity, age, etc...), individual criteria compare individuals. In words, individual fairness follow the principle that "similar individuals should receive similar treatments".

There is a very intuitive approach to fairness, which usually goes under the name of Fairness Through Unawareness (FTU), or Blindness, that prescribe not to explicitly employ sensitive features when making (automated) decisions. This is effectively a notion of individual fairness, since two individuals differing only for the values of their sensitive attributes would receive the same outcome.

However, in general, FTU is subject to several drawbacks, the main being that it does not take into account possible correlations between sensitive attributes and non-sensitive attributes employed in the decision-making process. For example, an agent with the (malignant) intention to discriminate on the basis of gender could introduce in the model a proxy variable for gender (i.e. a variable highly correlated with gender) and effectively using gender information while at the same time being compliant to the FTU prescription.

The problem of what variables correlated to sensitive ones are fairly employable by a model in the decision-making process is a crucial one, and is relevant for group concepts as well: independence metrics require a complete removal of sensitive information, while separation-based metrics allow for correlation, but only as far as the labeled target variable "justify" them.

The most general concept of individual fairness was introduced in the pioneer work by Dwork and collaborators in 2012[20] and can be thought of as a mathematical translation of the principle that the decision map taking features as input should be built such that it is able to "map similar individuals similarly", that is expressed as a Lipschitz condition on the model map. They call this approach Fairness Through Awareness (FTA), precisely as counterpoint to FTU, since they underline the importance of choosing the appropriate target-related distance metric in order to assess which individuals are similar in specific situations. Again, this problem is very related to the point raised above about what variables can be seen as "legitimate" in particular contexts.

Causality-based metrics

Causal fairness measures the frequency with which two nearly identical users or applications who differ only in a set of characteristics with respect to which resource allocation must be fair receive identical treatment.[21] An entire branch of the academic research on fairness metrics is devoted to leverage causal models to assess bias in machine learning models. This approach is usually justified by the fact that the same observational distribution of data may hide different causal relationships among the variables at play, possibly with different interpretations of whether the outcome are affected by some form of bias or not.[12]

Kusner et al.[22] propose to employ counterfactuals, and define a decision-making process counterfactually fair if, for any individual, the outcome does not change in the counterfactual scenario where the sensitive attributes are changed. The mathematical formulation reads:

${\displaystyle P(R_{A\leftarrow a}=1\ |\ A=a,X=x)=P(R_{A\leftarrow b}=1\ |\ A=a,X=x),\quad \forall a,b;}$

that is: taken a random individual with sensitive attribute ${\displaystyle A=a}$ and other features ${\displaystyle X=x}$ and the same individual if she had ${\displaystyle A=b}$, they should have same chance of being accepted. The symbol ${\displaystyle {\hat {R}}_{A\leftarrow a}}$ represents the counterfactual random variable ${\displaystyle R}$ in the scenario where the sensitive attribute ${\displaystyle A}$ is fixed to ${\displaystyle A=a}$. The conditioning on ${\displaystyle A=a,X=x}$ means that this requirement is at the individual level, in that we are conditioning on all the variables identifying a single observation.

Bias Mitigation strategies

Fairness can be applied to machine learning algorithms in three different ways: data preprocessing, optimization during software training, or post-processing results of the algorithm.

Preprocessing

Usually, the classifier is not the only problem; the dataset is also biased. The discrimination of a dataset ${\textstyle D}$ with respect to the group ${\textstyle A=a}$ can be defined as follows:

${\displaystyle disc_{A=a}(D)={\frac {|\{X\in D|X(A)\neq a,X(Y)=+\}|}{|\{X\in D|X(A)\neq a\}|}}-{\frac {|\{X\in D|X(A)=a,X(Y)=+\}|}{|\{X\in D|X(A)=a\}|}}}$

That is, an approximation to the difference between the probabilities of belonging in the positive class given that the subject has a protected characteristic different from ${\textstyle a}$ and equal to ${\textstyle a}$.

Algorithms correcting bias at preprocessing remove information about dataset variables which might result in unfair decisions, while trying to alter as little as possible. This is not as simple as just removing the sensitive variable, because other attributes can be correlated to the protected one.

A way to do this is to map each individual in the initial dataset to an intermediate representation in which it is impossible to identify whether it belongs to a particular protected group while maintaining as much information as possible. Then, the new representation of the data is adjusted to get the maximum accuracy in the algorithm.

This way, individuals are mapped into a new multivariable representation where the probability of any member of a protected group to be mapped to a certain value in the new representation is the same as the probability of an individual which doesn't belong to the protected group. Then, this representation is used to obtain the prediction for the individual, instead of the initial data. As the intermediate representation is constructed giving the same probability to individuals inside or outside the protected group, this attribute is hidden to the classificator.

An example is explained in Zemel et al.[23] where a multinomial random variable is used as an intermediate representation. In the process, the system is encouraged to preserve all information except that which can lead to biased decisions, and to obtain a prediction as accurate as possible.

On the one hand, this procedure has the advantage that the preprocessed data can be used for any machine learning task. Furthermore, the classifier does not need to be modified, as the correction is applied to the dataset before processing. On the other hand, the other methods obtain better results in accuracy and fairness.[24]

Reweighing

Reweighing is an example of a preprocessing algorithm. The idea is to assign a weight to each dataset point such that the weighted discrimination is 0 with respect to the designated group.[25]

If the dataset ${\textstyle D}$ was unbiased the sensitive variable ${\textstyle A}$ and the target variable ${\textstyle Y}$ would be statistically independent and the probability of the joint distribution would be the product of the probabilities as follows:

${\displaystyle P_{exp}(A=a\wedge Y=+)=P(A=a)\times P(Y=+)={\frac {|\{X\in D|X(A)=a\}|}{|D|}}\times {\frac {|\{X\in D|X(Y)=+\}|}{|D|}}}$

In reality, however, the dataset is not unbiased and the variables are not statistically independent so the observed probability is:

${\displaystyle P_{obs}(A=a\wedge Y=+)={\frac {|\{X\in D|X(A)=a\wedge X(Y)=+\}|}{|D|}}}$

To compensate for the bias, the software adds a weight, lower for favored objects and higher for unfavored objects. For each ${\textstyle X\in D}$ we get:

${\displaystyle W(X)={\frac {P_{exp}(A=X(A)\wedge Y=X(Y))}{P_{obs}(A=X(A)\wedge Y=X(Y))}}}$

When we have for each ${\textstyle X}$ a weight associated ${\textstyle W(X)}$ we compute the weighted discrimination with respect to group ${\textstyle A=a}$ as follows:

${\displaystyle disc_{A=a}(D)={\frac {\sum W(X)X\in \{X\in D|X(A)\neq a,X(Y)=+\}}{\sum W(X)X\in \{X\in D|X(A)\neq a\}}}-{\frac {\sum W(X)X\in \{X\in D|X(A)=a,X(Y)=+\}}{\sum W(X)X\in \{X\in D|X(A)=a\}}}}$

It can be shown that after reweighting this weighted discrimination is 0.

Inprocessing

Another approach is to correct the bias at training time. This can be done by adding constraints to the optimization objective of the algorithm.[26] These constraints force the algorithm to improve fairness, by keeping the same rates of certain measures for the protected group and the rest of individuals. For example, we can add to the objective of the algorithm the condition that the false positive rate is the same for individuals in the protected group and the ones outside the protected group.

The main measures used in this approach are false positive rate, false negative rate, and overall misclassification rate. It is possible to add just one or several of these constraints to the objective of the algorithm. Note that the equality of false negative rates implies the equality of true positive rates so this implies the equality of opportunity. After adding the restrictions to the problem it may turn intractable, so a relaxation on them may be needed.

This technique obtains good results in improving fairness while keeping high accuracy and lets the programmer choose the fairness measures to improve. However, each machine learning task may need a different method to be applied and the code in the classifier needs to be modified, which is not always possible.[24]

We train two classifiers at the same time through some gradient-based method (f.e.: gradient descent). The first one, the predictor tries to accomplish the task of predicting ${\textstyle Y}$, the target variable, given ${\textstyle X}$, the input, by modifying its weights ${\textstyle W}$ to minimize some loss function ${\textstyle L_{P}({\hat {y}},y)}$. The second one, the adversary tries to accomplish the task of predicting ${\textstyle A}$, the sensitive variable, given ${\textstyle {\hat {Y}}}$ by modifying its weights ${\textstyle U}$ to minimize some loss function ${\textstyle L_{A}({\hat {a}},a)}$.[27][28]

An important point here is that, in order to propagate correctly, ${\textstyle {\hat {Y}}}$ above must refer to the raw output of the classifier, not the discrete prediction; for example, with an artificial neural network and a classification problem, ${\textstyle {\hat {Y}}}$ could refer to the output of the softmax layer.

Then we update ${\textstyle U}$ to minimize ${\textstyle L_{A}}$ at each training step according to the gradient ${\textstyle \nabla _{U}L_{A}}$ and we modify ${\textstyle W}$ according to the expression:

${\displaystyle \nabla _{W}L_{P}-proj_{\nabla _{W}L_{A}}\nabla _{W}L_{P}-\alpha \nabla _{W}L_{A}}$
where $\alpha$ is a tuneable hyperparameter that can vary at each time step.

Graphic representation of the vectors used in adversarial debiasing as shown in Zhang et al.[27]

The intuitive idea is that we want the predictor to try to minimize ${\textstyle L_{P}}$ (therefore the term ${\textstyle \nabla _{W}L_{P}}$) while, at the same time, maximize ${\textstyle L_{A}}$ (therefore the term ${\textstyle -\alpha \nabla _{W}L_{A}}$), so that the adversary fails at predicting the sensitive variable from ${\textstyle {\hat {Y}}}$.

The term ${\textstyle -proj_{\nabla _{W}L_{A}}\nabla _{W}L_{P}}$ prevents the predictor from moving in a direction that helps the adversary decrease its loss function.

It can be shown that training a predictor classification model with this algorithm improves demographic parity with respect to training it without the adversary.

Postprocessing

The final method tries to correct the results of a classifier to achieve fairness. In this method, we have a classifier that returns a score for each individual and we need to do a binary prediction for them. High scores are likely to get a positive outcome, while low scores are likely to get a negative one, but we can adjust the threshold to determine when to answer yes as desired. Note that variations in the threshold value affect the trade-off between the rates for true positives and true negatives.

If the score function is fair in the sense that it is independent of the protected attribute, then any choice of the threshold will also be fair, but classifiers of this type tend to be biased, so a different threshold may be required for each protected group to achieve fairness.[29] A way to do this is plotting the true positive rate against the false negative rate at various threshold settings (this is called ROC curve) and find a threshold where the rates for the protected group and other individuals are equal.[29]

The advantages of postprocessing include that the technique can be applied after any classifiers, without modifying it, and has a good performance in fairness measures. The cons are the need to access to the protected attribute in test time and the lack of choice in the balance between accuracy and fairness.[24]

Reject Option based Classification

Given a classifier let ${\textstyle P(+|X)}$ be the probability computed by the classifiers as the probability that the instance ${\textstyle X}$ belongs to the positive class +. When ${\textstyle P(+|X)}$ is close to 1 or to 0, the instance ${\textstyle X}$ is specified with high degree of certainty to belong to class + or - respectively. However, when ${\textstyle P(+|X)}$ is closer to 0.5 the classification is more unclear.[30]

We say ${\textstyle X}$ is a "rejected instance" if ${\textstyle max(P(+|X),1-P(+|X))\leq \theta }$ with a certain ${\textstyle \theta }$ such that ${\textstyle 0.5<\theta <1}$.

The algorithm of "ROC" consists on classifying the non-rejected instances following the rule above and the rejected instances as follows: if the instance is an example of a deprived group (${\displaystyle X(A)=a}$) then label it as positive, otherwise, label it as negative.

We can optimize different measures of discrimination (link) as functions of ${\textstyle \theta }$ to find the optimal ${\textstyle \theta }$ for each problem and avoid becoming discriminatory against the privileged group.[30]

References

1. ^ Moritz Hardt, Berkeley. Retrieved 18 December 2019
2. ^ "IBM AI Fairness 360 open source toolkit adds new functionalities". Tech Republic.
3. ^ IBM AI Fairness 360. Retrieved 18 December 2019
4. ^ Fairness Flow el detector de sesgos de Facebook. Retrieved 28 December 2019
5. ^ ML-Fairness gym. Retrieved 18 December 2019
6. ^ "Attorney General Eric Holder Speaks at the National Association of Criminal Defense Lawyers 57th Annual Meeting and 13th State Criminal Justice Network Conference". www.justice.gov. 2014-08-01. Retrieved 2022-04-16.
7. ^ Mattu, Julia Angwin,Jeff Larson,Lauren Kirchner,Surya. "Machine Bias". ProPublica. Retrieved 2022-04-16.
8. ^ Rose, Adam (2010-01-22). Time. ISSN 0040-781X http://content.time.com/time/business/article/0,8599,1954643,00.html. Retrieved 2022-04-16. {{cite magazine}}: Missing or empty |title= (help)
9. ^ "Google says sorry for racist auto-tag in photo app". the Guardian. 2015-07-01. Retrieved 2022-04-16.
10. ^ "A beauty contest was judged by AI and the robots didn't like dark skin". the Guardian. 2016-09-08. Retrieved 2022-04-16.
11. ^ Buolamwini, Joy; Gebru, Timnit (February 2018). Gender Shades: Intersectional Accuracy Disparities in Commercial Gender Classification (PDF). Conference on Fairness, Accountability and Transparency. New York, NY, USA. pp. 77–91.
12. ^ a b c d Solon Barocas; Moritz Hardt; Arvind Narayanan, Fairness and Machine Learning. Retrieved 15 December 2019.
13. ^ Mayes, Elizabeth (2001). Handbook of Credit Scoring. NY, NY, USA: Glenlake Publishing. p. 282. ISBN 0-8144-0619-X.
14. ^ a b c Verma, Sahil, and Julia Rubin. "Fairness definitions explained." In 2018 IEEE/ACM international workshop on software fairness (fairware), pp. 1-7. IEEE, 2018.
15. ^ Chen, Violet (Xinying); Hooker, J. N. (2021). "Welfare-based Fairness through Optimization". arXiv:2102.00311 [cs.AI].
16. ^ Mullainathan, Sendhil (June 19, 2018). Algorithmic Fairness and the Social Welfare Function. Keynote at the 19th ACM Conference on Economics and Computation (EC'18). YouTube. 48 minutes in. In other words, if you have a social welfare function where what you care about is harm, and you care about harm to the African Americans, there you go: 12 percent less African Americans in jail overnight.... Before we get into the minutiae of relative harm, the welfare function is defined in absolute harm, so we should actually calculate the absolute harm first.
17. ^ Mitchell, Shira, Eric Potash, Solon Barocas, Alexander D'Amour, and Kristian Lum. "Algorithmic fairness: Choices, assumptions, and definitions." Annual Review of Statistics and Its Application 8 (2021): 141-163.
18. ^ Castelnovo, Alessandro, Riccardo Crupi, Greta Greco, Daniele Regoli, Ilaria Giuseppina Penco, and Andrea Claudio Cosentini. "A clarification of the nuances in the fairness metrics landscape." Scientific Reports 12, no. 1 (2022): 1-21.
19. ^ Mehrabi, Ninareh, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. "A survey on bias and fairness in machine learning." ACM Computing Surveys (CSUR) 54, no. 6 (2021): 1-35.
20. ^ Dwork, Cynthia, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. "Fairness through awareness." In Proceedings of the 3rd innovations in theoretical computer science conference, pp. 214-226. 2012.
21. ^ Galhotra, Sainyam; Brun, Yuriy; Meliou, Alexandra (2017). Fairness Testing: Testing Software for Discrimination. Proceedings of the 11th Joint Meeting of the European Software Engineering Conference and ACM SIGSOFT Symposium on the Foundations of Software Engineering (ESEC/FSE). pp. 498–510. arXiv:1709.03221. doi:10.1145/3106237.3106277. ISBN 9781450351058. S2CID 6324652.
22. ^ Kusner, M. J., Loftus, J., Russell, C., & Silva, R. (2017). Counterfactual fairness. Advances in neural information processing systems, 30.
23. ^ Richard Zemel; Yu (Ledell) Wu; Kevin Swersky; Toniann Pitassi; Cyntia Dwork, Learning Fair Representations. Retrieved 1 December 2019
24. ^ a b c Ziyuan Zhong, Tutorial on Fairness in Machine Learning. Retrieved 1 December 2019
25. ^ Faisal Kamiran; Toon Calders, Data preprocessing techniques for classification without discrimination. Retrieved 17 December 2019
26. ^ Muhammad Bilal Zafar; Isabel Valera; Manuel Gómez Rodríguez; Krishna P. Gummadi, Fairness Beyond Disparate Treatment & Disparate Impact: Learning Classification without Disparate Mistreatment. Retrieved 1 December 2019
27. ^ a b Brian Hu Zhang; Blake Lemoine; Margaret Mitchell, Mitigating Unwanted Biases with Adversarial Learning. Retrieved 17 December 2019
28. ^ Joyce Xu, Algorithmic Solutions to Algorithmic Bias: A Technical Guide. Retrieved 17 December 2019
29. ^ a b Moritz Hardt; Eric Price; Nathan Srebro, Equality of Opportunity in Supervised Learning. Retrieved 1 December 2019
30. ^ a b Faisal Kamiran; Asim Karim; Xiangliang Zhang, Decision Theory for Discrimination-aware Classification. Retrieved 17 December 2019


text:
## Condensates in Driven Aggregation Processes

### E. Ben-Naim and P.L. Krapivsky

Irreversible aggregation processes involving reactive and frozen clusters are investigated using the rate equation approach. In aggregation events, two clusters join irreversibly to form a larger cluster, and additionally, reactive clusters may spontaneously freeze. Frozen clusters do not participate in merger events. Generally, freezing controls the nature of the aggregation process, as demonstrated by the final distribution of frozen clusters. The cluster mass distribution has a power-law tail, $F_k\sim k^{-\gamma}$, when the freezing process is sufficiently slow. Different exponents, $\gamma=1$, $3$ are found for the constant and the product aggregation rates, respectively. For the latter case, the standard polymerization model, either no gels, or a single gel, or even multiple gels may be produced.

source, ps, pdf

format: plain


text:
View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# Which edge is which when tessellating?

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

6 replies to this topic

### #1cephalo  Members

Posted 22 April 2013 - 03:15 PM

Ok, so I have 10 control points for a 3 order bezier triangle. It is arbitrary which points are which, I know who they are and how to use them, but there is no obvious relation to these points from the edges to tessellate. In my hull shader, I decide how much to tessellate each of the three edges, but how do I know which edge is edge zero, one, two etc?

For example, if cp[0], cp[1] and cp[2] are the control points to my bezier triangle corners, how do I decide how much to tessellate each edge based on the screen size of the edge?

### #2Jason Z  Members

Posted 22 April 2013 - 07:53 PM

You know the orientation of the control points relative to one another, and you know the world transformation that they are being transformed with, so you should have the information that you need.  If you are currently doing the transformation in the domain shader, then you may have to move that back to the hull shader.  Then you can transform each control point, and then using whatever metric you want you can adjust the tessellation accordingly.

In general this is better than doing the transformation in the domain shader, since it is running after the amplification from tessellation.  Always try to push the computation upstream if possible!

Jason Zink :: DirectX MVP

Direct3D 11 engine on CodePlex: Hieroglyph 3

Games: Lunar Rift

### #3cephalo  Members

Posted 23 April 2013 - 07:29 AM

Here is my current hull shader:

PatchConstants PatchHS(InputPatch<VertexOutput,10> cp, uint patchID : SV_PrimitiveID)
{
PatchConstants pt;

pt.EdgeTess[0] = 6;
pt.EdgeTess[1] = 6;
pt.EdgeTess[2] = 6;
pt.InsideTess = 6;

return pt;
}

How do I know which cp's are associated with pt.EdgeTess[0]? I have to make sure that shared edges are tessellated the same way. My shader pipeline currently supports two forms of triangle input sets, one pointing up and the other pointing down. After translating them with my matrices, they could be oriented any old way. If one of my edges on my triangle is short on the screen, how do I know which element in the EdgeTess array to decrease?

### #4cephalo  Members

Posted 23 April 2013 - 07:50 AM

In general this is better than doing the transformation in the domain shader, since it is running after the amplification from tessellation.  Always try to push the computation upstream if possible!

In my case, the domain shader is calculating patch surface normals according to world space. If transform my control points to screen space in the hull shader, I wouldn't be able to calculate normals any more, because at that point all the geometry is co-planar correct?

Edited by cephalo, 23 April 2013 - 07:54 AM.

### #5cephalo  Members

Posted 23 April 2013 - 08:16 AM

Ok, I have discovered that by setting one of my tessellation factors to 3, I can find out by visual experimentation which edge is which. It appears to be a stable association that is NOT dependent on the view space. In my case, the edge from cp[0] to cp[1] is edge index 2, edge cp[1] to cp[2] is edge index 0 and edge cp[2] to cp[0] is edge index 1. In my case, they also seem to line up by accident so I don't have to worry about mismatched shared edges.

Strange. Is there any way to predict this without experimentation? There must be some rule it would seem.

### #6unbird  Members

Posted 23 April 2013 - 01:14 PM

It's fixed, and your result looks correct. edgen is opposite to vertexn. Haven't found that in the docs, only in this paper, page 4. Don't ask me about quad domains, haven't tried that.

### #7Jason Z  Members

Posted 24 April 2013 - 04:45 AM

Here is my current hull shader:

PatchConstants PatchHS(InputPatch<VertexOutput,10> cp, uint patchID : SV_PrimitiveID)
{
PatchConstants pt;

pt.EdgeTess[0] = 6;
pt.EdgeTess[1] = 6;
pt.EdgeTess[2] = 6;
pt.InsideTess = 6;

return pt;
}

How do I know which cp's are associated with pt.EdgeTess[0]? I have to make sure that shared edges are tessellated the same way. My shader pipeline currently supports two forms of triangle input sets, one pointing up and the other pointing down. After translating them with my matrices, they could be oriented any old way. If one of my edges on my triangle is short on the screen, how do I know which element in the EdgeTess array to decrease?

It actually doesn't matter (I know - that isn't intuitive...).  As long as neighboring patches share the same control points, and the control point to tessellation factor algorithm will produce the same output for the given input control points, then the order doesn't make any difference.

But for the same reason you are having trouble to understand it, it would be impossible to have a standard notation to say which control point goes where since it depends on the primitive topology, the number of control points, and so on.  I believe there is a way to identify where a control point is located within a control patch, but I don't think there is one for the oriented control patches.

Jason Zink :: DirectX MVP

Direct3D 11 engine on CodePlex: Hieroglyph 3

Games: Lunar Rift

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.


text:
# Topological invariance of intersection number

Let $X$ and $Y$ be algebraic curves in ${\mathbb P}^2$ and suppose they have an isolated intersection at $(0,0)$. Let $\hat{X}$ and $\hat{Y}$ be another such pair, and suppose that there exist neighborhoods $U$ and $\hat{U}$ of $(0,0)$ and a homeomorphism $\phi:U\rightarrow\hat{U}$ such that $\phi(U\cap X)=\hat{U}\cap \hat{X}$ and $\phi(U\cap Y)=\hat{U}\cap \hat{Y}$. It seems to be well-known that the pairs $X,Y$ and $\hat{X},\hat{Y}$ have the same intersection number at $(0,0)$. Who first proved this, and how? Where might an accessible modern presentation be found?

-
it may be helpful to know that the 'reason' this number is a homeomorphism invariant is that it's equal to the linking number of the links of $X$ and $Y$ (i.e. you intersect them with the boundary of a small ball around $(0,0)$). – Vivek Shende Feb 7 '13 at 4:35
Have a look at Brieskorn's book Plane Algebraic Curves. He has a lot historical data in that book and you might find the answer there. – Liviu Nicolaescu Feb 7 '13 at 10:21


text:
Civics

# Frankling D. Roosevelt.a) When was the presidential election held?b) How was Franklin D. Roosevelt commonly known as?c) What was his election manifesto?d) Name the policy formulated by him.

##### SOLUTION
a) In $1932$
b) Franklin D. Roosevelt was commonly known as FDR.
c) "I pledge you, I pledge myself to a New Deal for the Americans".
d) The policy formulated by him is known as New Deal.

Its FREE, you're just one step away

Subjective Medium Published on 15th 09, 2020
Questions 120418
Subjects 10
Chapters 88
Enrolled Students 76

#### Realted Questions

Q1 Single Correct Medium
Who grants recognition to the political parties?
• A. The people
• B. President
• C. Cabinet Minister
• D. Election Commission

Asked in: Civics - Electoral Politics

1 Verified Answer | Published on 15th 09, 2020

Q2 Single Correct Medium
Political equality can be identified with _______.
• A. Right to get admission in any school
• B. Right to enter any religious worship place
• C. Above all
• D. Principle of one person one vote

Asked in: Civics - Electoral Politics

1 Verified Answer | Published on 15th 09, 2020

Q3 Subjective Medium
Ramesh was not in class when this chapter was being taught. He came the next day and repeated what he had heard from his father. Can you tell Ramesh what is wrong with these statements?
Women always vote the way men tell them to. So what is the point of giving them the right to vote?

Asked in: Civics - Electoral Politics

1 Verified Answer | Published on 15th 09, 2020

Q4 Subjective Medium
Can we draw the following conclusions from the information given in this chapter? Give two facts to support your position for each of these.
Many reforms are needed to make our elections completely free and fair.

Asked in: Civics - Electoral Politics

1 Verified Answer | Published on 15th 09, 2020

Q5 Single Correct Medium
Election of the President can be challenged ______________.
• A. Before the Chief Election Commissioner
• B. Before Union Parliament
• C. It cannot be challenged
• D. In the Supreme Court

Asked in: Civics - Electoral Politics

1 Verified Answer | Published on 15th 09, 2020


text:
# What is the solution of the system? 5x+4y=-2 and x-4y=14

May 21, 2018

$\left(28 \frac{1}{3} , 2 \frac{5}{6}\right)$

#### Explanation:

We can make the second equation
$x = 4 y + 14$
Substituting that value into the first equation, we get
$5 \cdot \left(4 y + 14\right) + 4 y = - 2$
$24 y = 68$
$y = \frac{17}{6}$, or $2 \frac{5}{6}$
Substituting this value of $y$ into either equation, we solve for $x$ as $\frac{85}{3}$, or $28 \frac{1}{3}$

This gives us the solution $\left(28 \frac{1}{3} , 2 \frac{5}{6}\right)$


text:
# Local recovery bounds for prior support constrained Compressed Sensing

Prior support constrained compressed sensing has of late become popular due to its potential for applications. The existing results on recovery guarantees provide global recovery bounds in the sense that they deal with full support. However, in some applications, one might be interested in the recovery guarantees limited to the given prior support, such bounds may be termed as local recovery bounds. The present work proposes the local recovery guarantees and analyzes the conditions on associated parameters that make recovery error small.

• 1 publication
• 1 publication
• 2 publications
06/19/2016

### Tight Performance Bounds for Compressed Sensing With Group Sparsity

Compressed sensing refers to the recovery of a high-dimensional but spar...
04/13/2020

### Analysis of The Ratio of ℓ_1 and ℓ_2 Norms in Compressed Sensing

We first propose a novel criterion that guarantees that an s-sparse sign...
01/19/2022

### Dual-Code Bounds on Multiple Concurrent (Local) Data Recovery

We are concerned with linear redundancy storage schemes regarding their ...
09/02/2020

### Approximate Recovery of Initial Point-like and Instantaneous Sources from Coarsely Sampled Thermal Fields via Infinite-Dimensional Compressed Sensing

We propose a method for resolving the positions of the initial source of...
12/27/2019

### Derandomized compressed sensing with nonuniform guarantees for ℓ_1 recovery

We extend the techniques of Hügel, Rauhut and Strohmer (Found. Comput. M...
09/19/2020

### A Unified Approach to Uniform Signal Recovery From Non-Linear Observations

Recent advances in quantized compressed sensing and high-dimensional est...
07/01/2013

### Short Term Memory Capacity in Networks via the Restricted Isometry Property

Cortical networks are hypothesized to rely on transient network activity...

## 1 Introduction

In Compressed Sensing (CS), a sparse signal can be recovered from a small set of linear measurements satisfying with where is the number of nonzero elements in . The results guaranteeing the recovery performance depend on the coherence, Restricted Isometry Property (RIP) and Restricted Orthogonality Constant (ROC) of the sensing matrix candes2005decodingKashinEulerSq. In many applications, one obtains some a priori information about the partial support of the sparse solution to be recovered. For instance, in interior reconstruction in Computed Tomography, one has before hand some apriori information corresponding to the support of the interior region Klann2015WaveletMF,localCBP. There are other applications, like recovering time-correlated signals vaswani2010modified, wherein prior-support constrained sparse recovery attains importance. Of late, the support constrained CS has caught the attention of several researchers friedlander2011recoveringKlann2015WaveletMFvaswani2010modified to name a few. In vaswani2010modified, the authors have modified the 1-norm function by taking zero weights on the known partial support, minimizing thereby the terms in the complement of prior support set. While in friedlander2011recovering, by considering general values for weights, the authors have provided stability and robustness of weighted -norm minimization problem in terms of Restricted Isometry Constant (RIC). The authors of liu2014compressed have studied similar performance guarantees in terms of mutual coherence of associated sensing matrix. The work embedded in Chen2016RecoveryOS has provided a less restrictive sufficient condition and a tighter error bounds under some conditions for the weighted- norm problem in terms of RIC and ROC. More recently, the authors of Ge2018RecoveryOS have provided the stability and robustness of the weighted- norm in terms of block RIP conditions on the underlying measurement matrix.

### 1.1 Motivation for our work

In applications like interior tomography, however, one is interested in the recovery guarantees limited to the interior portion that is accounted for by partial support. This is because the recovery on interior portion only attains importance in such an application and the reconstruction outside interior portion is, in general, bad FarrokhiKlann2015WaveletMF. Motivated by this, the present work proposes a new local recovery bound, in the sense that it pertains only to the prior support. It is to be emphasized here that by a prior support set , we mean an arbitrary subset of “full support” , which, in general, does not have to be fully contained in the true support of . This is in contrast to the existing results that provide global bounds (that is, on entire solution support). Further, both analytically and empirically we demonstrate the conditions on associated parameters that reduce the reconstruction error.

The paper is organized as 5 sections. In section 2, we provide basic introduction to Compressed Sensing, existing recovery bounds and a summary of our contribution. Section 3 presents the local recovery bound followed by an analysis and comparison in section 4. The paper ends with the concluding remarks in section 5.

## 2 Compressed sensing

Compressed sensing(CS) is a technique that reconstructs a signal, which is compressible or sparse in some domain, from a small set of linear measurements. Let be the set of all k-sparse signals in . Here stands for the number of nonzero components in . The best -term approximation of retains at most largest magnitude coordinates of , the rest of the coordinates are set to zero. For simplicity, we denote by . For (

) and an error vector

, suppose such that . One may recover the sparsest solution of the noisy matrix system from the following minimization problem cai2010stable:

 (1)

where is a bounded subset of For noiseless case, and for noisy case . Since minimization problem becomes NP-hard as the dimension increases, the convex relaxation of problem (1) has been proposed as

 (2)

The coherence of a matrix is the largest absolute normalized inner product between different columns of it, that is,

 μ(A)=max1≤i,j≤M,i≠j|aTiaj|∥ai∥2∥aj∥2,

where denotes the column in . For a sparse vector , it is known elad2010sparse that the following inequality holds:

 (1−(k−1)μ)∥x∥22≤∥Ax∥22≤(1+(k−1)μ)∥x∥22. (3)

The -th Restricted Isometry Constant (-RIC) of a matrix is the smallest number such that

 (1−δk)∥x∥22≤∥Ax∥22≤(1+δk)∥x∥22,

for all -sparse vectors . The Restricted Orthogonality Constant(ROC) of a matrix is the smallest real number such that

 |η′A′TA~T~η|≤θs,~s∥η∥2∥~η∥2,

for all disjoint sets and with and such that and for all vectors and . Here, denotes the sub matrix of columns of restricted to the indices in . D. Donoho and X. Huo donoho2001uncertainty have shown exact recovery condition in noiseless case for in terms of mutual coherence. If is sparse vector and matrix is -RIP compliant, is an exact recovery condition for problem. Then T. Cai et. al. cai2010stable have extended this result to noisy case.

###### Theorem 2.1.

(T. Cai et. al. cai2010stable): Consider the model with Suppose is in , and represents its best approximation with

 k<12(1+1μ). (4)

Let be the minimizer of . Then obeys

 ∥x∗−x∥2≤C(0)0ϵ+C(0)1∥x−xk∥1,

where and

### 2.1 Compressed sensing with prior support constraint

It may be noted that the reconstruction method given by in (2) is non adaptive as no information about is used in . It can, however, be made partially adaptive by imposing constraints on the support of the solution to be obtained. In friedlander2011recovering liu2014compressed vaswani2010modified (and the references therein) the authors have modified the cost function of problem by incorporating the prior support information into the reconstruction process as detailed in the following subsection.

### 2.2 Previous Work

Consider that is the known partial support information of signal , which is expected in recovered solution. Suppose stands for the support of the best -term approximation of , where is the actual solution of . In vaswani2010modified, the authors have modified the problem by considering zero weights in and have posed it as follows:

 min∥xTc∥1 subject toy=Ax. (5)

In the above problem, the weights are set to 1 on and to 0 on . In friedlander2011recovering, nevertheless, the authors have posed this problem for a general weight vector and an arbitrary subset of the following way:

 (6)

where with for and for ,

can be drawn from the estimate of the support of the signal

or from its largest coefficients. The stability result proposed in friedlander2011recovering is as follows:

###### Theorem 2.2.

(M. Friedlander et. al. friedlander2011recovering): Let and let be its best term approximation, supported on . Let be an arbitrary set and define such that and . Suppose that there exists an , with , , and the measurement matrix has RIP with

 δak+aβ2δ(a+1)k

where for some given . Then the solution to the (6) obeys

 ∥x∗−x∥2≤C(1)0ϵ+C(1)1(w∥x−xk∥1+(1−w)∥xTc∩Tc0∥1), (8)

where

 C(1)0=2(1+w+(1−w√1+ρ−2αρ)√a)√1−δ(a+1)k−w+(1−w)√1+ρ−2αρ√a√1+δak % and C(1)1=2(ak)−1/2(√1−δ(a+1)k+√1+δak)√1−δ(a+1)k−w+(1−w)√1+ρ−2αρ√a√1+δak. (9)

It has been shown in friedlander2011recovering that a signal can be stably and robustly recovered from problem if at least of the partial support information is accurate. It is worth a mention here that the above stability result has been proposed in terms of RIC-. In liu2014compressed, however, the authors have proposed a similar stability result, albeit in terms of coherence parameter, which is summarized as follows:

###### Theorem 2.3.

(Haixiao et. al. liu2014compressed): Let , and let be its best -term approximation, supported on . Let be an arbitrary set and define such that and . Suppose that

 k

where , and . Then the solution to (6) obeys

 ∥x∗−x∥2≤C(2)0ϵ+C(2)1(w∥x−xk∥1+(1−w)∥xTc∩Tc0∥1), (11)

where

 C(2)0=2(1−(k−1)μ−μkw+(1+w)√μk(1+(k−1)μ))(1−(k−1)μ−μkw)√1+μ−√μ(1+μ)(1−w)√μk(1+ρ−2αρ) and C(2)1=2(1+μ)√μ(1−(k−1)μ−μkw)√1+μ−√μ(1+μ)(1−w)√μk(1+ρ−2αρ). (12)

The authors of Chen2016RecoveryOS have proposed less restrictive sufficient conditions and a tighter bound with respect to the standard 1-norm problem under some conditions for the weighted 1-norm problem in terms of RIC and ROC. The stability result is as follows:

###### Theorem 2.4.

(Chen et. al. Chen2016RecoveryOS) Let be an arbitrary signal and its best -term approximation support on with . Let be an arbitrary set and denote and such that and . Let with and is the minimizer of (6). If for some with , where with . Let , for and =max, for . Then

 ∥x∗−x∥2≤C(3)0ϵ+C(3)1(w∥x−xk∥1+(1−w)∥xTc∩Tc0∥1), (13)

where

 C(3)0=2√2(1+δa)d/a1−δa−Cα,wa,b,kθa,b;C(3)1=2√2dCα,wa,b,kθa,b(1−δa−Cα,wa,b,kθa,b)s+2√d. (14)

A vector , where is the block of of size w.r.t with , is said to be block - sparse over if the number of non-zero blocks in is at most . Recently the authors of Ge2018RecoveryOS have introduced the following weighted block -norm problem for a given disjoint prior block support estimates for with as

 minx∈Rn∥xw∥2,1=M∑i=1wi∥x[i]∥2subjectto∥y−Ax∥≤ϵ, (15)

where is defined by and for . Note that when for all , and block sparsity reduces to the standard sparsity and if the number of support estimates , then the weighted block -norm problem (15) reduces to the weighted 1-norm problem in (6). In this particular case the stable recovery result of (15) in Ge2018RecoveryOS deduces to the following result:

###### Theorem 2.5.

(Ge et.al. Ge2018RecoveryOS) For an arbitrary signal , which satisfies with , let be its best -term approximation and . Suppose that is the minimizer of (6) and is the prior block support of satisfying , . If A satisfies the RIP with for , where, and for . For , d=1 if and if . Then

 ∥x∗−x∥2≤C(4)0ϵ+C(4)1(w∥x−xk∥1+(1−w)∥xTc∩Tc0∥1), (16)

where

 C(4)0=2√2(t−d)(t−d+Υ2L)(1+δtk)(t−d+Υ2L)(√t−d(t−d+Υ2L)−δtk)C(4)1=2√k(√2δtkΥL+√(t−d+Υ2L)(t−d(t−d+Υ2L)−δtk)δtk(t−d+Υ2L)(√(t−d+Υ2L)t−d(t−d+Υ2L)−δtk)+1√d). (17)

## 3 Local recovery bounds

As discussed already, the present work deals with obtaining a recovery bound on for . It is shown in the later part that when contains the indices corresponding to the largest magnitude entries in , our error bound is much smaller than the global error bounds (8),(11),(13) and (16) for weighted-1-norm problem. Further, in most of the cases the sufficient condition on in this bound can be shown to be less pessimistic than the corresponding ones in the standard 1-norm (4) and weighted 1-norm cases (10). Our contribution may be summarized as the following result:

###### Theorem 3.1.

Let be in satisfying where and with . Let be its -term approximation supported on . Let be an arbitrary set. Define and such that and . Suppose that

 k<⎧⎪ ⎪⎨⎪ ⎪⎩(12√ρ(2w√α+1)(w+√w2+4(2w√α+1)(1+1μ)))2,~{}if~{}w∈(0,1]1ρ(1+1μ),~{}if~{}w=0, (18)

then the solution on to obeys

 ∥x∗T−xT∥2≤C0ϵ+C1(w∥x−xk∥1+(1−w)∥xTc∩Tc0∥1+∥xTc∩T0∥1), (19)

where

 C0=2√1+(ρk−1)μ(1+μ+wμ√ρk−μρk(2w√α+1)),C1=2μ√ρk(1+μ+wμ√ρk−μρk(2w√α+1)). (20)

Proof: Suppose . From the definition of , we have

 ∥x+h∥1,w≤∥x∥1,ww∥xT∩T0+hT∩T0∥1+w∥xT∩Tc0+hT∩Tc0∥1+∥xTc+hTc∥1≤w∥xT∩T0∥1+w∥xT∩Tc0∥1+∥xTc∥1w∥xT∩T0∥1−w∥hT∩T0∥1+w∥hT∩Tc0∥1−w∥xT∩Tc0∥1+∥hTc∥1−∥xTc∥1≤w∥xT∩T0∥1+∥xT∩Tc0∥1+∥xTc∥1∥hTc∥1≤w∥hT∩T0∥1−w||hT∩Tc0||1+2(w∥xT∩Tc0∥1+∥xTc∥1)∥1

Consider that . Then, we have

 ∥hTc∥1≤w∥hT∩T0∥1−w||hT∩Tc0||1+2e. (21)

Now, since and by the inequality (3), it follows that

 (1−(ρk−1)μ)∥hT∥22≤∣⟨AhT,AhT⟩∣≤∣⟨Ah,AhT⟩∣+∣⟨AhTc,AhT⟩∣≤∥Ah∥2∥AhT∥2+∑i∈Tc,j∈T∣⟨Ai,Aj⟩∣∣hihj∣≤2ϵ√1+(ρk−1)μ∥hT∥2+μ∥hTc∥1∥hT∥1. (22)

In view of the inequalities , and the ones in (21) and (22), we have the following:

 (1−(ρk−1)μ)∥hT∥2≤2ϵ√1+(ρk−1)μ+μ√ρk∥hTc∥1≤2ϵ√1+(ρk−1)μ+μ√ρk(w∥hT∩T0∥1−w∥hT∩Tc0∥1+2e)≤2ϵ√1+(ρk−1)μ+μ√ρk(2w∥hT∩T0∥1−w∥hT∥1+2e)≤2ϵ√1+(ρk−1)μ+2μ√ρke+μ√ρk(2w√αρk−w)∥hT∥2,

which results in

 (1+μ+wμ√ρk−μρk(2w√α+1))∥hT∥2≤2ϵ√1+(ρk−1)μ+2μ√ρke.

Consequently,

 ∥hT∥2≤2ϵ√1+(ρk−1)μ+2μ√ρke(1+μ+wμ√ρk−μρk(2w√α+1)). (23)

The conditions in (18) imply that , and the denominator on the right hand side of (23) are positive. ∎.

An investigation into the choices of , , and that result in smaller values for the RHS of (19) is presented in the following section.

###### Remark 3.2.

It is clear that the bound on sparsity in (18) becomes less restrictive for small values of and . For , the bound reduces to , which is an increasing function of . Similarly for , it is easy to verify that the -bound is a decreasing function of and the largest bound is obtained at and .

###### Remark 3.3.

In the subsequent part, we refer to the bounds in (8), (11),(13) and (16) as ‘global’ bounds while the one in (19) as a ‘local’ bound.

## 4 Analysis and comparison of ‘local‘ and ‘global’ error bounds

In this section, we analyze the behaviour of the bound provided in (19) in terms of the associated parameters and .

It may be noted that determines the relative size of with respect to the size of support of best -term approximation of . From (20), it can be seen that the coefficients and decrease with decrease in . Again, when , the -term in the denominator of coefficients is , which being positive increases with , making the coefficients decrease with . When , however, the -term in the denominator of the coefficients is , which is negative as , since is a nonempty subset of . As a result, it decreases with increase in , which makes the coefficients increase with . The stated behaviour of coefficients can be seen in Fig 1. In generating the plots in this figure, as an example, we have taken , considering the coherence of the underlying matrix as , like in liu2014compressed. Note that and lead to three possibilities for the values of , viz, and . Similarly, when , takes and as possible values.

Since term is controlled by , for the reconstruction error to be small in (19), the multiplier of should be small, where . The first two terms are small in the error expression as is the best--term approximation of and is the support of which can be further reduced by choosing optimal . In order to make small, we need to be small. This is possible if contains the largest components of or the cardinality of is as small as possible. The latter case can happen when is close to 1. In application like in interior tomography, this condition translates to interior portion possessing dominating pixels. As the objective of the paper not is related to tomography, we do not go into the details of it any further.

We have computed the values of and against different and , which are depicted in Fig. 2. Here

has been taken to be a normalized vector from Gaussian distribution with previously stated values for

and . The plots in this figure indicate that is large for , and for a given , it increases with . The smallest value for is obtained at . Again is large for . For smaller values of , decreases with and for , decreases with . This is due to the effect of . Overall, the error-bound takes its minimum value around and .

### 4.1 Comparison of bounds on k

Though the objective of present work is to propose an error bound restricted to a nonempty subset , a natural question arises whether our bound in (18) is better behaved than the ones associated with the global error bounds in the standard case (4) and in the weighted case (10). We compare the -bounds numerically in terms of a -ratio. By a -ratio in the standard case we mean the right hand side of our -bound in (18) divided by its counterpart in (4). Similarly we consider the k-ratio in the weighted one norm case with respect to (10). Fig. 3 provides a comparison of -ratios, which has been generated by considering, as examples, , and . It can be seen in both the cases that the -ratios are strictly greater than 1 for all and for all . It is clear from the graphs that, even for larger values of , our bound becomes less pessimistic than that of (4) and (10) for smaller values of for all . But since we are interested in finding error bounds on a subset , which has a smaller size than the support of the best -term approximation , we do not consider the cases for larger values for .

### 4.2 Comparison of bounds on error

The local error bound in Theorem 3.1 (that is, (19)) becomes relevant if its right hand side is less than that of the global bounds in Theorems 2.2, 2.3, 2.4 and 2.5. Since the stated right hand sides are functions of the solution vector with various associated parameters and different underlying conditions, comparing them for a general solution vector does not look practical. In view of this, we try to compare the coefficients (i.e, and with their respective counterparts in Theorems 2.2, 2.3, 2.4 and 2.5) when the associated error expressions coincide. It is clear that the associated error parts coincide if is small. That is, contains largest magnitude entries from . Consider a particular case for this in which . In such a case, both the error terms associated with coefficients in global as well as local error bounds coincide. Hence in this case it is enough to compare the corresponding coefficients and (that is, and are respectively compared to and for ).

The coefficients in (12) and (20) can be compared directly as both of them are in terms of mutual coherence parameter . The coefficients in (9), (14) and (17) are in terms of the RIC and ROC. In order to compare them with the corresponding ones in (20) which are in terms of , we use the upper bounds candes2005decodingelad2010sparse: and . For comparing with (9) we need a constant such that and . We take a simple choice . Again, for comparison with (14), we need two constants and . We set these to , which is permissible. Finally, for comparing with (17), we need a constant . In our case, as , we take a simple choice . The plots in Fig. 4, comparing the coefficients in the stated setting, are denoted through the legends ‘Local’, ‘Global(1), Global(2), Global(3) and Global(4), which stand respectively for the coefficients in (20), (12),(9),(14) and (17). From Fig 4, it is clear that our coefficients being much small imply that the right hand side of our bound is small compared to their global bounds at least in the case where contains the indices corresponding to largest magnitude entries in for all . As highlighted already, comparison of bounds in other cases does not look possible.

In generating Fig 4, we have taken and . It may be noted that the coefficients in (9) are negative for and in (14), gives which makes in (14) not defined at .

## 5 Conclusion

The present work has proposed a local recovery bound for prior support constrained compressed sensing, while the existing bounds are global in nature. In particular, an error estimate restricted to prior support, providing recovery guarantee, has been provided along with a bound on the sparsity of the solution to be recovered.

Acknowledgments:
The first author is thankful to the UGC, Government of India, (JRF/2016/409284) for its financial support. The second author gratefully acknowledges the support received from the MHRD, Government of India.


text:
Mathematics

# In the figure $\angle ABC={80}^{o}$. Find $\angle DGC$ and $\angle DEF$, given $AB||DE$ and $BC||EF$.

##### SOLUTION
Given $\angle ABC=80^\circ$
$AB\parallel DE$, $BC$ is transversal line,
Hence,
$\angle ABC=\angle DGC=80^\circ$

$BC\parallel EF$, $ED$ is transversal line,
Hence,
$\angle DEF=\angle DGC=80^\circ$

You're just one step away

Subjective Medium Published on 09th 09, 2020
Questions 120418
Subjects 10
Chapters 88
Enrolled Students 86

#### Realted Questions

Q1 TRUE/FALSE Medium
It is possible to have a triangle in which two of the angles are obtuse.
• A. True
• B. False

Asked in: Mathematics - Lines and Angles

1 Verified Answer | Published on 09th 09, 2020

Q2 Single Correct Medium
A line AB is parallel to the line CD. This is symbolically written as
• A. $\overleftrightarrow{AB} \neq \overleftrightarrow{CD}$
• B. $\overleftrightarrow{AB} = \overleftrightarrow{CD}$
• C. $\overleftrightarrow{AB} \perp \overleftrightarrow{CD}$
• D. $\overleftrightarrow{AB} || \overleftrightarrow{CD}$

Asked in: Mathematics - Lines and Angles

1 Verified Answer | Published on 09th 09, 2020

Q3 Subjective Medium
Write the supplement of:

$x^o$

Asked in: Mathematics - Lines and Angles

1 Verified Answer | Published on 09th 09, 2020

Q4 Single Correct Medium
Example for a pair of parallel lines
• A. corners of a room
• B. sides of a triangle
• C. none
• D. railway track

Asked in: Mathematics - Lines and Angles

1 Verified Answer | Published on 09th 09, 2020

Q5 Subjective Medium
what is the measure of complementary angle of ${ 20 }^{ \circ }$

Asked in: Mathematics - Lines and Angles

1 Verified Answer | Published on 09th 09, 2020


text:
Wang* , Wang* , and Jiang*: A Method of Image Identification in Instrumentation

# A Method of Image Identification in Instrumentation

Abstract: Smart city is currently the main direction of development. The automatic management of instrumentation is one task of the smart city. Because there are a lot of old instrumentation in the city that cannot be replaced promptly, how to makes low-cost transformation with Internet of Thing (IoT) becomes a problem. This article gives a low-cost method that can identify code wheel instrument information. This method can effectively identify the information of image as the digital information. Because this method does not require a lot of memory or complicated calculation, it can be deployed on a cheap microcontroller unit (MCU) with low read-only memory (ROM). At the end of this article, test result is given. Using this method to modify the old instrumentation can achieve the automatic management of instrumentation and can help build a smart city.

Keywords: Code Wheel Instrument , Image Identification , IoT , Smart City , Template Matching

## 1. Introduction

Smart city is currently the main direction of development. The Internet of Thing (IoT) of instrumentation is one task of the smart city. However, there is much old instrumentation such as the gas meter in the city. The quantity of them is very large and the cost of replacing them is very high. It becomes important to transform the old instrumentation with low-cost to make them automatic with IoT. Image recognition is a viable method. However, there is still no image recognition method for lowcost reconstruction of instrumentation. Other industries, such as medical and precision machining, have applied image recognition methods. But among the existing methods, the deployment costs are too high [1-4]. The method of texture recognition costs a high read-only memory (ROM). The method of convolution neural network has a complicated calculation [5-7]. All these are not conducive to lowcost transformation. The old code wheel instruments all have the feature of relatively fixed image area and relatively fixed pattern of number. This article gives a method that can effectively identify the information of image as the digital information based on the above feature. The method can identify the area with valid information and can cut it out. With the template matching method, it can effectively identify the meaning of image information. This method use with memory less than 128k and can be deployed on a cheap microcontroller unit (MCU) such as STM32 series or MK series. With simple calculation, this method can make the running time as short as 1s with 8 numbers of the code wheel instrumentation to identify. This method can make the old instruments identify information and upload the data automatically. Section 2 gives the hardware of image recognition device. Section 3 gives the image segmentation method. Section 4 gives image identification method. Section 5 gives a serious test results. And Section 6 is a conclusion of this article.

## 2. Hardware Design

The hardware of the image identification device has five modules. They are the power module, the camera module, the liquid crystal display (LCD) module, the wireless module and the MCU module. The structure of the modules is shown in Fig. 1.

Fig. 1.

System of image identification device.

Fig. 2.

Circuit design of camera module (a), MCU module (b), LCD module (c), and wireless module (d).

Fig. 3.

Image taken by camera module.

The MCU module uses MLK17 as the MCU. The KL17 series is optimized for cost-sensitive and battery powered applications requiring low-power general-purpose connectivity. The camera module takes photo of the code wheel of instrumentation and sends it to MCU. The wireless module uses the LSD4RF. It works in the 470 MHz band and communicates with the server. The LCD module is responsible for real-time display of the information. The circuit design of these modules is shown in Fig. 2 and the image of instrument’s code wheel taken by camera is shown in Fig. 3.

## 3. Image Cutting Method

In order to effectively identify the image information and reduce the amount of computation, it needs to cut the image to extract the valid part of the information. The original image shown in Fig. 3 is consisted of three colors, red, black, and white. In order to avoid other light interference and reduce the computational complexity, it removes the red layer information to make the new picture. Then it makes the new picture binarized and inverted to reduce the computational complexity. The method given by this article firstly looks for the vertices of the image. By calculating the sum of nine pixels, the formula for the vertices is as Eq. (1).

##### (1)
[TeX:] $$\sum _ { i - 3 , j - 3 } ^ { i , j } P I C ( i , j ) > 1040$$

where PIC(i, j) is new picture’s image matrix. If the sum is larger than 1040, it means that at least 8 white pixels are found. In order to reduce the calculation, the step to find four vertexes is as follow.

Step 1. Search the image from up to down and left to right, to find the first vertex called up-left vertex.

Step 2. The second vertex is called down-left vertex. It needs search its X-axis coordinate near the Xaxis coordinate of up-left vertex. And search its Y-axis coordinate from the bottom of the image to the top of the image. Then it determines the down-left vertex’s coordinate position.

Step 3. The third vertex is called up-right vertex. It needs search its X-axis coordinate near the Y-axis coordinate near the Y-axis coordinate of up-left vertex. And search its X-axis coordinate from the right of the image to the left of the image. Then it determines the up-right vertex’s coordinate position.

Step 4. The forth vertex is called down-right vertex. It needs search its X-axis coordinate near the Xaxis coordinate of up-right vertex. And search its Y-axis coordinate near the Y-axis coordinate of left-down vertex.

After determining the four vertices, it cuts the original image by four vertices. Then it needs to calculate the image rotation angle by Eq. (2).

##### (2)
[TeX:] $$\theta = \arctan \left( \frac { x _ { L D } - x _ { L U } } { y _ { L U } - y _ { L D } } \right)$$

where θ is the tilt angle. The xLD and yLD are the left-down vertex’s X-axis coordinate and Y-axis coordinate. The xLU and yLU are the left-up vertex’s X-axis coordinate and Y-axis coordinate.

After determining the image’s tilt angle, it needs to rotate the image with tilt angle using the method of bilinear interpolation.

It needs to cut every number’s image. The method given by this article calculates the image by Eq. (3).

##### (3)
[TeX:] $$A ( i ) = \sum _ { 1 } ^ { j } y _ { j }$$

where A(i) is a one dimensional vector and yj is the Y-label coordinate of one column of the image.

This method differentiates the vector and dramatic changes part is the edge of each number. Then it needs to cut the image with the certain edge.

Then here comes the image of each number and can do further process with matching its value.

## 4. Image Matching Method

This article gives a simple method to identify the number in the image. The old code wheel instruments all have a common feature that the fixed mechanical structure of the code wheel allows the position of the image to be relatively fixed as well. Each mechanical position of the wheel code has its corresponding image. The mechanical structure is shown in Fig. 4.

Fig. 4.

Mechanical structure of wheel code.

The method given by this article gives an image matching method that has the minimum amount of calculation. The image templates are generated by the image cutting method given by Section 3. All these image templates are the same size with image that needs to be identified. Also the templates are the bitmap after being binarized. Each number has 6 positions of mechanical structure. There are 60 image templates for all the numbers in each position. The image templates of the number are shown in Fig. 5.

When it starts to match the image with the image templates, it uses the Eq. (4).

##### (4)
[TeX:] $$\operatorname { Sum } ( n ) = \sum _ { i = 1 , j = 1 } ^ { i , j } \left( I ( i , j ) - T _ { n } ( i , j ) \right)$$

where I(i, j) is one pixel of the image to be identified and the i and j is the pixel’s X-axis coordinate and Y-axis coordinate. The Tn(i,j) is one pixel of the image template and the subscript n is the number of the image template. The Sum(n) is the sum of differences for each image pixel and template pixel of the number.

Fig. 5.

Image templates of number.

This method needs to calculate the sum of differences for the identified image with all the image template one by one with Eq. (4). Then if the Sum(n) is equal to 0, it shows that the identified image is completely match the image template of the number. Then matching the number of image template with true number and here comes the identified result. If the Sum(n) is not equal to 0, it needs to choose the minimum result and match the number n image template. Then matching the number of image template with true number.

## 5. Test Results

In order to ensure that the experimental test result is closer to the real environment, the test picture is manually added noise. The test image is shown as Fig. 6.

Then it processes the test image with the method given by this article. The images after binarized, cut rotated and inverted are shown in Fig. 7.

Fig. 6.

Test image.

Fig. 7.

(a) Image after binarized, (b) cut image, (c) cut image after rotated, and (d) cut image after inverted.

Then it starts matching cutting single number’s image with image template. The result is shown in Fig. 8.

Fig. 8.

Result of image identification.

The result is completely right. The running time of this method on the hardware platform given by Section 2 is about 1.1 seconds. This running time is within reasonable limits. The method of image identification is reliable and feasible.

## 6. Conclusion

This article gives a method can identify the number information. It can detect the information area of the image and cut it out. Then the method can find the small image with single number and cut it out. It uses a method of template matching to identify the number in the image. It only need run with low memory. It also has very small amount of computation that makes it can be deployed at a chip MCU. It makes easy to transform the old code wheel instruments to make them can do automatic meter reading and send the data up to the server. It can transform the existing old code wheel instruments with low cost and is suitable for large-scale. It can help accelerate the pace of smart city construction. This article also gives the hardware design of the image identification device. The method of code wheel image identification and the hardware design of the image identification device can help accelerate the smart city construction.

## Biography

##### Xiaoli Wang
https://orcid.org/0000-0002-7420-321X

He received his B.S. degree in electronic information science and technology and his M.E. degree in circuits and systems from Shandong University, Weihai, China, in 2002 and 2008, respectively. He is currently a senior experimentalist in the School of Mechanical, Electrical and Information Engineering, Shandong University, Weihai, China. His current research interests include micro-grid and embedded system development.

## Biography

##### Shilin Wang
https://orcid.org/0000-0002-2873-9240

He received the B.S. degree in electronic information science and technology from Shandong University, China in 2015. Now he is a postgraduate in the School of Mechanical, Electrical and Information Engineering, Shandong University, Weihai, China. His research interests cover signal processing and embedded development.

## Biography

##### Baochen Jiang
https://orcid.org/0000-0002-6055-2355

He received his B.S. degree in radio electronics from Shandong University, China, in 1983 and his M.E. degree in communication and electronic systems from Tsinghua University, China, in 1990. He is currently a professor and supervisor of postgraduate students at Shandong University, Weihai, China. His current research interests include signal and information processing, digital image/video processing and analysis, and smart grid technology.

## References

• 1 A. Vishnuvarthanan, M. P . Rajasekaran, V . Govinadaraj, Y. Zhang, A. Thiyagarajan, "Development of a combinational framework to concurrently perform tissue segmentation and tumor identification in T1-W , T2-W , FLAIR and MPR type magnetic resonance brain images," Expert Systems with Applications, 2018, vol. 95, pp. 280-311. doi:[[[10.1016/j.eswa.2017.11.040]]]
• 2 T. Go, H. Byeon, S. J. Lee, "Label-free sensor for automatic identification of erythrocytes using digital in-line holographic microscopy and machine learning," Biosensors and Bioelectronics, 2018, vol. 103, pp. 12-18. doi:[[[10.1016/j.bios.2017.12.020]]]
• 3 X. Ma, M. Tian, J. Zhang, L. Tang, F. Liu, "Flow pattern identification for two-phase flow in a U-bend and its contiguous straight tubes," Experimental Thermal and Fluid Science, 2018, vol. 93, pp. 218-234. doi:[[[10.1016/j.expthermflusci.2017.12.024]]]
• 4 H. Z. M, Shah, M. Sulaiman, A. Z. Shukor, Z. Kamis, A. Ab Rahman, "Butt welding joints recognition and location identification by using local thresholding," Robotics and Computer-Integrated Manufacturing, 2018, vol. 51, pp. 181-188. doi:[[[10.1016/j.rcim.2017.12.007]]]
• 5 Q. Zhao, F. Sun, W . Li, P . Liu, "Flame detection using generic color model and improved block-based PCA in active infrared camera," International Journal of Pattern Recognition and Artificial Intelligencearticle no. 1850014, 2018, vol. 32, no. article 1850014. doi:[[[10.1142/S0218001418500143]]]
• 6 Z. Liu, S. Wang, M. Zhang, "Improved sparse 3D transform-domain collaborative filter for screen content image denoising," International Journal of Pattern Recognition and Artificial Intelligencearticle no. 1854006, 2018, vol. 32, no. article 1854006. doi:[[[10.1142/S021800141854006X]]]
• 7 L. Lambert, G. Grusova, A. Buraetova, P. Matras, A. Lambertova, P. Kuchynaka, "The predictive value of computed tomography in the detection of reflux esophagitis in patients undergoing upper endoscopy," Clinical Imaging, 2018, vol. 49, pp. 97-100. doi:[[[10.1016/j.clinimag.2017.11.009]]]


text:
User tergi - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T13:28:39Z http://mathoverflow.net/feeds/user/24848 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/105425/finding-the-smallest-eigenvalues-of-a-large-but-structured-matrix/105434#105434 Answer by tergi for Finding the smallest eigenvalues of a large, but structured, matrix tergi 2012-08-25T00:36:11Z 2012-08-25T00:36:11Z
If it is a Laplacian then you not only know the smallest eigenvalue is zero, but you also know its corresponding eigenvector. You can use this information by essentially adding a single step to your procedure, it's something like adding back the mean of v to each element of Mv. Then use arnoldi to find the smallest (instead of second smallest) eigenpair.
 http://mathoverflow.net/questions/104948/distribution-of-maximum-of-a-uniform-multinomial-distribution/104954#104954 Answer by tergi for Distribution of Maximum of a uniform multinomial distribution tergi 2012-08-17T23:08:59Z 2012-08-17T23:08:59Z
This is addressed by Bruce Levin, 1983, "On Calculations Involving the Maximum Cell Frequency."

Also in http://www.jstor.org/stable/2347220 .
 http://mathoverflow.net/questions/104573/open-problems-in-sub-riemannian-geometry/104574#104574 Answer by tergi for Open problems in sub-Riemannian geometry tergi 2012-08-12T19:24:30Z 2012-08-12T19:24:30Z
Chapter 10 of "A Tour of Subriemannian Geometries, Their Geodesics and Applications" describes four open problems.
 http://mathoverflow.net/questions/104442/find-both-maximum-and-minimum-values-in-linear-programming-problem/104443#104443 Answer by tergi for Find both maximum and minimum values in linear programming problem tergi 2012-08-10T22:13:10Z 2012-08-10T22:13:10Z
Probably not much more efficient than finding the max and min solutions separately.
 http://mathoverflow.net/questions/104413/tail-bound-for-poisson-random-variable/104425#104425 Answer by tergi for Tail bound for Poisson random variable tergi 2012-08-10T17:33:49Z 2012-08-10T18:34:38Z
This is not a full answer, but according to this explanation I think the question asks whether $\Gamma(k, k \lambda) \geq e^{-\lambda} \Gamma(k)$ when $k \in Z^+$, and $\lambda \in (0, 1)$.

Edit: Some answers to this math.se question have lower bounds for the upper incomplete gamma function.
 http://mathoverflow.net/questions/73538/surface-fitting-with-convexity-requirement/104376#104376 Answer by tergi for Surface fitting with convexity requirement tergi 2012-08-09T21:15:27Z 2012-08-09T21:15:27Z
You should use an ellipsoid.
 http://mathoverflow.net/questions/104309/how-to-find-the-minimum-string-length-to-produce-a-set-of-a-given-size-with-a-min/104313#104313 Answer by tergi for How to find the minimum string length to produce a set of a given size with a minimum pairwise Hamming distance tergi 2012-08-08T22:41:53Z 2012-08-08T23:05:12Z
According to my interpretation of Table I of http://neilsloane.com/doc/Me54.pdf it was not known at the time whether you needed bit ($q=2$) strings of length $n=23$, $n=22$, or possibly only of length $n=21$, to construct a set of $x=50$ codewords that are separated from each other by at least Hamming distance $d=10$. This particular example may or may not still be an open question, but there is probably not a known general formula for $n$ in terms of $q$, $x$, and $d$.

Edit: The bounds update at http://webfiles.portal.chalmers.se/s2/research/kit/bounds/unr.html shows that $n$ is now known to be $22$ for the example above, but you can still see that a nice way to compute the function you want has not been discovered.
 http://mathoverflow.net/questions/104160/eigenvector-update-formula/104163#104163 Answer by tergi for eigenvector update formula tergi 2012-08-06T23:24:10Z 2012-08-06T23:32:28Z
By $A$ do you mean $B$?

Edit: You will probably also want to know quantitatively how `simple' $\lambda$ is, for example something like the distance to its nearest eigenvalue neighbor.
 http://mathoverflow.net/questions/104137/can-the-friendship-graph-be-determind-by-its-adjacency-spectrum/104159#104159 Answer by tergi for Can the friendship graph be determind by its adjacency spectrum? tergi 2012-08-06T22:56:06Z 2012-08-06T22:56:06Z
This isn't a real answer, but wolfram-alpha says that $F_n$ is determined by its (adjacency) spectrum for $n \in \lbrace 2,3,4 \rbrace$. It doesn't say anything about $n=5$.

http://www.wolframalpha.com/input/?i=%285%2C3%29-windmill+graph
 http://mathoverflow.net/questions/102652/given-a-grothendieck-topos-what-does-its-localic-groupoid-look-like/102679#102679 Answer by tergi for Given a Grothendieck topos, what does its localic groupoid look like? tergi 2012-07-19T15:56:47Z 2012-07-19T15:56:47Z
Starting from a topos $T$, construct a locale $L$ and a surjection $L \to T$ 'nice enough' (like a proper surjection). Then $(L, L \times TL,L \times TL \times TL)$ is a truncated simplicial locale, which can be seen as a localic groupoid. There is a canonical geometric morphism from the topos of sheaves on this groupoid to $T$, and if the surjection $L \to T$ was nice enough it's an isomorphism.
 http://mathoverflow.net/questions/102566/solving-a-system-of-linear-inequalities/102581#102581 Answer by tergi for Solving a system of linear inequalities tergi 2012-07-18T20:36:26Z 2012-07-18T20:36:26Z
From http://www.faqs.org/faqs/linear-programming-faq/

Q6.4: "I just want to know whether or not a feasible solution exists."

A: From the standpoint of computational complexity, finding out if an LP model has a feasible solution is essentially as hard as actually finding the optimal LP solution, within a factor of 2 on average, in terms of effort in the Simplex Method; plug your problem into a normal LP solver with any objective function you like, such as c=0. For MIP models, it's also difficult - if there exists no feasible solution, then you must go through the entire Branch and Bound procedure (or whatever algorithm you use) to prove this. There are no shortcuts in general, unless you know something useful about your model's structure (e.g., if you are solving some form of a transportation problem, you may be able to assure feasibility by checking that the sources add up to at least as great a number as the sum of the destinations).
 http://mathoverflow.net/questions/41994/basic-software-libraries-for-numerical-analysis-using-modern-programming-language/102088#102088 Answer by tergi for Basic software libraries for numerical analysis using modern programming languages? tergi 2012-07-13T01:10:48Z 2012-07-13T01:10:48Z
You should use code from Numerical Recipes. If you do this, then when people ask you for your code you can tell them that you aren't allowed to give it to them because it would violate the licence. Then people will stop bugging you and you won't have to reveal how messy your code is.
 http://mathoverflow.net/questions/101958/nearly-elliptic-equations/101960#101960 Answer by tergi for Nearly elliptic equations tergi 2012-07-11T16:05:01Z 2012-07-11T16:05:01Z
do you mean positive semi-definite
 http://mathoverflow.net/questions/101600/how-to-enumerate-all-possible-k-connected-components-partition-of-a-two-dimension/101603#101603 Answer by tergi for How to enumerate all possible k-connected-components partition of a two dimensional 4-connected grid tergi 2012-07-07T21:17:41Z 2012-07-07T22:07:22Z
Constraining m=n and k=2, this is http://oeis.org/A068416.
 http://mathoverflow.net/questions/105977/reversing-the-carry-operation-in-multiplication Comment by tergi tergi 2012-08-30T17:59:29Z 2012-08-30T17:59:29Z Any question that begins "Hello I'm not a mathematician" is going to be closed. http://mathoverflow.net/questions/105087/nash-equilibrium-of-simple-betting-game Comment by tergi tergi 2012-08-20T14:35:32Z 2012-08-20T14:35:32Z I find the terminology counterintuitive. Folding is usually defined so that if one player folds and the other player does not fold, then the player that does not fold gets a larger reward. http://mathoverflow.net/questions/105087/nash-equilibrium-of-simple-betting-game Comment by tergi tergi 2012-08-20T13:40:38Z 2012-08-20T13:40:38Z If the result is correct then maybe it is "highly counterintuitive" because of the counterintuitive folding rule "If either player folds, each player receives 0." http://mathoverflow.net/questions/104698/the-expected-minimum-hamming-distance-within-a-set-of-randomly-selected-binary-st Comment by tergi tergi 2012-08-14T15:14:59Z 2012-08-14T15:14:59Z possibly relevant --- mathoverflow.net/questions/16359/… http://mathoverflow.net/questions/104695/agostino-prastaro Comment by tergi tergi 2012-08-14T14:49:27Z 2012-08-14T14:49:27Z Is it cool to use mathoverflow for general discussion of an arxiv upload? If not, is there a forum for this specific purpose? http://mathoverflow.net/questions/104413/tail-bound-for-poisson-random-variable/104428#104428 Comment by tergi tergi 2012-08-10T18:21:56Z 2012-08-10T18:21:56Z @irchans: $\lambda$ is supposed to be in $(0,1)$. http://mathoverflow.net/questions/104309/how-to-find-the-minimum-string-length-to-produce-a-set-of-a-given-size-with-a-min Comment by tergi tergi 2012-08-08T21:52:05Z 2012-08-08T21:52:05Z This is close enough to sphere packing to probably be an open research question. http://mathoverflow.net/questions/104137/can-the-friendship-graph-be-determind-by-its-adjacency-spectrum/104159#104159 Comment by tergi tergi 2012-08-07T19:26:34Z 2012-08-07T19:26:34Z @Jernej: "graph features" of (2,3)-, (3,3), and (4,3)-windmill graphs include "determined by spectrum" (meaning adjacency spectrum) in wolfram alpha. The link in the answer above goes to a (5,3)-windmill graph which does not mention such a graph feature, probably because wolfram-alpha doesn't know the answer.


text:
# The orthocentre of a triangle whose vertices are $(0,0),(8,0),(4,6),$ is :

$(a)\;(4,3) \quad (b)\;(4,8/3) \quad (c)\;(3,4) \quad (d)\;none\;of\;these$

$(b)\;(4,8/3)$


text:
×

## Derivatives

A derivative is simply a rate of change. Whether you're modeling the movement of a particle or a supply/demand model, this is a key instrument of Calculus.

# Logarithmic Functions

When $$f(x) = \ln ( x^{13} )$$, what is the value of $$f'(37)?$$

Details and assumptions

$$\ln$$ is the logarithm base $$e$$, also called the natural logarithm.

If $$f(x) = 4 \ln (e^ {5} x)$$, what is the value of $$f'(1)$$?

If $$f(x) = \log_{2}{x}$$, what is $$f'(x)$$?

For $$y=6\ln x+9x,$$ what is the value of $$x \cdot \frac{dy}{dx} ?$$

If $$f(x) = \log_{3}{(x+2)}$$, what is $$f'(x)$$?

×


text:
New Member

1. Aug 16, 2015

Ashdawne

hello, Im ash. I saw this forum while doing homework and it looks like it could be a lot of help. I study calculus which involves physics. nice to meet you all

2. Aug 16, 2015

Staff: Mentor

Welcome to PF!


text:
On the spectral property of kernel-based sensor fusion algorithms of high dimensional data

Journal Article

In this paper, we apply local laws of random matrices and free probability theory to study the spectral properties of two kernel-based sensor fusion algorithms, nonparametric canonical correlation analysis (NCCA) and alternating diffusion (AD), for two sequences of random vectors $\mathcal{X}:=\{\xb_i\}_{i=1}^n$ and $\mathcal{Y}:=\{\yb_i\}_{i=1}^n$ under the null hypothesis. The matrix of interest is a product of the kernel matrices associated with $\mathcal{X}$ and $\mathcal{Y}$, which may not be diagonalizable in general. We prove that in the regime where dimensions of both random vectors are comparable to the sample size, if NCCA and AD are conducted using a smooth kernel function, then the first few nontrivial eigenvalues will converge to real deterministic values provided $\mathcal{X}$ and $\mathcal{Y}$ are independent Gaussian random vectors. We propose an eigenvalue-ratio test based on the real parts of the eigenvalues of the product matrix to test if $\mathcal{X}$ and $\mathcal{Y}$ are independent and do not share common information. Simulation study verifies the usefulness of such statistic.

Cited Authors

• Ding, X; Wu, H-T