text:
# NonlinearModelFit: fit a vector-valued function to a data vector

I have a vector of data points:

data = 10 Sin[#/10] + RandomVariate@NormalDistribution[] & /@
Range[200];

And I have model that provides the complete data vector as value

matrix = Table[i (Sin[j/10]), {i, 20}, {j, 200}];
weights[a_] := Table[PDF[NormalDistribution[a, 1], i], {i, Range@20}];
model[a_] := weights[a].matrix;

model[10] is a good approximation of data.

They way I currently determine the fit parameters is by using FindMinimum and explicitly minimize the fit penalty:

FindMinimum[
Total[(data - model[a])^2],
{{a, 10}}
]

This works nice. But the evaluation of fit statistics like error volumes is very tedious because the underlying matrix and the model function is rather complex. When fitting with NonlinearModelFit instead, a lot of those statistics are readily available. But I have struggled to adapt it accordingly:

Something like

NonlinearModelFit[
data,
model[a],
{{a, 1}},
var
]

Unfortunately, there are problems. Can it be adapted? I dont actually need any variables to fit the expressions.

Kind regards

• Welcome to Mathematica.SE! I suggest the following: 1) As you receive help, try to give it too, by answering questions in your area of expertise. 2) Read the faq! 3) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Also, please remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! – user9660 Apr 16 '15 at 18:22
• Doesn't NonlinearModelFit[ data, model[a], {{a, 10}}, var, Method -> "NMinimize" ] return the same or a better solution than your FindMinimum? – Dr. belisarius Jul 17 '15 at 19:27

I think using Quantile regression might do what you want. Quantile regression uses a minimization algorithm and if the fitting functions are B-splines you do not need to specify a model.

Similar problem and solution are discussed in more detail in Find Fit for Non-linear data .

If you really want to use the vectors of the matrix then you can use QuantileRegressionFit in the package linked below. (That is not straightforward, though. The matrix have to be converted into a list of functions, by say interpolation. I can work this solution out if it is of interest.)

The following steps apply Quantile regression with B-splines for the data in the question.

First, get the QuantileRegression.m package from MathematicaForPrediction at GitHub:

Import["https://raw.githubusercontent.com/antononcube/MathematicaForPrediction/master/QuantileRegression.m"]

Do the data generation with the command in the question:

data = 10 Sin[#/10] + RandomVariate@NormalDistribution[] & /@ Range[200];

data = Transpose[{Range[Length[data]], data}];

Find the regression quantile using B-splines of 2nd order:

qfunc = Simplify[
QuantileRegression[data, 12, {0.5}, InterpolationOrder -> 2][[1]]];

Plot the data and the fitted curve:

dGr = ListPlot[data, PlotRange -> All, PlotStyle -> Red];
qfGr = Plot[qfunc[x], {x, Min[data[[All, 1]]], Max[data[[All, 1]]]}];
Show[{dGr, qfGr}, Frame -> True]

Here is the fitted function after using PiecewiseExpand and Simplify:

qfunc = Evaluate[Simplify[PiecewiseExpand[qfunc[[1]]]]] &;
qfunc

Here is an example of approximation error statistics:

ListPlot[Map[{#[[1]], (qfunc[#1[[1]]] - #1[[2]])/#1[[2]]} &, data],
Filling -> Axis, Frame -> True]

As I understand the question, I think you are making things more difficult then they need be by calculating model fits in matrix. It seems you have already determined that the form of your model is $b \sin[\frac{x}{10}]$ and they you just need to fit $b$. This is exactly what NonlinearModelFit does. So you don't need to calculate out matrix and do your own minimisation function.

All that is needed is the data and the form.

data = 10 Sin[#/10] + RandomVariate@NormalDistribution[] & /@ Range[200];
fm = NonlinearModelFit[data, b Sin[x/10], {b}, x]
fm["BestFitParameters"]
fm["RSquared"]

Since data is a vector then it is fitted against successive x values (1, 2, ...). This is the first type of call listed in NonlinearModelFit's documentation. The fitted values and all the fit statistics are in fm. See the documentation for how to access them. I've tried a few executions and get very close to b -> 10 with perfect r-squared.

Hope this helps.

• Thanks for the reply. Unfortunately, the simple case of the example is not present in my real problem. There, the function to be fitted is not a sine wave but the result of a multidimensional convolution integral. Calculating all of those integrals using the explicit form NIntegrate is extremely time consuming. A fast way is to replace all the convolutions by dot products weighing a high-dimensional tensor of possible function values. This tensor is called "matrix" in my example and the individual convolutions are performed by dot-mulitcation by a weighting vector "weights". – tobalt Apr 22 '15 at 20:10


text:
# XXIV International Workshop on Deep-Inelastic Scattering and Related Subjects (DIS16)

Apr 11 – 15, 2016
DESY Hamburg
Europe/Berlin timezone

## Measurements of ttbar+X using the ATLAS detector

Apr 13, 2016, 3:10 PM
15m
SR4a (DESY Hamburg)

### SR4a

#### DESY Hamburg

Heavy Flavours (Charm, Beauty and Top)

### Speaker

Alexander Khanov (Oklahoma State)

### Description

The large centreofmass energy available at the protonproton collider LHC allows for the copious production of top quark pairs in association with other final state particles at high transverse momentum. The ATLAS experiment has measured several final state observables that are sensitive to additional radiation in top antitop quark final states. Results on the top production in association with W and Z bosons at both 8 and 13 TeV are presented along with measurements of the cross section for production with an associated isolated photon at 8 TeV. Analyses probing the top pair production with additional QCD radiation include the multiplicity of jets for various transverse momentum thresholds in the 13 TeV data. These measurements are compared to modern Monte Carlo generators based on NLO QCD matrix element or LO multileg matrix elements.

### Primary author

Dr Elizaveta Shabalina (University of Gottingen)

 Slides

format: plain


text:
1. ## riemann integral

If f is continous on [a,b],then f belongs to R[a,b],R-RIEMANN INTEGRAL

A continous function on [a,b] is always Riemann integrable. Since $f$ is continous it is bounded by extreme value theorem. Furthermore, continous functions on compact (in particular closed) sets are uniformly continous. To prove Riemann integrability we need to show $S_P(f) - s_P(f) < \epsilon$ where $P$ is a partition of $[a,b]$. Given any $\epsilon > 0$ there is a $\delta > 0$ such that $|x-y|<\delta \mbox{ and }x,y\in [a,b]\implies |f(x)-f(y)|<\epsilon$. Pick a partition $P$ such that $(x_i - x_{i-1}) < \delta$. Then $f$ assumes its maximum and minimum on each interval and so $S_P(f) - s_P(f) < \epsilon(b-a)$, and this quantity can be made arbitrary small.


text:
## Quasicone metric spaces and generalizations of Caristi Kirk’s theorem.(English)Zbl 1197.54051

L.-G. Huang and X. Zhang [J. Math. Anal. Appl. 332, No. 2, 1468–1476 (2007; Zbl 1118.54022)] introduced the notion of cone metric spaces (CMS) by replacing the real numbers by an ordered Banach space. In the present paper the authors extend some of the results in J. Caristi [Trans. Am. Math. Soc. 215, 241–251 (1976; Zbl 0305.47029)] and I. Ekeland [C. R. Acad. Sci., Paris, Sér. A 275, 1057–1059 (1972; Zbl 0249.49004)] to CMS and quasicone metric spaces. They prove, amongst others, the following theorems:
Theorem 2.4. Let $$(X,d)$$ be a complete CMS, $$P$$ a strongly minihedral normal cone, and $$\varphi: X\to P\subset E$$ ($$E$$ is a real Banach space) a lower-semicontinuous function. Then each selfmap $$T: X\to X$$ satisfying
$d(x, Tx)\leq\varphi(x)-\varphi(Tx),\quad\forall x\in X,$
has a fixed point in $$X$$.
Theorem 2.5. Let $$\varphi: X\to E$$ be a lower-semicontinuous function on a complete CMS, where $$P$$ is a strongly minihedral normal cone. If $$\varphi$$ is bounded below, then there exists $$y\in X$$ such that $\varphi(y)< \varphi(x)+ d(x,y),\quad\forall x\in X,\;\text{where }x\neq y.$

### MSC:

 54H25 Fixed-point and coincidence theorems (topological aspects) 47H10 Fixed-point theorems

### Keywords:

cone; fixed points

### Citations:

Zbl 1118.54022; Zbl 0305.47029; Zbl 0249.49004
Full Text:

### References:

 [1] Huang, L-G; Zhang, X, Cone metric spaces and fixed point theorems of contractive mappings, Journal of Mathematical Analysis and Applications, 332, 1468-1476, (2007) · Zbl 1118.54022 [2] Rezapour, Sh; Hamlbarani, R, Some notes on the paper: “Cone metric spaces and fixed point theorems of contractive mappings”, Journal of Mathematical Analysis and Applications, 345, 719-724, (2008) · Zbl 1145.54045 [3] Turkoglu D, Abuloha M: Cone metric spaces and fixed point theorems in diametrically contractive mappings.Acta Mathematica Sinica, English Series, submitted · Zbl 1203.54049 [4] Turkoglu, D; Abuloha, M; Abdeljawad, T, KKM mappings in cone metric spaces and some fixed point theorems, Nonlinear Analysis: Theory, Methods and Applications, 72, 348-353, (2010) · Zbl 1197.54076 [5] Şahin, İ; Telci, M, Fixed points of contractive mappings on complete cone metric spaces, Hacettepe Journal of Mathematics and Statistics, 345, 719-724, (2008) · Zbl 1190.47058 [6] Rezapour Sh, Derafshpour M, Hamlbarani R: A Review on Topological Properties of Cone Metric Spaces.Analysis, Topology and Applications 2008 (ATA2008), the 30th of May to the 4th of June, 2008, Technical Faculty, Cacak, University of Kragujevac Vrnjacka Banja, Serbia [7] Haghi RH, Rezapour Sh: Fixed points of multifunctions on regular cone metric spaces.Expositiones Mathematicae. In press · Zbl 1193.47058 [8] Rezapour, Sh; Haghi, RH, Fixed point of multifunctions on cone metric spaces, Numerical Functional Analysis and Optimization, 30, 825-832, (2009) · Zbl 1171.54033 [9] Klim, D; Wardowski, D, Dynamic processes and fixed points of set-valued nonlinear contractions in cone metric spaces, Nonlinear Analysis: Theory, Methods and Applications, 71, 5170-5175, (2009) · Zbl 1203.54042 [10] Caristi, J, Fixed point theorems for mappings satisfying inwardness conditions, Transactions of the American Mathematical Society, 215, 241-251, (1976) · Zbl 0305.47029 [11] Ekeland, I, Sur LES problèmes variationnels, Comptes Rendus de l’Académie des Sciences, 275, a1057-a1059, (1972) · Zbl 0249.49004 [12] Deimling K: Nonlinear Functional Analysis. Springer, Berlin, Germany; 1985:xiv+450. · Zbl 1257.47059 [13] Ćirić, LB, On a common fixed point theorem of a Greguš type, Publications de l’ Institut Mathématique, 49, 174-178, (1991) · Zbl 0753.54023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.


text:
# Isomorphism of ideals

I have a question related to this post: http://mathoverflow.net/questions/60412/generic-liftings-of-a-regular-sequence-on-the-initial-ideal

Suppose $I$ and $J$ are ideals in $R=k[x_1,\ldots,x_n]$ with $In(I)\cong In(J)$ where $In(I)$ is the ideal generated by the leading term of all those $f\in I$, with the additional assumption that the minimal number of generators generating $I$ equals the minimal number of generators generating $J$. Then doesn't that imply that $R/I$ is isomorphic to $R/J$?

Can someone give me a counter-example to this or refer me to a reference?

Addendum: suppose $k$ is algebraically closed.

-
What does it mean for two ideals to be isomorphic? What do you mean by "the number of generators"? The minimal number? –  Qiaochu Yuan May 22 '12 at 21:29
Thanks Qiaochu. I meant $R/I$ is isomorphic to $R/J$, and yes, I meant the minimal number of generators. I'll make the appropriate edits to the post. –  math-visitor May 22 '12 at 21:32
Also, what do you mean by leading term? Are you fixing a monomial order? –  Qiaochu Yuan May 22 '12 at 21:36
Yes, we fix a monomial order. Any monomial order will do-- we just need to fix it throughout the argument. –  math-visitor May 22 '12 at 21:38
This is quite false even when $n = 2$ and even for ideals which are generated by a single element. Take $I = (x^2 - y), J = (x^2 - y^2)$ where $x > y$ in the monomial order; then $k[x, y]/I \cong k[x]$ but $k[x, y]/J$ has a zero divisor, namely $x + y$.
Edit: Indeed it is false even when $n = 1$. Take $I = (x^2), J = (x^2 - x)$.
Ah, thanks Qiaochu! ${}{}{}$ –  math-visitor May 22 '12 at 21:45


text:
# Is this behaviour normal for a Lennard-Jones monte carlo simulation?

I am simulating a Lennard-Jones fluid using MC simulation. The code always uses a reduced unit. I want to find the potential energy of the system. Periodic boundary condition implemented. I have simulated with 2 particles to find out if the simulation gives correct result. For 2 particles the equilibrium separation is $$2^{1/6}$$ , so energy is -1. (Take $$\sigma =1$$) . The code is below.

import numpy as np
import random
import matplotlib.pyplot as plt

# reduced units:
#T(reduced) = kT/epsilon | r(reduced) = r/sigma | U(reduced) = U/epsilon
# General Parameters
DIM=2
npart=2
L=10
volume=L**DIM
density=npart/volume
print("volume = ", volume, " density = ", density,"Number of atoms =",npart)
print ("L is " ,L)
T = 2; Nsteps = 50000; maxdr =0.0001;printfeq=100;DIM=2
#System parameters
beta=1/T

def E(dr2):
"""Returns LJ 6-12 interaction energy for a particular distance between
2 particles"""

return  4*((dr2)**(-6) - (dr2)**(-3)) # r is given in unit of sigma. dr2 is distance^2

def P(x):
""" gives boltzman factor for position at x"""
return np.exp(-(beta*E(x)))

def PBC(L,pos):

"""PBC check for dim dimension system with equal length L in all dimension.
INPUT : position array,length,dimension
OUTPUT: New position
"""
for k in range(DIM):
if (pos[k]>0.5):
pos[k]=pos[k]-1
if (pos[k]<-0.5):
pos[k]=pos[k]+1

return (pos)

def distance(current_position):
"""Takes the current position array of the configuration and finds out
distance between each pairs. Neglectd if distance > rcutoff
INPUT: Array of current position of each particles
OUTPUT: Array containing distances between each pair of LJ particles.
"""
Distances=[]
for i in range (npart):
for j in range (i+1,npart):
dr=(current_position[i]-current_position[j])*L
dr2=np.dot(dr,dr)

if (dr2!=0):
Distances.append(dr2)

return Distances

Energy=[0 for _ in range (Nsteps)]
Distances=[0 for _ in range (Nsteps)]
current_position=np.zeros([npart,DIM])

#------------------ Initialise the Setup with particles distributed uniformly ------------

ip=-1
x=0
y=0
lim=int(np.sqrt(npart))+1
for i in range(0,lim):
for j in range(0,lim):
if(ip<npart):
x=i*(1/lim)
y=j*(1/lim)
current_position[ip]=np.array([x,y])
ip=ip+1
else:
break
MassCentre = np.sum(current_position,axis=0)/npart
current_position=current_position-MassCentre

Distances[0]=distance(current_position)

for i in Distances[0]:

Energy[0]+=E(i)
print(Energy[0])

# -------------------------MC Simulation ----------------------------
rejected=0
for step in range(1,Nsteps):
if (step%printfeq==0):
print ("Completed ",step,"steps")
trial_position=np.zeros([npart,DIM])

trial_energy=0

for i in range (npart):

displacex=(random.uniform(0,1)-0.5)*maxdr
displacey=(random.uniform(0,1)-0.5)*maxdr

pos=current_position[i]+np.array([displacex,displacey])
trial_position[i]=PBC(L,pos)
Distances[step]=distance(trial_position)
#print(trial_position)

for i in ((Distances[step])):
trial_energy+= E(i)
if (trial_energy<Energy[step-1]):
current_position=trial_position
Energy[step]=trial_energy
else:
delta=trial_energy-Energy[step-1]
if (random.random()<P(delta)):

current_position=trial_position
Energy[step]=trial_energy

else:
rejected+=1

Energy[step]=Energy[step-1]

print(Energy)
print ("Rejected moves ",rejected,"out of",Nsteps)
steps=np.arange(0,Nsteps)
plt.figure(1)
plt.plot(steps, Energy,'o',label='simulation result')
#plt.plot(steps, Distances,'b-',label='simulation result')
plt.xlabel(' steps')
plt.ylabel('Energy of configuration')
plt.show()

I have used 50000 steps with no separate steps for equilibrium. The output I get is like

I want to know if this behavior is normal. It doesn't seem so. The sudden jump of potential energy to -1. Or am I doing something wrong? In MC I don't have info on kinetic energy, so I can't check energy conservation.Thank you in advance.

There are few issues in your code. The main one is that, in the P(x) function, return np.exp(-(beta*E(x))) should be return np.exp(-(beta*x)).
Then you should increase the maxdr value. I reckon a value of 0.01 should be enough. These two changes are enough to get a plot that looks realistic.
• Sure, but you call it like this: P(delta), where delta is an energy difference. Mar 28 '20 at 17:33


text:
# Møller scattering amplitudes

In order to compute the scattering cross section for Møller scattering, one needs the amplitudes for both the $t$- and the $u$-channel. Since the cross section is proportional to $|\mathcal{M}|^2$, the matrix element squared, and since there are two channels, we will get mixed terms. One of these terms is, after averaging over the possible spin states:

$$-\frac{e^4}{4 t u}\mathop{Tr}\left[ (p_3\!\!\!\!\!/+m)\gamma^\mu(p_1\!\!\!\!\!/+m)\gamma^\beta(p_4\!\!\!\!\!/+m)\gamma_\mu(p_2\!\!\!\!\!/+m)\gamma_\beta \right],$$ where $e$ is the electron charge, $m$ the electron mass, $p_1,p_3$ the momenta of the incoming electrons, $p_2,p_4$ the momenta of the outgoing ones and $\gamma$ the $\gamma$-matrices. $\mathop{Tr}$ stands for the trace of an operator. $t$ and $u$ are Mandelstam variables.

Now, one could simply expand the expression I have to take the trace of but this will lead to an exploding amount of terms. So, is there any smart way of calculating this trace without getting lost in cumbersome calculations?

Typically, one uses the fact that the trace of an odd number of gamma matrices vanishes in $d$ dimensions other than select odd $d$. This allows you to see, by inspection really, the contributing terms. It usually amounts to dropping some mass contributions, for example. In your case, there is more simplication to be made first by anti commuting the $\gamma^{\mu}$ and $\gamma^{\beta}$ so as to e.g rewrite the pair $\gamma^{\mu}\gamma_{\mu} = d1$. This then leaves you with a trace of at most four gamma matrices, which is relatively simple and whose evaluation is explicitly given in the literature.


text:
James Frederick Libby
09 Jul 2019, 11:36
Dear Manish,
There are still a few things to be fixed. Some of which I had already pointed out.
Jim

General
- CP should be in italics everywhere, you have just fixed the cases I highlighted then forgot to do the rest

Page 1

Fig. 1 - the reference for this is not [3], it is where you good the figure from, which I think was the Acheivements paper you originally had there.

Then large -> Then a large

the division symbol (which you thought I suggested because I was commenting that you should remove the colon) should be remove before Eq. 1. No colons are required before Eq. 2 or the definitions of R either.

Page 2

Table 1: Remove Sr. No column

Page 3

the collision data -> collision data

With phase II results, we -> We

last line of Sec. 1: Monte Carlo (MC) -> MC [as it has already been defined]

The study begins with the reconstruction of -> We reconstruct the decay

Distribution -> The distribution

invariant -> the invariant (twice)

Invariant mass -> The invariant mass distribution

are are -> is

D^{0}(hh)->D^{0}(K^+K^-} then delete 'where $h$ is Kaon'

The work...-> Fig. 4 shows the $M_{\rm bc}$ and $\Delta E$ distributions reconstructed from the MC sample; work is in progress to reconstruct $B$ mesons in the Phase II data.

Page 4
The large statistics....Clear ->The full $50~\mathrm{ab}^{-1}$ data sample to be collected by Belle II at SuperKEKB will provide a substantial improvement in the precision measurement of $\phi_3$. A clear

at an -> corresponding to an

Subscribe to this discussion. You will then receive all new comments by email.


text:
# In which of the following circuits is the total voltage drop equal to the sum of the voltage drops in various elements of the circuits?

This question was previously asked in
PGCIL DT Electrical 13 Aug 2021 Official Paper (NR I)
View all PGCIL Diploma Trainee Papers >
1. Series resistance circuit
2. Parallel magnetic circuit
3. Series magnetic circuit
4. Series electric circuit

## Answer (Detailed Solution Below)

Option 4 : Series electric circuit

## Detailed Solution

• In the series Electric circuit, we used the Voltage Division Rule (VDR) of KVL to find the voltage drop across various elements in a given circuit.
• While in the Parallel Electric circuit, we used the Current Division Rule (CDR) of KCL to find the current through various elements in a given circuit.

Explanation:

Kirchhoff’s Voltage Law (KVL): It states that the algebraic sum of all voltage around a close path or loop is zero.

Mathematically, KVL implies that

$$\mathop \sum \limits_{m = 1}^M {v_m} = 0$$

Where M is the number of voltages in a loop or number of branches in a loop

And, vm is mth voltage.

Consider a circuit shown below in which R1 and R2 are two resistance, v1, v2 are two voltage source which causes current (I) flow in the loop.

The sign of voltage drop across the passive element is such a way that the current entering from the positive terminal.

Applying KVL on this circuit

V1 + V4 – IR1 – IR2 = 0

Or, V1 + V4 = IR1 + IR2

Hence, the Sum of Voltage drops = Sum of Voltage rises

Note: KVL deals with the conservation of energy.


text:
Free Version
Moderate

# Parallelogram Law and Right Triangles

LINALG-EF4XYQ

Let $\vec v$ and $\vec w$ be two vectors which form the legs of a right triangle with side lengths $5$, $12$, and $13$.

Find $\lVert v+w\rVert$.

A

$12$

B

$13$

C

$30$

D

$144$

E

$169$


text:
# Compositional Embeddings Using Complementary Partitions for Memory-Efficient Recommendation Systems

Modern deep learning-based recommendation systems exploit hundreds to thousands of different categorical features, each with millions of different categories ranging from clicks to posts. To respect the natural diversity within the categorical data, embeddings map each category to a unique dense representation within an embedded space. Since each categorical feature could take on as many as tens of millions of different possible categories, the embedding tables form the primary memory bottleneck during both training and inference. We propose a novel approach for reducing the embedding size in an end-to-end fashion by exploiting complementary partitions of the category set to produce a unique embedding vector for each category without explicit definition. By storing multiple smaller embedding tables based on each complementary partition and combining embeddings from each table, we define a unique embedding for each category at smaller cost. This approach may be interpreted as using a specific fixed codebook to ensure uniqueness of each category's representation. Our experimental results demonstrate the effectiveness of our approach over the hashing trick for reducing the size of the embedding tables in terms of model loss and accuracy, while retaining a similar reduction in the number of parameters.

## Authors

• 5 publications
• 19 publications
• 17 publications
• 16 publications
• ### High-Performance Training by Exploiting Hot-Embeddings in Recommendation Systems

Recommendation models are commonly used learning models that suggest rel...

• ### Semantically Constrained Memory Allocation (SCMA) for Embedding in Efficient Recommendation Systems

Deep learning-based models are utilized to achieve state-of-the-art perf...
02/24/2021 ∙ by Aditya Desai, et al. ∙ 0

• ### Binary Code based Hash Embedding for Web-scale Applications

08/24/2021 ∙ by Bencheng Yan, et al. ∙ 0

• ### Random Offset Block Embedding Array (ROBE) for CriteoTB Benchmark MLPerf DLRM Model : 1000× Compression and 2.7× Faster Inference

Deep learning for recommendation data is the one of the most pervasive a...
08/04/2021 ∙ by Aditya Desai, et al. ∙ 1

• ### Mixed-Precision Embedding Using a Cache

In recommendation systems, practitioners observed that increase in the n...
10/21/2020 ∙ by Jie Amy Yang, et al. ∙ 0

• ### Category-Aware Location Embedding for Point-of-Interest Recommendation

Recently, Point of interest (POI) recommendation has gained ever-increas...
07/31/2019 ∙ by Hossein A. Rahmani, et al. ∙ 0

• ### Categorical Perception: A Groundwork for Deep Learning

Classification is one of the major tasks that deep learning is successfu...
12/10/2020 ∙ by Laurent Bonnasse-Gahot, et al. ∙ 0

##### This week in AI

Get the week's most popular data science and artificial intelligence research sent straight to your inbox every Saturday.

## 1 Introduction

The design of modern deep learning-based recommendation models (DLRMs) is challenging because of the need to handle a large number of categorical (or sparse) features. For personalization or click-through rate (CTR) prediction tasks, examples of categorical features could include users, posts, or pages, with hundreds or thousands of these different features (Naumov et al., 2019). Within each categorical feature, the set of categories could take on many diverse meanings. For example, social media pages could contain topics ranging from sports to movies.

In order to exploit this categorical information, DLRMs utilize embeddings to map each category to a unique dense representation in an embedded space; see Cheng et al. (2016); He et al. (2017); Wang et al. (2017); Guo et al. (2017); Lian et al. (2018); Zhou et al. (2018b, c); Naumov (2019). More specifically, given a set of categories and its cardinality , each categorical instance is mapped to an indexed row vector in an embedding table , as shown in Figure 1. Rather than predetermining the embedding weights, it has been found that jointly

training the embeddings with the rest of the neural network is effective in producing accurate models.

Each categorical feature, however, could take on as many as tens of millions of different possible categories (i.e., ), with an embedding vector dimension . Because of the vast number of categories, the number of embedding vectors form the primary memory bottleneck within both DLRM training and inference since each table could require multiple GBs to store.111Note that the relative dimensionality significantly differs from traditional language models, which use embedding vectors of length 100 to 500, with dictionaries of a maximum of hundreds of thousands of words.

One natural approach for reducing memory requirements is to decrease the size of the embedding tables by defining a hash function (such as a remainder function) that maps each category to an embedding index, where the embedding size is strictly smaller than the number of categories222We consider the case where the hashing trick is used primarily for reducing the number of categories. In practice, one may hash the categories for indexing and randomization purposes, then apply a remainder function to reduce the number of categories. Our proposed technique applies to the latter case. (Weinberger et al., 2009). However, this approach may blindly map vastly different categories to the same embedding vector, resulting in loss of information and deterioration in model quality. Ideally, one ought to reduce the size of the embedding tables while still producing a unique representation for each category in order to respect the natural diversity of the data.

In addition, DLRMs do not currently exploit the natural partitionable or hierarchical structure that exists within categorical data; in particular, if a categorical feature is naturally partitioned in multiple ways, current models do not capitalize on these partitions to improve model performance or reduce model complexity. Consider, for example, a categorical feature consisting of different cars as part of a dataset to predict the CTR of a particular advertisement. Each car consists of a different make, type, color, year, etc. These properties generate natural partitions of the set of cars. This structure ought to be identified to reduce the dimensionality of the model while constructing meaningful information.

In this paper, we propose an approach for generating a unique embedding for each categorical feature by using complementary partitions of the category set to generate compositional embeddings, which interact multiple smaller embeddings to produce a final embedding. These complementary partitions could be obtained from inherent characteristics of the categorical data, or enforced artificially to reduce model complexity. We propose concrete methods for artificially defining these complementary partitions and demonstrate their usefulness on modified Deep and Cross (DCN) (Wang et al., 2017) and Facebook DLRM networks (Naumov et al., 2019) on the Kaggle Criteo Ad Display Challenge dataset. These methods are simple to implement, compress the model for both training and inference, do not require any additional pre- or post-training processing, and better preserve model quality than the hashing trick.

### 1.1 Related Work

Wide and deep models (Cheng et al., 2016) jointly train both a deep network and linear model to combine the benefits of memorization and generalization for recommendation systems. Factorization machines (Rendle, 2010, 2012) played a key role in the next step of development of DLRMs by identifying that sparse features (induced by nominal categorical data) could be appropriately exploited by interacting different dense representations of sparse features with an inner product to produce meaningful higher-order terms. Generalizing this observation, some recommendation models (Guo et al., 2017; He et al., 2017; Wang et al., 2017; Lian et al., 2018; Zhou et al., 2018c) jointly train a deep network with a specialized model in order to directly capture higher-order interactions in an efficient manner. The Facebook DLRM network (Naumov et al., 2019)

mimics factorization machines more directly by passing the pairwise dot product between different embeddings into a multilayer perceptron (MLP). More sophisticated techniques that incorporate trees, memory, and (self-)attention mechanisms (to capture sequential user behavior) have also been proposed

(Zheng et al., 2018; Zhou et al., 2018a, b; Zhu et al., 2018).

Towards the design of the embeddings, Naumov (2019) proposed an approach for prescribing the embedding dimension based on the amount of information entropy contained within each categorical feature. Yin and Shen (2018) used perturbation theory for matrix factorization problems to similarly analyze the effect of the embedding dimension on the quality of classification. These methods focused primarily on the choice of .

Much recent work on model compression also use compositional embeddings to reduce model complexity; see Shu and Nakayama (2017); Chen et al. (2018). Most of these approaches require learning and storing discrete codes, similar to the idea of product quantization (Jegou et al., 2010), where each category’s index is mapped to its corresponding embedding indices . In order to learn these codes during training, one is required to store them, hence requiring parameters with only potential to decrease . Since in recommendation systems, these approaches unfortunately remain ineffective in our setting.

Unlike prior approaches that focus on reducing , our method seeks to directly reduce the embedding size using fixed codes that do not require additional storage while enforcing uniqueness of the final embedding. Related work by Khrulkov et al. (2019) may be interpreted as a specific operation applied to each element of the embedding table, similar to the framework described here.

### 1.2 Main Contributions

Our main contributions in this paper are as follows:

• We propose a novel modification for reducing the size of the embedding tables while still yielding a unique embedding vector for each category. The trick uses both the quotient and remainder functions to produce two different embeddings, then combines these embeddings to yield the final embedding, called a compositional embedding. This reduces the number of embedding parameters from up to , where is the number of categories and is the embedding dimension.

• We abstract this approach to compositional embeddings based on complementary partitions of the category set. Complementary partitions require each category to be distinct from every other category according to at least one partition. This has the potential to reduce the number of embedding parameters to where is the number of partitions.

• The experimental results demonstrate that our compositional embeddings yield better performance than the hashing trick, which is commonly used in practice. Although the best operation for defining the compositional embedding may vary, the element-wise multiplication operation produces embeddings that are most scalable and effective in general.

Section 2 will provide a simple example to motivate our framework for reducing model complexity by introducing the quotient-remainder trick. In Section 3, we will define complementary partitions, and provide some concrete examples that are useful in practice. Section 4 describes our proposed idea of compositional embeddings and clarifies the tradeoffs between this approach and using a full embedding table. Lastly, Section 5 gives our experimental results.

## 2 A Simple Example

Recall that in the typical DLRM setup, each category is mapped to a unique embedding vector in the embedding table. Mathematically, consider a single categorical feature and let denote an enumeration of .333As an example, if the set of categories consist of , then a potential enumeration of is , , and . Let be its corresponding embedding matrix or table, where is the dimension of the embeddings. We may encode each category (say, category with index ) with a one-hot vector by , then map this to a dense embedding vector by

 xemb=WTei. (1)

Alternatively, the embedding may also be interpreted as a simple row lookup of the embedding table, i.e. . Note that this yields a memory complexity of for storing embeddings, which becomes restrictive when is large.

The naive approach of reducing the embedding table is to use a simple hash function (Weinberger et al., 2009), such as the remainder function, called the hashing trick. In particular, given an embedding table of size where , that is, , one can define a hash matrix by:

 Ri,j={1if jmodm=i0otherwise. (2)

Then the embedding is performed by:

 xemb=˜WTRei. (3)

This process is summarized in Algorithm 1.

Although this approach significantly reduces the size of the embedding matrix from to since , it naively maps multiple categories to the same embedding vector, resulting in loss of information and rapid deterioration in model quality. The key observation is that this approach does not yield a unique embedding for each unique category and hence does not respect the natural diversity of the categorical data in recommendation systems.

To overcome this, we propose using the quotient-remainder trick. Assume for simplicity that divides (although this does not have to hold in order for the trick to be applied). Let “” denote integer division or the quotient operation. Using two complementary functions – the integer quotient and remainder functions – we can produce two separate embedding tables and combine the embeddings in such a way that a unique embedding for each category is produced. This is formalized in Algorithm 2.

More rigorously, define two embedding matrices: and . Then define an additional hash matrix

 Qi,j={1if j∖m=i0otherwise. (4)

Then we obtain our embedding by

 xemb=WT1Rei⊙WT2Qei (5)

where denotes element-wise multiplication. This trick results in a memory complexity of , a slight increase in memory compared to the hashing trick but with the benefit of producing a unique representation. We demonstrate the usefulness of this method in our experiments in Section 5.

## 3 Complementary Partitions

The quotient-remainder trick is, however, only a single example of a more general framework for decomposing embeddings. Note that in the quotient-remainder trick, each operation (the quotient or remainder) partitions the set of categories into multiple “buckets” such that every index in the same “bucket” is mapped to the same vector. However, by combining embeddings from both the quotient and remainder together, one is able to generate a distinct vector for each index.

Similarly, we want to ensure that each element in the category set may produce its own unique representation, even across multiple partitions. Using basic set theory, we formalize this concept to a notion that we call complementary partitions. Let denote the equivalence class of induced by partition .444We slightly abuse notation by denoting the equivalence class by its partition rather than its equivalence relation for simplicity. For more details on set partitions, equivalence classes, and equivalence relations, please refer to the Appendix.

###### Definition 1.

Given set partitions of set , the set partitions are complementary if for all such that , there exists an such that .

As a concrete example, consider the set . Then the following three set partitions are complementary: , , and . In particular, one can check that each element is distinct from every other element according to at least one of these partitions.

Note that each equivalence class of a given partition designates a “bucket” that is mapped to an embedding vector. Hence, each partition corresponds to a single embedding table. Under complementary partitions, after each embedding arising from each partition is combined through some operation, each index is mapped to a distinct embedding vector, as we will see in Section 4.

### 3.1 Examples of Complementary Partitions

Using this definition of complementary partitions, we can abstract the quotient-remainder trick and consider other more general complementary partitions. These examples are proved in the Appendix. For notational simplicity, we denote the set for a given .

1. Naive Complementary Partition: If

 P={{x}:x∈S}

then is a complementary partition by definition. This corresponds to a full embedding table with dimension .

2. Quotient-Remainder Complementary Partitions: Given , the partitions

 P1 ={{x∈S:ε(x)∖m=l}:l∈E(⌈|S|/m⌉)} P2 ={{x∈S:ε(x)modm=l}:l∈E(m)}

are complementary. This corresponds to the quotient-remainder trick in Section 2.

3. Generalized Quotient-Remainder Complementary Partitions: Given for such that , we can recursively define complementary partitions

 P1 ={{x∈S:ε(x)modm1=l}:l∈E(m1)} Pj ={{x∈S:ε(x)∖Mjmodmj=l}:l∈E(mj)}

where for . This generalizes the quotient-remainder trick.

4. Chinese Remainder Partitions: Consider a pairwise coprime factorization greater than or equal to , that is, for for all and for all . Then we can define the complementary partitions

 Pj={{x∈S:ε(x)modmj=l}:l∈E(mj)}

for .

More arbitrary complementary partitions could also be defined depending on the application. Returning to our car example, one could define different partitions based on the year, make, type, etc. Assuming that the unique specification of these properties yields a unique car, these partitions would indeed be complementary. In the following section, we will demonstrate how to exploit this structure to reduce memory complexity.

## 4 Compositional Embeddings Using Complementary Partitions

Generalizing our approach in Section 2, we would like to create an embedding table for each partition such that each equivalence class is mapped to an embedding vector. These embeddings could either be combined using some operation to generate a compositional embedding or used directly as separate sparse features (which we call the feature generation approach). The feature generation approach, although effective, may significantly increase the amount of parameters needed by adding additional features while not utilizing the inherent structure that the complementary partitions are formed from the same initial categorical feature.

More rigorously, consider a set of complementary partitions of the category set . For each partition , we can create an embedding table where each equivalence class is mapped to an embedding vector indexed by and is the embedding dimension for embedding table . Let be the function that maps each element to its corresponding equivalence class’s embedding index, i.e. .

To generate our (operation-based) compositional embedding, we interact all of the corresponding embeddings from each embedding table for our given category to obtain our final embedding vector

 xemb=ω(WT1ep1(x),WT2ep2(x),...,WTkepk(x)) (6)

where is an operation function. Examples of the operation function include (but are not limited to):

1. Concatenation: Suppose , then .

2. Addition: Suppose for all , then .

3. Element-wise Multiplication: Suppose for all , then 555

This is equivalent to factorizing the embeddings into the product of tensorized embeddings, i.e. if

is a -dimensional tensor containing all embeddings and for is the embedding table for partition , then
for fixed, where denotes the tensor outer product. This is similar to Khrulkov et al. (2019) but instead applied vector-wise rather than component-wise..

One can show that this approach yields a unique embedding for each category under simple assumptions. We show this in the following theorem (proved in the Appendix). For simplicity, we will restrict ourselves to the concatenation operation.

###### Theorem 1.

Assume that the vectors in each embedding table are distinct, that is for for all . If the concatenation operation is used, then the compositional embedding of any category is unique, i.e. if and , then .

This approach reduces the memory complexity of storing the entire embedding table to . Assuming and can be chosen arbitrarily, this approach yields an optimal memory complexity of , a stark improvement over storing and utilizing the full embedding table. This approach is visualized in Figure 2.

### 4.1 Path-Based Compositional Embeddings

An alternative approach for generating embeddings is to define a different set of transformations for each partition (aside from the first embedding table). In particular, we can use a single partition to define an initial embedding table then pass our initial embedding through a composition of functions determined by the other partitions to obtain our final embedding vector.

More formally, given a set of complementary partitions of the category set , we can define an embedding table for the first partition, then define sets of functions for every other partition. As before, let be the function that maps each category to its corresponding equivalence class’s embedding index.

To obtain the embedding for category , we can perform the following transformation

 xemb=(Mk,pk(x)∘...∘M2,p2(x))(Wep1(x)). (7)

We call this formulation of embeddings path-based compositional embeddings because each function in the composition is determined based on the unique set of equivalence classes from each partition, yielding a unique “path” of transformations. These transformations may contain parameters that also need to be trained concurrently with the rest of the network. Examples of the function could include:

1. Linear Function: If and are parameters, then .

2. Multilayer Perceptron (MLP): Let be the number of layers. Let and and for denote the number of nodes at each layer. Then if , , …, , , , …, are parameters, and

is an activation function (say, ReLU or sigmoid function) that is applied componentwise, then

 Mj,i(z)=ALσ(...A2σ(A1z+b1)+b2...)+bL.

Unlike operation-based compositional embeddings, path-based compositional embeddings require non-embedding parameters within the function to be learned, which may complicate training. The reduction in memory complexity also depends on how these functions are defined and how many additional parameters they add. For linear functions or MLPs with small fixed size, one can maintain the complexity. This is visualized in Figure 3.

## 5 Experiments

In this section, we present a comprehensive set of experiments to test the quotient-remainder trick for reducing the number of parameters while preserving model loss and accuracy over many different operations. In particular, we show that quotient-remainder trick allows us to trade off model accuracy attained by full embedding tables with model size obtained with the hashing trick.

For comparison, we consider both DCN (Wang et al., 2017) and Facebook DLRM networks. These two networks were selected as they are representative of most models for CTR prediction. We provide the model and experimental setup below.

### 5.1 Model Specifications

The DCN architecture considered in this paper consists of a deep network with 3 hidden layers consisting of 512, 256, and 64 nodes, respectively. The cross network consists of 6 layers. An embedding dimension of 16 is used across all categorical features.

The Facebook DLRM architecture consists of a bottom (or dense) MLP with 3 hidden layers with 512, 256, and 64 nodes, respectively, and an top (or output) MLP with 2 hidden layers consisting of 512 and 256 nodes. An embedding dimension of 16 is used. When thresholding, the concatenation operation uses an embedding dimension of 32 for non-compositional embeddings.

Note that in the baseline (using full embedding tables), the total number of rows in each table is determined by the cardinality of the category set for the table’s corresponding feature.

### 5.2 Experimental Setup and Data Pre-processing

The experiments are performed on the Criteo Ad Kaggle Competition dataset (Kaggle). Kaggle has 13 dense features and 26 categorical features. It consists of approximately 45 million datapoints sampled over 7 days. We use the first 6 days as the training set and split the 7th day equally into a validation and test set. The dense features are transformed using a log-transform. Unlabeled categorical features or labels are mapped to NULL or , respectively.

Note that for this dataset, each category is preprocessed to map to its own index. However, it is common in practice to apply the hashing trick to map each category to an index in an online fashion and to randomize the categories prior to reducing the number of embedding rows using the remainder function. Our techniques may still be applied in addition to the initial hashing as a replacement to the remainder function to systematically reduce embedding sizes.

Each model is optimized using the Adagrad (Duchi et al., 2011) and AMSGrad (Kingma and Ba, 2014; Reddi et al., 2019)

optimizers with their default hyperparameters; we choose the optimizer that yields the best validation loss. Single epoch training is used with a batch size of 128 and no regularization. All experiments are averaged over 5 trials. Both the mean and a single standard deviation are plotted. Here, we use an embedding dimension of 16. The model loss is evaluated using binary cross-entropy.

Only the test loss is shown for brevity unless designated otherwise. Please refer to the Appendix for a complete set of experimental results.

### 5.3 Simple Comparison

To illustrate the quotient-remainder trick, we provide a simple comparison of the validation loss throughout training for full embedding tables, the hashing trick, and the quotient-remainder trick (with the element-wise multiplication) in Figure 4. We enforce 4 hash collisions (yielding about a reduction in model size). Each curve shows the average and standard deviation of the validation loss over 5 trials.

As expected, we see in Figure 4

that the quotient-remainder trick interpolates between the compression of the hashing trick and the accuracy attained by the full embedding tables.

### 5.4 Compositional Embeddings

To provide a more comprehensive comparison, we vary the number of hash collisions enforced within each feature and plot the number of parameters against the test loss for each operation. We enforce between 2-7 and 60 hash collisions on each categorical feature. We plot our results in Figure 5, where each point corresponds to the averaged result for a fixed number of hash collisions over 5 trials. In particular, since the number of embedding parameters dominate the total number of parameters in the entire network, the number of hash collisions is approximately inversely proportional to the number of parameters in the network.

The multiplication operation performs best overall, performing closely to the feature generation baseline which comes at the cost of an additional half-million parameters for the Facebook DLRM and significantly outperforming all other operations for DCN. Interestingly, we found that AMSGrad significantly outperformed Adagrad when using the multiplication operation. Compared to the hashing trick with 4 hash collisions, we were able to attain similar or better solution quality with up to 60 hash collisions, an approximately smaller model. With up to 4 hash collisions, we are within 0.3% of the baseline model for DCN and within 0.7% of the baseline model for DLRM. Note that the baseline performance for DLRM outperforms DCN in this instance.

Because the number of categories within each categorical feature may vary widely, it may be useful to only apply the hashing trick to embedding tables with sizes larger than some threshold. To see the tradeoff due to thresholding, we consider the thresholds and plot the threshold number against the test loss for 4 hash collisions. For comparison, we include the result with the full embedding table as a baseline in Figure 6.

We see that when thresholding is used, the results are much more nuanced and improvement in performance depends on the operation considered. In particular, we find that the element-wise multiplication works best for DCN, while the concatenation operation works better for Facebook DLRM. For DLRM, we were able to observe an improvement from a 0.7% error to 0.5% error to the baseline while maintaining an approximate reduction in model size. The performance, however, may still vary depending on the number of hash collisions used.

### 5.5 Path-Based Compositional Embeddings

In these experiments, we consider the quotient-remainder trick for path-based compositional embeddings. Here, we fix to 4 hash collisions and define an MLP with a single hidden layer of sizes 16, 32, 64, and 128. The results are shown in Table 1.

From Table 1, we obtain an optimal hidden layer of size 64. The trend follows an intuitive tradeoff: using a smaller network may be easier to train but may not sufficiently transform the embeddings, while a larger network may have greater capacity to fit a more complex transformation but require more parameters to be learned. In this case, the modified DCN outperforms the modified DLRM network in this case, although this is not true in general.

As seen in Figure 5, using the quotient-remainder trick enforces arbitrary structures on the categorical data which can yield arbitrary loss in performance, as expected. This yields a trade-off between memory and performance; a larger embedding table will yield better model quality, but at the cost of increased memory requirements. Similarly, using a more aggressive version of the quotient-remainder trick will yield smaller models, but lead to a reduction in model quality. Most models exponentially decrease in performance with the number of parameters.

Both types of compositional embeddings reduce the number of parameters by implicitly enforcing some structure defined by the complementary partitions in the generation of each category’s embedding. Hence, the quality of the model ought to depend on how closely the chosen partitions reflect intrinsic properties of the category set and their respective embeddings. In some problems, this structure may be identified; however, the dataset considered in this paper contains no additional knowledge of the categories. Since practitioners performing CTR prediction typically apply the hashing trick, our method clearly improves upon this baseline with only small additional cost in memory.

Path-based compositional embeddings also yield more compute-intensive models with the benefit of lower model complexity. Whereas the operation-based approach attempts to definitively operate on multiple coarse representations, path-based embeddings explicitly define the transformations on the representation, a more difficult but intriguing problem. Unfortunately, our preliminary experiments show that our current implementation of path-based compositional embeddings do not supersede operation-based compositional embeddings; however, we do believe that path-based compositional embeddings are potentially capable of producing improved results with improved modeling and training techniques, and are worthy of further investigation.

## 6 Conclusion

Modern recommendation systems, particularly for CTR prediction and personalization tasks, handle large amounts of categorical data by representing each category with embeddings that require multiple GBs each. We have proposed an improvement for reducing the number of embedding vectors that is easily implementable and applicable end-to-end while preserving uniqueness of the embedding representation for each category. We extensively tested multiple operations for composing embeddings from complementary partitions.

Based on our results, we suggest combining the use of thresholding with the quotient-remainder trick (and compositional embeddings) in practice. The appropriate operation depends on the network architecture; in these two cases, the element-wise multiplication operation appear to work well.

This work provides an improved trick for compressing embedding tables by reducing the number of embeddings in the recommendation setting, with room for design of more intricate operations. There are, however, general weaknesses of this framework; it does not take into account the frequency of categories or learn the intrinsic structure of the embeddings as in codebook learning. Although this would be ideal, we found that categorical features for CTR prediction or personalization are far less structured, with embedding sizes that often prohibit the storage of an explicit codebook during training. It remains to be seen if other compression techniques that utilize further structure within categorical data (such as codebook learning (Shu and Nakayama, 2017; Chen et al., 2018)) can be devised or generalized to end-to-end training and inference for CTR prediction.

#### Acknowledgments

We thank Tony Ginart, Jianyu Huang, Krishnakumar Nair, Jongsoo Park, Misha Smelyanskiy, and Chonglin Sun for their helpful comments. Also, we express our gratitude to Jorge Nocedal for his consistent support and encouragement.

## References

• T. Chen, M. R. Min, and Y. Sun (2018) Learning k-way d-dimensional discrete codes for compact embedding representations. arXiv preprint arXiv:1806.09464. Cited by: §1.1, §6.
• H. Cheng, L. Koc, J. Harmsen, T. Shaked, T. Chandra, H. Aradhye, G. Anderson, G. Corrado, W. Chai, M. Ispir, et al. (2016) Wide & deep learning for recommender systems. In Proceedings of the 1st workshop on deep learning for recommender systems, pp. 7–10. Cited by: §1.1, §1.
• J. Duchi, E. Hazan, and Y. Singer (2011) Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research 12 (Jul), pp. 2121–2159. Cited by: §5.2.
• H. Guo, R. Tang, Y. Ye, Z. Li, and X. He (2017) DeepFM: a factorization-machine based neural network for ctr prediction. arXiv preprint arXiv:1703.04247. Cited by: §1.1, §1.
• X. He, L. Liao, H. Zhang, L. Nie, X. Hu, and T. Chua (2017) Neural collaborative filtering. In Proceedings of the 26th international conference on world wide web, pp. 173–182. Cited by: §1.1, §1.
• H. Jegou, M. Douze, and C. Schmid (2010) Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence 33 (1), pp. 117–128. Cited by: §1.1.
• V. Khrulkov, O. Hrinchuk, L. Mirvakhabova, and I. Oseledets (2019) Tensorized embedding layers for efficient model compression. arXiv preprint arXiv:1901.10787. Cited by: §1.1, footnote 5.
• D. P. Kingma and J. Ba (2014) Adam: a method for stochastic optimization. arXiv preprint arXiv:1412.6980. Cited by: §5.2.
• J. Lian, X. Zhou, F. Zhang, Z. Chen, X. Xie, and G. Sun (2018) xDeepFM: combining explicit and implicit feature interactions for recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1754–1763. Cited by: §1.1, §1.
• M. Naumov, D. Mudigere, H. M. Shi, J. Huang, N. Sundaraman, J. Park, X. Wang, U. Gupta, C. Wu, A. G. Azzolini, et al. (2019) Deep learning recommendation model for personalization and recommendation systems. arXiv preprint arXiv:1906.00091. Cited by: §1.1, §1, §1.
• M. Naumov (2019) On the dimensionality of embeddings for sparse features and data. arXiv preprint arXiv:1901.02103. Cited by: §1.1, §1.
• S. J. Reddi, S. Kale, and S. Kumar (2019) On the convergence of adam and beyond. arXiv preprint arXiv:1904.09237. Cited by: §5.2.
• S. Rendle (2010) Factorization machines. In 2010 IEEE International Conference on Data Mining, pp. 995–1000. Cited by: §1.1.
• S. Rendle (2012) Factorization machines with LibFM. ACM Transactions on Intelligent Systems and Technology (TIST) 3 (3), pp. 57. Cited by: §1.1.
• R. Shu and H. Nakayama (2017) Compressing word embeddings via deep compositional code learning. arXiv preprint arXiv:1711.01068. Cited by: §1.1, §6.
• R. Wang, B. Fu, G. Fu, and M. Wang (2017) Deep & cross network for ad click predictions. In Proceedings of the ADKDD’17, pp. 12. Cited by: §1.1, §1, §1, §5.
• K. Weinberger, A. Dasgupta, J. Attenberg, J. Langford, and A. Smola (2009) Feature hashing for large scale multitask learning. arXiv preprint arXiv:0902.2206. Cited by: §1, §2.
• Z. Yin and Y. Shen (2018) On the dimensionality of word embedding. In Advances in Neural Information Processing Systems, pp. 887–898. Cited by: §1.1.
• L. Zheng, C. Lu, L. He, S. Xie, V. Noroozi, H. Huang, and P. S. Yu (2018) Mars: memory attention-aware recommender system. arXiv preprint arXiv:1805.07037. Cited by: §1.1.
• C. Zhou, J. Bai, J. Song, X. Liu, Z. Zhao, X. Chen, and J. Gao (2018a) ATRank: an attention-based user behavior modeling framework for recommendation. In

Thirty-Second AAAI Conference on Artificial Intelligence

,
Cited by: §1.1.
• G. Zhou, N. Mou, Y. Fan, Q. Pi, W. Bian, C. Zhou, X. Zhu, and K. Gai (2018b) Deep interest evolution network for click-through rate prediction. arXiv preprint arXiv:1809.03672. Cited by: §1.1, §1.
• G. Zhou, X. Zhu, C. Song, Y. Fan, H. Zhu, X. Ma, Y. Yan, J. Jin, H. Li, and K. Gai (2018c) Deep interest network for click-through rate prediction. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1059–1068. Cited by: §1.1, §1.
• H. Zhu, X. Li, P. Zhang, G. Li, J. He, H. Li, and K. Gai (2018) Learning tree-based deep model for recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1079–1088. Cited by: §1.1.

## Appendix A Background on Set Partitions, Equivalence Relations, and Equivalence Classes

For completeness, we include the definitions of set partitions, equivalence relations, and equivalence classes, which we use extensively in the paper.

###### Definition 2.

Given a set , a set partition is a family of sets such that:

1. for all where .

###### Definition 3.

A binary relation on a set is an equivalence relation if and only if for ,

1. if and only if

2. If and , then .

###### Definition 4.

Given an equivalence relation on , the equivalence class of is defined as

 [a]R={b:(a,b)∈R}.

Given a set partition , we can define an equivalence relation on defined as if and only if such that . (One can easily show that this binary relation is indeed an equivalence relation.) In words, is “equivalent” to if and only if and are in the same set of the partition. This equivalence relation yields a set of equivalence classes consisting of for .

As an example, consider a set of numbers . One partition of is . Then the equivalence classes are defined as and .

To see how this is relevant to compositional embeddings, consider the following partition of the set of categories :

 P={{x∈S:ε(x)modm=l}:l∈N} (8)

where is given. This partition induces an equivalence relation as defined above. Then each equivalence class consists of all elements whose remainder is the same, i.e.

 [x]R={y:ε(y)modm=ε(x)modm}. (9)

Mapping each equivalence class of this partition to a single embedding vector is hence equivalent to performing the hashing trick, as seen in Section 2.

## Appendix B Proof of Complementary Partition Examples

In this section, we prove why each of the listed family of partitions are indeed complementary. Note that in order to show that these partitions are complementary, it is sufficient to show that for each pair of , there exists a partition such that .

1. If , then is a complementary partition.

###### Proof.

Note that since all are in different sets by definition of , for all .

2. Given , the partitions

 P1 ={{x∈S:ε(x)∖m=l}:l∈E(⌈|S|/m⌉)} P2 ={{x∈S:ε(x)modm=l}:l∈E(m)}

are complementary.

###### Proof.

Suppose that such that and . (If , then we are done.) Then there exists an such that and . In other words, and where . Since , we have that , and hence . Thus, and , so .

3. Given for such that , we can recursively define complementary partitions

 P1 ={{x∈S:ε(x)modm1=l}:l∈E(m1)} (10) Pj ={{x∈S:ε(x)∖Mjmodmj=l}:l∈E(mj)} (11)

where for . Then are complementary.

###### Proof.

We can show this by induction. The base case is trivial.

Suppose that the statement holds for , that is if for for and are defined by equation 10 and equation 11, then are complementary. We want to show that the statement holds for .

Consider a factorization with elements, that is, if for for . Let for be defined as in equation 10 and equation 11 with

 Sl1 ={x∈S:ε(x)modm1=l} (12) Slj ={x∈S:ε(x)∖Mjmodmj=l} (13)

for all and .

Let with . Since , . We want to show that for some . We have two cases:

1. If , then we are done.

2. Suppose . Then

 ε(x)∖Mjmodmj=ε(y)∖Mjmodmj=~l

for some . Consider the subset

 ~S={x∈S:ε(x)∖Mk+1modmk+1=~l}.

Note that . We will define an enumeration over by

 ~ε(x)=ε(x)−~lk∏i=1mi.

Note that this is an enumeration since if , then

 ε(x)=~lk∏i=1mi+c

for , so . This function is clearly a bijection on since is a bijection. Using this new enumeration, we can define the sets

 ~Sl1 ={x∈S:ε(x)modm1=l} ~Slj ={x∈S:ε(x)∖Mjmodmj=l}

where for and , and their corresponding partitions

 ~P1 ={~Sl1:l∈E(m1)} ~Pj ={~Slj:l∈E(mj)}.

Since , by the inductive hypothesis, we have that this set of partitions are complementary. Thus, there exists an such that .

In order to show that this implies that , one must show that for all and .

To see this, since , by modular arithmetic we have

 ε(x)modm1=~ε(x)modm1

and

 ε(x)∖Mjmodmj =ε(x)∖(j−1∏i=1mi)modmj =(~lk∏i=1mi+~ε(x))∖(j−1∏i=1mi)modmj =~ε(x)∖(j−1∏i=1mi)modmj

for . Thus, for all and and we are done.

4. Consider a pairwise coprime factorization greater than or equal to , that is, for for all and for all . Then we can define the partitions

 Pj={{x∈S:ε(x)modmj=l}:l∈E(mj)}

for . Then are complementary.

###### Proof.

Let . Since for are pairwise coprime and , by the Chinese Remainder Theorem, there exists a bijection defined as . Let such that . Then , and so there must exist an index such that , as desired. Hence .

## Appendix C Proof of Theorem 1

###### Theorem 1.

Assume that vectors in each embedding table are distinct, that is for for all . If the concatenation operation is used, then the compositional embedding of any category is unique, i.e. if and , then .

###### Proof.

Suppose that and . Let be complementary partitions. Define to be their respective embedding tables. Since the concatenation operation is used, denote their corresponding final embeddings as

 xemb =[xT1,xT2,...,xTk]T yemb =[yT1,yT2,...,yTk]T

respectively, where are embedding vectors from each corresponding partition’s embedding table.

Since are complementary and , for some . Thus, since the embedding vectors in each embedding table is distinct, . Hence, , as desired.

## Appendix D Additional Experimental Results

We present complete results on the training, validation, and test loss/accuracy against the number of parameters for 2-7 and 60 hash collisions on DCN and Facebook DLRM networks over 5 trials in Figures 7 and 8. We observe consistent results between the training, validation, and test performance across both networks. As noted in Section 5, the element-wise multiplication operation appears to perform best across both networks.

In order to avoid evaluating the training loss and accuracy on the entire training set, we approximate these quantities by averaging over a window from the results of the forward pass over the last 1024 iterations. This notably results in a larger standard deviation compared to the validation and test loss and accuracy.

We present the complete results for the thresholding experiments, where we compare the threshold against the test loss for 4 hash collisions; see Figures 9 and 10. We also plot the number of parameters against the threshold number in Figure 11.

We also present the complete results for the path-based compositional embeddings with different MLP sizes in Table 2. A full table containing results from the best operation for each fixed number of hash collisions is provided in Table 3. The table containing the thresholding experimental results for 4 hash collisions is provided in Table 4.


text:
# Finding the volume enclosed by two surfaces of revolution

I've come this far as to combine both functions in a graph:

f = Plot[4 - x^2, {x, -10, 10}]
g = Plot[-1 + 4 x, {x, -10, 10}]
Show[g, f, PlotRange -> All]

Solved the intersections:

sol = x /. NSolve[f == g, x, Reals]

{-5., 1.}

Next thing I would like to do is integrate and rotate the area between the intersects enclosed by the functions around the X axis and calculate the volume of the resulting rotational body. I'm fairly new to Mathematica and require some help to finish the plot.

EDIT: I have painted the area, so it is clear which area is meant to be revolved:

• I'm not sure what you mean by "rotate the region". Do you want to create a solid of revolution using the region between the two curves? If yes, which axis are you rotating around? – Szabolcs Sep 9 '17 at 19:04
• 1) I think you want 4 - x^2 rather than 4 - x. 2) What line in 3D space to want as the axis of revolution? – m_goldberg Sep 9 '17 at 19:13
• @Szabolcs around the X axis. I mean the Area, the 2 functions are enclosing between the intersections. Do you have an idea how to plot this? – BlkPengu Sep 9 '17 at 22:03

This is not an answer, but an explanation of why the question, as currently posed, is not clear.

If the two curves are rotated about the x-axis, they do not enclose a simple closed region -- they produce as region that self-intersects and for which it is difficult to define volume. Here are two views of a half-revolution plot that show the difficulty of determining the volume.

However, if the two curves are translated upward by 21, then revolving them about the x-axis produces a simple closed region for which has a volume that can be computed with reasonable effort.

Is volume enclosed by the translated curves the one you want?

### Update

Code for producing the half-revolution plots

f[x_] := 4 - x^2
g[x_] := -1 + 4 x
fSurface =
RevolutionPlot3D[f[x], {x, -5, 1}, {u, 0, π},
ColorFunction -> (White &), RevolutionAxis -> "X"];
gSurface =
RevolutionPlot3D[g[x], {x, -5, 1}, {u, 0, π},
ColorFunction -> (White &), RevolutionAxis -> "X"];
Show[
fSurface, gSurface,
BoxRatios -> {1, 1, 1}, PlotRange -> All, Lighting -> "Neutral"]

This may be the answer you are looking for. I will solve the problem by translating the curves.

The functions after translating the curves upward by 21.

f[x_] := 25 - x^2
g[x_] := 20 + 4 x
Plot[{f[x], g[x]}, {x, -5, 1}]

The surfaces of revolution

fSurface =
RevolutionPlot3D[f[x], {x, -5, 1}, {u, 0, 2 π},
ColorFunction -> (White &), RevolutionAxis -> "X"];
gSurface =
RevolutionPlot3D[g[x], {x, -5, 1}, {u, 0, 2 π},
ColorFunction -> (White &), RevolutionAxis -> "X"];
Show[
fSurface, gSurface,
BoxRatios -> {1, 1, 1}, PlotRange -> All, Lighting -> "Neutral"]

The inner surface of revolution and the volume it encloses

inner =
Volume @
ImplicitRegion[y^2 + z^2 <= g[x]^2, {{x, -5, 1}, {y, -24, 24}, {z, -24, 24}}]

1152 π

The outer surface of revolution and the volume it encloses

outer =
Volume @
ImplicitRegion[y^2 + z^2 <= f[x]^2, {{x, -5, 1}, {y, -25, 25}, {z, -25, 25}}]

(11376 π)/5

The volume enclosed between the two surfaces

outer - inner

(5616 π)/5

Getting the volume by integration (which for this problem is much faster)

Integrate[π (f[x]^2 - g[x]^2), {x, -5, 1}]

(5616 π)/5

• I edited the post to depict the exact area I want to revolve around the X axis. I'm not sure which one of your plots that is, but I get what the problem is. Those look almost like Klein Bottles in some way. However the last plot looks promising. – BlkPengu Sep 10 '17 at 11:19
• Could you add the syntax used to plot the objects pictured above? I could learn a great deal from it. – BlkPengu Sep 10 '17 at 11:23
• @BlkPengu. I have updated my post to provide the code you asked for and some more that I think will answer your question. – m_goldberg Sep 10 '17 at 22:18

This is an approach (note volume of RegionDifference does not seem to work):

f[x_] := 4 - x^2
g[x_] := 4 x - 1
region = ImplicitRegion[
0 < y^2 + z^2 <= Max[f[x]^2, g[x]^2], {{x, -5, 1}, y, z}];
mr = ImplicitRegion[
0 < y^2 + z^2 <= Min[f[x]^2, g[x]^2], {{x, -5, 1}, y, z}];
ro = RegionDifference[region, mr];
rplot = RegionPlot3D[ro, PlotPoints -> 100, PlotStyle -> Opacity[0.6],
Background -> Black];
rot[a_] := RotationMatrix[a, {1, 0, 0}]
ppl[a_] :=
ParametricPlot3D[{rot[a].{x, 0, f[x]}, rot[a].{x, 0, g[x]}}, {x, -5,
1}, PlotStyle -> Directive[Red, Thick]]
Manipulate[Show[rplot, ppl[a]], {a, 0, 2 Pi}]

Volume:

Through[{Simplify, N}[Volume[region] - Volume[mr]]]

yields:

{-(8/5) (-394 + 49 Sqrt[7]) π, 1328.81}


text:
using signed int for values that should never be negative

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

Recommended Posts

The game engine my company has licensed does this all the time - it will use signed math for a simple for loop. It seems to me that this is bad practice and can, in some circumstances, result in severe security vulnerabilities. Should I always be using unsigned types for types that are never negative, or am I overreacting and adding complexity where it is completely unnecessary?

Share on other sites
I have one question for you to consider. When is 4294967295 preferable to -1 when it comes to invalid values?

Share on other sites
I wouldn't say that using signed integers for values that will never be negative is bad practice as such, it's certainly quite common practice and you can use -1 to represent an uninitialised state which can be handy.

I personally however do use unsigned ints quite extensively, like: for (unsigned int i = 0; i < something; ++i)

If I see a signed integer I don't automatically assume it'll be used for negative values but the possibility exists, if I see an unsigned integer then I know it will always be positive, being explicit about your intentions never hurts.

Ofcourse, signed integers usually have a lower maximum (positive) range than an unsigned integer, so sometimes the decision is effectively made for you based on what you need.

Share on other sites
Quote:
 Original post by PromitI have one question for you to consider. When is 4294967295 preferable to -1 when it comes to invalid values?

I think he might be asking this:
for (int i = 0; i < 10; i++) {  a[i] = i; <-- array index cannot be negative in a sane application};

Personally, I try to match signedness with context.

Using unsigned types isn't always just gravy, and I had to deal with a very nasty side-effect of it.

The loop as simple:
size_t MAX = (a - b);size_t i = 0;while ( i < MAX ) // do something

But... due to various circumstances, MAX was initialized to -1, and hilarity ensued. If signed types were allowed, negative values would properly terminate the loop.

So it's not a sure-fire way to solve or prevent bugs.

There was also another conflict I encounter.

While designing a Buffer class, I chose STL's types. Size was size_t, since buffer size is either 0 or positive number.

But then I used pointer difference to obtain used size (curr_ptr - begin_ptr), which is typed as ptrdiff_t. Obviously, ptrdiff_t is signed, although.

Here's where compiler was hinting at something - even if I design a class correctly, and make sure it works, the language no longer guarantees that pointers are truly properly initialized.

So if compiler is warning you about sign conversions, it's usually a sign you're avoiding something, or trying to make something messy. In my case, it was perfectly warranted, since I was deliberately mixing incompatible types, even though I was trying to be smart about it.

Use whatever you see fit. But make sure you take into consideration the warnings compiler might start issuing over your choices. They'll usually expose very subtle situations.

Share on other sites
for (int i = 0; i < 10; i++) {  a[i] = i; <-- array index cannot be 4 billion in a sane application either.};

Share on other sites
This is a personal view and obviously not widespread in use (as judged from the posts here) but I always try to use the sign according to context. So if a loop should not be negative then unsigned will be used; if a generated random value should be positive then I'll use unsigned, etc (actually this issue of signed and unsigned becomes absolutely critical within some pseudo-random number generator algorithms). I feel it is just good practice to be aware of the allowable or expected limits of all parts of the code no matter how small, and to code accordingly.

--random

Share on other sites
Quote:
 Original post by Sneftelfor (int i = 0; i < 10; i++) { a[i] = i; <-- array index cannot be 4 billion in a sane application either.};

er, why would i be 4 billion, and why would having i be -1 make a difference?

Share on other sites
Quote:
 Original post by random_thinkerThis is a personal view and obviously not widespread in use (as judged from the posts here) but I always try to use the sign according to context. So if a loop should not be negative then unsigned will be used; if a generated random value should be positive then I'll use unsigned, etc (actually this issue of signed and unsigned becomes absolutely critical within some pseudo-random number generator algorithms). I feel it is just good practice to be aware of the allowable or expected limits of all parts of the code no matter how small, and to code accordingly.--random

I think to some extent this can be bad - for example, using a char to represent an ascii value is fine, but chances are it just means 3 bytes are wasted because everything is int-aligned.

Share on other sites
using signed in a for loop is totally normal. Not a "security risk". I once tried to do this but then you end up using the value to pass into a function which expects signed int, and end up with a nasty mess of casts.

int is the simple and the default thing to use, whenever you don't have extremely large values to deal with (or bitmasks).

Share on other sites
Quote:
Original post by thedustbustr
Quote:
 Original post by Sneftelfor (int i = 0; i < 10; i++) { a[i] = i; <-- array index cannot be 4 billion in a sane application either.};

er, why would i be 4 billion, and why would having i be -1 make a difference?

The point is that unsigned values cause bugs and vulnerabilities in exactly the same places as signed values. The computer doesn't do the range checking for you either way.

Share on other sites
One thing to be aware of when using unsigned integers is that the result of an arithmetic operation involving a signed and an unsigned integer is unsigned. So if you have a signed integer, and you subtract an unsigned integer from it, if the result would be negative, you will get wrapping.

#include <iostream>int main(){	int i = 100;	unsigned j = 200;	float k = i - j;	std::cout << k << std::endl;}

Although I use unsigned integers to enforce the constraint that a value will never be negative, when you're doing a lot of arithmetic with a mixture of signed and unsigned integers, it can make sense to make them signed and avoid subtle bugs caused by implicit conversions.

Share on other sites
Quote:
Original post by thedustbustr
Quote:
 Original post by Sneftelfor (int i = 0; i < 10; i++) { a[i] = i; <-- array index cannot be 4 billion in a sane application either.};

er, why would i be 4 billion, and why would having i be -1 make a difference?

Because in the unsigned world, -1 is equal to 4294967295.

So if you had some strange code that set i to -1, it would crash whether you used a signed or unsigned int.

Share on other sites
Quote:
Original post by Sc4Freak
Quote:
Original post by thedustbustr
Quote:
 Original post by Sneftelfor (int i = 0; i < 10; i++) { a[i] = i; <-- array index cannot be 4 billion in a sane application either.};

er, why would i be 4 billion, and why would having i be -1 make a difference?

Because in the unsigned world, -1 is equal to 4294967295.

So if you had some strange code that set i to -1, it would crash whether you used a signed or unsigned int.
I would prefer unsigned in such a case. an index of 4294967295 will obviously always crash with 32-bit addressing, whereas an index of -1 might simply access a different variable on the stack/heap.

The only place where using unsigned trips you up (that I can remember) is when doing a decreasing loop that has an ending condition of i>=0, which becomes an infinite loop.

Share on other sites
Quote:
 Original post by thedustbustrThe game engine my company has licensed does this all the time - it will use signed math for a simple for loop. It seems to me that this is bad practice and can, in some circumstances, result in severe security vulnerabilities.Should I always be using unsigned types for types that are never negative, or am I overreacting and adding complexity where it is completely unnecessary?

Sticking to the original topic of a "simple for loop", why type out anything more than 3 letters?

I *always* use a simple int for "simple for loops".

// spawn a bunch of random objectsfor (int i = 0; i < 50; ++i)    spawnRandomObject();

Not really sure how I can be more "safe".

Share on other sites
Quote:
Original post by iMalc
Quote:
Original post by Sc4Freak
Quote:
Original post by thedustbustr
Quote:
 Original post by Sneftelfor (int i = 0; i < 10; i++) { a[i] = i; <-- array index cannot be 4 billion in a sane application either.};

er, why would i be 4 billion, and why would having i be -1 make a difference?

Because in the unsigned world, -1 is equal to 4294967295.

So if you had some strange code that set i to -1, it would crash whether you used a signed or unsigned int.
I would prefer unsigned in such a case. an index of 4294967295 will obviously always crash with 32-bit addressing, whereas an index of -1 might simply access a different variable on the stack/heap.
No, that's the thing. An index of 4294967295 will access exactly the same thing as an index of -1. From the CPU's point of view, there literally is zero difference between the two situations.

Share on other sites
Quote:
 Original post by SneftelNo, that's the thing. An index of 4294967295 will access exactly the same thing as an index of -1. From the CPU's point of view, there literally is zero difference between the two situations.

My example wasn't best, the point I was trying to make is that an array index, as a value, cannot be signed. a[-1] isn't allowed, as such it makes no sense to use it. With a variable, it's possible to do it, but it's not sane. Depending on the compiler, the results might even be deterministic, but still not sane. So might as well enforce this relation.

However, unsigned types may lead to slightly more elegant code (or not, depends).

template < class T >T get( unsigned int index ) {  if ( index < n_elements ) {    return ...  } else {    // error  }}

compared to:
template < class T >T get( int index ) {  if ( (index >= 0) && ( index < n_elements )) {    return ...  } else {    // error  }}

since it allows you to establish hard relation. Even if a negative index is passed, it only requires one test.

The decrementing while statement is tricky as well, since subtle flaws can lead to, as mentioned, infinite loops.

Overall, unsigned types are just fine for things that are unsigned. But they come with their own set of problems and gotchas.

Share on other sites
Quote:
 Original post by Antheusa[-1] isn't allowed, as such it makes no sense to use it.

int a[2];int *b = a+1;b[-1] = 3;

I've actually seen this sort of thing on more than one occasion, usually in code converted from FORTRAN.

Anyways, I think we're both arguing the same side, sooo.

Share on other sites
All this info scares me; it looks like these int/unsigned loops are not as inherently safe as they should be. Maybe a suitable solution is to use some new types for loops that check for these conditions, like Astrachan does in some of his classes, something like:

for( isFirst; !isDone; isNext ){    // Whatever...}

--random

Share on other sites
I definitely think it is a mistake to use an unsigned variable just because the values are expected to never be negative. Two reasons:
• It gives you a false sense of security. As pointed earlier, it doesn't catch or prevent problems, and the mistaken assumptions in some of the posts above illustrate the point.
• Mixing signed and unsigned variables results in a lot of casting, which reduces readability and leads to bugs.

I use unsigned values for bit manipulation, for variables that need an extra bit of range, and for compatibility.

Does anyone use unsigned char if the value is expected to always fit in 8 bits? In other words, does anyone advocate doing this?
    for ( unsigned char i = 0; i < 10; ++i )    ...
For the same reasons described above, I don't use char or short just because the values are expected to be in their ranges. I just use int. In fact I only use char for text and can't think of any reason for ever using short (if I need specific sizes, types such as __int8 and __int16 are more appropriate).

[Edited by - JohnBolton on September 16, 2007 2:06:00 AM]

Share on other sites
C++ is just an inherently unsafe language, and unbounded loops have the inherent problem (and benefit) of iterating for some unknown number of times that could depend on values being computed within the loop itself. It is up to the programmer to ensure that loops eventually terminate and at the proper time, while not performing undefined operations.

If you want to enforce really strict safety, I've read that Eiffel is designed for that sort of thing. It has ways to insert whatever kinds of checks you like.

Using an unsigned int on a 32 bit machine probably won't cause any harm since it is difficult to imagine a loop counting past two billion, and in the rare case that such a thing is necessary it is a simple change to use an unsigned int, a long, or a bigint class.

Share on other sites
Maybe this is a wild idea to the extreme, but what about something like:

#include <limits>#include <stdexcept>template<typename baseType> class iter_t{public:	iter_t(baseType lower, baseType upper) :		lower_(lower), upper_(upper),		min_limit_(std::numeric_limits<baseType>::min()),		max_limit_(std::numeric_limits<baseType>::max())	{		checkLower(lower);		checkUpper(upper);	}	void isFirst()	{		counter_ = lower_;	}	void isFirst(baseType lower)	{		checkLower(lower);		counter_ = lower;	}	void isNext()	{		++counter_;	}	bool isDone()	{		return (counter_ == upper_ );	}        // Could include another settable isDone(baseType) method but        // checking each loop would slow things considerably.private:	baseType counter_;	const baseType lower_;	const baseType upper_;	const baseType min_limit_;	const baseType max_limit_;	void checkLower(baseType lower)	{		if (lower < min_limit_ )		{			// issue some error condition...		}	}	void checkUpper(baseType upper)	{		if (upper > max_limit_ )		{			// issue some error condition...		}	}};

Used in source something like:

iter_t<int> i(0,500);	for( i.isFirst(); !i.isDone(); i.isNext() ){	// do something...	}	for( i.isFirst(10); !i.isDone(); i.isNext() ){	// do something...}

This would be for determinant loops; a condition could be added for indeterminant loops as well, that accepts another form of computed baseType limit.

Edit - What is this weirdness? I've benchmarked the above code against a standard loop producing 100 million random numbers with my fastest generator, and consistently outperforms a standard loop by about 15%. What gives?

Results are something like:

// For standard 'for' loop:
Elapsed time : 0.84s. // Sometimes as high as 0.98s.

// For 'iter_t' loop:
Elapsed time : 0.73s. // Pretty much stable at 0.73s.

Comparative source code follows:

int j = 0;double time = 0;timer.mark();	// Simple timer class, already initialized.for ( j=0; j!=100000000; ++j){	pGen->next();}time = timer.read();std::cout << "\nElapsed time   : " << time << "s." << std::endl;	iter_t<int> i(0,100000000);	timer.mark();for( i.isFirst(); !i.isDone(); i.isNext() ){	pGen->next();}time = timer.read();std::cout << "\nElapsed time   : " << time << "s." << std::endl;

Is this because there is something run-time 'dynamic' going on with the use of 'int', and something compile-time 'static; going on with 'iter_t'? Thinking about doing some major refactoring here....

Edit again...Revised iter_t (static invocation is consistently 0.7s for 100 million random numbers) and tried some run-time trials for comparison purposes. Code of run-time is:

unsigned lower = STUtility::promptRange("Select a lower bound within the range : ",-100,100000000);unsigned upper = STUtility::promptRange("Select a upper bound within the range : ",-100,100000000);	iter_t<unsigned> test(lower,upper);	timer.mark();for( test.isFirst(); !test.isDone(); test.isNext() ){	pGen->next();}time = timer.read();std::cout << "\nElapsed time   : " << time << "s." << std::endl;lower = STUtility::promptRange("Select a lower bound within the range : ",-100,100000000);upper = STUtility::promptRange("Select a upper bound within the range : ",-100,100000000);timer.mark();	for ( j=lower; j!=upper; ++j){	pGen->next();}time = timer.read();std::cout << "\nElapsed time   : " << time << "s." << std::endl;

Interestingly, the iter_t is still faster. Results are:

Select a lower bound within the range : -100 to 100000000 : 0
Select a upper bound within the range : -100 to 100000000 : 100000000

Elapsed time : 1.57s.

Select a lower bound within the range : -100 to 100000000 : 0
Select a upper bound within the range : -100 to 100000000 : 100000000

Elapsed time : 1.68s.

Note: Type is unsigned because I'm in the process of testing the error conditions. I wouldn't necessarily use unsigned in this context.

--random

[Edited by - random_thinker on September 16, 2007 8:56:19 AM]

Share on other sites
Wondering if this speed improvement with 'iter_t' is just a compiler-specific issue? All these benchmarks are on G++ (GCC) 4.0.3 (Ubuntu 4.0.3-1ubuntu5).

--random

Share on other sites
Quote:
 Original post by SneftelNo, that's the thing. An index of 4294967295 will access exactly the same thing as an index of -1. From the CPU's point of view, there literally is zero difference between the two situations.

Assuming a 32-bit twos complement signed integer representation. A sign magnitude integer implementation would probably do something different.

Share on other sites
Fascinated by this problem. To solve some of the issues pointed out in this thread, and also some buffer overflow and possible security problems, what about using an int_t type, something like:

#include <iostream>#include <limits>#include "../Headers/Utilities/Error.h"template<typename intType>class int_t{public:	int_t() :		value_(0)	{	}		int_t(const intType arg) :		value_(arg)	{	}		int_t(const int_t<intType>& arg) :		value_(arg.value_)	{	}		~int_t()	{	}	int_t operator=(const int_t<intType> arg)	{		value_ = arg.value_;		return *this;	}		int_t operator=(const intType arg)	{		value_ = arg;		return *this;	}		int_t operator+(const intType arg) const	{		return (int_t(value_ + arg));	}		int_t operator+(const int_t<intType> arg) const	{		return (int_t(value_ + arg.value_));	}		int_t operator-(const intType arg) const	{			return (int_t(value_ - arg));	}			int_t operator-(const int_t<intType> arg) const	{		return (int_t(value_ - arg.value_));	}		int_t operator*(const intType arg) const	{			return (int_t(value_ * arg));	}				int_t operator*(const int_t<intType> arg) const	{		return (int_t(value_ * arg.value_));	}		int_t operator/(const intType arg) const	{		if (arg == 0)		{			STUtility::error error_cond("Divide by zero");			error_cond.die();		}		return (int_t(value_ / arg));	}		int_t operator/(const int_t<intType> arg) const	{		if (arg.value_ == 0)		{			STUtility::error error_cond("Divide by zero");			error_cond.die();		}		return (int_t(value_ / arg.value_));	}		int_t operator%(const intType arg) const	{		return (int_t(value_ % arg));	}		int_t operator%(const int_t<intType> arg) const	{		return (int_t(value_ % arg.value_));	}		int_t operator&(const intType arg) const	{		return (int_t(value_ & arg));	}		int_t operator&(const int_t<intType> arg) const	{		return (int_t(value_ & arg.value_));	}		int_t operator|(const intType arg) const	{		return (int_t(value_ | arg));	}		int_t operator|(const int_t<intType> arg) const	{		return (int_t(value_ | arg.value_));	}		int_t operator^(const intType arg) const	{		return (int_t(value_ ^ arg));	}		int_t operator^(const int_t<intType> arg) const	{		return (int_t(value_ ^ arg.value_));	}		int_t operator~() const	{		return (~value_);	}		int_t operator<<(const intType arg) const	{		return (int_t(value_ << arg));	}		int_t operator<<(const int_t<intType> arg) const	{		return (int_t(value_ << arg.value_));	}		int_t operator>>(const intType arg) const	{		return (int_t(value_ >> arg));	}		int_t operator>>(const int_t<intType> arg) const	{		return (int_t(value_ >> arg.value_));	}		bool operator==(const intType arg) const	{		return (int_t(value_ == arg));	}		bool operator==(const int_t<intType> arg) const	{		return (int_t(value_ == arg.value_));	}		bool operator!=(const intType arg) const	{		return (int_t(value_ != arg));	}		bool operator!=(const int_t<intType> arg) const	{		return (int_t(value_ != arg.value_));	}		bool operator>=(const intType arg) const	{		return (int_t(value_ >= arg));	}		bool operator>=(const int_t<intType> arg) const	{		return (int_t(value_ >= arg.value_));	}		bool operator>(const intType arg) const	{		return (int_t(value_ > arg));	}		bool operator>(const int_t<intType> arg) const	{		return (int_t(value_ > arg.value_));	}		bool operator<=(const intType arg) const	{		return (int_t(value_ <= arg));	}		bool operator<=(const int_t<intType> arg) const	{		return (int_t(value_ <= arg.value_));	}		bool operator<(const intType arg) const	{		return (int_t(value_ < arg));	}		bool operator<(const int_t<intType> arg) const	{		return (int_t(value_ < arg.value_));	}		int_t operator++()	{		++value_;		return (*this);	}		int_t operator--()	{		--value_;		return (*this);	}		intType value()	{		return value_;	}	private:	intType value_;};template<typename intType>std::ostream & operator<<(std::ostream & out, int_t<intType> arg){	return out << arg.value(); }template<typename intType>std::istream & operator>>(std::istream & in, int_t<intType> arg){	return in >> arg.value(); }

--random

Share on other sites
Quote:
 Original post by JohnBoltonI definitely think it is a mistake to use an unsigned variable just because the values are expected to never be negative. Two reasons:It gives you a false sense of security. As pointed earlier, it doesn't catch or prevent problems, and the mistaken assumptions in some of the posts above illustrate the point.

I only use unsigned integers to indicate an intention rather than to catch mistakes; I certainly don't feel any safer using them.

Quote:
 Mixing signed and unsigned variables results in a lot of casting, which reduces readability and leads to bugs.

If used consistently and at appropriate circumstances then there's little reason that casting for signedness within your own code need occur. If you're using a library then there is always the risk that you have a different convention on the use of primitive types. The library I use most often is the SC++L; which consistently defines size_type to be an unsigned integer so I rarely need to cast for signedness at all.

Quote:
 I use unsigned values for bit manipulation, for variables that need an extra bit of range, and for compatibility.

I use signed values when I need negative numbers or for compatibility.

Quote:
 Does anyone use unsigned char if the value is expected to always fit in 8 bits? In other words, does anyone advocate doing this?  for ( unsigned char i = 0; i < 10; ++i ) ...

This is a very good point.
I wouldn't advocate this; I would wager most people associate char with characters, strings and bytes; as a result I'd only use a char when dealing with one of those three things.
Even though using a char may be more explicit about the range it would obfuscate the intended purpose of the variable if just used for natural numbers in this way.

Quote:
 For the same reasons described above, I don't use char or short just because the values are expected to be in their ranges. I just use int. In fact I only use char for text and can't think of any reason for ever using short (if I need specific sizes, types such as __int8 and __int16 are more appropriate).

Personally I think that using either a signed or unsigned integer is fine provided it's consistent. Relying on unsigned values to catch bugs for you is risky and as shown in the posts above often mistaken. As long as types are used appropriately I have no problem reading or even writing code using either convention (but if left to my own devices I would default to using unsigned integers for non-negative values).
I wasn't trying to trash the use of signed integers btw, I just want to provide a balanced argument :-)

As for short there really is little reason to use it by itself, if you have a lot of integers packed together then using short could half the memory requirement, the first example that springs to mind is an index buffer/array.

Share on other sites

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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

• Forum Statistics

• Total Topics
628711
• Total Posts
2984341

• 23
• 11
• 10
• 13
• 14


text:
# B Asymptotic function

1. Mar 26, 2017

### Debaa

What is an asymptotic function. How do you integrate it?

2. Mar 26, 2017

### Ssnow

An asymptotic function $f$ is a function that has the same behaviour of another function $g$, at least in a small neighborhood ...
For example the Taylor expansion gives you a polynomial that has the same behaviour of $g$. The Taylor expansion is not always practicable. In mathematics there is a notation used in the asymptotic expansion called ''big-$O$'' notation.
For discrete functions $f(n)=O(g(n))$ if $g$ is an upper bound on $f$: there exists a fixed constant $c$ and a fixed $n_{0}$ such that for all $n≥n_{0}$,

$f(n) ≤ cg(n)$.

We say $f$ is $o(g(n))$ (read: "$f$ is little-$o$ of $g$'') if for all arbitrarily small real $c > 0$, for all but perhaps finitely many $n$,

$f(n) ≤ cg(n)$.

We say that f is $\Theta(g(n))$ (read: "$f$ is theta of $g$") if $g$ is an accurate characterization of $f$ for large $n$: it can be scaled so it is both an upper and a lower bound of $f$.

Details of Taylor expansion, $O$-notation, or asymptotic analysis are in https://en.wikipedia.org/wiki/Taylor_series , https://en.wikipedia.org/wiki/Big_O_notation , https://en.wikipedia.org/wiki/Asymptotic_analysis

Ssnow

3. Mar 26, 2017

Thanks


text:
## A community for students. Sign up today

Here's the question you clicked on:

## anonymous 4 years ago Suppose that a guitar string has a length of 1.1 m, a mass of 0.12 kg and a tension of 125 N. What is the speed of the wave on the string?

• This Question is Closed
1. experimentX
2. anonymous

wave speed 'v' ---> $v = \frac{\sqrt{T}} {\sqrt{mu}}$ where, T=tension mu=linear mass density (i.e. mass per unit length of the wire)

3. anonymous

that means, mu=mass/length

4. anonymous

Hi you can use from this: $v=\sqrt{T/\lambda }$ where lambda is mass per meter

#### Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy