text:
mozilla

# Revision 189484 of Reference

• Revision slug: Talk:JavaScript/Reference
• Revision title: Reference
• Revision id: 189484
• Created:
• Creator: Dria
• Is current revision? No
• Comment /* deprecated pre box */

## Revision Content

I think the rest of the Reference is now finished. Just need to complete Math and Number objects.

working on this now

dria 15:39, 1 Jun 2005 (PDT)

### deprecated pre box

Is there any wiki markup available for deprecated examples?

--Maian 20:24, 25 Aug 2005 (PDT)

Help:Custom_Templates#Template:deprecated_header --Nickolay 00:58, 26 Aug 2005 (PDT)
Hmm, that was a bad question. What I meant to ask is: what markup should I use for bad examples (which aren't necessarily deprecated), i.e. examples that show what not to do? --Maian 02:07, 26 Aug 2005 (PDT)
Oh, I don't think so, but you can ask dria to create a CSS class for that. --Nickolay 11:50, 26 Aug 2005 (PDT)
I'll add it to my TODO list for the new skins. I have to go through them again this weekend to fix up some stuff anyhow. Good idea, Maian. Thanks :) -- dria 21:06, 26 Aug 2005 (PDT)

### semicolons

Should semicolons be added to all the examples?

--Maian 21:06, 25 Aug 2005 (PDT)

The original authors didn't use semicolons, but I'd add them. --Nickolay 00:58, 26 Aug 2005 (PDT)

## Revision Source

I think the rest of the Reference is now finished.  Just need to complete Math and Number objects.

 working on this now

dria 15:39, 1 Jun 2005 (PDT)

 deprecated pre box

Is there any wiki markup available for deprecated examples?

--Maian 20:24, 25 Aug 2005 (PDT)

 Hmm, that was a bad question.  What I meant to ask is: what markup should I use for bad examples (which aren't necessarily deprecated), i.e. examples that show what not to do? --Maian 02:07, 26 Aug 2005 (PDT)

 Oh, I don't think so, but you can ask dria to create a CSS class for that. --Nickolay 11:50, 26 Aug 2005 (PDT)

 I'll add it to my TODO list for the new skins.  I have to go through them again this weekend to fix up some stuff anyhow.  Good idea, Maian.  Thanks :) -- dria 21:06, 26 Aug 2005 (PDT)

 semicolons

Should semicolons be added to all the examples?

--Maian 21:06, 25 Aug 2005 (PDT)

 The original authors didn't use semicolons, but I'd add them. --Nickolay 00:58, 26 Aug 2005 (PDT)


text:
## Cryptology ePrint Archive: Report 2015/513

Computing Individual Discrete Logarithms Faster in $GF(p^n)$

Aurore Guillevic

Abstract: The Number Field Sieve (NFS) algorithm is the best known method to compute discrete logarithms (DL) in finite fields $\mathbb{F}_{p^n}$, with $p$ medium to large and $n \geq 1$ small. This algorithm comprises four steps: polynomial selection, relation collection, linear algebra and finally, individual logarithm computation. The first step outputs two polynomials defining two number fields, and a map from the polynomial ring over the integers modulo each of these polynomials to $\mathbb{F}_{p^n}$. After the relation collection and linear algebra phases, the (virtual) logarithm of a subset of elements in each number field is known. Given the target element in $\mathbb{F}_{p^n}$, the fourth step computes a preimage in one number field. If one can write the target preimage as a product of elements of known (virtual) logarithm, then one can deduce the discrete logarithm of the target.

As recently shown by the Logjam attack, this final step can be critical when it can be computed very quickly. But we realized that computing an individual DL is much slower in medium- and large-characteristic non-prime fields $\mathbb{F}_{p^n}$ with $n \geq 3$, compared to prime fields and quadratic fields $\mathbb{F}_{p^2}$. We optimize the first part of individual DL: the \emph{booting step}, by reducing dramatically the size of the preimage norm. Its smoothness probability is higher, hence the running-time of the booting step is much improved. Our method is very efficient for small extension fields with $2 \leq n \leq 6$ and applies to any $n > 1$, in medium and large characteristic.

Category / Keywords: Discrete logarithm, finite field, number field sieve, individual logarithm

Original Publication (with minor differences): IACR-ASIACRYPT-2015
DOI:
10.1007/978-3-662-48797-6_7

Date: received 27 May 2015, last revised 25 May 2016

Contact author: aurore guillevic at ucalgary ca

Available format(s): PDF | BibTeX Citation

Note: Minor modification of ASIACRYPT 2015 version (typo in Table 3 corrected).

Short URL: ia.cr/2015/513

[ Cryptology ePrint archive ]

format: plain


text:
Part 1 of a two-part series

Daniel Winton is a graduate student in mathematics at Buffalo. He did an independent study with me last semester on descriptive complexity.

Today we begin a two-part series written by Daniel on a foundational result in this area involving first-order logic and star-free languages.

Dick and I have discussed how GLL might act during the terrible coronavirus developments. We could collect quantitative and theoretical insights to help understand what is happening and possibly contribute to background for attempts to deal with it. Our March 12 post was this kind, and was on the wavelength of an actual advance in group testing announced in Israel two days ago, as noted in a comment. We could try to be even more active than that. We could focus on entertainment and diversion. Our annual St. Patrick’s Day post mentioned the ongoing Candidates Tournament in chess, with links to follow it live 7am–noon EDT. Game analysis may be found here and elsewhere.

Here we’re doing what we most often do: present a hopefully sprightly angle on a technical subject. We offer this in solidarity with the many professors and teachers who are beginning to teach online to many students. The subject of regular languages is the start of many theory courses and sometimes taught in high schools. Accordingly, Dick and I decided to prefix a section introducing regular languages as a teaching topic and motivating the use of logic, before entering the main body written by Daniel.

## Regular Languages and Logic

Regular languages are building blocks used throughout computer science. They can be defined in many ways. Two major types of descriptions are:

1. Regular expressions. For example, the regular expression

$\displaystyle b^{*}(a b^{*} a b^{*})^{*}$

describes the set of strings over the alphabet ${\{a,b\}}$ that have an even number of ${a}$‘s.

2. Finite automata, for example:

The regular languages defined by (1) and (2) are the same. All regular expressions have corresponding finite automata. This equivalence makes a powerful statement about the concept of regular languages. The more and more diverse definitions we have, the better we understand a concept. This leads us to consider other possible definitions.

A natural kind of definition involves logic. Studying complexity classes through logic and model theory has proven fruitful, creating descriptive complexity as an area. Good news: there are logic definitions equivalent to the regular languages. Bad news: they require going up to second-order logic. We would like to stay with first-order logic. So we ask:

What kind of languages can we define using only first-order logic (FOL) and simple predicates like “the ${i}$th bit of ${x}$ is ${a}$” and “place ${i}$ comes before place ${j}$“?

The answer is the star-free languages, which form a subclass ${\mathsf{SF}}$ of the regular languages. They were made famous in the book Counter-Free Automata by Robert McNaughton and Seymour Papert, where the equivalence to FOL was proved. A portentous fact is that these automata cannot solve simple tasks involving modular counting. Nor can perceptrons—the title subject of a book at the same time by Papert with Marvin Minsky, which we discussed in relation to both AI and circuit complexity. This post will introduce ${\mathsf{SF}}$ and FOL, prove the easier direction of the characterization, and give two lemmas for next time. The second post will present a new way to visualize the other direction. The rest of this post is by Daniel Winton.

## No Stars Upon Thars

A regular language over an alphabet ${\Sigma}$ is one with an expression that can be obtained by applying the union, concatenation, and Kleene star operations a finite number of times on the empty set and singleton subsets of ${\Sigma}$. Star-free languages are defined similarly but give up the use of the Kleene star ${{}^*}$ operation, while adding complementation (${\sim}$) as a basic operation. The star-free languages are a subset of the regular languages, because regular languages are closed under complementation.

Complementation often helps find star-free expressions that we ordinarily write using stars. For instance, if the alphabet ${\Sigma}$ is ${\{a,b\}}$, then ${(\sim \emptyset)}$ gives ${(a + b)^*}$. The following lemma gives a family of regular expressions that use Kleene star but are really star-free.

Lemma 1 The language given by taking the Kleene star operation on a union of singleton elements in an alphabet ${\Sigma}$ is star-free.

Proof. For ${\Sigma=\{a_1, ..., a_n, b_1, ..., b_m\}}$ we have that ${(b_1+ ... + b_m)^*}$ can be given by

$\displaystyle \sim((\sim\emptyset) (a_1+ ... + a_n) (\sim\emptyset)). \quad$

$\Box$

For example, the language ${b^*ab^*ab^*}$ is star-free because ${b^*}$ is by this lemma. This idea extends also to forbidden substrings—e.g., the set of strings with no ${aa}$ is ${\;\sim((\sim\emptyset)aa(\sim\emptyset))}$.

The language ${(ab + ba + bb)^*}$ is not the same, however, and it is not star-free. Intuitively this is because it involves modular counting: an ${aa}$ in an odd position is OK but not even. The parity language ${b^*(ab^*ab^*)^*}$ from the introduction is another example. So ${\mathsf{SF}}$ is a proper subset of the regular languages. What kind of subset? This is where having a third description via logic is really useful.

## The First Order of Business

In addition to the familiar Boolean operations ${\wedge,\vee,\neg,\rightarrow,\leftrightarrow}$ and truth values, first-order logic provides variables that range over elements of a structure and quantifiers on those variables. Since we will be concerned with Boolean strings ${x}$, the variables will range over places in the string ${0,\dots,n-1}$, where ${n = |x|}$. A logic also specifies a set of predicates that relate variables and interact with the structure. For strings we have:

• ${X_c(i)}$, meaning that the symbol indexed ${i}$ in ${x}$ is the character ${c}$. The logic gives one such predicate for each ${c \in \Sigma}$.

• ${i < j}$, with the obvious meaning for natural numbers ${i}$ and ${j}$.

We can take the ${X_c}$ for granted since we are talking about strings, but we need to say that predicates like ${i + j = k}$ and ${i\cdot j = k}$ are excluded, so we call this ${\mathsf{FO}[<]}$. We could define equality by ${i = j \equiv \lnot(i < j \lor j < i)}$ but we regard equality as inherent.

We can use ${<}$ to define the successor relation ${S(i,j)}$, which denotes that position ${j}$ comes immediately after position ${i}$:

$\displaystyle S(i,j) \equiv i

Note the use of quantifiers. We can use quantifiers to say things about the string ${x}$ too. For instance, the language ${L}$ of strings having no ${aa}$ substrings is defined by the logical sentence

$\displaystyle \sigma_L = (\forall i,j):S(i,j) \rightarrow \neg (X_a(i) \land X_a(j)).$

It is implicit here that ${i}$ and ${j}$ are always in-bounds. If ${n}$ were a legal constant with ${X_c(n)}$ always false then a string like ${bbba}$ (which belongs to ${L}$) would falsify ${\sigma_L}$ with ${i = n-1}$ and ${j = n}$.

How big is ${\mathsf{FO}[<]}$? We'll see it is no more and no less than ${\mathsf{SF}}$.

## From SF to FO

To prove that any language ${L}$ in ${\mathsf{SF}}$ has a definition in ${\mathsf{FO}}$, we will not only give a sentence ${\sigma_L}$ but also a formula ${\phi_L(i,j)}$. We will define this formula to indicate that for a given string ${x}$, the portion of the string between indices ${i}$ and ${j-1}$ is in ${L}$. Then for the correct choices of ${i}$ and ${j}$, ${\phi_L(i,j)}$ gives ${L}$. We define ${\phi}$ to test middle portions of strings, because it handles lengths better for the induction in the concatenation case.

Theorem 2

Every language in ${\mathsf{SF}}$ is definable in ${\mathsf{FO}[<]}$.

The proof is a nice example where “building up” to prove something more general—involving two extra variables—makes induction go smoothly.

Proof: Let ${L}$ be a star-free regular language and ${L'=\{\langle x, i ,j \rangle:}$ the portion of the string ${x}$ between indices ${i}$ (inclusive) and ${j}$ (exclusive) is contained in ${L\}}$. Let ${\phi_L(i,j)\in \sf{FO}[<]}$ be the formula denoting that for a given string ${x, x[i,j)\in L}$, that is, ${\phi_L(i,j)}$ is the representation of ${L'}$ in ${\mathsf{FO}[<]}$. We will show that such a ${\phi_L(i,j)}$ exists via induction on ${L}$. This is sufficient, as for a given symbol ${n}$ that always represents the length of a string ${x}$, ${\phi_L(0,n)}$ is the formula in ${\mathsf{FO}[<]}$ representing the language ${L}$.

First, we must show that ${\phi_L}$ is in ${\mathsf{FO}[<]}$ for ${L}$ one of the basis languages, ${\emptyset, \epsilon}$, and ${c}$, for some ${c}$ in ${\Sigma}$. We have that:

$\displaystyle \begin{array}{rcl} \phi_\emptyset(i,j) &=& \texttt{false};\\ \phi_\epsilon(i,j) &=& i=j;\\ \phi_c(i,j) &=& (X_c(i)\land S(i,j)). \end{array}$

Now, we must show that given star-free languages ${L_1}$ and ${L_2}$ with FO${[<]}$ translations ${\psi_1(i,j)}$ and ${\psi_2(i,j)}$ respectively, we have ${\phi_{L_1\cup L_2}(i,j)}$, ${\phi_{L_1\cdot L_2}(i,j)}$, and ${\phi_{\sim L_1}(i,j)}$ are in ${\sf{FO}[<]}$. Then:

$\displaystyle \begin{array}{rcl} \phi_{L_1\cup L_2}(i,j)&=&\psi_1(i,j) \lor \psi_2(i,j);\\ \\ \phi_{L_1\cdot L_2}(i,j)&=&\exists k(i\leq k \land k \leq j) (\psi_1(i,k) \land \psi_2(k,j));\\ \\ \phi_{\sim L_1}(i,j)&=&\lnot \psi_{1}(i,j). \end{array}$

Since star-free languages can be obtained by applying the union, concatenation, and complementation operations a finite number of times on ${\emptyset}$ and singleton subsets of ${\Sigma}$, this completes the proof of ${\mathsf{SF} \subseteq \mathsf{FO}[<]}$. $\Box$

## Two Lemmas For Next Time

Prefatory to showing (in the next post) that ${\mathsf{FO}[<]}$ is contained in ${\mathsf{SF}}$, we prove properties about substrings on the ends of star-free languages, rather than in the middle as with the trick in the proof of Theorem 2.

Let ${L}$ be a language over an alphabet ${\Sigma}$ and ${w}$ be a word in ${\Sigma^n}$ for some ${n\in \mathbb{N}}$. Define ${L/w}$, the right quotient of ${L}$ by ${w}$, by ${L/w =\{v: vw \in L\}}$ and ${L\backslash w}$, the left quotient of ${L}$ by ${w}$, by ${L\backslash w=\{v:wv \in L\}}$. First we handle right quotients:

Lemma 3 If ${L}$ is star-free, then ${L/w}$ is star-free.

Proof: For any word ${w}$ over ${\Sigma}$ we define a function ${f_w(\alpha)}$ by ${f_w(\alpha)=\alpha'}$ where ${L(\alpha')=L(\alpha)/w}$. If ${w = \epsilon}$, then ${f_w(\alpha)=\alpha}$, and so the statement of the lemma trivially holds. So let ${w = vc}$ for some string ${v}$ and character ${c}$. Note that ${L/(vc) = (L/c)/v}$. Thus ${f_{vc}(\alpha) = f_v(f_c(\alpha))}$ for all ${\alpha}$. Hence it suffices to define ${f_c(\alpha)}$ for any single character ${c}$ by recursion on ${\alpha}$. We have:

$\displaystyle \begin{array}{rcl} f_c(\emptyset)&=&\emptyset;\\ f_c(\epsilon)&=&\emptyset;\\ f_c(c)&=&\epsilon;\\ f_c(a)&=&\emptyset, \end{array}$

and recursively:

$\displaystyle \begin{array}{rcl} f_c(\alpha \cup\beta)&=&f_c(\alpha) \cup f_c(\beta);\\\\ f_c(\alpha\cdot\beta)&=&\begin{cases} \alpha\cdot f_c(\beta) & \epsilon\not\in L(\beta), \\ \alpha\cdot f_c(\beta) \cup f_c(\alpha) & otherwise\text{;} \end{cases}\\\\ f_c(\sim\alpha)&=&\sim f_c(\alpha). \end{array}$

In general, if ${w = c_1 c_2 \cdots c_{n-1} c_n}$, then

$\displaystyle L/w = f_{c_1}(f_{c_2}(\dots f_{c_{n-1}}(f_{c_n}(\alpha))\dots)).$

$\Box$

Lemma 4 If ${L}$ is star-free, then ${L\backslash w}$ is star-free.

The proof of Lemma 4 is similar to the proof of Lemma 3. The main differences lie in the concatenation subcase for the ${w=c}$ case and the order of quotienting when using this operation repeatedly.

Proof: For any word ${w}$ over ${\Sigma}$ we define a function ${f_w(\alpha)}$ by ${f_w(\alpha)=\alpha'}$ where ${L(\alpha')=L(\alpha)\backslash w}$. If ${w = \epsilon}$, then ${f_w(\alpha)=\alpha}$, and so the statement of the lemma trivially holds. So let ${w = vc}$ for some string ${v}$ and character ${c}$. Note that ${L\backslash(vc) = (L\backslash v)\backslash c}$. Thus ${f_{vc}(\alpha) = f_c(f_v(\alpha))}$ for all ${\alpha}$. Hence it suffices to define ${f_c(\alpha)}$ for any single character ${c}$ by recursion on ${\alpha}$. We have:

$\displaystyle \begin{array}{rcl} f_c(\emptyset)&=&\emptyset;\\ f_c(\epsilon)&=&\emptyset;\\ f_c(c)&=&\epsilon;\\ f_c(a)&=&\emptyset.\\ \end{array}$

and recursively:

$\displaystyle \begin{array}{rcl} f_c(\alpha\cup\beta)&=&f_c(\alpha)\cup f_c(\beta);\\\\ f_c(\alpha\cdot\beta)&=&\begin{cases} f_c(\alpha)\cdot\beta & \epsilon\not\in L(\alpha), \\ f_c(\alpha)\cdot\beta \cup f_c\beta) & otherwise\text{;} \end{cases}\\\\ f_c(\sim \alpha)&=&\sim f_c(\alpha). \end{array}$

In general, if ${w = c_1 c_2 \cdots c_{n-1} c_n}$, then

$\displaystyle L\backslash w = f_{c_n}(f_{c_{n-1}}(\dots f_{c_{2}}(f_{c_1}(\alpha))\dots)).$

$\Box$

## Open Problems

There are richer systems such as ${\mathsf{FO}(+)}$ and ${\mathsf{FO}(+,\cdot)}$. Note that ${\mathsf{FO}(+)}$ allows defining the ${<}$ relation via ${i < j \equiv (\exists k) \lnot(k= 0) \land i + k = j}$. We can define non-regular languages such as ${{a^n b^n}}$ in ${\mathsf{FO}(+)}$. The class ${\mathsf{FO}(+,\times)}$ famously equals uniform ${\mathsf{AC^0}}$, see chapter 5 of Neil Immerman's book Descriptive Complexity. Thus we hope our new style for proving ${\mathsf{FO}[<] \subseteq \mathsf{SF}}$ (to come in the next part) will build a nice foundation for visualizing these higher results.

March 21, 2020 5:27 pm

SF = FO[<] is known as Theorem of Schützenberger. What is not very well-known is that
Schützenberger gave another characterization of SF in terms of regular expressions:
A language is star-free iff it expressible by regular expressions where the use of the star-
operation is only allowed over (prefix?)codes of bounded synchronization delay.

• March 21, 2020 9:30 pm

Thanks. More detail is available in this 2007 survey, and we followed its ascriptions.

March 22, 2020 2:45 pm

SInce FO[<] is in my mind an alias of SF, I made this mistake. Sch. related automata and syntactic monoids to expressions, while the relations to logic are off course due to M.+P. Sorry for that.

NB: The reference to Schützenberger's other characterization of SF was given to me by one of the authors of the survey.

March 22, 2020 4:07 pm

Maybe I misunderstood something. I think the proposal for defining equality in FOL[<] contains a typo? Doesn't seem to be well-formed. If I'm mistaken, please clarify. thanks!


text:
+0

Find the largest prime number p such that when 2012! is written in base p, it has at least p trailing zeroes.

0
74
7
+79

Find the largest prime number p such that when 2012! is written in base p, it has at least p trailing zeroes.

May 9, 2019

#1
+101771
+1

Find the largest prime number p such that when 2012! is written in base p, it has at least p trailing zeroes.

If you write any number in a different base then the number of zeros will be the number of times that base can be divided into the number

For example.   20 written in base 2 will have 2 zeros at the end because 20 can be divided by 2 twice and get an integer answer.

I have deleted what I wrote after this point because it was nonsense.  BUT

You should be able to use this initial fact to help determine the correct answer.

May 12, 2019
edited by Melody  May 12, 2019
#2
+1

Melody why is that? we can divide 2012! by 2 more than once

Guest May 12, 2019
#3
+101771
0

Yes, you are absolutely correct.  Great observation!

My last sentence is completely wrong.  (I willl delete it with an explanatory note)

I think you can still use the beginning of my explanation to determine the correct answer.  I may do it myself when I have a little more time.

May 12, 2019
#4
+101771
+2

Find the largest prime number p such that when 2012! is written in base p, it has at least p trailing zeroes.

The answer is 43 because 43^2 is the biggest squared prime number that is less than 2012!

I did work this our logically but BUT I will admit that it may be difficult for me to show this logic.

I will try

Say the number was not 2012! Say it is what ever number factorial that will work if

p is 2

1*2*3*4 = 1*2*3*2*2 = 3*2*2*2   this will have 3 trailing zeros when written in base 2 (there is no version with only 2 trailing zeros)

so if p=2 then it would have to be factorial 4.          Note that 2^2=4

Try p=3

I need the smallest factorial (X!) where X! written in base 3 has at least 3 trainling zeros. So I need at least 3^3 = 27 to be a factor

1*2*3*4*5*6*7*8*9 = 1*2*3*4*5*2*3*7*8*3*3 = 3^4 * 2*4*5*2*7*8  = 9!

when 9! is written in base 3 there will be 4 trailing zeros .. It is imposible to have only 3

Try p=5

I need the smallest factorial (X!) where X! written in base 5 has at least 5 trainling zeros. So I need at least 5^5  to be a factor

1*2*3*4*5*6*7*8*9*10* ..... 25

= (Some integer without 5 as a factor)* 5*1*   5*2  *  5*3  * 5*4  *  5*5

= (Some integer without 5 as a factor)* 5 *  5 *  5* 5  *  5*5

= (Some integer without 5 as a factor)* 5^6

when 25! is written in base 5 there will be 6 trailing zeros .. It is imposible to have only 5

Let me try and explan the general version.

Let the number be p

Consider  this
$$(p^2)!=1*2*......1p.......*2p........*(p-1)p.....*(pp) \\ (p^2)!=1*2*...1*2* ...*(p-1).....*p^{(p-1)}.....*p^2\\ (p^2)!=(\text{An interger without p as a factor}).....*p^{(p-1)}.....*p^2\\ (p^2)!=(\text{An interger without p as a factor}).....*p^{(p+1)}\\$$

Back to the original question

Find the largest prime number p such that when 2012! is written in base p, it has at least p trailing zeroes.

$$\sqrt{2012}\approx 44.8$$

The closest prime number less than 44.8 is 43

So  p=43

-------------------------------------------------------------------------

Lets check

$$2012! = \text{(Some integer that does not have 43 as a factor)}*43*2*43*3*43 *..........42*43*43*43\\ 2012! = \text{(Some integer that does not have 43 as a factor)}*43^{42}*43*43\\ 2012! =\text{(Some integer that does not have 43 as a factor)}*43^{44}\\ \text{When written in Base 43 2012! will have 44 trailing zeros.}$$

What about if p=47, maybe it will work too?

$$2012! = \text{(Some integer that does not have 47 as a factor)}*47*2*47*3*47 *..........42*47\\ 2012! = \text{(Some integer that does not have 43 as a factor)}*47^{42}\\ \text{When written in Base 47 2012! will only have 42 trailing zeros.}\\ \text {so Base 47 will definitely not work}$$

.
May 13, 2019
#5
+1

Hello Melody: I wrote a very short code to convert 2012! to base 43 in its entirety: Here are just the beginnings of the number and its trailing zeros. They count to 47 zeros.
(6, 38, 32, 10, 35............   14, 21, 18, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)

P.S. I also converted it to base 47 and it gives 42 zeros.

May 13, 2019
edited by Guest  May 13, 2019
#6
+1

Note: To count the number of trailing zeros of N! in any base above 36, simply divide N by the powers of the base that are <= N.

Example: 2012! in base 43, we simply divide:2012 / 43^1 + 2012 / 43^2 =46 + 1= 47 zeros. Just take the INTEGER part.

2012! in base 47: 2012 / 47^1 + 2012 / 47^2 = 42 + 0 = 42 zeros. [47^2 is > than 2012, hence = 0]

May 13, 2019
#7
+101771
+2

Yes that sounds reasonable.

You say there are 47 trailing zeros

Our number is  2012!

43^2 = 1849

Since 1849 is smaller than 2012 so I would expect there to be more than 44 trailing zeros when 2012! is written in base 43.

I know I have told you many times before but I really like your little lines of code that you figure out and run.

It is a really helpful check mechanism.

I'd really like it if you became a member.

You could call yourself  CodeDude    OR    Cplusplus ( I think C++ is the code you use??)   LOL

OR you could chose whatever you want.

May 14, 2019


text:
# Why space must be quantised on a different scale to matter

### Submission summary

 As Contributors: Matthew J. Lake Preprint link: scipost_202009_00001v2 Date submitted: 2021-02-03 11:07 Submitted by: Lake, Matthew J. Submitted to: SciPost Physics Proceedings Proceedings issue: 4th International Conference on Holography, String Theory and Discrete Approach in Hanoi Academic field: Physics Specialties: Quantum Physics Approaches: Theoretical, Phenomenological

### Abstract

The scale of quantum mechanical effects in matter is set by Planck's constant, $\hbar$. This represents the quantisation scale for material objects. In this article, we give a simple argument why the quantisation scale for space, and hence for gravity, cannot be equal to $\hbar$. Indeed, assuming a single quantisation scale for both matter and geometry leads to the worst prediction in physics', namely, the huge difference between the observed and predicted vacuum energies. Conversely, assuming a different quantum of action for geometry, $\beta \neq \hbar$, allows us to recover the observed density of the Universe. Thus, by measuring its present-day expansion, we may in principle determine, empirically, the scale at which the geometric degrees of freedom must be quantised.

###### Current status:
Has been resubmitted

Dear Editor(s),

Please see attached the revised manuscript of scipost_202009_00001v1. I have amended the text in order to address the referee’s comments and a detailed list of all changes is given below. These mostly take the form of footnotes, in order to preserve the essay-style flow of the original draft. I thank the referee for taking the time to read through the manuscript carefully and giving feedback. I hope that these changes have satisfactorily addressed his / her remaining concerns.

Best wishes,

Matt

### List of changes

A footnote has been added at the end of the last sentence on pg 1 clarifying the meaning of the term ‘quantisation scale’.
• A footnote has been added at the end of the sentence below Eq. (3.1). This is to clarify the way in which whole functions, $g(x’-x)$, may be associated with single points, $x$, as well as how the model defines points’ in both the quantum and classical regimes.
• A footnote was added at the end of sentence following Eq. (3.3). This is to clarify the precise meaning of the term ‘quantum geometry wave’.
• The final sentence of the Conclusions has been changed from “These include the proposal that the observed vacuum energy is related to the quantisation scale of space itself \cite{Lake:2019oaz,Lake:2019nmn}.” to “These include the proposal that the observed vacuum energy, and the present-day accelerated expansion of the universe that it drives, are related to the quantum properties of space-time \cite{Lake:2019oaz,Lake:2019nmn}. In this model, a measurement of the dark energy density constitutes a de facto measurement of the geometry quantisation scale, $\beta$, fixing its value to $\beta \simeq \hbar \times 10^{-61}$.” Although this is clearly a postdiction rather than a prediction of the model, it provides a concrete link between observations and the smeared-space model parameters, in response to the referee’s final point.
• Two new references have been added, which appear as refs. [5] and [23] in the new draft.

### Submission & Refereeing History

#### Published as SciPost Phys. Proc. 4, 014 (2021)

Resubmission scipost_202009_00001v4 on 8 July 2021
Resubmission scipost_202009_00001v3 on 24 April 2021

Resubmission scipost_202009_00001v2 on 3 February 2021
Submission scipost_202009_00001v1 on 1 September 2020

## Reports on this Submission

### Anonymous Report 2 on 2021-3-29 (Invited Report)

• Cite as: Anonymous, Report on arXiv:scipost_202009_00001v2, delivered 2021-03-29, doi: 10.21468/SciPost.Report.2738

### Strengths

1- Deals with an important problem in theoretical physics

### Weaknesses

1- The main claim does not logically follow from an argument as presented.
2- Some statements lack rigorous explanation.
3- Certain similar approaches in the literature are not mentioned.
4. Some important issues are not addressed.

### Report

In the submitted manuscript the author suggests a new physical scale where geometry is quantized and proposes an uncertainty relation that involves this scale and explains the cosmological constant problem.

The idea of a quantization scale for spacetime which has no a priori relation to $\hbar$ and a possible coarse-graining of spacetime at high energy is certainly not new. One can find rigorous arguments and specific models for instance in Phys.Lett.B 331 (1994) 39-44 by Doplicher, Fredenhagen and Roberts or Annals Phys. 219 (1992) 187-198 by Madore. The author presents a similar suggestion, however it is not supported by rigorous arguments or a particular model that can realise it. The title of the manuscript claims that space must be quantised with a new scale, but the argumentation is that this must be so due to the smallness of the vacuum energy. It is not clear how the cosmological constant problem necessarily leads to this conclusion. In the body of the paper, the only explanation is that “we have no a priori reason to believe that space must be quantized on the same scale […]”. Although this is not incorrect, and indeed it has been suggested many decades ago, it does not follow as a logical conclusion from the cosmological constant problem.

Moreover, the lack of a specific model in the manuscript raises questions such as what is the precise mathematical description of the “smeared space”, how does classical geometry emerge, and whether Lorentz invariance is lost. None of these important issues is addressed. Based on the above, I cannot recommend the submitted manuscript for publication in its present form.

### Requested changes

1- The main claim of the paper should be scaled down, already in the title and also in the main text. There is no rigorous argument establishing that a new quantization scale "must" exist. The proposal should be presented as a possibility, not as a certain conclusion.

2- Mention and comparison with previous similar proposals is required, such as the ones of Doplicher, Fredenhagen and Roberts, and Madore.

3- The author should explain how classical space(time) emerges, presumably in the limit $\beta \to 0$.

4- Previous approaches to the quantization of space at a new scale have addressed the question of doing this in a Lorentz invariant way. The author is asked to explain whether Lorentz invariance is lost or not, and if it does how does the proposal avoid being ruled out.

5- It would be advisable to support the proposal with a particular model/theory that can implement the modified uncertainty relation (4). Heisenberg's uncertainty relation leads to a noncommutative phase space; is there a similar noncommutative space or some other specific geometric picture that underlies the proposal of the paper?

• validity: ok
• significance: ok
• originality: ok
• clarity: ok
• formatting: reasonable
• grammar: perfect

### Author:  Matthew J. Lake  on 2021-04-22  [id 1375]

(in reply to Report 2 on 2021-03-29)
Category:

Reply to the Referee Report for Why space must be quantised on a different scale to matter' [scipost-202009-00001v2]

I thank the referee for their comments, and for drawing several references to my attention, which I was not previously aware of. I have cited these in the updated manuscript, together with some additional related literature. Below, I provide detailed replies to the points raised in the report. However, first, let me say that, as a contribution to a conference proceedings, my original draft was written with two important aims in mind:

1. To provide an accurate written summary of the presentation I actually gave at the 4th International Conference on Holography in Hanoi, and

2. To avoid undue technical detail in the text itself, which would be inappropriate for a proceedings article. Instead, I aimed to cite the relevant (already published) works, in which the technical discussion and mathematical details of the model are contained.

For these reasons, I have not made major changes to the manuscript. Instead, I address the questions raised by the referee, in depth, in this reply letter, and have added only short notes to the text to highlight the references where the relevant technical details can be found. For clarity, the referee's questions are given in quotation marks and my responses are written in normal type.

Report:

"In the submitted manuscript the author suggests a new physical scale where geometry is quantized and proposes an uncertainty relation that involves this scale and explains the cosmological constant problem.

"The idea of a quantization scale for spacetime which has no a priori relation to $\hbar$ and a possible coarse-graining of spacetime at high energy is certainly not new. One can find rigorous arguments and specific models for instance in Phys. Lett. B 331 (1994) 39-44 by Doplicher, Fredenhagen and Roberts or Annals Phys. 219 (1992) 187-198 by Madore."

I have read the works cited by the referee in detail, and cannot find any reference to a second quantisation scale. In the works by Madore and others, uncertainty relations for spatial coordinates are introduced by introducing noncommutative geometry (NCG) in the position space representation, e.g., by introducing an X-X commutator of the form $[X^i,X^j] = \sigma^2 \, \delta^{ij}$. Here, $\sigma$ is a constant with dimensions $[L]$ or, equivalently, $[M]^{-1}$ (if $\hbar = c = 1$). It is important to recognise that this does not constitute a second quantisation scale, which must have units of action, $[L][M]$. To obtain a new quantisation scale from NCG models, one must also introduce a similar relation in the momentum space representation, e.g., $[P_i,P_j] = \tilde{\sigma}^2 \, \delta_{ij}$, where $\tilde{\sigma}$ has dimensions $[M]$, or equivalently $[L]^{-1}$. It is then straightforward to see that, setting

$(\Delta X^i) _{min} \simeq \sigma$,

where $\sigma = l_{\rm Pl}$ is the Planck length, and

$(\Delta P_j)_{\rm min} \simeq \tilde{\sigma}$,

where $\tilde{\sigma} \simeq m_{\rm dS}$ and $m_{\rm dS} \simeq \hbar\sqrt{\Lambda}$ is the de Sitter mass, the new quantisation scale is $\beta \simeq \sigma \tilde{\sigma} \simeq \hbar\sqrt{\rho_{\Lambda}/\rho_{\rm Pl}}$. This is exactly Eq. (6) in the present text.

The studies by Doplicher, Fredenhagen and Roberts, and by Madore, cited above, certainly do not do this, and, to the best of my knowledge, neither do any of the subsequent related works. I am not sure why this is, and I confess that I am not an expert on NCG, but I could imagine that there are significant technical barriers to the consistent implementation of such a model.

However, if such a model were to be self-consistently constructed, it should be stressed that, since the X-X and P-P commutators above do not refer to the position and momentum of material particles, but, instead, to delocalised, or smeared out' spatial points, the new quantisation scale $\beta \simeq \sigma \tilde{\sigma}$ need not have any a priori relation with $\hbar$. It would, instead, represent the quantisation scale for the spatial background on which canonical quantum matter propagates, which is much more reminiscent of our model than conventional NCG theories. Despite this, there are still many differences, which are discussed below in response to the referee's other questions.

"The author presents a similar suggestion, however it is not supported by rigorous arguments or a particular model that can realise it."

The formalism of the model is presented in a series of published works, which are cited at the relevant points in the manuscript, see refs. [16], [17], [18] and [19]. (Please note that the book chapter, [19], has not yet been formally published, because the hardback copy is still in print. However, the manuscript available on the arXiv has been accepted, in its current form, after a rigorous review process by Springer. I append the letter of acceptance to the end of this reply letter.)

"The title of the manuscript claims that space must be quantised with a new scale, but the argumentation is that this must be so due to the smallness of the vacuum energy. It is not clear how the cosmological constant problem necessarily leads to this conclusion."

The argument for this claim is based on the following, very general, observations:

1. If the Planck length is a fundamental length scale in nature, then classical spatial points are in some way delocalised' in the quantum theory of gravity. This introduces metric fluctuations over Planck-scale volumes and, hence, a minimum observable position $(\Delta X^i)_{\rm min}$ of the order of the Planck length. (This is certainly not a new idea and is a mainstay of most approaches to quantum gravity.)

2. A Planck-scale fluctuation of the spacetime metric, over a volume $\sim (\Delta X)_{\rm min}^3$, must carry an associated momentum, which we label $\Delta P$. (The italicised word must here is important.)

3. The associated energy density is of order $\rho \simeq \Delta P/(\Delta X)_{\rm min}^3$. We stress that this is the energy density induced by quantum fluctuations of the spacetime metric, i.e., the energy density of the quantum spatial background, not the energy density of the canonical quantum matter that propagates within it.

4. On dimensional grounds, $\Delta P \simeq \kappa/l_{\rm Pl}$, where $\kappa$ has dimensions of action. Clearly, if $\kappa = \hbar$, i.e., if space is quantised on the same scale as matter, then $\rho \simeq \rho_{\rm Pl}$. Therefore, since the observed vacuum density is much lower than the Planck density, $\kappa \ll \hbar$.

Essentially, we argue that this conclusion is logically inherent in all previous works on quantum gravity (or at least those which assume Planck-scale metric fluctuations) but, for some reason, has never been fully explored in the literature. In Sections 3 and 4, we argue that setting $\kappa \equiv \beta \simeq \sigma\tilde{\sigma} \simeq \hbar\sqrt{\rho_{\Lambda}/\rho_{\rm Pl}}$, i.e., setting $\sigma \simeq l_{\rm Pl}$ and $\tilde{\sigma} \simeq m_{\rm dS}$, allows us to recover the observed vacuum energy density, $\rho_{\Lambda} \simeq \Lambda/G$, though it should be noted that, in order to realise this, we are required to make several other assumptions. The additional assumptions required are discussed, explicitly, in Section 4, but we make no strong claims for their acceptance.

As a happy byproduct, we also recover the GUP, EUP and EGUP, previously proposed in the quantum gravity literature. Equivalently, we may say that the generalised uncertainty relations naturally motivate a specific vacuum energy model, which saturates the EGUP, and that both arise, ultimately, from the existence of a second quantisation scale for space(time). Note that the EUP and EGUP, as presented in the existing literature, are recovered only when $\kappa \equiv \beta \propto \sqrt{\Lambda}$.

Nonetheless, the observation that $\rho_{\rm vac} \ll \rho_{\rm Pl}$, plus the existence of a Planck length cut-off for spatial wavelengths, requires $\kappa \ll \hbar$, regardless of whether this is identified with the observed value of the cosmological constant.

"In the body of the paper, the only explanation is that we have no a priori reason to believe that space must be quantized on the same scale [...]' ”

As stated above, this is not the only explanation given in the body of the paper. The argument given in Sections 2 and 3 of the text was condensed into points 1-4 in the previous response.

"Although this is not incorrect, and indeed it has been suggested many decades ago, it does not follow as a logical conclusion from the cosmological constant problem."

I completely agree with this statement, but am not aware of any specific references in which a second quantisation scale (quantum of action) for space was suggested. If such a suggestion was made decades ago, then it is certainly an oversight on my part not to have cited these works! I would be most grateful if the referee could point me in their direction, and will also cite them in any future work on this topic.

"Moreover, the lack of a specific model in the manuscript raises questions such as what is the precise mathematical description of the “smeared space”, how does classical geometry emerge, and whether Lorentz invariance is lost. None of these important issues is addressed. Based on the above, I cannot recommend the submitted manuscript for publication in its present form."

The results quoted in the manuscript are based on a very specific model, with a rigorously defined mathematical formalism, which was developed in a series of papers, [16], [17], [18] and [19]. All the questions raised by the referee are explicitly addressed therein, e.g., how does classical geometry emerge?' (see ref. [16] Section 3.1, below Eq. (47), and Section 4.1),whether Lorentz invariance is lost?' (see ref. [19] Section 2). These points are discussed further below, but were not treated in detail in the present manuscript, since this would have been inappropriate for a conference proceedings.

(To be honest, I am not at all sure whether the referees were made aware, by SciPost, that the text is a contribution to a conference proceedings and was never intended as a research article. Therefore, it contains only a very brief summary of already published work. I stress that the omission of mathematical details is by design and that said details can be found in the works cited in the text. Needless to say, if the referee was misinformed, by SciPost, as to the nature and purpose of the article, this is in no way his / her fault.)

Requested changes:

"1. The main claim of the paper should be scaled down, already in the title and also in the main text. There is no rigorous argument establishing that a new quantization scale "must" exist. The proposal should be presented as a possibility, not as a certain conclusion."

To be honest, the title of the paper was not meant to be taken too literally. I completely agree with the referee, that such a title would be completely inappropriate for a research article, but I considered it within the scope of artistic license for the title of a conference talk. This was deliberately provocative', to some degree, since it it was intended to grab, and hopefully keep, the attention of the audience. The title of the present manuscript is exactly the title of the talk I gave at the conference in Hanoi, because this is already a a matter of public record. (The conference program has long since been published.)

For this reason, with the referee's permission, I would like to keep the present title. However, I have no strong feelings on this either way, and, if he / she feels that another title would be more appropriate, I am happy to comply with this request. In this case, I would suggest either Why space could be quantised on a different scale to matter' orShould space be quantised on a different scale to matter?'.

Corresponding changes of language could also be made throughout the text, but I refer again to points 1-4 above, which I regard as a strong argument in favour of a new quantisation scale, $\kappa \ll \hbar$. A more detailed mathematical argument for its existence is given in [16], [18], [19]. See, for example, the treatment of delocalised (smeared') momentum measurements, in a universe with a finite de Sitter horizon, given in [16], Section 3.1.3.

"2. Mention and comparison with previous similar proposals is required, such as the ones of Doplicher, Fredenhagen and Roberts, and Madore."

These have been added to the text. Once again, I thank the referee for bringing them to my attention.

"3. The author should explain how classical space(time) emerges, presumably in the limit $\beta \rightarrow 0$."

The emergence of the canonical quantum limit, that is, of quantum matter on a classical space(time) background, is dealt with explicitly in [16] (see Section 3.1, below Eq. (47)). The key point is that, although there are three ways to take the limit $\beta \rightarrow 0$, two of them lead to inconsistencies. Since $\beta \simeq \sigma\tilde{\sigma}$, where $\sigma$ sets the smearing scale for the position space representation and $\tilde{\sigma}$ sets the smearing scale for momentum space, setting $\beta \rightarrow 0$ by taking either $\sigma > 0$, $\tilde{\sigma} \rightarrow 0$ or $\sigma \rightarrow 0$, $\tilde{\sigma} > 0$ leads to a smearing of one representation while the other remains purely classical. In these cases, the mathematical formalism of the theory breaks down. Therefore, we are required to set $\sigma \rightarrow 0$ and $\tilde{\sigma} \rightarrow 0$, simultaneously. In this limit, we recover the predictions of canonical quantum theory [16]. A short note has been added to the text to highlight this point.

"4. Previous approaches to the quantization of space at a new scale have addressed the question of doing this in a Lorentz invariant way. The author is asked to explain whether Lorentz invariance is lost or not, and if it does how does the proposal avoid being ruled out."

This is an important point, which relates to one of the model's strongest advantages. It is well known that mainstream approaches to GUP models, based on modified commutation relations (including those derived from NCG) suffer from severe pathologies. These include:

1. Violation of the equivalence principle.

2. Violation of Lorentz invariance in the relativistic limit.

3. The reference frame dependence of the minimum' length.

4. The inability to construct sensible multi-particle states, known as the soccer ball problem'.

Ultimately, all of these problems, including the breaking of Lorentz invariance, arise from the breaking of the shift-isometry subgroup of the Poincare group, which also forms a subgroup of the Galilean group in the nonrelativistic limit. (See [19] and references therein, including the reviews of GUP literature by Hossenfelder [Living Reviews in Relativity volume 16, Article number: 2 (2013)] and Tawfik and Diab [Int. J. Mod. Phys. D 23 (2014) 1430025].) A major advantage of our model is that it generates generalised uncertainty relations (GURs) without introducing modified commutators of the form suggested in the existing literature. Instead, the canonical X-P commutator is simply rescaled, such that $\hbar \rightarrow \hbar + \beta$. (See also Bishop et al, Phys. Lett. B, Volume 816, 10 May 2021, 136265, for work in a similar direction.) This preserves translation invariance, even in the presence of a minimum length, since the reference frame of the background space is quantised, but not discretised.

Therefore, although we have not constructed an explicitly Lorentz invariant extension of the model, it is clear that a major obstacle to its implementation, which exists in all virtually all other GUP models, has been removed by the careful construction of our model in the nonrelativisitic limit. I completely agree with the referee that this point is important, but I did not have time to address it adequately in my conference talk, even in the Q and A. Therefore, since it is dealt with at length in already published work, I regarded it as beyond the scope of the present summary.

" 5. It would be advisable to support the proposal with a particular model/theory that can implement the modified uncertainty relation (4). Heisenberg's uncertainty relation leads to a noncommutative phase space; is there a similar noncommutative space or some other specific geometric picture that underlies the proposal of the paper?"

As explained above, the model is very particular, and is based on a rigorous mathematical formalism that was developed in a series of already published works, [16], [17], [18] and [19]. Below, I outline some of its essential features, including its differences with, and similarities to, previous models in the quantum gravity literature. I hope that this will clear up any remaining confusion.

With regard to this point, there is an unfortunate confusion of terminology, which, however, we were unable to avoid, even with the help of a thesaurus. In the review by Madore [arXiv:gr-qc/9709002], he states that points are somehow smeared out' orfuzzy'. It is important to recognise that points in our model are delocalised (smeared), not in the sense of NCG, but in the way that a quantum reference frame (QRF) is delocalised, or smeared, with respect to its classical counterpart. (See, for example, the work by Giacomini, Castro-Ruiz and Brukner [Nature Communications volume 10, Article number: 494 (2019)].) Importantly, this allows us to derive GURs, incorporating the minimum length and momentum scales, $(\Delta X^i)_{\rm min}$

of the order of the Planck legnth and $(\Delta P_j)_{\rm min}$ of the order of the de Sitter mass, even in the presence of commuting coordinates, i.e.,

$[X^i,X^j] = 0$, $[P_i,P_j] = 0$

[16,18,19]. The underlying geometric picture is illustrated, heuristically, in Figure 1 of ref. [16], for a toy one-dimensional universe.

More specifically, our model represents a nontrivial two-parameter generalisation (including $\hbar$ and $\beta$) of the formalism derived by Giacomini et al. This leads to a nontrivial generalisation of the canonical de Broglie relation (Eq. (38) in [16]), which, however, remains consistent with a generalised Galiliean and/or Poincare invariance. This generalisation consists in transforming space(time) `points' into superpositions thereof, translations into superpositions of translations, and Galilean or Lorentz velocity boosts into superpositions of boosts, etc. (Note, also, that trivial two-parameter generalisations of the form $p = \hbar k \mapsto p = \hbar k, \, p' = \beta k'$, i.e., models that treat quantum spacetime like quantum matter, but with a different quantisation constant, are already ruled out by well known no go theorems. See [19] and references therein for further discussion.) Although it was arrived at independently, and via somewhat different arguments, it is straightforward to verify that the formalism of the smeared space model [16,18,19] reduces, in the limit $\beta \rightarrow \hbar$, to the QRF formalism published in Nature Communications.

Strengths:

"1. Deals with an important problem in theoretical physics."

Weaknesses:

"1. The main claim does not logically follow from an argument as presented."

I cannot agree with this statement. While there is, of course, reasonable doubt over the validity of any scientific model, the results presented in the manuscript are supported by a rigorous mathematical formalism, which was developed logically from its underlying assumptions in a series of published works, [16], [17]. [18] and [19]. (There is also a new work, submitted as an invited contribution to a special issue of Quantum Reports, which further develops the implications of the model for quantum information theory, see [Quantum Rep. 2021, 3(1), 196-227].)

1. Some statements lack rigorous explanation.

I completely agree! However, I stress again that this was by design, not by omission, and that the rigorous explanations and arguments for the results presented in the manuscript are given in [16], [17], [18] and [19]. In total, these works comprise nearly 150 pages of material, so that many compromises had to be made when preparing the talk summary.

"3. Certain similar approaches in the literature are not mentioned."

These have been added, together with a brief note explaining their similarities, and important differences, with the model presented.

"4. Some important issues are not addressed."

I hope that the comments above have now addressed these issues, to the referee's satisfaction.

### Anonymous Report 1 on 2021-2-10 (Invited Report)

• Cite as: Anonymous, Report on arXiv:scipost_202009_00001v2, delivered 2021-02-10, doi: 10.21468/SciPost.Report.2536

### Strengths

1. New interpretation of the quantization process
2. Development of a nonlocal quantum theoretical approach
3. Cosmological applications, related to the interpretation of dark energy.

### Weaknesses

1. More physical applications and tests are necessary to support the main idea.

### Report

The author has improved the initial version of the manuscript, and hence I think that teh present version is suitable for publication in SciPost.

• validity: good
• significance: good
• originality: high
• clarity: top
• formatting: excellent
• grammar: perfect


text:
# Write an algebraic expression for: 6 more than a number c.

Write an algebraic expression for: 6 more than a number c.

• Questions are typically answered in as fast as 30 minutes

### Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Mitchel Aguirre

more than =+
$$\Rightarrow6+c$$
Result:
6+c


text:
Department of

# Mathematics

Seminar Calendar
for events the day of Thursday, February 10, 2005.

.
events for the
events containing

Questions regarding events or the calendar should be directed to Tori Corkery.
     January 2005          February 2005            March 2005
Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
1          1  2  3  4  5          1  2  3  4  5
2  3  4  5  6  7  8    6  7  8  9 10 11 12    6  7  8  9 10 11 12
9 10 11 12 13 14 15   13 14 15 16 17 18 19   13 14 15 16 17 18 19
16 17 18 19 20 21 22   20 21 22 23 24 25 26   20 21 22 23 24 25 26
23 24 25 26 27 28 29   27 28                  27 28 29 30 31
30 31

Thursday, February 10, 2005

1:00 pm in 241 Altgeld Hall,Thursday, February 10, 2005

#### Diophantine Approximation with mild divisibility constraints

###### Emre Alkan (UIUC)

Abstract: I will present a survey on the history of Diophantine approximation problems using special subsets of integers and also talk about recent work on this jointly with A. Zaharescu and G. Harman

1:00 pm in Altgeld Hall 347,Thursday, February 10, 2005

#### General Graph Braid Groups and the Two Strand Case

###### Lucas Sabalka (UIUC)

Abstract: If $\Gamma$ is any finite graph, then the \emph{unlabelled configuration space of $n$ points on $\Gamma$} is the space of $n$-element subsets of $\Gamma$ (without repetition). The \emph{braid group of $\Gamma$ on $n$ strands} is the fundamental group of this space. Let $\Gamma$ be a planar graph. We prove that the two strand braid group on $\Gamma$ has a presentation in which every relator is a commutator "given by" the boundaries of two disjoint regions in $\Gamma$, and any two disjoint regions give rise to a commutator relator.

2:00 pm in 345 Altgeld Hall,Thursday, February 10, 2005

#### Isotopies of Lagrangian spheres

###### Richard Hind (Notre Dame)

Abstract: Lagrangian spheres arise naturally in symplectic manifolds as vanishing cycles of Lefschetz fibrations. We try to classify such spheres up to Hamiltonian diffeomorphism in some simple symplectic 4-manifolds. Sometimes, like in S^2 x S^2, there is a unique Lagrangian sphere, but other manifolds contain nonequivalent Lagrangian spheres which can be homotopic or even smoothly isotopic.

2:00 pm in 241 Altgeld Hall,Thursday, February 10, 2005

#### Henn's calculation of the cohomology of S_2 at p=3

###### Charles Rezk (UIUC Math)

2:00 pm in Altgeld Hall 243,Thursday, February 10, 2005

#### Optimal transportation and the quasiconformal Jacobian problem

###### Leonid Kovalev (Washington University, St. Louis)

Abstract: The quasiconformal Jacobian problem, which originated in a 1990 paper of David and Semmes, asks for an analytic description of the Jacobian determinants of quasiconformal mappings. A part of this difficult problem is to characterize the singular sets of such Jacobians. We prove that every set of Hausdorff dimension less than 1 is a singular set for some quasiconformal mapping. The proof involves some ideas from the theory of optimal transportation, such as the Wasserstein metric. This is joint work with Diego Maldonado.

3:00 pm in 347 Altgeld Hall,Thursday, February 10, 2005

#### Elimination of Imaginaries in Algebraically Closed Valued Fields

###### David Lippel (Notre Dame)

Abstract: This talk will provide an overview of the work done to describe the models of ACVF.

3:00 pm in 243 Altgeld Hall,Thursday, February 10, 2005

#### Tight Closure and Its Applications (II)

###### Jinjia Li   [email] (UIUC Math)

Abstract: We will discuss the colon capturing phenomena of tight closure and use it to prove that direct summand of a regular ring is Cohen-Macauly in characteristic p.

4:00 pm in 245 Altgeld Hall,Thursday, February 10, 2005

#### Representations of Affine Lie algebras

###### Vyjayanthi Chari (University of California at Riverside)

Abstract: In this talk, we first discuss briefly the definition of affine Lie algebras and their quantum analogs, and survey the various kinds of representation theory of these algebras. We then discuss a surprising connection between these representations discovered in joint work with S. Loktev, in particular an isomorphism between the Weyl modules and the Demazure modules. We also show that the results solve a substantial case of some conjectures of Feigin and Loktev on the fusion product of modules. Host: Bill Haboush


text:
# Efficient Annotation Cookbook for Image Classification

Based on the paper “Towards Good Practices for Efficiently Annotating Large-Scale Image Classification Datasets,” accepted by CVPR21 as Oral presentation.

Yuan-Hong Liao https://andrewliao11.github.io (University of Toronto, Vector Institute) , Amlan Kar https://amlankar.github.io (University of Toronto, Vector Institute, Nvidia) , Sanja Fidler http://www.cs.utoronto.ca/~fidler/ (University of Toronto, Vector Institute, Nvidia)
04-06-2021

Data is the engine of modern computer vision, which necessitates collecting large-scale datasets. This is expensive, and guaranteeing the quality of the labels is a major challenge. We investigate efficient annotation strategies for collecting multi-class classification labels for a large collection of images.

In this paper, we show that incorporating machine learner to online labeling coupled with several good design choices, we can increase the annotation efficiency significantly. We end up being 2.7x efficient (w/ 63% less annotations) w.r.t prior work and 6.7x efficient (w/ 85% less annotations) w.r.t. manual annotations.

# Laborious Annotation Process

A common approach used in practice is to query humans to get a fixed number of labels per datum and aggregate them presumably because of its simplicity and reliability. This can be prohibitively expensive and inefficient in human resource utilization for large datasets, as it assumes equal effort needed per datum.

# Background and Testbed

### How to aggregate labels: DS model

The Dawid-Skene model views the annotation process as jointly inferring true labels and worker skills. The joint probability of true labels $$\mathcal{Y}$$, annotations $$\mathcal{Z}$$, and worker skills $$\mathcal{W}$$ is defined as the product of the prior of true labels and worker skills and the posterior of the annotations. We first define the notations, $$\mathcal{I_j}$$: the images annotated by the $$j^{th}$$ worker, $$\mathcal{W_i}$$: the workers that annotate the $$i^{th}$$ image, $$N$$: the number of images, $$M$$: the number of workers. Now, we can define the joint probability as $$P(\mathcal{Y}, \mathcal{Z}, \mathcal{W}) = \prod_{i \in [N]} p(y_i) \prod_{j \in [M]} p(w_j) \prod_{i, j \in \mathcal{W_i}} p(z_{ij} | y_i, w_j)$$. In practice, inference is performed using expectation maximization, where parameters for images or workers are optimized at a time, \begin{align} \bar{y_i} &= \arg \max p(y_i) \prod_{j \in \mathcal{W_i}} p(z_{ij} | y_i, \bar{w_j}) \\ \bar{w_j} &= \arg \max p(w_j) \prod_{i \in \mathcal{I_j}} p(z_{ij} | \bar{y_i}, w_j) \\ \end{align}

Prior work moves to an online setting and improves DS model by using machine learning model predictions as image prior $$p(y_i)$$, opening up the window of incorporating machine learner and DS model. However, they only perform experiments in a small-scale setting. We ask ourselves: How many annotations can we possibly reduce to annotate a large scale image classification dataset, such as ImageNet?

### Testbed: ImageNet100 Sandbox

Evaluating and ablating multi-class label annotation efficiency at scale requires large datasets with diverse and relatively clean labels. We construct multiple subsets of the ImageNet dataset for our experiments. The following table shows the details of the different subsets in ImageNet100 Sandbox.

Dataset #Images #Classes Worker Acc. Fine-Grained
Commodity 20140 16 0.76
Vertebrate 23220 18 0.72
Insect + Fungus 16770 13 0.65 V
Dog 22704 19 0.43 V
ImageNet100 125689 100 0.7 V

Prior work simulates workers as confusion matrices. Class confusion was modeled with symmetric uniform noise, which can result in over-optimistic performance estimates. Human annotators exhibit asymmetric and structured confusion i.e., classes get confused with each other differently. In Fig.1, we compare the number of annotations per image in simulation using uniform label noise vs. structured label noise that we crowdsource. We see significant gaps between the two. This arises particularly when using learnt models in the loop due to sensitivity to noisy labels coming from structured confusion in the workers. Therefore, we use simulated workers with structured noise in ImageNet100 Sandbox.

We simulate the process of annotating ImageNet100 and perform various ablation on the system, spanning from models, workers, and data itself. We end up being 2.7x efficient (w/ 63% less annotations) w.r.t prior work and 6.7x efficient (w/ 85% less annotations) w.r.t. manual annotations .

In the following, we show how each component affects the final efficiency:

# Matters of Model Learning

### Online-Labeling is a Semi-Supervised Problem

During online-labeling, the goal is to infer true labels for all images in the dataset, making model learning akin to transductive learning , where the test set is observed and can be used for learning. Thus, it is reasonable to expect efficiency gains if the dataset’s underlying structure is exploited by putting the unlabeled data to work, using semi-supervised learning. In Fig.2 we perform Peudolabel and Mixmatch in online-labeling.

With recent advances in self-supervised learning, it is feasible to learn strong image feature extractors that rival supervised learning, using pretext tasks without any label. This allows learning in-domain feature extractors for annotation tasks, as opposed to using features pre-trained on ImageNet We compare the efficacy of using BYOL , SimCLR , MoCo , relative location prediction and rotation prediction learnt on full ImageNet raw images as the feature extractor. In Fig.3, we show that improvements in self-supervised learning consistently increase the efficiency for datasets with both fine and coarse-grained labels, with up to 5x improvement at similar accuracy compared to not using a machine learning model in the loop (online DS).

### Clean Validation set Matters in Accuracy and Calibration Error

The validation set plays an important role in online-labeling. It is used to perform model selection and model calibration. Prior work uses a modified cross-validation approach to generate model likelihoods. We find that this could underperform when the estimated labels are noisy, which pollutes the validation set and makes calibration challenging. Instead, we propose to use the clean prototype images as the validation set. In our paper, we use 10 prototype images per class. We perform 3-fold cross-validation in this experiment. When not using cross-validation, we either randomly select a subset as the validation set or use the (clean) prototype images as the validation set. In Fig.4, we ablate the importance of having a clean validation set and performing cross-validation in terms of accuracy and expected calibration error on the most challenging subset, the Dog subset.

# Matters of Workers

### It’s worth using Gold Standard Question sometimes

In reality, the requestor can ask gold standard questions or apply prior knowledge to design the prior $$p(w_j)$$. We explore two possible prior A) Considering class identity and B) Considering worker identity. To consider the class identity, the task designer needs to have a clear thought of which classes are more difficult than others. To consider the worker’s identity, the task designer needs to query several gold standard questions from each worker. In Fig.5, we find that considering worker identity is especially useful for fine-grained datasets, such as Dog subset, improving 15 accuracy points in Dog, while in Commodity, the improvement is marginal.

### Tradeoff between number of workers and time cost

One way to speed up the dataset annotation process is to hire more workers at the same time. However, under a fixed number of total annotations, having more workers means having fewer observations for each worker, resulting in poor worker skill estimation. We explore this tradeoff by manipulating the number of workers involved in Fig.6. The gap is surprisingly high in the fine-grained dataset (14% accuracy points difference in Dog subset), while there is nearly no tradeoff in the coarse-grained dataset, such as Commodity subset.

# Matters of Data

### Pre-filtering Dataset to some extent

We have assumed that the requestor performs perfect filtering before annotation, i.e., all the images to be annotated belong to the target classes, which does not always hold. We add an additional “None of These” class and ablate annotation efficiency in the presence of unfiltered images. We include different numbers of images from other classes and measure the mean precision with the number of annotations of the target classes. In Fig.7, we see that even with 100% more images from irrelevant classes, we can retain comparable efficiency on a fine-grained dataset.

### Early Stopping Saves you some Money

A clear criterion to stop annotation is when the unfinished set of images (images with estimated risk greater than a threshold) is empty. However, we observe that the annotation accuracy usually saturates and then grows slowly because of a small number of data points that are heavily confused by the pool of workers used. Therefore we suggest that the requestor 1) stop annotation at this time and separately annotate the small number of unfinished samples, possibly with expert annotators, and 2) set a maximum number of annotations per image. In Fig.8, we show this is sufficient. We set the maximum annotations of each example to be 3 and early stop when the size of the finished set does not increase from its maximum value for 5 consecutive steps.

# Analysis

### Greedy Task Assignment w/ estimated Worker Skills

There are certain particularly hard classes, with only a few workers having enough expertise to annotate them correctly. We ask whether the learnt skills can be used to assign tasks better. Prior work on (optimal) task assignment tackle crowdsourcing settings with vastly different simplifying assumptions , and designing a new task assignment scheme is out of the scope of this paper. We verify if the learnt worker skills help with task assignment by proposing a simple greedy algorithm with a cap on the maximum number of annotations per worker. Fig.9 shows that the above-mentioned task assignment scheme consistently improves over the random assignment, implying that the learnt skills are both representative and good enough to bring some improvements.

Fig.10 visualizes the worker’s importance versus the number of annotations per worker. Since there is no exploration in the proposed task assignment, the workers are separated into two groups: overwork (top right) and underwork (bottom left).

### How does the Annotation Process look like

To further see how the annotation process is like, we sample 100 data points on the Commodity subset and visualize the risk change and accuracy change through time. In the top row of Fig.11, we show the risk of the aggregated probability $$p_i$$ and the risk of the machine learner’s probability $$p_i^{\text{ML}}$$. Each column represents one data point. We can see from the aggregated probability (top-left) that the risk gradually decreases as time goes by. Comparing the risk of $$p_i$$ and $$p_i^{\text{ML}}$$, we find that the annotation process can be separated into two stages. In the first stage, the machine learner dominates the progress, while in the second stage, the worker annotations dominate it.

In the bottom row of Fig.11, we show the correctness of each example of $$p_i$$ and $$p_i^{\text{ML}}$$. This coincides with the trend mentioned above. The reason that the machine learner saturates quickly might be due to the lack of expressivity. In our work, our machine learner only fine-tunes the last few layers.

# Discussion

We presented improved online-labeling methods for large multi-class datasets. In a realistically simulated experiment with 125k images and 100 labels from ImageNet, we observe a 2.7x reduction in annotations required w.r.t. prior work to achieve 80% top-1 label accuracy. Our framework goes on to achieve 87.4% top-1 accuracy at 0.98 labels per image. Along with our improvements, we leave open questions for future research. 1) Our simulation is not perfect and does not consider individual image difficulty, instead only modeling class confusion. 2) How does one accelerate labeling beyond semantic classes, such as classifying the viewing angle of a car? 3) ImageNet has a clear label hierarchy, which can be utilized to achieve orthogonal gains in the worker skill estimation 4) Going beyond classification is possible with the proposed model by appropriately modeling annotation likelihood as demonstrated in . However, accelerating these with learning in the loop requires specific attention to detail per task, which is an exciting avenue for future work. 5) Finally, we discussed annotation at scale, where improvements in learning help significantly. How can these be translated to small datasets?

## Acknowledgments

This work was supported by ERA, NSERC, and DARPA XAI. SF acknowledges the Canada CIFAR AI Chair award at the Vector Institute.

This webpage is based on Distill Template generated from here

## Paper

This paper is accepted to CVPR2021 as Oral presentations.

@misc{liao2021good,
title={Towards Good Practices for Efficiently Annotating Large-Scale Image Classification Datasets},
author={Yuan-Hong Liao and Amlan Kar and Sanja Fidler},
year={2021},
eprint={2104.12690},
archivePrefix={arXiv},
primaryClass={cs.CV}
}
Branson, Steve, Grant Van Horn, and Pietro Perona. 2017. “Lean Crowdsourcing: Combining Humans and Machines in an Online System.” In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR).
Chen, Ting, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. 2020. “A Simple Framework for Contrastive Learning of Visual Representations.” arXiv Preprint arXiv:2002.05709.
Chen, Xi, Qihang Lin, and Dengyong Zhou. 2015. “Statistical Decision Making for Optimal Budget Allocation in Crowd Labeling.” The Journal of Machine Learning Research 16 (1): 1–46.
Dawid, Alexander Philip, and Allan M Skene. 1979. “Maximum Likelihood Estimation of Observer Error-Rates Using the EM Algorithm.” Journal of the Royal Statistical Society: Series C (Applied Statistics) 28 (1): 20–28.
Doersch, Carl, Abhinav Gupta, and Alexei A Efros. 2015. “Unsupervised Visual Representation Learning by Context Prediction.” In Proceedings of the IEEE International Conference on Computer Vision, 1422–30.
Gidaris, Spyros, Praveer Singh, and Nikos Komodakis. 2018. “Unsupervised Representation Learning by Predicting Image Rotations.” arXiv Preprint arXiv:1803.07728.
Grill, Jean-Bastien, Florian Strub, Florent Altché, Corentin Tallec, Pierre H Richemond, Elena Buchatskaya, Carl Doersch, et al. 2020. “Bootstrap Your Own Latent: A New Approach to Self-Supervised Learning.” arXiv Preprint arXiv:2006.07733.
Guo, Chuan, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. 2017. “On Calibration of Modern Neural Networks.” arXiv Preprint arXiv:1706.04599.
He, Kaiming, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. 2019. “Momentum Contrast for Unsupervised Visual Representation Learning.” arXiv Preprint arXiv:1911.05722.
Ho, Chien-Ju, Shahin Jabbari, and Jennifer Wortman Vaughan. 2013. “Adaptive Task Assignment for Crowdsourced Classification.” In International Conference on Machine Learning, 534–42.
Hua, Gang, Chengjiang Long, Ming Yang, and Yan Gao. 2013. “Collaborative Active Learning of a Kernel Machine Ensemble for Recognition.” In Proceedings of the IEEE International Conference on Computer Vision, 1209–16.
Joachims, Thorsten. 1999. “Transductive Inference for Text Classification Using Support Vector Machines.” In ICML, 200–209.
Kaur, Parneet, Karan Sikka, Weijun Wang, Serge Belongie, and Ajay Divakaran. 2019. “Foodx-251: A Dataset for Fine-Grained Food Classification.” arXiv Preprint arXiv:1907.06167.
Lin, Tsung-Yi, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick. 2014. “Microsoft Coco: Common Objects in Context.” In European Conference on Computer Vision, 740–55. Springer.
Long, Chengjiang, and Gang Hua. 2015. “Multi-Class Multi-Annotator Active Learning with Robust Gaussian Process for Visual Recognition.” In Proceedings of the IEEE International Conference on Computer Vision, 2839–47.
Russakovsky, Olga, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, et al. 2015. “ImageNet Large Scale Visual Recognition Challenge.” http://arxiv.org/abs/1409.0575.
Van Horn, Grant, Steve Branson, Scott Loarie, Serge Belongie, and Pietro Perona. 2018. “Lean Multiclass Crowdsourcing.” In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2714–23.

### Corrections

If you see mistakes or want to suggest changes, please create an issue on the source repository.


text:
# How to Retrain Inception's Final Layer for New Categories

Modern object recognition models have millions of parameters and can take weeks to fully train. Transfer learning is a technique that shortcuts a lot of this work by taking a fully-trained model for a set of categories like ImageNet, and retrains from the existing weights for new classes. In this example we'll be retraining the final layer from scratch, while leaving all the others untouched. For more information on the approach you can see this paper on Decaf.

Though it's not as good as a full training run, this is surprisingly effective for many applications, and can be run in as little as thirty minutes on a laptop, without requiring a GPU. This tutorial will show you how to run the example script on your own images, and will explain some of the options you have to help control the training process.

## Training on Flowers

Before you start any training, you'll need a set of images to teach the network about the new classes you want to recognize. There's a later section that explains how to prepare your own images, but to make it easy we've created an archive of creative-commons licensed flower photos to use initially. To get the set of flower photos, run these commands:

cd ~
tar xzf flower_photos.tgz

Once you have the images, you can build the retrainer like this, from the root of your TensorFlow source directory:

bazel build tensorflow/examples/image_retraining:retrain

If you have a machine which supports the AVX instruction set (common in x86 CPUs produced in the last few years) you can improve the running speed of the retraining by building for that architecture, like this (after choosing appropriate options in configure):

bazel build --config opt tensorflow/examples/image_retraining:retrain

The retrainer can then be run like this:

bazel-bin/tensorflow/examples/image_retraining/retrain --image_dir ~/flower_photos

This script loads the pre-trained Inception v3 model, removes the old top layer, and trains a new one on the flower photos you've downloaded. None of the flower species were in the original ImageNet classes the full network was trained on. The magic of transfer learning is that lower layers that have been trained to distinguish between some objects can be reused for many recognition tasks without any alteration.

## Bottlenecks

The script can take thirty minutes or more to complete, depending on the speed of your machine. The first phase analyzes all the images on disk and calculates the bottleneck values for each of them. 'Bottleneck' is an informal term we often use for the layer just before the final output layer that actually does the classification. This penultimate layer has been trained to output a set of values that's good enough for the classifier to use to distinguish between all the classes it's been asked to recognize. That means it has to be a meaningful and compact summary of the images, since it has to contain enough information for the classifier to make a good choice in a very small set of values. The reason our final layer retraining can work on new classes is that it turns out the kind of information needed to distinguish between all the 1,000 classes in ImageNet is often also useful to distinguish between new kinds of objects.

Because every image is reused multiple times during training and calculating each bottleneck takes a significant amount of time, it speeds things up to cache these bottleneck values on disk so they don't have to be repeatedly recalculated. By default they're stored in the /tmp/bottleneck directory, and if you rerun the script they'll be reused so you don't have to wait for this part again.

## Training

Once the bottlenecks are complete, the actual training of the top layer of the network begins. You'll see a series of step outputs, each one showing training accuracy, validation accuracy, and the cross entropy. The training accuracy shows what percent of the images used in the current training batch were labeled with the correct class. The validation accuracy is the precision on a randomly-selected group of images from a different set. The key difference is that the training accuracy is based on images that the network has been able to learn from so the network can overfit to the noise in the training data. A true measure of the performance of the network is to measure its performance on a data set not contained in the training data -- this is measured by the validation accuracy. If the train accuracy is high but the validation accuracy remains low, that means the network is overfitting and memorizing particular features in the training images that aren't helpful more generally. Cross entropy is a loss function which gives a glimpse into how well the learning process is progressing. The training's objective is to make the loss as small as possible, so you can tell if the learning is working by keeping an eye on whether the loss keeps trending downwards, ignoring the short-term noise.

By default this script will run 4,000 training steps. Each step chooses ten images at random from the training set, finds their bottlenecks from the cache, and feeds them into the final layer to get predictions. Those predictions are then compared against the actual labels to update the final layer's weights through the back-propagation process. As the process continues you should see the reported accuracy improve, and after all the steps are done, a final test accuracy evaluation is run on a set of images kept separate from the training and validation pictures. This test evaluation is the best estimate of how the trained model will perform on the classification task. You should see an accuracy value of between 90% and 95%, though the exact value will vary from run to run since there's randomness in the training process. This number is based on the percent of the images in the test set that are given the correct label after the model is fully trained.

## Visualizing the Retraining with TensorBoard

The script includes TensorBoard summaries that make it easier to understand, debug, and optimize the retraining. For example, you can visualize the graph and statistics, such as how the weights or accuracy varied during training.

To launch TensorBoard, run this command during or after retraining:

tensorboard --logdir /tmp/retrain_logs

Once TensorBoard is running, navigate your web browser to localhost:6006 to view the TensorBoard.

The script will log TensorBoard summaries to /tmp/retrain_logs by default. You can change the directory with the --summaries_dir flag.

The TensorBoard README has a lot more information on TensorBoard usage, including tips & tricks, and debugging information.

## Using the Retrained Model

The script will write out a version of the Inception v3 network with a final layer retrained to your categories to /tmp/output_graph.pb, and a text file containing the labels to /tmp/output_labels.txt. These are both in a format that the C++ and Python image classification examples can read in, so you can start using your new model immediately. Since you've replaced the top layer, you will need to specify the new name in the script, for example with the flag --output_layer=final_result if you're using label_image.

Here's an example of how to build and run the label_image example with your retrained graphs:

bazel build tensorflow/examples/label_image:label_image && \
bazel-bin/tensorflow/examples/label_image/label_image \
--graph=/tmp/output_graph.pb --labels=/tmp/output_labels.txt \
--output_layer=final_result \
--image=\$HOME/flower_photos/daisy/21652746_cc379e0eea_m.jpg

You should see a list of flower labels, in most cases with daisy on top (though each retrained model may be slightly different). You can replace the --image parameter with your own images to try those out, and use the C++ code as a template to integrate with your own applications.

If you'd like to use the retrained model in a Python program this example from @eldor4do shows what you'll need to do.

## Training on Your Own Categories

If you've managed to get the script working on the flower example images, you can start looking at teaching it to recognize categories you care about instead. In theory all you'll need to do is point it at a set of sub-folders, each named after one of your categories and containing only images from that category. If you do that and pass the root folder of the subdirectories as the argument to --image_dir, the script should train just like it did for the flowers.

Here's what the folder structure of the flowers archive looks like, to give you and example of the kind of layout the script is looking for:

In practice it may take some work to get the accuracy you want. I'll try to guide you through some of the common problems you might encounter below.

## Creating a Set of Training Images

The first place to start is by looking at the images you've gathered, since the most common issues we see with training come from the data that's being fed in.

For training to work well, you should gather at least a hundred photos of each kind of object you want to recognize. The more you can gather, the better the accuracy of your trained model is likely to be. You also need to make sure that the photos are a good representation of what your application will actually encounter. For example, if you take all your photos indoors against a blank wall and your users are trying to recognize objects outdoors, you probably won't see good results when you deploy.

Another pitfall to avoid is that the learning process will pick up on anything that the labeled images have in common with each other, and if you're not careful that might be something that's not useful. For example if you photograph one kind of object in a blue room, and another in a green one, then the model will end up basing its prediction on the background color, not the features of the object you actually care about. To avoid this, try to take pictures in as wide a variety of situations as you can, at different times, and with different devices. If you want to know more about this problem, you can read about the classic (and possibly apocryphal) tank recognition problem.

You may also want to think about the categories you use. It might be worth splitting big categories that cover a lot of different physical forms into smaller ones that are more visually distinct. For example instead of 'vehicle' you might use 'car', 'motorbike', and 'truck'. It's also worth thinking about whether you have a 'closed world' or an 'open world' problem. In a closed world, the only things you'll ever be asked to categorize are the classes of object you know about. This might apply to a plant recognition app where you know the user is likely to be taking a picture of a flower, so all you have to do is decide which species. By contrast a roaming robot might see all sorts of different things through its camera as it wanders around the world. In that case you'd want the classifier to report if it wasn't sure what it was seeing. This can be hard to do well, but often if you collect a large number of typical 'background' photos with no relevant objects in them, you can add them to an extra 'unknown' class in your image folders.

It's also worth checking to make sure that all of your images are labeled correctly. Often user-generated tags are unreliable for our purposes, for example using #daisy for pictures of a person named Daisy. If you go through your images and weed out any mistakes it can do wonders for your overall accuracy.

## Training Steps

If you're happy with your images, you can take a look at improving your results by altering the details of the learning process. The simplest one to try is --how_many_training_steps. This defaults to 4,000, but if you increase it to 8,000 it will train for twice as long. The rate of improvement in the accuracy slows the longer you train for, and at some point will stop altogether, but you can experiment to see when you hit that limit for your model.

## Distortions

A common way of improving the results of image training is by deforming, cropping, or brightening the training inputs in random ways. This has the advantage of expanding the effective size of the training data thanks to all the possible variations of the same images, and tends to help the network learn to cope with all the distortions that will occur in real-life uses of the classifier. The biggest disadvantage of enabling these distortions in our script is that the bottleneck caching is no longer useful, since input images are never reused exactly. This means the training process takes a lot longer, so I recommend trying this as a way of fine-tuning your model once you've got one that you're reasonably happy with.

You enable these distortions by passing --random_crop, --random_scale and --random_brightness to the script. These are all percentage values that control how much of each of the distortions is applied to each image. It's reasonable to start with values of 5 or 10 for each of them and then experiment to see which of them help with your application. --flip_left_right will randomly mirror half of the images horizontally, which makes sense as long as those inversions are likely to happen in your application. For example it wouldn't be a good idea if you were trying to recognize letters, since flipping them destroys their meaning.

## Hyper-parameters

There are several other parameters you can try adjusting to see if they help your results. The --learning_rate controls the magnitude of the updates to the final layer during training. Intuitively if this is smaller then the learning will take longer, but it can end up helping the overall precision. That's not always the case though, so you need to experiment carefully to see what works for your case. The --train_batch_size controls how many images are examined during one training step, and because the learning rate is applied per batch you'll need to reduce it if you have larger batches to get the same overall effect.

## Training, Validation, and Testing Sets

One of the things the script does under the hood when you point it at a folder of images is divide them up into three different sets. The largest is usually the training set, which are all the images fed into the network during training, with the results used to update the model's weights. You might wonder why we don't use all the images for training? A big potential problem when we're doing machine learning is that our model may just be memorizing irrelevant details of the training images to come up with the right answers. For example, you could imagine a network remembering a pattern in the background of each photo it was shown, and using that to match labels with objects. It could produce good results on all the images it's seen before during training, but then fail on new images because it's not learned general characteristics of the objects, just memorized unimportant details of the training images.

This problem is known as overfitting, and to avoid it we keep some of our data out of the training process, so that the model can't memorize them. We then use those images as a check to make sure that overfitting isn't occurring, since if we see good accuracy on them it's a good sign the network isn't overfitting. The usual split is to put 80% of the images into the main training set, keep 10% aside to run as validation frequently during training, and then have a final 10% that are used less often as a testing set to predict the real-world performance of the classifier. These ratios can be controlled using the --testing_percentage and --validation_percentage flags. In general you should be able to leave these values at their defaults, since you won't usually find any advantage to training to adjusting them.

Note that the script uses the image filenames (rather than a completely random function) to divide the images among the training, validation, and test sets. This is done to ensure that images don't get moved between training and testing sets on different runs, since that could be a problem if images that had been used for training a model were subsequently used in a validation set.

You might notice that the validation accuracy fluctuates among iterations. Much of this fluctuation arises from the fact that a random subset of the validation set is chosen for each validation accuracy measurement. The fluctuations can be greatly reduced, at the cost of some increase in training time, by choosing --validation_batch_size=-1, which uses the entire validation set for each accuracy computation.

Once training is complete, you may find it insightful to examine misclassified images in the test set. This can be done by adding the flag --print_misclassified_test_images. This may help you get a feeling for which types of images were most confusing for the model, and which categories were most difficult to distinguish. For instance, you might discover that some subtype of a particular category, or some unusual photo angle, is particularly difficult to identify, which may encourage you to add more training images of that subtype. Oftentimes, examining misclassified images can also point to errors in the input data set, such as mislabeled, low-quality, or ambiguous images. However, one should generally avoid point-fixing individual errors in the test set, since they are likely to merely reflect more general problems in the (much larger) training set.