text:
# Calculating Induced EMF in Moving Wire

1. Aug 16, 2013

### JSGandora

In the classic problem of the induced EMF in a moving conductor (as in the picture above), the calculation for the induced EMF is as follows

$E=\frac{d\Phi_B}{dt}=\frac{d(BA)}{dt}=\frac{Bd(A)}{dt}=\frac{Bd(Lx)}{dt}=\frac{BLdx}{dt}=BLv.$

The derivation assumes that the magnetic field B is constant throughout the entire time the flux is changing. I am confused because it does not seem like the magnetic field is constant because while there is an induced EMF in the wire, there must also be self induction that occurs (since the induced current in the coil also produces a magnetic field) thereby changing the already present magnetic field. So in fact the magnetic field is a function of time inside the coil of wire. Is the self induction so insignificant that the calculation can assume that the magnetic field does not change?

2. Aug 16, 2013

### cabraham

If the rod and loop have a high resistance value, greater than inductive reactance, then self inductance need not be considered. But if both the loop and rod have a low resistance value, so that XL is greater than or close in value to R, then we cannot ignore self inductance.

You're thinking the right way. For a more detailed explanation, I would review an electric machines text. Here are my references I used in college/graduate school.

Leander Matsch - "Electromagnetic & Electromechanical Machines"

Fitzgerald, Kingsley, Umans - "Electric Machinery"

Dr. Umans was my professor in spring 2010 when I took his power and machines course. He teaches at MIT, and he was lecturing at Case in Cleveland where I am a Ph.D. student. He's very good.

Incidentally that problem appeared on my Ph.D. qualifier written exam, and I gave the same answer you did. I computed the induction due to the external field, then computed self inductance. I got it right and passed the exam. There were many other problems as well.

Claude

3. Aug 16, 2013

### technician

Can you make clear what you mean by XL and R
What is the value of the induced emf if it is not Blv?.....you do realise that this is the standard text book answer....is it wrong?

4. Aug 17, 2013

### cabraham

XL = Lω. The value of the "induced emf" is often taken as "Blv", which is the induced emf due to external flux. The general approach is to take the distributed resistance and inductance of the loop and lump them into R & L. The induced emf equals the open circuit voltage, Voc, since the open circuit condition has very little current, hence self inductance is negligible.

When loaded (loop closed), the equivalent circuit is a voltage source of Voc, plus an inductive reactance XL, plus resistance R. Current I is computed using circuit theory. The impedance Z is just R + jXL, or its magnitude is |Z| = √R2 + XL2. |I| =Voc/|Z|.

As far as "Blv" being the "standard text book answer" goes, not in the text books I referenced is that the answer. Any machines book will affirm my answer. I believe we spoke on this subject recently. Are you familiar with ac circuit theory? Do you know reactance as well as resistance. In dc theory, V = I*R, but with ac we must use V = I*Z, where Z = R + jX. Did I help.

Claude

Last edited: Aug 17, 2013
5. Aug 18, 2013

### Philip Wood

CAB: I agree with the general thrust of your answer, but don't like your use of $X_L = \omega L$, because this is only applicable when a sinusoidal current is flowing. In the case of an arbitrary movement of the rod on the rails we have to use the more general term $E_{back} = - \frac{d\widetilde{\Phi}}{dt}$ in which $\widetilde{\Phi}$ is the flux due to the induced current, if any. This emf acts in the opposite direction to BLv (in which B is the externally applied field), and doesn't act at all if the circuit is open.

[Original post corrected.]

Last edited: Aug 18, 2013
6. Aug 18, 2013

### technician

The value of the "induced emf" is often taken as "Blv",

Yhe induced emf is always taken to be Blv. If the induced emf = Blv and an induced current arises (because of a complete circuit of resistance R) then the current is Blv/R.
The magnetic field around the moving wire resulting from the induced current does not change the value of the original field. The moving wire with its associated field is moving through the applied field. There is now a Force acting on the wire and this should be apparent on some diagrams I am attaching.
The equations that have been given in an earlier post relate to AC circuit theory, not this aspect of physics.....ω has no meaning in this problem.

#### Attached Files:

File size:
25.2 KB
Views:
123
• ###### resultant.jpg
File size:
18.4 KB
Views:
126
7. Aug 18, 2013

### Philip Wood

Technician. You're right about the meaningless of $\omega$ of course, and I'd now argue that even L is pretty meaningless, because the circuit's shape keeps changing, but I don't agree that the induced emf is simply BLv, when there is a current flowing - if by B you mean the externally applied field.

8. Aug 18, 2013

### technician

First of all, lets be clear...when I say 'I' I mean my references...text books, past exam papers and answers etc.....I am not inventing Faradays laws!!!!
The (every !!!) text book answer is that E = Blv and yes...B is the externally applied field. If you have some (text book or other) reference that this is not correct then we all need to know and we can disregard the text books that state it to be the case.
I think I am correct in saying that the wire does not cut through the lines of force created by the induced current created by the induced emf given by E = Blv.... so this has no effect on E.?????
We cannot progress in this thread without this being cleared up.

Last edited: Aug 18, 2013
9. Aug 19, 2013

### vanhees71

In this simple case you can (with overwhelming accuracy) neglect self-inductance and just use Farday's Law in integral form, which reads (note that this is not accurate in many textbooks, but it's pretty well described in Wikipedia)
$$\mathcal{E}=\int_{\partial A} \mathrm{d} \vec{x} \cdot [\vec{E}+\vec{v} \times \vec{B}]=-\frac{\mathrm{d}}{\mathrm{d} t} \int_{A} \mathrm{d} \vec{F} \cdot \vec{B}.$$
Let's take the plane of the circuit as the $xy$ plane of a Cartesian coordinate system with the moving rod in $y$ direction.

Let's take the area as given by the circuit and let's integrate counter clockwise. Then the area element is $\mathrm{d} \vec{F} =\vec{e}_z \mathrm{d} x \mathrm{d} y$. Then tha appropriate magnetic flux thus is
$$\Phi_A=\int_{A} \mathrm{d} \vec{F} \cdot \vec{B}=-B L (x_0+v t).$$
Here $L$ is the length of the rod and $(x_0+v t)$ the momentary length of the other wires perpendicular to it.

The left-hand side of the equation, i.e., the line integral, only gives a net contribution for integrating along the pieces of the circuit along the $y$ axis. For the piece at rest you have $\vec{v}(\vec{x})=0$ and the integral over the electric field across the resistor gives $R I$ (with the sign according to the direction of the current given in the figure).

For the moving piece, if assumed as an ideal conductor there must be no net electric field, i.e, you have $\vec{E}+\vec{v} \times \vec{B}=0$. Note that there is an electric field along the wire such that
$$\vec{E}=-\vec{v} \times \vec{B}=-v \vec{e}_x \times (-B \vec{e}_z)=-v B \vec{e}_y$$
such that there is no net electric field in the rest frame of the moving rod!

$$\mathcal{E}=R I=-\frac{\mathrm{d} \Phi_A}{\mathrm{d} t}=B L v.$$
Note that this calculation only analyzes the stationary state, i.e., the rod should have moved with constant velocity through the homogeneous magnetic field for some time before such that initial-state ("transient") effects can be negelected.

10. Aug 19, 2013

### cabraham

But any waveform can be resolved into a sum of sine and cosine functions. Even a non-periodic waveform has a Fourier transform. This seems to annoy everybody. Induction motors are a prime example of induction taking place in a loop with very low R value.

If induced emf was constant independent of load such as self inductance, then the power would increase w/o limit as R decreases. We already know that as the rotor R value decreases, power in heating said rotor increases until R equals XL. Then as R drops below XL, rotor heat goes DOWN. This is due to self inductance.

Thus for ac domain, I = Voc/(√R2 + XL2). For R << XL, I = Voc/R.

In your example, if open circuit voltage is "Blv", with the loop resistance of R and inductance L, we cannot ignore L unless we know it is << RT, where T is pulse width. We discussed a transient case in another thread where I included time constants. If L is small, and the induced voltage waveform is a rectangular pulse, that is L/R time constant << T (pulse width), we can assume I = Voc/R. But if L/R approaches or exceeds T, then, I = (Voc/R)(1 - e-Rt/L).

Here L is increasing as loop area increases. If the track was infinite in length, we would need to compute the Voc waveform. A ramp would result for a dc flux value. The ramp is a constant times "t" (time). The slope of this ramp must be compared to R/L. If slope << R/L, then L will influence the value of I. Later tonight after work, I can compute the infinite track case, slope, then compute L/R constant and its influence.

In technician's sketches, please refer to the current in the rod and associated magnetic field. The rod current is part of the loop which includes the track and closed end as well. Using right hand rule, the flux due to current is oriented exactly opposite to external flux. I will draw a sketch for that as well.

Motor/generator text books laid this issue to rest in 19th century. The current I is not simply Voc/R. It could be for small L value, but in general L cannot be ignored in loops with very low R. In this example the track and rod are metal such that R is very low. L comes into play in these scenarios. More later.

Claude

11. Aug 19, 2013

### cabraham

Induction does not require that force lines be cut. The original induction due to external mag field is due to a changing flux due to changing area. B is constant, but ∅ is changing, as ∅=AB. The loop current is I, and N=1 since the loop has but 1 turn. So ∅ = Li. Then d∅/dt = d(Li)/dt = idL/dt + Ldi/dt, since L changes it must be included in the derivative. So we get a 1st order diff eq in i, with time varying coefficient. I will solve and post tonight. This is not a trivial problem.

Do not make the assumption that L can be ignored. Depending on the values of the parameters, sometimes L can be ignored. But I prefer to compute the solution accounting for L, then if the numbers allow, I can drop L from further consideration since it changes the answer very little. But it's always better to take it into account, because you can see how much error is incurred by dropping it. BR.

"Every text book" does not say what you say, all of mine do not. Again, I've said this a lot, but machine texts are the horse's mouth on this subject. Study synchronous and induction ac motors, and inductance is always included, both stator and rotor. To compute current, the open circuit voltage is divided by the total impedance, R + jXL. The texts I mentioned are a good starting point.

Claude

12. Mar 7, 2015

### Jackson Lee

Admittedly the shape of the loop is changing, but the inductance reactance always exist. I think it is meaningful.


text:
## Multiplying Integers

### Learning Outcomes

• Multiply integers with different signs
• Multiply integers with the same sign
• Multiply an integer by -1

Since multiplication is mathematical shorthand for repeated addition, our counter model can easily be applied to show multiplication of integers. Let’s look at this concrete model to see what patterns we notice. We will use the same examples that we used for addition and subtraction.

We remember that $a\cdot b$ means add $a,b$ times. Here, we are using the model shown in the graphic below just to help us discover the pattern.

Now consider what it means to multiply $5$ by $-3$. It means subtract $5,3$ times. Looking at subtraction as taking away, it means to take away $5,3$ times. But there is nothing to take away, so we start by adding neutral pairs as shown in the graphic below.

In both cases, we started with $\mathbf{\text{15}}$ neutral pairs. In the case on the left, we took away $\mathbf{\text{5}},\mathbf{\text{3}}$ times and the result was $-\mathbf{\text{15}}$. To multiply $\left(-5\right)\left(-3\right)$, we took away $-\mathbf{\text{5}},\mathbf{\text{3}}$ times and the result was $\mathbf{\text{15}}$. So we found that

$\begin{array}{ccc}5\cdot 3=15\hfill & & -5\left(3\right)=-15\hfill \\ 5\left(-3\right)=-15\hfill & & \left(-5\right)\left(-3\right)=15\hfill \end{array}$

Notice that for multiplication of two signed numbers, when the signs are the same, the product is positive, and when the signs are different, the product is negative.

### Multiplication of Signed Numbers

The sign of the product of two numbers depends on their signs.

Same signs Product
•Two positives

•Two negatives

Positive

Positive

Different signs Product
•Positive • negative

•Negative • positive

Negative

Negative

### example

Multiply each of the following:

1. $-9\cdot 3$
2. $-2\left(-5\right)$
3. $4\left(-8\right)$
4. $7\cdot 6$

Solution:

 1. $-9\cdot 3$ Multiply, noting that the signs are different and so the product is negative. $-27$
 2. $-2\left(-5\right)$ Multiply, noting that the signs are the same and so the product is positive. $10$
 3. $4\left(-8\right)$ Multiply, noting that the signs are different and so the product is negative. $-32$
 4. $7\cdot 6$ The signs are the same, so the product is positive. $42$

### try it

Watch the following video for more examples of how to multiply integers with different signs, and the same sign.

When we multiply a number by $1$, the result is the same number. What happens when we multiply a number by $-1?$ Let’s multiply a positive number and then a negative number by $-1$ to see what we get.

$\begin{array}{ccc}\hfill -1\cdot 4\hfill & & \hfill -1\left(-3\right)\hfill \\ \hfill -4\hfill & & \hfill 3\hfill \\ \hfill -4\text{ is the opposite of }\mathbf{\text{4}}\hfill & & \hfill \mathbf{\text{3}}\text{ is the opposite of }-3\hfill \end{array}$

Each time we multiply a number by $-1$, we get its opposite.

### Multiplication by $-1$

Multiplying a number by $-1$ gives its opposite.

$-1a=-a$

### example

Multiply each of the following:

1. $-1\cdot 7$
2. $-1\left(-11\right)$

format: plain


text:
# Is our complementary solution guaranteed to be linearly independent?

## Main Question or Discussion Point

I had kind of a general question. Say I have a second order, homogeneous ODE. Say I use one of the general techniques to generate a complementary solution for my ODE and I end up with something of the form y = C1(solution1) + C2(solution2)

Am I gauranteed that these two solutions will be linearly independent or do I need to verify with the Wronskian each time?

Also, can I think of linearly independent solutions as a "basis" like I do in linear algebra? It seems like it because its my understanding that any solution for the ODE is simply a linear combination of solutions in this "basis"

Also, can we tell the dimensions of this basis based on the order of the ODE? Like, a second order ODE has two solutions in its basis, a third order has 3, a first order has one, etc.

Thanks!

Related Differential Equations News on Phys.org
Yes, you can think of the solutions as a basis in a vector space. In this case, they're basis functions in a space of functions, but most of the ideas from vector algebra still apply.

I think often the techniques chosen to generate solutions are meant to come up with solutions out of orthogonal functions--sines and cosines, for instance, are automatically linlearly independent as long as none of their frequencies are the same. Someone may know more on this matter, though.

HallsofIvy
Homework Helper
A complementary solution can't be "dependent" on the solution to the homogeneous equation. Suppose the equation is L(f)= g(x) where L is the linear differential operator, u(x) a linear combination of the independent solutions to the homogenelus equation, and v(x) a complementary solution. To be dependent means that there exist numbers, a and b, non-zero, such that au(x)+ bv(x)= 0. Applying L to both sides of that, L(au(x)+ bv(x))= aL(u)+ bL(v)= a(0)+ b(g)= 0 so that bg(x)= 0 for all x. Since g is not always 0, b= 0. That makes our original equation au(x)= 0 for all x and so a= 0.

The solutions to any linear homogeneus nth order differential equation form a vector space of dimension n. The solutions to a non-homogeneous linear equation do NOT form a vector space but do form a "linear manifold". If you think of a one-dimensional vector space as a line through the origin of a xy-coordinate system, or a two dimensional vector space as a plane through the origin of a xyz-coordinate system, then you can think of a one dimensional "linear manifold" as a line NOT through the origin or a two dimensional "linear manifold" NOT through the origin.

Last edited by a moderator:
If you think of a one-dimensional vector space as a line through the origin of a xy-coordinate system, or a two dimensional vector space as a plane through the origin of a xyz-coordinate system, then you can think of a one dimensional "linear manifold" as a line NOT through the origin or a two dimensional "linear manifold" NOT through the origin.

Thank you, this really does help me visualize this.

So I want to make sure I understand. So for example, when dealing with non homogeneous equations, does it mean we can't establish a "basis" or fundamental set of solutions so that every particular solution can be expressed as a linear combination of those solutions?

y'' - 5y' + 4y = 8ex

I can generate a basis for the vector space of solutions for the associated homogeneous equation and its B = {e4x,ex} (I got this by solving the auxilary equation and attaining distinct real roots x=4 and x=1)

Using variation of parameters, I can then generate a particular solution for this sytem:

yp=(-8/9)ex-(8/3)xex

To make sure it is indeed a particular solution I took y'p and y''p and plugged it in to the original ODE and it does check out. However, yp is not a linear combination of the functions in B.

oh wait I think I get it, the "basis" as I'm thinking of it for a nohomogeneous linear 2nd order ODE would be B={b1,b2,yp}

where b1 and b2 are the functions in the basis for the associated homogeneous ODE and yp is a particular solution satisfying the non homogeneous ODE.

EDIT: Oh waaaait... No what I just wrote is wrong. Any solution Y(x) of the non homogeneous system can be expressed as:

Y=C1b1+C2b2+yp

So I can see why {b1,b2,yp} is NOT a "basis" because we can't just have any linear combination of these to generate solutions, the solutions are linear combinations of b1 and b2 with yp simply added on (not any multiple of yp)! So this is why it's not a vector space but a linear manifold as you described it

Last edited:


text:
Home > Error Correction > Error Correction Coding Gain

# Error Correction Coding Gain

## Contents

If the average number of nearest neighbors per transmitted bit K b ( A ) {\displaystyle K_{b}(A)} is equal to one, the effective coding gain γ e f f ( A This curve can be plotted using the union bound estimate (UBE) P b ( E ) ≈ K b ( A ) Q 2 γ c ( A ) E b ERROR The requested URL could not be retrieved The following error was encountered while trying to retrieve the URL: http://0.0.0.4/ Connection to 0.0.0.4 failed. Text is available under the Creative Commons Attribution-ShareAlike License; additional terms may apply. news

Generated Sun, 09 Oct 2016 14:44:49 GMT by s_ac5 (squid/3.5.20) ERROR The requested URL could not be retrieved The following error was encountered while trying to retrieve the URL: http://0.0.0.10/ Connection The specific problem is: poor formatting, only a single source, and extremely difficult to read Please help improve this article if you can. (October 2014) (Learn how and when to remove The UBE becomes P s ( E ) ≈ K s ( A ) Q 3 γ c ( A ) S N R n o r m , {\displaystyle P_{s}(E)\approx E b / N 0 {\displaystyle E_{b}/N_{0}} curve at the target P b ( E ) {\displaystyle P_{b}(E)} . https://en.wikipedia.org/wiki/Coding_gain

## Error Correction Coding Mathematical Methods And Algorithms

Please try the request again. If the average number of nearest neighbors per transmitted bit K b ( A ) {\displaystyle K_{b}(A)} is equal to one, the effective coding gain γ e f f ( A Please try the request again. Error Correction Code Example Your cache administrator is webmaster.

Generated Sun, 09 Oct 2016 14:44:49 GMT by s_ac5 (squid/3.5.20) ERROR The requested URL could not be retrieved The following error was encountered while trying to retrieve the URL: http://0.0.0.6/ Connection Error Correction Coding Mathematical Methods And Algorithms Pdf Download The system returned: (22) Invalid argument The remote host or network may be down. no coding). look at this web-site Example The table below lists the nominal spectral efficiency, nominal coding gain and effective coding gain at P b ( E ) ≈ 10 − 5 {\displaystyle P_{b}(E)\approx 10^{-5}} for Reed–Muller

Please try the request again. Error Correction Code Flash Memory Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization. Use of this web site signifies your agreement to the terms and conditions. Please try the request again.

The nominal coding gain γ c ( A ) {\displaystyle \gamma _{c}(A)} is defined as γ c ( A ) = d min 2 ( A ) 4 E b . Your cache administrator is webmaster. Error Correction Coding Mathematical Methods And Algorithms Text is available under the Creative Commons Attribution-ShareAlike License; additional terms may apply. Error Correction Coding Moon Your cache administrator is webmaster.

Generated Sun, 09 Oct 2016 14:44:49 GMT by s_ac5 (squid/3.5.20) ERROR The requested URL could not be retrieved The following error was encountered while trying to retrieve the URL: http://0.0.0.7/ Connection navigate to this website The UBE becomes P s ( E ) ≈ K s ( A ) Q 3 γ c ( A ) S N R n o r m , {\displaystyle P_{s}(E)\approx Generated Sun, 09 Oct 2016 14:44:49 GMT by s_ac5 (squid/3.5.20) This curve can be plotted using the union bound estimate (UBE) P b ( E ) ≈ K b ( A ) Q 2 γ c ( A ) E b Forward Error Correction Coding

Power-limited regime In the power-limited regime (where the nominal spectral efficiency ρ ≤ 2 {\displaystyle \rho \leq 2} [b/2D or b/s/Hz], i.e. For the special case of a binary linear block code C {\displaystyle C} with parameters ( n , k , d ) {\displaystyle (n,k,d)} , the nominal spectral efficiency is ρ Please help to improve this article by introducing more precise citations. (January 2013) (Learn how and when to remove this template message) This article may require cleanup to meet Wikipedia's quality http://napkc.com/error-correction/error-coding-correction.php The system returned: (22) Invalid argument The remote host or network may be down.

Please try the request again. Error Correction Code Calculator Power-limited regime In the power-limited regime (where the nominal spectral efficiency ρ ≤ 2 {\displaystyle \rho \leq 2} [b/2D or b/s/Hz], i.e. the domain of binary signaling), the effective coding gain γ e f f ( A ) {\displaystyle \gamma _{\mathrm {eff} }(A)} of a signal set A {\displaystyle A} at a given


text:
# Fine-tuned Noise

When we decide to train a cool machine learning model, the most common machinery to get us there is stochastic gradient descent. From its humble beginnings as “cheapskate gradient descent”, SGD blows away its vanilla counterpart on highly non-convex loss surfaces. To me, the fact that such a simple hill-climbing technique has dominated modern non-convex optimization is fascinating. However, the presence of spurious local minima and saddle points makes analysis more complex. It’s important to understand how our intuitions about SGD dynamics can change when we remove our classical convex assumptions. The jump to the non-convex setting invites the use of frameworks like dynamical systems theory and stochastic differential equations, which provide models for thinking about long-term dynamics and short-term stochasticity in the optimization landscape.

Today I will be talking about what appears at first to be a simple nuisance in the world of gradient descent: noise. The only difference between stochastic gradient descent and vanilla gradient descent is the fact that the former uses a noisy approximation of the gradient. The structure of this noise ends up being the driving force behind the “exploratory” behavior of SGD for non-convex problems. I’ll talk a bit about the structure of this noise, connect it with some ideas from information geometry and stochastic nonlinear systems, and conclude with a discussion on some practical implications for these results.

## The covariance structure of mini-batch noise

Let’s introduce our problem setup. Suppose I would like to minimize a loss function $f: \mathbb{R}^n \rightarrow \mathbb{R}$ with a finite dataset consisting of $N$ examples. For parameters $x \in \mathbb{R}^n$, I will call the loss on the $i$th example $f_i(x)$. Now, $N$ is presumably quite large, so we’ll estimate the dataset gradient $g_N = \frac1N \sum_{i=1}^N \nabla f_i(x)$ with a mini-batch estimate $g_B = \frac1m \sum_{i \in B} \nabla f_i(x)$, where $B \subseteq \{1,2,\ldots,N\}$ is a mini-batch of size $m$. Although $g_N$ is itself a noisy estimate of $\nabla f(x)$, it turns out that mini-batch sampling produces an estimate with an interesting covariance structure.

Lemma 1 (Chaudhari & Soatto): When sampling with replacement, the variance of the mini-batch gradient for batch size $m$ is given by $\text{Var}(g_B) = \frac1m D(x)$, where

What does this result mean? Well, let’s put ourselves in-context. In a lot of optimization problems, our underlying goal is to maximize the likelihood of some configuration of the parameters. So our loss is a negative log-likelihood. For classification problems, this is cross-entropy. In this case, the first term $\hat{I}(x) = \sum_{i=1}^N \nabla f_i(x) \nabla f_i(x)^T$ is an estimate of (minus) the covariance of the gradient of the log-likelihood. This is the observed Fisher information. As $N \rightarrow \infty$, this approaches the Fisher information matrix. This is precisely the Hessian of the relative entropy (KL divergence). But the KL divergence is a constant factor away from the cross-entropy loss (negative log-likelihood) we were attempting to minimize.

Hence, the covariance of mini-batch noise is asymptotically related to the Hessian of our loss. In fact, when $x$ approaches a local minimum, the covariance approaches a scaled version of the Hessian.

### A detour into the Fisher information

Before I continue a bit into SGD-specific analysis, let’s take a moment to consider the connection between the Fisher information matrix $I(x)$ and the Hessian $\nabla^2 f(x)$. $I(x)$ is the variance of the log-likelihood gradient. How does variance relate to the curvature of the loss surface? Suppose we’re at a strict local minimum of $f$, i.e. $I(x^*) = \nabla^2 f(x^*)$ is positive definite. $I(x)$ induces a metric called the Fisher-Rao metric near $x^*$: $d(x,y) = \sqrt{(x-y)^T I(x^*)(x-y)}$. Interestingly, the Fisher-Rao norm of the parameters provides an upper bound on the generalization error. This means we can be more confident about the generalization ability of flatter minima.

### Back to the story

This immediately introduces some interesting conjectures about the dynamics of SGD. Let’s make a CLT-type assumption for a second and suppose we can decompose our estimate $g_B$ into the “true” dataset gradient and a noise term: $g_B = g_N + \frac{1}{\sqrt{B}}n(x)$, where $n(x) \sim \mathcal{N}(0, D(x))$. Moreover, for simplicity, assume we’re close to a minimum so that $D(x) \approx \nabla^2 f(x)$. $n(x)$ has a density $\rho (z)$ with a quadratic form in the $\exp$ argument:

This makes it clear that the eigenvalues of the Hessian play an important role in determining the sort of minima considered “stable” by SGD. When I’m at a sharp minimum where there are many large, positive eigenvalues, I am more likely to add noise that “pushes me out” of what would have been a basin of attraction in the vanilla gradient case. Similarly, for flat minima, I am more likely to “settle down.” We can make this precise using the following trick:

Lemma 2: Let $v \in \mathbb{R}^n$ be a random vector with mean $0$ and covariance $D$. Then $\mathbb{E}\left[ \|v\|^2 \right ] = \text{Tr}(D)$.

By using this lemma and Markov’s inequality for our picture, we can see that larger perturbations are more likely when the Hessian has high curvature. We can also consider a “radius of stability” around a local minimum $x^*$: for a fixed $\epsilon \in (0,1)$, there exists some $r(x^*) > 0$ such that if our starting point $x_0$ satisfies $% $, the probability that the $t$-th iterate satisfies $% $ for all $t \geq 0$ is at least $1 - \epsilon$. In this case, we can say $x^*$ is stochastically stable with radius $r(x^*)$. Combining this notion of stability with our previous informal argument, we get the following picture:

Micro-theorem 1: the radius of stability $r(x^*)$ for a strict local minimum $x^*$ is inversely proportional to the spectral radius of $\nabla^2 f(x^*)$.

Let’s connect this to what we know about the Fisher information. If flatter minima are more stable under the dynamics of SGD, this means that SGD implicitly provides a form of regularization. It does this by injecting anisotropic noise to push us out of regions where the Fisher-Rao norm hints at unfavorable generalization conditions.

## Implications for deep learning: degeneracy of the Hessian and “wide valleys”

An interesting phenomenon within deep learning is overparameterization. We often have many more parameters than we do examples ($d >> N$). In this case, $D(x)$ is highly degenerate, i.e. it has a lot of zero (or near-zero) eigenvalues. This means there are a lot of directions along which the loss function is locally constant. This paints an interesting picture of the optimization landscape for these networks: SGD spends most of the time traversing “wide valleys.” The noise is spread out along the few directions of higher curvature, which counteracts $g_N$’s push towards the bottom of this valley.

## Contemporary concerns: batch size, learning rate, and the generalization gap

Since we scale $n(x)$ by a factor of $\frac{1}{\sqrt{m}}$ before adding it to our vanilla gradient, increasing the batch size scales down the overall variance of our mini-batch estimate. This is a problem, since large batch sizes enable faster training of models at scale. It’s faster in two important ways: training error tends to converge in fewer gradient updates, and large batches let us take advantage of data parallelism at scale. However, increasing the batch size without any tricks can cause the test error to increase. This phenomenon is known as the “generalization gap” and there are a few working hypotheses for why this might be the case. One popular explanation is that our “exploratory noise” is no longer powerful enough to push us out of the basin of attraction of a sharp minimum. One solution is to simply scale up the learning rate to increase the contribution of this noise. These scaling rules have been pretty successful.

## Long-term concerns: escaping saddle points

Although the generalization gap has become a popular topic of discussion lately, there is also a lot of prior work studying how saddle points affect things. Although we don’t converge to saddle points asymptotically, we can still get stuck near them for a really long time. And even though larger batch sizes seem to encourage sharper minima, really large batch sizes lead us to deterministic trajectories that get stuck near saddle points. This work shows that injecting sufficiently large isotropic noise can help us escape saddle points. I’m willing to bet that mini-batch SGD provides enough noise along the problematic dimensions to escape them too if the noise has sufficient “amplification.”

Once we manage to solve the “sharp minima” problem, saddle points seem to be the next big barrier to large-scale optimization. For example, I trained ResNet34 on CIFAR-10 with plain SGD. As I increased the batch size up to 4096, the generalization gap appeared. After this point (I tested up to a batch size of 32k, with 50k training examples), performance degrades significantly: training error and test error both plateau in only a few epochs, and the network fails to converge to a useful solution. Here’s a preliminary (i.e. ugly and in-progress) plot of these results:

## Next steps?

Most of the proposed solutions to deal with sharp minima/saddle points revolve around (a) injecting isotropic noise or (b) maintaining a particular “learning rate to batch size” ratio. I don’t think these will be enough in the long-run. Isotropic noise does a poor job of taking into account the “wide valley” structure of our loss landscape. Increasing the learning rate also increases the contribution of the vanilla gradient, which makes our weight update bigger. I think the right approach is to come up with efficient ways to simulate the anisotropy of mini-batch noise in a way that’s “decoupled” from the learning rate and batch size. There are efficient ways to do this using sub-sampled gradient information and the Hessian-vector product, which I’m experimenting with right now. I would love to hear other ideas on how to solve this issue. In the meantime, there’s a lot of theoretical work to be done to understand these dynamics in more detail, especially in a deep learning context.


text:
# RTS questions (unit system)

This topic is 4664 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Ok, this is a mock up of the object system that I currently have:
-CRenderable
+--CUnit (marine, tank, etc)
+--CBuilding (base, turret, etc)

-CObjectFactory

CRenderable* pObj = new CUnit;
//blah

pObj = new CUnit;
//blah
etc

My two questions are: 1)Am I going to have problems with my object factory when it comes to sorting (since CUnit and CBuilding will have different variables in them)? 2)Is this an okay (I'm not looking for perfect right now) object system (other than it needs to be expanded a little bit)? Thanks!

##### Share on other sites
Hypothetically, your CRenderable class should contain the coordinate data (x,y,w,h or whatever) for the unit, and you'll probably want to sort by (y+h), so you should be fine.

(assuming you want to sort them by y-value so they draw right without any depth testing)

##### Share on other sites
My CRenderable contains:
static CTextureManager*		m_pTextureMgr;static IDirect3DDevice9*	m_pDevice;D3DXVECTOR2			m_Position;dftge::CVertex			m_Vertices[4];dftge::CTexture*		m_pTexture;RECT				m_BoundingRect;float				m_fWidth, m_fHeight;

And they are sorted by Y+H.

##### Share on other sites
Well, I don't really see much of a problem beyond the fact that it might be a bit of a pain when you get down to gameplay programming and you have to identify the distinctions between a unit and a building.

A solution I would offer is to make a common interface for them - which may or may not be possible depending on how you've designed your game.

The way I designed my 4E4 crap (which was going to be an RTS) was to treat buildings and units exactly the same, except to give buildings a UNIT_IMMOBILE flag. This was primarily because there were quite a few units (pirate boats) which acted both as buildings and as units. But again, it was really a design decision.

In the end, you'll have to think out exactly what you'll need to do in terms of gameplay. I've coded myself into a paper bag *hundreds* of times because I didn't think of something I'd need, and not having it in there pretty much crippled everything else.

So yeah. You'll probably want to take the time to evaluate exactly what you want to do with your units, and if storing them using the factory method is the best idea or not. For me, it came down to "Why, exactly, makes a building different from a unit?" My answer, as mentioned, was that buildings couldn't move.

Granted, the 4E4 engine did implode on itself, so you might not want to trust my design advice (lol).

##### Share on other sites
Quote:
 Original post by MushuWell, I don't really see much of a problem beyond the fact that it might be a bit of a pain when you get down to gameplay programming and you have to identify the distinctions between a unit and a building.A solution I would offer is to make a common interface for them - which may or may not be possible depending on how you've designed your game.The way I designed my 4E4 crap (which was going to be an RTS) was to treat buildings and units exactly the same, except to give buildings a UNIT_IMMOBILE flag. This was primarily because there were quite a few units (pirate boats) which acted both as buildings and as units. But again, it was really a design decision.In the end, you'll have to think out exactly what you'll need to do in terms of gameplay. I've coded myself into a paper bag *hundreds* of times because I didn't think of something I'd need, and not having it in there pretty much crippled everything else.So yeah. You'll probably want to take the time to evaluate exactly what you want to do with your units, and if storing them using the factory method is the best idea or not. For me, it came down to "Why, exactly, makes a building different from a unit?" My answer, as mentioned, was that buildings couldn't move.Granted, the 4E4 engine did implode on itself, so you might not want to trust my design advice (lol).

lol

Thanks for all the help Mushu!

1. 1
Rutin
26
2. 2
3. 3
JoeJ
20
4. 4
5. 5

• 9
• 9
• 9
• 46
• 41
• ### Forum Statistics

• Total Topics
631750
• Total Posts
3002060
×


text:
# Functional Analysis, topology induced by infinite norm

In the $C[0,1]$ function space, do all norms induce a finer topology than the topology induced by infinite norm ($\sup$ norm)?

-
Dear Louis, I edited your question. Can you check that I didn't change the intended meaning? Thank you. –  Matt N. Sep 19 '12 at 12:42

To expand on Nate's answer:

To see that the $L^1$-topology is coarser than the $\sup$-topology it is enough to exhibit a set that is open in the $\sup$-topology but not in the $L^1$-topology. To this end, consider the open unit ball around zero in the $\sup$ norm, $B_{\|\cdot\|_\infty}(0, 1)$. If this ball was open in the $L^1$-topology we'd be able to find an $\varepsilon$ for every point $x$ in it such that the $\varepsilon$-ball $B_{L^1}(x, \varepsilon)$ was contained in $B_{\|\cdot\|_\infty}(0, 1)$.

To see that this is not true, consider the point $0$. Let $\varepsilon = \frac{1}{n}> 0$ be arbitrary and consider $B_{L^1}(0, \frac{1}{n})$. Define $$f_n(x) = \begin{cases} 10 \sin(n \cdot 10 x) & x \in [0, \frac{\pi}{n \cdot 10}] \\ 0 & \text{ otherwise } \end{cases}$$

$f_n$ is continuous and $\int_{[0,1]} f_n dx = \frac{2}{n}$ but $\|f_n \|_\infty = 10$. Hence for every $\varepsilon$ we can find $n$ such that $f_n \in B_{L^1}(0, \varepsilon)$ but $f_n \notin B_{\|\cdot\|_\infty}(0,\varepsilon)$, hence for all $\varepsilon$, $B_{L^1}(0, \varepsilon) \subsetneq B_{\|\cdot\|_\infty}(0,\varepsilon)$.

-

Certainly not. For example, the $L^1$ norm $\|f\|_{L^1} := \int_0^1 |f(x)|\,dx$ induces a coarser topology than the sup norm.

-
Please include the absolute value within the integral (it is too short for an edit). –  Vobo Sep 19 '12 at 12:16


text:
# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
A note on quenched moderate deviations for Sinai’s random walk in random environment. (English) Zbl 1171.60396
Summary: We consider the continuous time, one-dimensional random walk in random environment in Sinai’s regime. We show that the probability for the particle to be, at time $t$ and in a typical environment, at a distance larger than ${t}^{a}$ ($0) from its initial position, is $exp\left\{-\mathrm{Const}·{t}^{a}/\left[\left(1-a\right)lnt\right]\left(1+o\left(1\right)\right)\right\}$.
##### MSC:
 60K37 Processes in random environments 60F10 Large deviations 82B41 Random walks, random surfaces, lattice animals, etc. (statistical mechanics) 82B44 Disordered systems (equilibrium statistical mechanics)


text:
(a)

$A_x=0$, $B_y=\SI{60}{kN}\uparrow$, $A_y=\SI{60}{kN}\uparrow$, $V=\SI{-15}{kN}$, $A=0$, $M=\SI{112.5}{kNm}$

(b)

$A_x=\SI{300}{kN}\leftarrow$, $A_y=\SI{210}{kN}\uparrow$, $M_A=\SI{2100}{kNm}\curvearrowleft$, $V=\SI{210}{kN}$, $A=\SI{300}{kN}$, $M=\SI{-1050}{kNm}$

(c)

$A_x=0$, $B_y=\SI{72}{kN}\uparrow$, $A_y=\SI{72}{kN}\uparrow$, $V=\SI{18.9}{kN}$, $A=\SI{14.3}{kN}$, $M=\SI{96.8}{kNm}$

(d)

$A_perp=\SI{78.4}{kN}\nearrow$, $C_y=\SI{67.9}{kN}\downarrow$, $C_x=\SI{136}{kN}\rightarrow$, $V=\SI{67.9}{kN}$, $A=\SI{-39}{kN}$, $M=\SI{272}{kNm}$


text:
# Implications of INL on the accuracy and resolution of an ADC

I was trying to understand the meaning of various specs given in a typical ADC datasheet, and I came across this article. Now, if I understand correctly, it seems to me that the accuracy of the ADC in bits can be taken as $n - \log_2{{e}}$ bits, where $n$ is the number of output bits of the device (its resolution?) and $e$ is the INL (integral non-linearity) error in terms of LSB.

My questions are:

1. Is my understanding correct? If not, what is the correct explanation?
2. If a 16-bit ADC has a INL of $\pm 4$ LSB, can we say that the accuracy of the ADC is 14-bit, and will have to ignore the lowest 2 bits for most practical purposes?
3. Here is a 16-bit ADC with a typical INL of $\pm 0.4$ LSB. Does this mean the device has a typical accuracy of more than 17-bits? How is this possible? Or does it mean the device typically has an accuracy of over 17 bits, but since it has only 16 output bits, it has to truncate the data to a lower resolution?


text:
# Combinatorial Sampling

#### 03/29/2022

This document covers topics in generating random samples of combinations/permutations. It is encouraged to read General Combinatorics first.

To illustrate this in base R, let us consider getting 5 random combinations of the vector 1:20 of length 10. How should we proceed?

## Base R

A naive approach would be to generate all of the combinations using combn and then call sample:

naive <- function(v, m, n, s) {
allCombs <- combn(v, m)
set.seed(s)
allCombs[, sample(ncol(allCombs), n)]
}

fiveRndCombs <- naive(20, 10, 5, 42)
t(fiveRndCombs)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
#> [1,]    1    3    5   10   11   14   15   16   18    20
#> [2,]    1    3    4    9   10   11   12   13   18    19
#> [3,]    2    3    4    6    9   10   12   13   15    19
#> [4,]    1    4    5   10   13   14   15   17   18    19
#> [5,]    1    3    4    5    7    8   13   15   18    19

This is okay for this small example (there are only choose(20, 10) = 184756 results), however what if we wanted to find one hundred thousand random combinations from the vector 1:100 of length 20? Clearly, the approach above will not be feasible as there are far too many results to generate (choose(100, 20) = 5.359834e+20). Furthermore, there are internal limitations on sample. If we try to pass choose(100, 20), we will get an error:

sample(choose(100, 20), 5)
#> Error in sample.int(x, size, replace, prob) : invalid first argument

We could also try calling sample(100, 20) a bunch of times and hope we don’t get duplicate combinations. This is neither promising nor elegant.

## RcppAlgos Solutions

RcppAlgos provides four functions: comboSample, permuteSample, partitionsSample, and comboGroupsSample for seamlessly attacking these types of problems. All functions provide the following:

• Easily generate random samples of combinations/permutations/partitions or partition of groups in parallel.
• You can pass a vector of specific indices or rely on the internal sampling functions. We call sample when the total number of results is small and for larger cases, the sampling is done in a very similar fashion to urand.bigz from the gmp package.
• Consistent interface to their respective general functions (i.e. {combo/permute/partitions}General and comboGroups)
• Useful when we need a reproducible set of random combinations/permutations/partitions or partitions of groups.
• If the gmp library is needed, the seed parameter must be set in order to have reproducible results (E.g. set.seed()) has no effect in these cases).

## comboSample and permuteSample

Let’s first look at the first problem above (i.e. getting 5 random combinations of the vector 1:20 of length 10):

library(RcppAlgos)
set.seed(42)
comboSample(20, 10, n = 5)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
#> [1,]    1    3    5   10   11   14   15   16   18    20
#> [2,]    1    3    4    9   10   11   12   13   18    19
#> [3,]    2    3    4    6    9   10   12   13   15    19
#> [4,]    1    4    5   10   13   14   15   17   18    19
#> [5,]    1    3    4    5    7    8   13   15   18    19

## Use the seed argument directly to produce the same output
comboSample(20, 10, n = 5, seed = 42)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
#> [1,]    1    3    5   10   11   14   15   16   18    20
#> [2,]    1    3    4    9   10   11   12   13   18    19
#> [3,]    2    3    4    6    9   10   12   13   15    19
#> [4,]    1    4    5   10   13   14   15   17   18    19
#> [5,]    1    3    4    5    7    8   13   15   18    19

## fiveRndCombs produced above
identical(t(fiveRndCombs),
comboSample(20, 10, n = 5, seed = 42))
#> [1] TRUE

### Samples of Results with Repetition

Just like with comboGeneral and permuteGeneral, we can explore results with repetition.

comboSample(10, 8, TRUE, n = 3, seed = 84)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,]    2    5    5    7    9    9    9    9
#> [2,]    4    5    8    8    8   10   10   10
#> [3,]    2    6    6    6    6    6    9    9

permuteSample(10, 8, TRUE, n = 3)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,]    4   10    4    4   10    2    2   10
#> [2,]    1    4    5   10    5    5    2    2
#> [3,]    4    1    7    9    1    5    6    5

comboSample(10, 12, freqs = 1:10, n = 3)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12]
#> [1,]    2    2    3    5    5    6    6    6    7     8     9    10
#> [2,]    1    2    3    3    5    5    6    7    9     9     9     9
#> [3,]    1    2    5    5    5    6    6    9   10    10    10    10

permuteSample(10, 12, freqs = 1:10, n = 3, seed = 123)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12]
#> [1,]    2    8    7    4    8    9   10   10    7     1     8     2
#> [2,]    5    5    9    8    1    8    3    2    6     4     3    10
#> [3,]   10    3    8    8    4    8    8    6   10     6     3     8

### Specific Results with sampleVec

We can also utilize sampleVec to generate specific results.

## E.g. the below generates the 1st, 5th, 25th, 125th, and
#> 625th lexicographical combinations
comboSample(10, 8, TRUE, sampleVec = c(1, 5, 25, 125, 625))
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,]    1    1    1    1    1    1    1    1
#> [2,]    1    1    1    1    1    1    1    5
#> [3,]    1    1    1    1    1    1    3    8
#> [4,]    1    1    1    1    1    3    6    9
#> [5,]    1    1    1    1    5    6   10   10

## Is the same as:
comboGeneral(10, 8, TRUE)[5^(0:4), ]
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,]    1    1    1    1    1    1    1    1
#> [2,]    1    1    1    1    1    1    1    5
#> [3,]    1    1    1    1    1    1    3    8
#> [4,]    1    1    1    1    1    3    6    9
#> [5,]    1    1    1    1    5    6   10   10

### Using namedSample

Have you ever wondered which lexicographical combinations/permutations are returned when sampling? No worries, simply set namedSample = TRUE:

testInd <- permuteSample(30, 10, n = 3, seed = 100, namedSample = TRUE)
testInd
#>                [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
#> 86626302070118   24   26    7   29    3   21   20    9   16    28
#> 15871916538841    5   12   21    9    6    3   14   23    4    20
#> 87932455980012   25    6   20   23   18   10   27   30   19    29

## Same output as above
permuteSample(30, 10, sampleVec = row.names(testInd))
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
#> [1,]   24   26    7   29    3   21   20    9   16    28
#> [2,]    5   12   21    9    6    3   14   23    4    20
#> [3,]   25    6   20   23   18   10   27   30   19    29

### Parallel Computing and GMP Support

Just like the General counterparts, the sampling functions utilize GMP to allow for exploration of combinations/permutations of large vectors where the total number of results is enormous. They also offer parallel options using Parallel or nThreads.

## Uses min(stdThreadMax() - 1, 5) threads (in this case)
permuteSample(500, 10, TRUE, n = 5, seed = 123, Parallel = TRUE)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
#> [1,]   55  435  274  324  200  152    6  313  121   377
#> [2,]  196  166  331  154  443  329  155  233  354   442
#> [3,]  235  325   94   27  370  117  302   86  229   126
#> [4,]  284  104  464  104  207  127  117    9  390   414
#> [5,]  456   76  381  456  219   23  376  187   11   123

permuteSample(factor(state.abb), 15, n = 3, seed = 50, nThreads = 3)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15]
#> [1,] ME   FL   DE   OK   ND   CA   PA   AL   ID   MO    NM    HI    KY    MT    NJ
#> [2,] AZ   CA   AL   CT   ME   SD   ID   SC   OK   NH    HI    TN    ND    IA    MT
#> [3,] MD   MO   NC   MT   NH   AL   VA   MA   VT   WV    NJ    NE    MN    MS    MI
#> 50 Levels: AK AL AR AZ CA CO CT DE FL GA HI IA ID IL IN KS KY LA MA MD ME MI MN ... WY

permuteCount(factor(state.abb), 15)
#> Big Integer ('bigz') :
#> [1] 2943352142120754524160000

### Efficiency

The algorithms are incredibly efficient and offer tremendous gains over the naive approach above:

## the function "naive" is defined above
system.time(naive(25, 10, 5, 15))
#>   user  system elapsed
#>  3.197   0.066   3.287

system.time(comboSample(25, 10, n = 5, seed = 15))
#>   user  system elapsed
#>  0.002   0.000   0.001

Even when dealing with extremely large numbers, these algorithms are very fast. And using the parallel options have even greater effects than we saw with the general counterparts (typically around ~2-3 times faster with the general functions, whereas with the last example below with sampling we see a nearly 5 fold improvement).

## Lightning fast even with examples involving many results
system.time(comboSample(2500, 100, n = 5, seed = 15))
#>    user  system elapsed
#>   0.002   0.000   0.002

## The total number of combinations has ~180 digits
gmp::log10.bigz(comboCount(2500, 100))
#> [1] 180.9525

## Still fast with larger samples
system.time(comboSample(2500, 100, n = 1e4, seed = 157))
#>    user  system elapsed
#>   1.124   0.008   1.142

## Using Parallel/nThreads in these cases has an even greater effect
system.time(comboSample(2500, 100, n = 1e4, seed = 157, nThreads = 8))
#>    user  system elapsed
#>   2.032   0.005   0.268

### User Defined Functions

Again, just as with the general functions, you can pass a custom function to combo/permuteSample using the FUN argument.

permuteSample(5000, 1000, n = 3, seed = 101, FUN = sd)
#> [[1]]
#> [1] 1431.949
#>
#> [[2]]
#> [1] 1446.859
#>
#> [[3]]
#> [1] 1449.272

## Example using complex numbers
myCplx <- as.complex(1:100 + rep(c(-1, 1), 50) * 1i)

permuteSample(myCplx, 10, freqs = rep(1:5, 20),
n = 3, seed = 101, FUN = function(x) {
sqrt(sum(x))
})
#> [[1]]
#> [1] 24.83948+0i
#>
#> [[2]]
#> [1] 20.9285+0.04778i
#>
#> [[3]]
#> [1] 22.20379+0.09007i

## partitionsSample

The partitionsSample function allows one to draw a random sample of partitions of a number. Many of the features present in comboSample and permuteSample are available in partitionsSample.

## Use the seed parameter to obtain reproducible results
partitionsSample(100, 8, TRUE, n = 3, seed = 42)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,]    1    1    3    3    4   20   23   45
#> [2,]    1    1    2    7   14   14   29   32
#> [3,]    2   10   11   11   16   16   16   18

## Used namedSample to obtain the lexicographical indices
partitionsSample(100, 8, TRUE, n = 3, seed = 42, namedSample = TRUE)
#>        [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> 61413     1    1    3    3    4   20   23   45
#> 54425     1    1    2    7   14   14   29   32
#> 623844    2   10   11   11   16   16   16   18

## Use sampleVec to obtain specific results
partitionsSample(100, 8, TRUE, sampleVec = c(61413, 54425, 623844))
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,]    1    1    3    3    4   20   23   45
#> [2,]    1    1    2    7   14   14   29   32
#> [3,]    2   10   11   11   16   16   16   18

partitionsCount(2500, 10)
#> Big Integer ('bigz') :
#> [1] 2621914835336941325

## Algorithms are very efficient
system.time(serial <- partitionsSample(2500, 10, n = 1e3,
seed = 8128))
#>    user  system elapsed
#>   5.220   0.010   5.235

## Use nThreads for greater efficiency
system.time(multi <- partitionsSample(2500, 10, n = 1e3,
seed = 8128, nThreads = 8))
#>    user  system elapsed
#>  10.723   0.022   1.358

identical(multi, serial)
#> [1] TRUE

## Even works with non-standard setup
partitionsSample(17 + (1:10) * 3, 10, TRUE,
target = 320, n = 3, seed = 111)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
#> [1,]   23   23   26   26   29   29   38   38   41    47
#> [2,]   26   26   26   29   29   29   32   41   41    41
#> [3,]   20   23   23   26   26   35   38   41   44    44

There are sampling algorithms available for most partition cases, but some cases are not covered. For example, with standard multisets, we are currently unable to efficiently generate the nth lexicographical result. Another example is when the source vector is not uniform (e.g. when the distance between each element is irregular).

Observe the following:

## No sampling algorithm available when the source vector is not uniform
partitionsSample(c(1, 4, 6, 7, 10, seq(11, 100, 7)), 10, n = 1, target = 340)
#> Error in partitionsSample(c(1, 4, 6, 7, 10, seq(11, 100, 7)), 10, n = 1,  :
#>   Partition sampling not available for this case.

## As stated above, the standard multiset case doesn't work either
partitionsSample(0:50, 6, freqs = rep(1:3, 17), n = 2)
#> Error in partitionsSample(0:50, 6, freqs = rep(1:3, 17), n = 2) :
#>   Partition sampling not available for this case.

## If we use freqs to indicate that zeros can repeat,
## then we can obtain random samples
partitionsSample(0:50, 6, freqs = c(50, rep(1, 50)), n = 3, seed = 222)
#>      [,1] [,2] [,3] [,4] [,5] [,6]
#> [1,]    0    0    1    4    9   36
#> [2,]    0    0    0    0   17   33
#> [3,]    2    4    5    6    8   25

## Even works when the vector is restricted in regards to the target
partitionsSample(0:50, 6, freqs = c(50, rep(1, 50)),
n = 3, seed = 222, target = 100)
#>      [,1] [,2] [,3] [,4] [,5] [,6]
#> [1,]    0    1    6   15   29   49
#> [2,]    0    0    0    8   43   49
#> [3,]    4    7   17   19   22   31

There is ongoing research in this area and our goal is to eventually be able to cover the standard multiset case.

## Sampling Partitions of Groups of Equal Size with comboGroupsSample

Just as we can generate random samples of combinations and permutations, we are also able to generate random samples of partitions of groups of equal size. There are many problems that present in this manner. Below, we examine one involving playing cards.

Let’s say we have 4 players and each player is to have 3 cards a piece. Given that the deck is shuffled, the dealer then distrubutes 12 cards.

What possible hands can each player have?

See Creating A Deck Of Cards In R Without Using While And Double For Loop (Credit to @MichaelChirico)

cards <- c(2:10, "J", "Q", "K", "A")
suits <- c("♠", "♥", "♦", "♣")
deck <- paste0(rep(cards, length(suits)),  #card values
rep(suits, each = length(cards))) #suits

set.seed(1738)
shuffled <- factor(deck[sample(52)], levels = deck)

## Here are 3 possibilities
comboGroupsSample(shuffled[1:12], numGroups = 4, n = 2, seed = 13)
#>      Grp1 Grp1 Grp1 Grp2 Grp2 Grp2 Grp3 Grp3 Grp3 Grp4 Grp4 Grp4
#> [1,] 8♦   3♥   5♦   9♦   J♠   7♥   8♠   K♦   10♦  A♦   J♥   3♦
#> [2,] 8♦   K♦   10♦  9♦   J♥   3♥   J♠   8♠   3♦   A♦   5♦   7♥
#> 52 Levels: 2♠ 3♠ 4♠ 5♠ 6♠ 7♠ 8♠ 9♠ 10♠ J♠ Q♠ K♠ A♠ 2♥ 3♥ 4♥ 5♥ 6♥ 7♥ 8♥ ... A

comboGroupsSample(shuffled[1:12], numGroups = 4, retType = "3Darray",
n = 2, seed = 13, namedSample = TRUE)
#> , , Grp1
#>
#>       [,1] [,2] [,3]
#> 13784 8♦   3♥   5♦
#> 9152  8♦   K♦   10♦
#>
#> , , Grp2
#>
#>       [,1] [,2] [,3]
#> 13784 9♦   J♠   7♥
#> 9152  9♦   J♥   3♥
#>
#> , , Grp3
#>
#>       [,1] [,2] [,3]
#> 13784 8♠   K♦   10♦
#> 9152  J♠   8♠   3♦
#>
#> , , Grp4
#>
#>       [,1] [,2] [,3]
#> 13784 A♦   J♥   3♦
#> 9152  A♦   5♦   7♥
#>
#> 52 Levels: 2♠ 3♠ 4♠ 5♠ 6♠ 7♠ 8♠ 9♠ 10♠ J♠ Q♠ K♠ A♠ 2♥ 3♥ 4♥ 5♥ 6♥ 7♥ 8♥ ... A♣♣


text:
Macro & Micro economics ECONOMICS

Click here for more on this paper……. Click here to have a similar A+ quality paper done for you by one of our writers within the set deadline at a discounted

Project description
1. Using the following McConnell textbook weblink for a LAST WORD:

Lojack: A CASE OF POSITIVE EXTERNALITIES, evaluate and describe in similar format the CASE OF NEGATIVE EXTERNALITIES.

http://novellaqalive2.mhhe.com/sites/0077238737/student_view0/ebook/chapter16/chbody25/last_word.htm

Click here for more on this paper……. Click here to have a similar A+ quality paper done for you by one of our writers within the set deadline at a discounted

2. Discuss the various types of unemployment. Define and include relevant examples of each. Have you witnessed anyone you know who are or were “unemployed”? Include their economic story.

What is the definition (and fully explain) the goal “Full Employment.”

If actual inflation is greater than anticipated inflation, who “benefits” and who is “hurt.” Explain.

Is GDP an accurate indicator of economic well-being?
Is GDP an inaccurate indicator of economic well-being?
3 You are a macro policy maker for the CEA (Council of Economic Advisors). You

Click here for more on this paper……. Click here to have a similar A+ quality paper done for you by one of our writers within the set deadline at a discounted

have experience with the Congress (Fiscal Policy).

Current BLS and BEA statistics on the United States Economic situation:

*Real Gross Domestic Product (in billions of 2005 dollars) $12,000 RGDP a year ago$13,000

*CPI (Consumer Price Index) 200
CPI a year ago 190

*Unemployment Rate 10.5%
Unemployment Rate a year ago 7.0%
What economic problem for the United States?
What are your Fiscal Policy goals?

Click here for more on this paper……. Click here to have a similar A+ quality paper done for you by one of our writers within the set deadline at a discounted

What Fiscal Policy would you consider appropriate? Why?
Analyze using Aggregate Demand (AD)/Short-RunAggregate Supply (SRAS), Long-Run Aggregate Supply (LRAS) diagram to illustrate the effects of your policy recommendations on the economy. What would you anticipate will happen and give full explanation of the following:

Output
Employment
Price Level

Click here for more on this paper……. Click here to have a similar A+ quality paper done for you by one of our writers within the set deadline at a discounted

Interest Rates (Money Market Graphic Analysis REQUIRED)
Investment (business sector) (Investment Demand Graph Analysis REQUIRED)
Federal Budget (Deficit or Surplus)
International Value of the US dollar

4. Go to the FOMC (Federal Open Market Committee of the Federal Reserve System)
—- the FED, the United States Central Bank website.

http://www.federalreserve.gov/

Click here for more on this paper……. Click here to have a similar A+ quality paper done for you by one of our writers within the set deadline at a discounted

Watch the most recent press conference of the FED CHAIR, Janet
Yellen, reporting on the recent June 2014 FED meeting.

Then, GO TO:

Recent Developments>>Federal Reserve Issues FOMC Statement

http://www.federalreserve.gov/newsevents/press/monetary/20140618a.htm

Review the June 18, 2014 FED Press Release paragraph by paragraph indicating the “macroeconomic principles (concepts, visuals, graphs with full labeling and explanation) you learned in EC201E-N1. Hopefully, you have gain experience/connection/practice by doing course suggested “”Two-minute” Drill daily throughout the course.

Click here for more on this paper……. Click here to have a similar A+ quality paper done for you by one of our writers within the set deadline at a discounted

## Plagiarism Checker

Submit your documents and get free Plagiarism report

Free Plagiarism Checker


text:
### How to Obfuscate MPC Inputs

##### Abstract

We introduce the idea of input obfuscation for secure two-party computation ($\textsf{io2PC}$). Suppose Alice holds a private value $x$ and wants to allow clients to learn $f(x,y_i)$, for their choice of $y_i$, via a secure computation protocol. The goal of $\textsf{io2PC}$ is for Alice to encode $x$ so that an adversary who compromises her storage gets only oracle access to the function $f(x,\cdot)$. At the same time, there must be a 2PC protocol for computing $f(x,y)$ that takes only this encoding (and not the plaintext $x$) as input. We show how to achieve $\textsf{io2PC}$ for functions that have virtual black-box (VBB) obfuscation in either the random oracle model or generic group model. For functions that can be VBB-obfuscated in the random oracle model, we provide an $\textsf{io2PC}$ protocol by replacing the random oracle with an oblivious PRF. For functions that can be VBB-obfuscated in the generic group model, we show how Alice can instantiate a "personalized" generic group. A personalized generic group is one where only Alice can perform the algebraic operations of the group, but where she can let others perform operations in that group via an oblivious interactive protocol.

Note: Full version of an IACR publication in TCC 2022

Available format(s)
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in TCC 2022
Keywords
Secure Multiparty Computation Obfuscation Virtual Black Box
Contact author(s)
mcquoidi @ oregonstate edu
rosulekm @ eecs oregonstate edu
xujiay @ oregonstate edu
History
2022-10-26: approved
See all versions
Short URL
https://ia.cr/2022/1463

CC BY

BibTeX

@misc{cryptoeprint:2022/1463,
author = {Ian McQuoid and Mike Rosulek and Jiayu Xu},
title = {How to Obfuscate MPC Inputs},
howpublished = {Cryptology ePrint Archive, Paper 2022/1463},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/1463}},
url = {https://eprint.iacr.org/2022/1463}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.


text:
My Math Forum Simpler proof of fermat's last theorem

 Number Theory Number Theory Math Forum

 August 6th, 2015, 07:54 AM #1 Senior Member   Joined: Aug 2010 Posts: 158 Thanks: 4 Simpler proof of fermat's last theorem Please can I have comments on my proof.
 August 6th, 2015, 08:21 AM #2 Senior Member   Joined: Aug 2010 Posts: 158 Thanks: 4 Fermat’s Last Theorem This theorem basically states that Aⁿ + Bⁿ ≠ Cⁿ i.e. Cⁿ - Bⁿ ≠ Aⁿ if n > 2, A, B, C and n are all positive integers. Andrew Wiles, a British mathematician, produced a lengthy proof of over 100 pages in the mid 1990s. Let it be initially assumed that Fermat’s inequation is not true i.e. Cⁿ - Bⁿ = Aⁿ. If A, B and C have a highest common factor > 1, f say, fⁿ can be cancelled out to give a new Fermat equation with new values for A, B and C. Therefore in order to prove Fermat’s Last Theorem it is sufficient to consider only cases where A, B and C do not have any common prime factors i.e. ‘primitive’ equations. If n is an odd non-prime, Aⁿ + Bⁿ = Cⁿ can always be rewritten such that the new value of n can always be made prime e.g. 6⁹ = 216³. It is therefore also sufficient to consider only odd prime values of n and even values of n >2 in order to prove Fermat’s Last Theorem. Fermat’s Last Theorem can therefore be restated as 2 corollaries. Corollary 1 Cⁿ - Bⁿ ≠ Aⁿ if n > 2 is a prime number. A, B and C are positive integers that don’t have any common prime factors. Corollary 2 Cⁿ - Bⁿ ≠ Aⁿ if n >2 is an even number i.e. Z² - Y² ≠ X² where X = A^t, Y = B^t, Z = C^t, 2t = n. A, B and C are positive integers that don’t have any common prime factors. Proof of Corollary 1 The first step of the proof is to show that C - B < A if Cⁿ - Bⁿ = Aⁿ. Assume C - B < A. This means that (C - B)^n < Aⁿ i.e. (C - B)^n < Cⁿ - Bⁿ. Let C - B = D i.e. C = B + D then (C - B)^n < Cⁿ - Bⁿ can be rewritten as Dⁿ < (B + D)^n - Bⁿ which after expanding the brackets gives Dⁿ < Dⁿ + nBⁿ⁻ᶦD + …….. + nDⁿ⁻ᶦB and so the initial assumption is true i.e. C - B < A. Let pᵐ be part of the prime factor decomposition of A where p is one of its prime factors. Let pᵐ = [C-B]/K. The value of K is dependent on the value of C - B and the prime factor p of A that is under consideration. K is clearly some fraction that has the prime factor decomposition of its numerator and denominator to be made up of some or all of the prime factors of A only or its numerator and/or denominator could equal 1. Cⁿ - Bⁿ = [C-B][Cⁿ⁻ᶦ + Cⁿ⁻²B+ Cⁿ⁻³B² + ....+ CBⁿ⁻² + Bⁿ⁻ᶦ] = Aⁿ can therefore be rewritten as Cⁿ - Bⁿ = {[C-B]/K}[Cⁿ⁻ᶦ + Cⁿ⁻²B+ Cⁿ⁻³B² + ....+ CBⁿ⁻² + Bⁿ⁻ᶦ]K = Aⁿ i.e. Cⁿ - Bⁿ = pᵐ [Cⁿ⁻ᶦ + Cⁿ⁻²B+ Cⁿ⁻³B² + ....+ CBⁿ⁻² + Bⁿ⁻ᶦ]K = Aⁿ It should be clear that pᵐ = [C-B]/K should be a factor of the positive integer [Cⁿ⁻ᶦ + Cⁿ⁻²B+ Cⁿ⁻³B² + ....CBⁿ⁻² + Bⁿ⁻ᶦ]K if pᵐ [Cⁿ⁻ᶦ + Cⁿ⁻²B+ Cⁿ⁻³B² + ....+ CBⁿ⁻² + Bⁿ⁻ᶦ]K = Aⁿ. Algebraic long division of [Cⁿ⁻ᶦ + Cⁿ⁻²B+ Cⁿ⁻³B² + .... + CBⁿ⁻² + Bⁿ⁻ᶦ]K by pᵐ = [C-B]/K which equals algebraic long division of [Cⁿ⁻ᶦ + Cⁿ⁻²B+ Cⁿ⁻³B² + ....+ CBⁿ⁻² + Bⁿ⁻ᶦ]K² by (C-B) always gives a remainder of nBⁿ⁻ᶦK². For pᵐ = [C-B]/K to be a factor of [Cⁿ⁻ᶦ + Cⁿ⁻²B+ Cⁿ⁻³B² + ....CBⁿ⁻² + Bⁿ⁻ᶦ]K then (nBⁿ⁻ᶦK²)/(C-B)=nBⁿ⁻ᶦK/pᵐ needs to be a positive integer for each and every prime factor, p, of A. Since A and B don’t have any common prime factors it is therefore sufficient to consider only nK/p^m i.e. it needs to be a positive integer for each and every prime factor, p, of A. A little thought will show that since C - B < A there must exist at least one prime factor, p, of A that will not make nK/pᵐ a positive integer since the denominator of K will be p^j where j ≤ m and the numerator of K will not have p as a prime factor. Proof of Corollary 2 The first step of the proof is to show that Z - Y < X if Z² - Y² = X² . Assume Z - Y < X. This means that (Z - Y)^2 < X^2 i.e. (Z - Y)^2 < Z² - Y². Let Z - Y = D i.e. Z = Y + D then (Z - Y)^2 < Z² - Y² can be rewritten as D^2 < (Y + D)^2 - Y^2 which after expanding the brackets gives D^2 < D^2+ 2DY and so the initial assumption is true i.e. Z - Y < X. Let p^(mt) be part of the prime factor decomposition of X where p is one of its prime factors. Let p^(mt) = [Z-Y]/K. The value of K is dependent on the value of Z - Y and the prime factor p of X that is under consideration. K is clearly some fraction that has the prime factor decomposition of its numerator and denominator to be made up of some or all of the prime factors of X only or its numerator and/or denominator could equal 1. Z² - Y² = (Z - Y)(Z + Y) = X² can therefore be rewritten as Z² - Y² = [(Z - Y)/K][Z + Y]K = X² i.e. Z² - Y² = p^(mt)[Z + Y]K = X² It should be clear that p^(mt) = [Z-Y]/K should be a factor of the positive integer [Z + Y]K if p^(mt)[Z + Y]K = X². Algebraic long division of [Z + Y]K by p^(mt) = [Z-Y]/K which equals algebraic long division of [Z + Y]K^2 by [Z-Y] always gives a remainder of 2YK². For p^(mt) = [Z-Y]/K to be a factor of [Z + Y]K then 2YK²/[Z-Y] = 2YK/p^(mt) needs to be a positive integer for each and every prime factor, p, of X. Since X and Y don’t have any common prime factors it is therefore sufficient to consider only 2K/p^(mt) i.e. it needs to be a positive integer for each and every prime factor, p, of X. A little thought will show that since Z - Y < X there must exist at least one prime factor, p, of X that will not make 2K/p^(mt) a positive integer since the denominator of K will be p^j where j ≤ mt and the numerator of K will not have p as a prime factor.
 August 6th, 2015, 08:39 AM #3 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Corollary 2 has been known for hundreds of years, so I'll limit myself to your proof of Corollary 1 which is essentially FLT itself. Your first mistake is the second sentence, in which you assume the thing you're trying to prove. I'm sure there are many further mistakes in your supposed proof, but I don't think it's worth my time to find others pro bono.
August 6th, 2015, 10:26 AM   #4
Senior Member

Joined: Sep 2010

Posts: 221
Thanks: 20

Quote:
 Originally Posted by MrAwojobi ... can therefore be rewritten as Cⁿ - Bⁿ = {[C-B]/K}[Cⁿ⁻ᶦ + Cⁿ⁻²B+ Cⁿ⁻³B² + ....+ CBⁿ⁻² + Bⁿ⁻ᶦ]K = Aⁿ i.e. Cⁿ - Bⁿ = pᵐ [Cⁿ⁻ᶦ + Cⁿ⁻²B+ Cⁿ⁻³B² + ....+ CBⁿ⁻² + Bⁿ⁻ᶦ]K = Aⁿ It should be clear that pᵐ = [C-B]/K should be a factor of the positive integer [Cⁿ⁻ᶦ + Cⁿ⁻²B+ Cⁿ⁻³B² + ....CBⁿ⁻² + Bⁿ⁻ᶦ]K if pᵐ [Cⁿ⁻ᶦ + Cⁿ⁻²B+ Cⁿ⁻³B² + ....+ CBⁿ⁻² + Bⁿ⁻ᶦ]K = Aⁿ. Algebraic long division of [Cⁿ⁻ᶦ + Cⁿ⁻²B+ Cⁿ⁻³B² + .... + CBⁿ⁻² + Bⁿ⁻ᶦ]K by pᵐ = [C-B]/K which equals algebraic long division of [Cⁿ⁻ᶦ + Cⁿ⁻²B+ Cⁿ⁻³B² + ....+ CBⁿ⁻² + Bⁿ⁻ᶦ]K² by (C-B) always gives a remainder of nBⁿ⁻ᶦK².
What should be clear is absolutely unclear, instead it is wrong. Why divisor of C-B must divide the polynomial in brackets if the long division of the latter by C-B being performed before the birth of p^m (not after all manipulations with it) would give remainder coprime with C-B?
It seems you repeat your old scheme somehow transformed.

 August 6th, 2015, 12:17 PM #5 Senior Member   Joined: Aug 2010 Posts: 158 Thanks: 4 I have simply used proof by contradiction i.e. the initial assumption that FLT is false which ends up with a contradiction at the end of my proof. So read the whole of my proof CRGreathouse before you dismiss it willy nilly.
 August 6th, 2015, 12:32 PM #6 Senior Member   Joined: Aug 2010 Posts: 158 Thanks: 4 McPogor, if you spend more time to reason out what is unclear to you then maybe it will become clear. How you cannot see that if p^m is a factor of A then it should also be a factor of A^n/p^m which is essentially the polynomial term multiplied by K you refer to is beyond me.
August 6th, 2015, 02:09 PM   #7
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
 Originally Posted by MrAwojobi I have simply used proof by contradiction
No. A proof by contradiction has you assume some proposition $P$, prove a contradiction, and then conclude $\neg P.$ You assume P, prove P, and then conclude P, which is invalid.

 August 6th, 2015, 03:04 PM #8 Senior Member   Joined: Aug 2010 Posts: 158 Thanks: 4 You are wrong about what you claim I have done CRGreathouse. What I have done is to assume that FLT is an equation, treated it as an equation and I show that it ends up being an inequation. What I have done is a proof by contradiction because my initial assumption was eventually shown by me to be impossible.
 August 6th, 2015, 03:10 PM #9 Senior Member   Joined: Apr 2015 From: Barto PA Posts: 170 Thanks: 18 Someone recently posted an alleged proof of FLT along the same 'lines' as your argument. The problem is that, in both arguments, it was not shown how the case n = 2 is not contradict- ed (considering C - B can be factored if n is ANY positive integer). So your first problem is to avoid that contradiction.
August 6th, 2015, 11:04 PM   #10
Math Team

Joined: Nov 2014
From: Australia

Posts: 689
Thanks: 244

Quote:
 Originally Posted by MrAwojobi Proof of Corollary 1 The first step of the proof is to show that C - B < A if Cⁿ - Bⁿ = Aⁿ. Assume C - B < A.
I believe this is the line that CRG is talking about.

 Tags fermat, proof, simpler, theorem

,

,

,

,

### Willeys proof of FLT

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post MrAwojobi Number Theory 9 April 15th, 2015 12:59 AM MrAwojobi Number Theory 39 August 5th, 2014 11:34 AM MrAwojobi Number Theory 20 June 16th, 2014 09:32 PM jhon13 Algebra 4 May 24th, 2012 09:26 AM gyro Number Theory 7 May 9th, 2012 08:05 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top


text:
Produced in R version 3.5.2.

Why fit a deterministic process model?

• We’re focusing on biological dynamic systems, which are typically far from perfectly predictable.

• Deterministic latent process models are perfectly predictable, given the parameter values and initial conditions. One might therefore expect that these determinstic process models are problematic as statistical descriptions of unpredictable systems.

• Exception: an imperfectly measured chaotic system is both deterministic and unpredictable. However, there has been little success using this class of models for fitting biological systems.

• Exception: for short time series, the role of dynamic stochasticity may be negligible compared to measurement error, parameter uncertainty and uncertainty about initial values.

• Deterministic latent process models are useful as a benchmark when fitting POMP models.

Benchmarking

• Recall that it is statistically meaningful to compare likelihoods between entirely different classes of models for the same data, for example by AIC.

• A benchmark is a simple model that is fitted with the goal of providing a sanity check on a more sophisticated model. We believe that the complex model should fit the data better, but we want to check!

• Some simple benchmarks can be constructed with relatively little effort:

• independent, identically distributed observations.

• ARMA models are appropriate for time series which appear stationary, perhaps after differencing.

• Regression models, including nonlinear regression models such as ordinary differential equation models for compartment models.

The likelihood for a deterministic latent process

Suppose that the latent process is deterministic. In our POMP notation, this lets us write the latent process as $X_{n}=x_n(\theta),$ so that the latent process is a known and non-random function of $$\theta$$ for each $$n$$. What is the likelihood?

Since the probability of the observation, $$Y_n$$, depends only on $$X_n$$ and $$\theta$$, and since, in particular $$Y_{m}$$ and $$Y_{n}$$ are independent given $$X_{m}$$ and $$X_{n}$$, we have ${\mathcal{L}}(\theta) = \prod_{n} f_{Y_n|X_n}\big(y_n^*;x_n(\theta),\theta\big)$ or $\ell(\theta) = \log{\mathcal{L}}(\theta) = \sum_{n} \log f_{Y_n|X_n}\big(y_n^*;x_n(\theta),\theta\big).$ The following diagram illustrates this.

In this diagram, $$\hat y_n$$ refers to the model prediction, $$\hat y_n = {\mathbb{E}\left[{Y_n \vert X_n=x_n(\theta)}\right]}$$, and $$y_n^*$$ is data.


text:
# Also in the Article

Phylogenetic and population genetic analysis
This protocol is extracted from research article:
A multihost bacterial pathogen overcomes continuous population bottlenecks to adapt to new host species

Procedure

To infer the isolate genealogies and branch lengths, we manually constructed core genome SNP alignments from the variants characterized and used them to build minimum evolution phylogenetic trees using the maximum composite likelihood method in MEGA (Molecular Evolutionary Genetics Analysis) (59). This method was used because of the short evolutionary frames and previous knowledge on the transmission chains. From the variants identified, we estimated the substitution rates as described in Eq. 1: number of mutations (m) divided by the genome size (N) times the generations (t/g). Considering a replication time of 30 min for S. aureus, 1 year is approximately equivalent to 18,000 generations.$μ=mN*(tg)$(1)

To examine within-host dynamics, we calculated the total number of SNPs per isolate, as well as fixed and variable SNPs present in each of the three isolates from individual sheep. We applied a general linear regression model on SNP counts versus number of days to estimate differences between the molecular clocks for transmissions and within single host population dynamics. Pairwise genetic distances were calculated as the number of SNPs between two isolates from the same host.

Note: The content above has been extracted from a research article, so it may not display correctly.

Q&A


text:
# Tag Info

## New answers tagged group-theory

0

In the absence of Yukawa couplings (only kinetic terms), the SM has the global flavor symmetry: $$G_{y=0} = U(N_f)^5=U(3)^5$$ Because there are 5 distinct representations in the SM (3 for quarks: $u_R$, $d_R$, $Q_L$; and 2 for leptons: $e_R$, $L_L$). However, $U(N) \sim SU(N)\times U(1)$, so the group can also be written as: $$G_{y=0} = SU(3)^5 \times ... 0 I often see \mathrm{SU}{(3)}_\text{flavor}. However, I have seen$$\mathrm{U}(3)_\mathrm L \times \mathrm{U}(3)_\mathrm R = \mathrm{SU}(3)_\mathrm L \times \mathrm{SU}(3)_\mathrm R \times \mathrm{U}(1)_\text{vector} \times \mathrm{U}(1)_\text{axial}$$where the last one is broken by the quantum anomaly. See slide 14 in this lecture summary of Theoretical ... 1 Your SU(3)\otimes SU(3)={\bf 1}\oplus {\bf 8} above is a chimaeric typo from hell. OK, I'll just give you the self-evident answers, but they would be meaningless junk numbers if you failed to reproduce them directly on the basis of your SU(3) text or the WP article which explains the rules and the Dynkin representation notation, D(p,q), which connects to ... 1 Well, you might have spared yourself confusion and grief by checking your peculiar language in SO(3), which any undergraduate is familiar with. Let me illustrate this for SO(3), before moving on to the much messier SU(3). For SO(3), Kronecker-composing two vectors (spin 1, so 3 s) yields a spin 2 quintet (call it φ, so 5), a triplet (π) and a singlet (s), ... 3 The way to do this is using the Wigner-Eckart theorem. The way it is applied to your problem is as follows:$$ \left\langle nlm |\vec{r}| n'l'm'\right\rangle = \left\langle nl ||\vec{r}|| n'l'\right\rangle \left\langle l' m' 1 q | l m\right\rangle  where the second factor is a Clebsch-Gordan coefficient and $q=-1,0,1$ indicates the type of transition. For ...

0

Subalgebras whose root system is not a subset of the root system of the original algebra are called special subalgebras. Therefore, the generators are not a subset of the original's group generators. That is not quite right. A special subalgebra is one such that their step operators do not form a subset of the algebra step operators.That is what is ...

0

It results from the combination of two facts: $i$) the embedding of $U(1)_Y$ into $SU(2)_R \times U(1)_{B-L}$, and $ii$) the normalization of the $U(1)$ charges. Let me take the simpler chain: $SU(2)_L \times SU(2)_R \times U(1)_{B-L} \to SU(2)_L \times U(1)_Y$. $i$) At the scale of the left-right symmetry, the hypercharge gets merged into $SU(2)_R \times ... 3 Apologies for not producing a most general answer for arbitrary Lie groups, (which you might tease with great effort out of WP ), but only a trail-map for your particular (charmed!) problem. I call it charmed because it should remind you of the Lorentz group, with a,b,c parameterizing Kx,Ky,Kz boosts and d,e,f the three J rotation angles. Decent treatments ... 2 This is the prototypical example of a superselection rule. The operator$U(2\pi)$commutes with all observables (because it represents a full rotation, and is hence physically a "do nothing" operator), and yet is not a multiple of the identity (because it is -1 on the fermionic and 1 on the bosonic parts of the Hilbert space). Therefore, the representation ... 2 The spin$s$of a particle characterizes how the rotation generators act on it. In$D$dimensions, you represent the little group$SO(D-1)$for massive particles and$SO(D-2)$for massless ones. In fact, you really need to consider its universal cover$\textrm{Spin}(n)$which happen to be just its double cover. Now, you can define the spin to be the largest ... 1 To a given Lie algebra$\mathfrak g$there is a unique group$\tilde G$, called the universal covering group, with the property of being simply connected. For example, the covering group of the algebra$\mathfrak{su}(2)$is$SU(2)$. The other groups,$\{G\}$, associated to the same algebra can be obtained from the covering group in the following way ... 4 The vector$(0,0,0,v)is left invariant by the set of matrices of the form \begin{align*} M=\begin{bmatrix} R & \vec 0 \\ \vec 0^T & 1\end{bmatrix} \end{align*} where\det(M)=\det(R)=1$and$M^{-1}=M^T$implies$R^{-1}=R^T$. By definition,$SO(3)$is the group of 3 by 3 orthogonal matrices with determinant 1. In general, you need to know the Lie ... 0 Yes, any group can be a gauge group. To each oriented edge of the lattice you assign a group element, with the opposite orientations of an edge associated to inverse group elements. The observables are conjugacy classes of products of group elements around a loop of oriented edges. The most basic such observable is the product of group elements around an ... 0 (I) Assuming there are$N$distinct fermions in your Lagrangian (e.g. quarks in the standard model), the kinetic term will have the$U(N)\times U(N)$symmetry. This symmetry is broken by the mass term, however, which couples fermions with different handedness. (II) If$V$is the fundamental representation of a Lie group (with dual/conjugate representation ... 1 Yes, the first part of your question is appreciated and answered soundly. The fermion kinetic term splits into two independent parts involving left and right Weyl spinors respectively, so each is independent under a separate U(N) as your wrote down. The second question is a matter of language. A generator is a matrix with one adjoint index, a here, ranging ... 0 I will talk about$SU(3) \times SU(2)$. First, a matrix$T_3 \in SU(3)$acts in the fundamental representation on$\mathbb C^3$in the following way: A vector$\vec v \in \mathbb C^3$with components$v_i$is mapped to$v'_i = (T_3)_{ij} v_j$. Similarly, a$T_2 \in SU(2)$acts on$\vec w \in \mathbb C^2$as$w'k = (T_2)_{kl} w_l$. The bifundamental ... 2 Anthony Zee just came out with Group Theory in a Nutshell for Physicists - covers most of what a undergrad physics student needs including finite groups and representations, except Young diagrams. 2 Let$\phi : \mathbb{R}^4\to V$be a field with (complex) target vector space$V$, transforming in a finite-dimensional projective representation$\rho_\text{fin} : \mathrm{SO}(1,3)\to\mathrm{U}(V)$. As it is a field, the representation of the translations$\mathbb{R}^4$on$V$is the trivial one, since the field transforms as$\phi(x)\overset{x\mapsto ...

2

I cannot quite vouch for exhaustive panoramas, but the crucial point is that GL(N), SU(N) matrices are representable in a nonhermitean basis discovered by Sylvester in 1882, the clock and shift matrices which he called nonions for N=3 (long before the Gell-Mann basis!), sedenions, etc. Their braiding relations, and maximal grading, and hence commutators, ...

Top 50 recent answers are included


text:
It is currently 19 Feb 2019, 16:48

### GMAT Club Daily Prep

#### Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

# If a turtle traveled of a mile in 5 minutes, what was its sp

Author Message
TAGS:
GRE Prep Club Legend
Joined: 07 Jun 2014
Posts: 4856
GRE 1: Q167 V156
WE: Business Development (Energy and Utilities)
Followers: 102

Kudos [?]: 1741 [0], given: 397

If a turtle traveled of a mile in 5 minutes, what was its sp [#permalink]  18 Jun 2018, 14:48
Expert's post
00:00

Question Stats:

87% (00:51) correct 12% (00:00) wrong based on 8 sessions
If a turtle traveled $$\frac{1}{30}$$ of a mile in 5 minutes, what was its speed in miles per hour?

(A) 0.02
(B) 0.16
(C) 0.4
(D) 0.6
(E) 2.5
[Reveal] Spoiler: OA

_________________

Sandy
If you found this post useful, please let me know by pressing the Kudos Button

Try our free Online GRE Test

Director
Joined: 20 Apr 2016
Posts: 817
WE: Engineering (Energy and Utilities)
Followers: 9

Kudos [?]: 588 [0], given: 113

Re: If a turtle traveled of a mile in 5 minutes, what was its sp [#permalink]  02 Jul 2018, 05:04
sandy wrote:
If a turtle traveled $$\frac{1}{30}$$ of a mile in 5 minutes, what was its speed in miles per hour?

(A) 0.02
(B) 0.16
(C) 0.4
(D) 0.6
(E) 2.5

In 5 minutes the turtle travelled = $$\frac{1}{30}$$ of mile

Therefore in 60 minutes the turtle travelled = $${\frac{1}{(30 * 5)}} * 60 = 0.4 miles/hr$$
_________________

If you found this post useful, please let me know by pressing the Kudos Button

Rules for Posting https://greprepclub.com/forum/rules-for ... -1083.html

GRE Prep Club Legend
Joined: 07 Jun 2014
Posts: 4856
GRE 1: Q167 V156
WE: Business Development (Energy and Utilities)
Followers: 102

Kudos [?]: 1741 [0], given: 397

Re: If a turtle traveled of a mile in 5 minutes, what was its sp [#permalink]  07 Jul 2018, 04:48
Expert's post
Explanation

The turtle traveled $$\frac{1}{30}$$of a mile (D) in 5 minutes (t), which is $$\frac{1}{12}$$of an hour. Using the D = RT formula, solve for r:

$$\frac{1}{30}=\frac{1}{12} r$$

0.4 = r
_________________

Sandy
If you found this post useful, please let me know by pressing the Kudos Button

Try our free Online GRE Test

Re: If a turtle traveled of a mile in 5 minutes, what was its sp   [#permalink] 07 Jul 2018, 04:48
Display posts from previous: Sort by


text:
Machine Learning

# Prediction intervals for Random Forests

An aspect that is important but often overlooked in applied machine learning is intervals for predictions, be it confidence or prediction intervals. For classification tasks, beginning practitioners quite often conflate probability with confidence: probability of 0.5 is taken to mean that we are uncertain about the prediction, while a prediction of 1.0 means we are absolutely certain in the outcome. But there are two concepts being mixed up here. A prediction of 0.5 could mean that we have learned very little about a given instance, due to observing no or only a few data points about it. Or it could be that we have a lot of data, and the response is fundamentally uncertain, like flipping a coin.

For regression, a prediction returning a single value (typically meant to minimize the squared error) likewise does not relay any information about the underlying distribution of the data or the range of response values we might later see in the test data.

Looking at the following plots, both the left and right plot represent similar, learned models for predicting Y from X. But while the model predictions would be similar, confidence in them would be quite different for obvious reasons: we have much less and more spread out data in the second case.

A useful concept for quantifying the latter issue is prediction intervals. A prediction interval is an estimate of an interval into which the future observations will fall with a given probability. In other words, it can quantify our confidence or certainty in the prediction. Unlike confidence intervals from classical statistics, which are about a parameter of population (such as the mean), prediction intervals are about individual predictions.

For linear regression, calculating the predictions intervals is straightforward (under certain assumptions like the normal distribution of the residuals) and included in most libraries, such as R’s predict method for linear models.

But how to calculate the intervals for tree based methods such as random forests?

### Quantile regression forests

A general method for finding confidence intervals for decision tree based methods is Quantile Regression Forests.
The idea behind quantile regression forests is simple: instead of recording the mean value of response variables in each tree leaf in the forest, record all observed responses in the leaf. The prediction can then return not just the mean of the response variables, but the full conditional distribution $$P(Y \leq y \mid X = x)$$ of response values for every $$x$$. Using the distribution, it is trivial to create prediction intervals for new instances simply by using the appropriate percentiles of the distribution. For example, the 95% prediction intervals would be the range between 2.5 and 97.5 percentiles of the distribution of the response variables in the leaves. And of course one could calculate other estimates on the distribution, such as median, standard deviation etc. Unfortunately, quantile regression forests do not enjoy too wild of a popularity. While it is available in R’s quantreg packages, most machine learning packages do not seem to include the method.

### Random forests as quantile regression forests

But here’s a nice thing: one can use a random forest as quantile regression forest simply by expanding the tree fully so that each leaf has exactly one value. (And expanding the trees fully is in fact what Breiman suggested in his original random forest paper.) Then a prediction trivially returns individual response variables from which the distribution can be built if the forest is large enough. One caveat is that expanding the tree fully can overfit: if that does happen, the intervals will be useless, just as the predictions. The nice thing is that just like accuracy and precision, the intervals can be cross-validated.

### Example

Let’s look at the well-known Boston housing dataset and try to create prediction intervals using vanilla random forest from scikit-learn:

from sklearn.ensemble import RandomForestRegressor
import numpy as np
X = boston["data"]
Y = boston["target"]
size = len(boston["data"])

We’ll use 400 samples for training, leaving 106 samples for test. The size of the forest should be relatively large, so let’s use 1000 trees.

trainsize = 400
idx = range(size)
#shuffle the data
np.random.shuffle(idx)
rf = RandomForestRegressor(n_estimators=1000, min_samples_leaf=1)
rf.fit(X[idx[:trainsize]], Y[idx[:trainsize]])

We can now define a function to calculate prediction intervals for every prediction:

def pred_ints(model, X, percentile=95): err_down = [] err_up = [] for x in range(len(X)): preds = [] for pred in model.estimators_: preds.append(pred.predict(X[x])[0]) err_down.append(np.percentile(preds, (100 - percentile) / 2. )) err_up.append(np.percentile(preds, 100 - (100 - percentile) / 2.)) return err_down, err_up

Let’s compute 90% prediction intervals and test how many observations in the test set fall into the interval.

err_down, err_up = pred_ints(rf, X[idx[trainsize:]], percentile=90) truth = Y[idx[trainsize:]]
correct = 0.
for i, val in enumerate(truth): if err_down[i] <= val <= err_up[i]: correct += 1
print correct/len(truth)

0.905660377358

This is pretty close to what we expected: 90.6% of observations fell into the prediction intervals. Plotting the true values and predictions together with error bars visualizes this nicely.

If we set prediction interval to be 50% for the same model and test data, we see 51% of predictions fall into the interval, again very close to the expected value . Plotting the error bars again, we see that they are significantly smaller:

What can also be observed on the plot that on average, predictions that are more accurate have smaller prediction intervals since these are usually “easier” predictions to make. The correlation between absolute prediction error and prediction interval size is ~0.6 for this dataset.

And again, just as one can and should use cross-validation for estimating the accuracy of the model, one should also cross-validate the intervals to make sure that they give unbiased results on the particular dataset at hand. And just like one can do probability calibration, interval calbiration can also be done.

## Caveats

There are situations when the tree is not expanded fully, such that there is more than one data point per leaf. This can happen because either
a) a node is already pure, so splitting further makes no sense, or
b) the node is not pure, but the feature vector is exactly the same for all responses, so there isn’t anything to do a further split on.

In case of a), we know the response and node size, so we still know the distribution perfectly and can use it for calculating the intervals. If case b) happens, we are in trouble, since we don’t know the distribution of responses in the non-expanded leaf. Luckily, the latter very rarely happens with real world datasets and is easy to check for.

Utilizing prediction intervals can be very beneficial in many machine learning and data science tasks, since they can tell a lot about the underlying data that we are learning about and provide a simple way to sanity check our results. While they seem to enjoy relatively widespread use for linear models due to the ease of access with these methods, they tend to be underutilized for tree-based methods such as random forests. But actually they are relatively straightforward to use (keeping the caveats in mind) by utilizing the fact that a random forest can return a conditional distribution instead of just the conditional mean. In fact, estimating the intervals this way can be more robust than prediction intervals for linear methods, since it does not rely on the assumption of normally distributed residuals.