text:
# Introduction

## The Problem

Reddit is an expansive site. Anyone who has spent any significant amount of time on it knows what I mean. There is a subreddit for seemingly every topic anyone could ever want to discuss or even think about (and many that most do not want think about).

Reddit is a powerful site; a tool for connecting and sharing information with like- or unlike-minded individuals around the world. When used well, it can be a very useful resource.

On the other hand, the deluge of information that's constantly piling into the pages of can be overwhelming and lead to wasted time. As with any tool, it can be used for good or for not-so-good.

A common problem that Redditors experience, particularly those who are relatively new to the site, is where to post content. Given that there are subreddits for just about everything, with wildly varying degrees of specificity it can be quite overwhelming trying to find the best place for each post.

Just to illustrate the point, some subreddits get weirdly specific. I won't go into the really weird or NSFW, but here are some good examples of what I mean by specific:

...need I go on? (If you're curious and/or want to be entertained indefinitely, here is a thread with these and much, much more.)

Most of the time when a post is deemed irrelevant to a particular subreddit, it will simply be removed by moderators or a bot. However, depending on the subreddit and how welcoming they are to newbies, sometimes it can lead to very unfriendly responses and/or bans.

So how does one go about deciding where to post or pose a question?

Post Here aims to take the guesswork out of this process.

## The Solution

The goal with the Post Here app, as mentioned, is to provide a tool that makes it quick and easy to find the most appropriate subreddits for any given post. A user would simply provide the title and text of the their prospective post and the app would provide the user with a list of subreddit recommendations.

Recommendations are produced by a model attempts to predict which subreddit a given post would belong to. The model was built using Scikit-learn, and was trained on a large dataset of reddit posts. In order to serve the recommendations to the web app, an API was built using Flask and deployed to Heroku.

The live version of the app is linked below.

## My Role

I worked on the Post Here app with a remote, interdisciplinary team of data scientists, machine learning engineers, and web developers. I was one of two machine learning engineers on the team, responsible for the entire process of building and training the machine learning models. The two data scientists on the team were primarily responsible for building and deploying the API.

The main challenge we ran into, which directed much of the iterative process, was scope management.

At this point in my machine learning journey, this was one of the larger datasets that I'd taken on. Uncompressed, the dataset we used was over 800mb of mostly natural language text. The dataset and the time constraint—we had less than four full days of work to finish the project—were the primary causes of the challenges we ended up facing.

With such a dataset, one important concept we had to keep in mind was the curse of dimensionality, which is basically a title for the various problems and phenomena that occur when dealing with extremely highly dimensional datasets. When processed, a natural language dataset of this size would likely fall prey to this curse and may prove somewhat unwieldy without large amounts of processing power.

I ended up researching and applying various methods of addressing this problem in order to fit the processing/modeling pipeline on the free Heroku Dyno, with a memory limit of 500mb, while preserving adequate performance. Many of our deployments failed because the pipeline, when loaded into memory on the server, exceeded that limit.

One important tradeoff we had to wrangle with was how much, and in what ways we could limit the dataset—i.e. how many classes to try and predict, and how many observations per class to include when training. The original dataset contains data for 1,000 subreddits. It was not within the scope of a a four-day project to build a classification model of a caliber that could accurately classify 1,000 classes.

In the beginning, we did try to build a basic model trained on all 1,000 classes. But with the time and processing power I had, it proved to be untenable. In the end, we settled for a model that classified text into 305 subreddits with a test precision-at-k of .75, .88, and .92 for 'k' of 1, 3, and 5, respectively.

## Imports and Configuration

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns

import os
import janitor

from sklearn.model_selection import train_test_split
from sklearn.preprocessing import LabelEncoder
from sklearn.ensemble import RandomForestClassifier
from sklearn.naive_bayes import MultinomialNB
from sklearn.feature_selection import chi2, SelectKBest

# === NLP Imports === #
from sklearn.feature_extraction.text import TfidfVectorizer

# Configure pandas display settings
pd.options.display.max_colwidth = 100

# Set random seed
seed = 92

# The Data

The dataset we ended up using to train the recommendation system is called the Reddit Self-Post Classification Task dataset, available on Kaggle thanks to Evolution AI. The full dataset clocks in at over 800mb, containing 1,013,000 rows: 1,000 posts each from 1,013 subreddits.

For more details on the dataset, including a nice interactive plot of all of the subreddits, refer to Evolution AI's blog post.

## Wrangling and Exploration

First, I needed to reduce the size of the dataset. I defined a subset of 12 categories which I thought were most relevant to the task at hand, and used that list to do the initial pruning. Those 12 categories left me with 305 unique subreddits and 305,000 rows. The list I used was as follows:

• health
• profession
• electronics
• hobby
• writing/stories
• social_group
• stem
• parenting
• books
• finance/money
• travel

Next, I took a random sample of those 305,000 rows. The result was a dataset with 91,500 rows, now consisting of between 250 and 340 rows per subreddit. If I tried to use all of the features (tokens, or words) that resulted from this corpus, even in its reduced state, it would still result in a serialized vocabulary and/or model too large for our free Heroku Dyno. However, the features used in the final model can be chosen based on how useful they are for the classification.

According to the dataset preview on Kaggle, there are quite a large number of missing values in each of the features—12%, 25%, and 39% of the subreddit, title, and selftext columns, respectively. However, I did not find any sign of those null values in the dataset nor mention of them in the dataset's companion blog post or article. I chocked it up to an error in the Kaggle preview.

Finally, I went about doing some basic preprocessing to get the data ready for vectorization. As described in the description page on Kaggle, newline and tab characters were replaced with their HTML equivalents, <lb> and <tab>. I removed those and other HTML entities using a simple regular expression. I also concatenated title and selftext into a single text feature in order to process them together.

rspct = pd.read_csv("assets/data/rspct.tsv", sep="\t")
print(rspct.shape)

(1013000, 4)

id subreddit title selftext
0 6d8knd talesfromtechsupport Remember your command line switches... Hi there, <lb>The usual. Long time lerker, first time poster, be kind etc. Sorry if this isn't the right place...<lb><lb>Alright. Here's the story. I'm an independent developer who produces my ow...
1 58mbft teenmom So what was Matt "addicted" to? Did he ever say what his addiction was or is he still chugging beers while talking about how sober he is?<lb><lb>Edited to add: As an addict myself, anyone I know whose been an addict doesn't drin...
2 8f73s7 Harley No Club Colors Funny story. I went to college in Las Vegas. This was before I knew anything about motorcycling whatsoever. Me and some college buddies would always go out on the strip to the dance clubs. We alwa...

### Nulls

Kaggle says that 12%, 25%, and 39% of the subreddit, title, and selftext columns are null, respectively. If that is indeed the case, they did not get read into the dataframe correctly. However, it could be an error on Kaggle's part, seeing as there is no mention of these anywhere else in the description or blog post or article, nor sign of them during my explorations.

rspct.isnull().sum()

id           0
subreddit    0
title        0
selftext     0
dtype: int64

### Preprocessing

To prune the list of subreddits, I'll load in the subreddit_info.csv file, join, then choose a certain number of categories (category_1) to filter on.

info = pd.read_csv("assets/data/subreddit_info.csv", usecols=["subreddit", "category_1", "category_2"])
print(info.shape)

(3394, 3)

subreddit category_1 category_2
rspct = pd.merge(rspct, info, on="subreddit").drop(columns=["id"])
print(rspct.shape)

(1013000, 5)

subreddit title selftext category_1 category_2
0 talesfromtechsupport Remember your command line switches... Hi there, <lb>The usual. Long time lerker, first time poster, be kind etc. Sorry if this isn't the right place...<lb><lb>Alright. Here's the story. I'm an independent developer who produces my ow... writing/stories tech support
1 talesfromtechsupport I work IT for a certain clothing company and they use iPod Touchs for scanning some items [ME]- Thank you fro calling Store support, this is David. How may I help you?<lb><lb>[Store]- Yeah, my iPod is frozen<lb><lb>[ME]- Okay, can I have you hold down the power and the home button at t... writing/stories tech support
2 talesfromtechsupport It... It says right there on the screen...? Hi guys! <lb><lb>&nbsp;<lb><lb>LTL, FTP - all that jazz. Starting you off with a short one.<lb><lb>&nbsp;<lb><lb>I'm the senior supporter at a smaller tech company with clients all over t... writing/stories tech support
3 talesfromtechsupport The computers not working. FIX IT NOW! Hey there TFTS! This is my second time posting. I don't work for any tech support company, but I do have friends, family and teachers at school that have no idea how stuff works.<lb><lb>This tale ... writing/stories tech support
4 talesfromtechsupport A Storm of Unreasonableness Usual LTL, FTP. I have shared this story on a different site, but after reading TFTS for sometime I figured it'd belong here as well. <lb><lb>This is from when I worked at a 3rd party call center ... writing/stories tech support
rspct.isnull().sum()  # That's a good sign

subreddit     0
title         0
selftext      0
category_1    0
category_2    0
dtype: int64
rspct["category_1"].value_counts()

video_game               100000
tv_show                   68000
health                    58000
profession                56000
software                  52000
electronics               51000
music                     43000
sports                    40000
sex/relationships         31000
hobby                     30000
geo                       29000
crypto                    29000
company/website           28000
other                     27000
anime/manga               26000
drugs                     23000
writing/stories           22000
programming               21000
arts                      21000
autos                     20000
education                 17000
animals                   17000
politics/viewpoint        16000
social_group              16000
card_game                 15000
food/drink                15000
stem                      14000
hardware/tools            14000
parenting                 13000
religion/supernatural     13000
books                     12000
appearance                11000
finance/money             10000
board_game                 9000
meta                       9000
movies                     7000
rpg                        7000
travel                     5000
Name: category_1, dtype: int64
keep_cats = [
"health",
"profession",
"electronics",
"hobby",
"writing/stories",
"social_group",
"stem",
"parenting",
"books",
"finance/money",
"travel",
]

# Prune dataset to above categories
# Overwriting to save memory
rspct = rspct[rspct["category_1"].isin(keep_cats)]
print(rspct.shape)
print("Unique subreddits:", len(rspct["subreddit"].unique()))

(305000, 5)
Unique subreddits: 305

subreddit title selftext category_1 category_2
0 talesfromtechsupport Remember your command line switches... Hi there, <lb>The usual. Long time lerker, first time poster, be kind etc. Sorry if this isn't the right place...<lb><lb>Alright. Here's the story. I'm an independent developer who produces my ow... writing/stories tech support
1 talesfromtechsupport I work IT for a certain clothing company and they use iPod Touchs for scanning some items [ME]- Thank you fro calling Store support, this is David. How may I help you?<lb><lb>[Store]- Yeah, my iPod is frozen<lb><lb>[ME]- Okay, can I have you hold down the power and the home button at t... writing/stories tech support
rspct = rspct.sample(frac=.3, random_state=seed)
print(rspct.shape)

(91500, 5)

subreddit title selftext category_1 category_2
594781 stepparents Ex Wants Toddler Son (2M) to Meet Her AP/SO - x-post from /r/divorce Quick background: My soon-to-be ex-wife (26F) and I (27M) have been separated for about 5 months now. She has been in a serious relationship her AP (23M) whom she met and cheated on me with 6 mont... parenting step parenting
617757 bigseo Do we raise our pricing? I took a management role at an agency. We're way, way under $500/mo for SEO pricing - and I'm embarrassed to say that we're hurting for business. Seems to me that it's a struggle to get clients to... profession seo 642368 chemistry Mac vs. PC? Hello, all! I am currently a senior in high school and in the fall I will be going to SUNY Geneseo, majoring in chemistry and minoring in mathematics. <lb><lb>Geneseo requires it’s students to get... stem chemistry 325221 migraine Beer as an aural abortive? Hiya folks,<lb><lb>I've been a migraine sufferer pretty much my whole life. For me intense auras, numbness, confusion, the inability to speak or see is BY FAR the worst aspect of the ordeal. When ... health migraine 524939 MouseReview Recommend office mouse I was hoping you folks could help me out. Here's my situation and requirements:<lb><lb>* I don't play games at all<lb>* Budget$30.00 or less<lb>* Shape as close to old Microsoft Intellimouse Opti... electronics computer mouse
# Concatenate title and selftext
rspct["text"] = rspct["title"] + " " + rspct["selftext"]

# Drop categories
rspct = rspct.drop(columns=["category_1", "category_2", "title", "selftext"])

# NOTE: takes a couple minutes to run
rspct["text"] = rspct["text"].str.replace("(<lb>)*|(<tab>)*|(&)*|(nbsp;)*", "")

subreddit text
594781 stepparents Ex Wants Toddler Son (2M) to Meet Her AP/SO - x-post from /r/divorce Quick background: My soon-to-be ex-wife (26F) and I (27M) have been separated for about 5 months now. She has been in a serious...
617757 bigseo Do we raise our pricing? I took a management role at an agency. We're way, way under $500/mo for SEO pricing - and I'm embarrassed to say that we're hurting for business. Seems to me that it's a s... 642368 chemistry Mac vs. PC? Hello, all! I am currently a senior in high school and in the fall I will be going to SUNY Geneseo, majoring in chemistry and minoring in mathematics. Geneseo requires it’s students to... 325221 migraine Beer as an aural abortive? Hiya folks,I've been a migraine sufferer pretty much my whole life. For me intense auras, numbness, confusion, the inability to speak or see is BY FAR the worst aspect o... 524939 MouseReview Recommend office mouse I was hoping you folks could help me out. Here's my situation and requirements:* I don't play games at all* Budget$30.00 or less* Shape as close to old Microsoft Intellimou...
subreddits = rspct["subreddit"].unique()
print(len(subreddits))
subreddits[:50]

305

array(['stepparents', 'bigseo', 'chemistry', 'migraine', 'MouseReview',
'Malazan', 'Standup', 'preppers', 'Invisalign', 'whatsthisplant',
'CrohnsDisease', 'KingkillerChronicle', 'OccupationalTherapy',
'churning', 'Libraries', 'acting', 'eczema', 'Allergies',
'WayfarersPub', 'synthesizers', 'StopGaming', 'stopsmoking',
'eroticauthors', 'amazonecho', 'TalesFromThePizzaGuy',
'Sleepparalysis', 'ProtectAndServe', 'short', 'Fibromyalgia',
'teaching', 'PlasticSurgery', 'insomnia', 'PLC', 'rapecounseling',
'peacecorps', 'paintball', 'autism', 'Nanny', 'Plumbing',
'Epilepsy', 'asmr', 'fatpeoplestories', 'Magic'], dtype=object)
rspct["subreddit"].value_counts()

Dreams             340
HFY                333
Cubers             333
cassetteculture    333
...
foreignservice     265
WritingPrompts     263
immigration        263
TryingForABaby     262
Physics            250
Name: subreddit, Length: 305, dtype: int64

# Modeling

## Label Encoding

# This process naively transforms each class of the target into a number
le = LabelEncoder() # Instantiate a new encoder instance
le.fit(y_train)  # Fit it on training label data

# Transform both using the trained instance
y_train = le.transform(y_train)
y_val = le.transform(y_val)
y_test  = le.transform(y_test)

y_train[:8]

array([ 92, 140,  65,  90, 278,  65, 272, 212])

## Vectorization

A vectorizer is used to extract numerical features (information) from a corpus of natural language text. I used a bag-of-words method of vectorization, which for the most part, disregards grammar.

The output of this vectorizer is a document-term matrix, with the documents (observations, or rows) on one axes and the terms (words, bigrams) on the other. This matrix can be thought of as a sort of vocabulary, or text-number translator.

At first, the "vocabulary" derived from the corpus using the vectorizer was the largest object when serialized. Luckily, there are many options and parameters available to reduce its size, most of which are simply different methods for reducing the number of features (terms) it contains.

One option is to put a hard limit of 100,000 on the number of features in the vocabulary. This is a simple, naive limit on the generated features, and thus, the resulting vocabulary size.

I decided to remove stopwords before vectorization in hopes that this would reduce the size of the vector vocabulary. To my initial surprise, removing the stop words (using NLTK's list) actually increased the size of the serialized vocab from 59mb to 76mb.

After some consideration, I found this to be a reasonable result. I figured that many of the stop words are short ("I", "me", "my", etc.), and their removal caused the average length of words (and therefore bigrams as well) in the vocab to increase. While this may not account for the entirety of the difference, this provides some intuition as to why there is a difference.

Although the vocab without stop words was larger, I ended up using it anyways because it provided an extra ~0.01 in the precision-at-k score of the final model.

lengths = []
three_or_below = []
for word in stop_words:
lengths.append(len(word))
if len(word) <= 4:
three_or_below.append(len(word))

print(f"There are {len(stop_words)} stop words in the list.")
print(f"{len(three_or_below)} are 4 chars long or shorter.")
print(f"Average length is: {np.mean(lengths)}.")

There are 179 stop words in the list.
109 are 4 chars long or shorter.
Average length is: 4.229050279329609.

tfidf = TfidfVectorizer(
max_features=100000,
min_df=10,
ngram_range=(1,2),
stop_words=stop_words,  # Use nltk's stop words
)

# Fit the vectorizer on the feature column to create vocab (doc-term matrix)
vocab = tfidf.fit(X_train)

# Get sparse document-term matrices
X_train_sparse = vocab.transform(X_train)
X_val_sparse = vocab.transform(X_val)
X_test_sparse = vocab.transform(X_test)

X_train_sparse.shape, X_val_sparse.shape, X_test_sparse.shape

((65880, 63588), (7320, 63588), (18300, 63588))

## Feature Selection

As mentioned previously, the size of the corpus means the dimensionality of the featureset after vectorization will be very high. I passed in 100,000 as the maximum number of features to the vectorizer, limiting the initial size of the vocab. However, the features would have to be reduced more before training the model, as it is generally not good practice to have a larger number of features (100,000) than observations (91,500).

To reduce it down from that 100,000, I used a process called select k best, which does exactly what it sounds like: selects a certain number of the best features. The key aspect of this process is how to measure the value of the features; how to find which ones are the "best". The scoring function I used in this case is called ch2 (chi-squared).

This function calculates chi-squared statistics between each feature and the target, measuring the dependence, or correlation, between them. The intuition here is that features which are more correlated with the target are more likely to be useful to the model.

I played around with some different values for the maximum number of features to be selected. Ultimately, I was once again limited by the size of the free Heroku Dyno, and settled on 20,000. This allowed the deployment to go smoothly while retaining enough information for the model to have adequate performance.

selector = SelectKBest(chi2, k=20000)

selector.fit(X_train_sparse, y_train)

X_train_select = selector.transform(X_train_sparse)
X_val_select = selector.transform(X_val_sparse)
X_test_select  = selector.transform(X_test_sparse)

X_train_select.shape, X_val_select.shape, X_test_select.shape

((65880, 20000), (7320, 20000), (18300, 20000))

## Model validation

In this case, the model has a target that it is attempting to predict—a supervised problem. Therefore, the performance can be measured on validation and test sets.

To test out the recommendations I copied some posts and put them through the prediction pipeline to see what kinds of subreddits were getting recommended. For the most part, the predictions were decent.

The cases where the recommendations were a little less than ideal happened when I pulled example posts from subreddits that were not in the training data. The model generally did a good job recommending similar subreddits.

### Baseline

For the baseline model, I decided to go with a basic random forest. This choice was somewhat arbitrary, though I was curious to see how a random forest would do with such a high target cardinality (number of classes/categories).

The baseline precision-at-k metrics for the random forest on the validation set were .54, .63, and .65, for k of 1, 3, and 5, respectively.

def precision_at_k(y_true, y_pred, k=5):
y_true = np.array(y_true)
y_pred = np.array(y_pred)
y_pred = np.argsort(y_pred, axis=1)
y_pred = y_pred[:, ::-1][:, :k]
arr = [y in s for y, s in zip(y_true, y_pred)]
return np.mean(arr)

rfc = RandomForestClassifier(max_depth=32, n_jobs=-1, n_estimators=200)
rfc.fit(X_train_select, y_train)

RandomForestClassifier(max_depth=32, n_estimators=200, n_jobs=-1)
y_pred_proba_rfc = rfc.predict_proba(X_val_select)

# For each prediction, find the index with the highest probability
y_pred_rfc = np.argmax(y_pred_proba_rfc, axis=1)
y_pred_rfc[:10]

array([296, 139, 177,  78,  12, 177, 161, 216,  40,  31])
print("Validation scores:")
print("  [email protected] =", np.mean(y_val == y_pred_rfc))
print("  [email protected] =", precision_at_k(y_val, y_pred_proba_rfc, 3))
print("  [email protected] =", precision_at_k(y_val, y_pred_proba_rfc, 5))

Validation scores:
[email protected] = 0.5368852459016393
[email protected] = 0.6282786885245901
[email protected] = 0.6502732240437158

### Multinomial Naive Bayes

Multinomial naive Bayes is a probabilistic learning method for multinomially distributed data, and one of two classic naive Bayes algorithms used for text classification. I decided to iterate with this algorithm because it is meant for text classification tasks.

The precision-at-k metrics for the final Multinomial naive Bayes model on the validation set were .76, .88, and .9188, for k of 1, 3, and 5, respectively. Performance on the test set was nearly identical: .75, .88, and .9159.

nb = MultinomialNB(alpha=0.1)
nb.fit(X_train_select, y_train)

MultinomialNB(alpha=0.1)

### Evaluate on validation set

y_pred_proba_val = nb.predict_proba(X_val_select)

# For each prediction, find index with highest probability
y_pred_val = np.argmax(y_pred_proba_val, axis=1)
y_pred_val[:10]

array([274, 139,  57,  78,  12,  17, 151, 216,  40, 171])
print("Validation scores:")
print("  [email protected] =", np.mean(y_val == y_pred_val))
print("  [email protected] =", precision_at_k(y_val, y_pred_proba_val, 3))
print("  [email protected] =", precision_at_k(y_val, y_pred_proba_val, 5))

Validation scores:
[email protected] = 0.7599726775956284
[email protected] = 0.8834699453551913
[email protected] = 0.9188524590163935

### Evaluate on test set

y_pred_proba_test = nb.predict_proba(X_test_select)

# For each prediction, find index with highest probability
y_pred_test = np.argmax(y_pred_proba_test, axis=1)
y_pred_test[:10]

array([ 97, 199, 116, 249,  43, 203, 263, 275,  96,  27])
print("Test scores:")
print("  [email protected] =", np.mean(y_test == y_pred_test))
print("  [email protected] =", precision_at_k(y_test, y_pred_proba_test, 3))
print("  [email protected] =", precision_at_k(y_test, y_pred_proba_test, 5))

Test scores:
[email protected] = 0.7498360655737705
[email protected] = 0.8834426229508197
[email protected] = 0.9159562841530055

## Recommendations

The API should return a list of recommendations, not a single prediction. To accomplish this, I wrote a function that returns the top 5 most likely subreddits and their respective probabilities.

# The main functionality of the predict API endpoint
def predict(title: str, submission_text: str, return_count: int = 5):
"""Serve subreddit predictions.

Parameters
----------
title : string
Title of post.
submission_text : string
Selftext that needs a home.
return_count    : integer
The desired number of recommendations.

Returns
-------
Python dictionary formatted as follows:
[{'subreddit': 'PLC', 'proba': 0.014454},
...
{'subreddit': 'Rowing', 'proba': 0.005206}]
"""
# Concatenate title and post text
fulltext = str(title) + str(submission_text)
# Vectorize the post -> sparse doc-term matrix
post_sparse = vocab.transform([fulltext])
# Feature selection
post_select = selector.transform(post_sparse)
# Generate predicted probabilities from trained model
proba = nb.predict_proba(post_select)
# Wrangle into correct format
proba_dict = (pd
.DataFrame(proba, columns=[le.classes_])  # Classes as column names
.T  # Transpose so column names become index
.reset_index()  # Pull out index into a column
.rename(columns={"level_0": "name", 0: "proba"})  # Rename for aesthetics
.sort_values(by="proba", ascending=False)  # Sort by probability
.iloc[:return_count]  # n-top predictions to serve
.to_dict(orient="records")
)
proba_json = {"predictions": proba_dict}

return proba_json

title_science = """Is there an evolutionary benefit to eating spicy food that lead to consumption across numerous cultures throughout history? Or do humans just like the sensation?"""

post_science = """I love spicy food and have done ever since I tried it. By spicy I mean HOT, like chilli peppers (we say spicy in England, I don't mean to state the obvious I'm just not sure if that's a global term and I've assumed too much before). I love a vast array of spicy foods from all around the world. I was just wondering if there was some evolutionary basis as to why spicy food managed to become some widely consumed historically. Though there seem to

It way well be that we just like a tingly mouth, the simple things in life."""

science_recs = predict(title_science, post_science)
science_recs

{'predictions': [{'name': 'GERD', 'proba': 0.009900622287634142},
{'name': 'Allergies', 'proba': 0.009287774623361566},
{'name': 'ibs', 'proba': 0.009150308633162811},
{'name': 'fatpeoplestories', 'proba': 0.00851982441049019}]}
title_pc = """Looking for help with a build"""

post_pc = """I posted my wants for my build about 2 months ago. Ordered them and when I went to build it I was soooooo lost. It took 3 days to put things together because I was afraid I would break something when I finally got the parts together it wouldn’t start, I was so defeated. With virtually replacing everything yesterday it finally booted and I couldn’t be more excited!"""

post_pc_recs = predict(title_pc, post_pc, 10)
post_pc_recs

{'predictions': [{'name': 'lego', 'proba': 0.008418484170536294},
{'name': 'rccars', 'proba': 0.008112076951648648},
{'name': 'MechanicalKeyboards', 'proba': 0.0078335440606017},
{'name': 'fightsticks', 'proba': 0.007633958584830632},
{'name': 'Luthier', 'proba': 0.00716176615193545},
{'name': 'modeltrains', 'proba': 0.007088134228361153},
{'name': 'vandwellers', 'proba': 0.006700262151491209},
{'name': 'cosplay', 'proba': 0.006536648725434882},
{'name': 'homestead', 'proba': 0.006166832450007183}]}
post_title = """What to do about java vs javascript"""

post = """I am a new grad looking for a job and currently in the process with a company for a junior backend engineer role. I was under the impression that the position was Javascript but instead it is actually Java. My general programming and "leet code" skills are pretty good, but my understanding of Java is pretty shallow. How can I use the next three days to best improve my general Java knowledge? Most resources on the web seem to be targeting complete beginners. Maybe a book I can skim through in the next few days?

Edit:

A lot of people are saying "the company is a sinking ship don't even go to the interview". I just want to add that the position was always for a "junior backend engineer". This company uses multiple languages and the recruiter just told me the incorrect language for the specific team I'm interviewing for. I'm sure they're mainly interested in seeing my understanding of good backend principles and software design, it's not a senior lead Java position."""

# === Test out the function === #
post_pred = predict(post_title, post)  # Default is 5 results
post_pred

{'predictions': [{'name': 'cscareerquestions', 'proba': 0.516989539243874},
{'name': 'devops', 'proba': 0.031462691062989795},
{'name': 'interviews', 'proba': 0.02846504725703069},
{'name': 'datascience', 'proba': 0.024227300545057697},
{'name': 'bioinformatics', 'proba': 0.017516176338177075}]}
title_book = "Looking for books with great plot twists"

# This one comes from r/suggestmeabook
post2 = """I've been dreaming about writing my own stort story for a while but I want to give it an unexpected ending. I've read lots of books, but none of them had the plot twist I want. I want to read books with the best plot twists, so that I can analyze what makes a good plot twist and write my own story based on that points. I don't like romance novels and I mostly enjoy sci-fi or historical books but anything beside romance novels would work for me, it doesn't have to be my type of novel. I'm open to experience after all. I need your help guys. Thanks in advance."""

# === This time with 10 results === #
post2_pred = predict(title_book, post2, 10)
post2_pred

{'predictions': [{'name': 'suggestmeabook', 'proba': 0.4070015062748489},
{'name': 'writing', 'proba': 0.14985778378113648},
{'name': 'eroticauthors', 'proba': 0.07159411817054702},
{'name': 'whatsthatbook', 'proba': 0.06062653422250441},
{'name': 'ComicBookCollabs', 'proba': 0.027277418056905547},
{'name': 'Malazan', 'proba': 0.019514923212723943},
{'name': 'TheDarkTower', 'proba': 0.017162701613834493},
{'name': 'WoT', 'proba': 0.011165890302931272},
{'name': 'readyplayerone', 'proba': 0.007566597361383115}]}

## Model deployment

As mentioned, the model, vocab, and feature selector were all serialized using Python's pickle module. In the Flask app, the pickled objects are loaded and ready for use, just like that.

I will go over the details of how the Flask app was set up in a separate blog post.

# Final Thoughts

For me, the most important and valuable aspects of this project were mainly surrounding the challenge of scope management. I constantly had to ask myself, "What is the best version of this I can create given our limitations?"

At first, I thought it would be feasible to predict all of the 1,000+ subreddits in the data, and wasted hours of valuable time attempting to do so. While I had tested various strategies of reducing the complexity of the model, the performance was rather terrible when it was trained on 100 or less examples of each of the complete list of subreddits.

The data scientist who I primarily worked with (we had one data scientist in addition to him and one other machine learning engineer, both of whom did not contribute significantly to the project) kept telling me that I should try reducing the number of classes first, allowing for more examples of each class and fewer classes for the model to predict.

Ultimately, this is the strategy that worked best, and I wasted valuable time by not listening to him the first few times he recommended that strategy. Good teamwork requires the members being humble and listening, something that I have taken to heart since the conclusion of this project.

## Scope Management, Revisited

As time was very short while building this initial recommendation API, there are many things that we wished we could have done but simply did not have the time. Here are a few of the more obvious improvements that could be made.

The first, and most obvious one, is to simply deploy to a more powerful server, such as one hosted on AWS Elastic Beanstalk or EC2. This way, we could use the entire dataset to train an optimal model without worrying (as much) about memory limits.

Second, I could use a Scikit-learn pipeline to validate and tune hyperparameters using cross-validation, instead of a separate validation set. Also, this pipeline could be serialized as a single large object, rather than as separate pieces (encoder, vectorizer, feature selector, and classifier). As a final note for this particular train of thought, Joblib could potentially provide more efficient serialization than the Pickle module, allowing a more complex pipeline to be deployed on the same server.

Third, a model could've been trained to classify the input post first into a broad category. Then, some sort of model could be used to to classify into a specific subreddit within that broad category. I'm not sure about the feasibility of the second part of this idea, but thought it could be an interesting one to explore.

Lastly, different classes and calibers of models could have been tested for use in the various steps in the pipeline. In this case, I'm referring primarily to using deep learning/neural networks. For example, word vectors could be generated with word embedding models such as Word2Vec. Or the process could be recreated with a library like PyTorch, and a framework like FastText.

I plan to explore at least some of these in separate blog posts.

As always, thank you for reading! I'll see you in the next one.


text:
## The lower classes of things

Everything is free to move across borders, except… some lesser things.

It’s a long-standing principle of law, in the “developed” world at least, that “freedom” means the ability to move across borders without hindrance or restriction. This is commonly called “globalization”. Borders fade away and become irrelevant; non-discrimination becomes a defining, enlightened principle; and the world becomes one cosmopolitan village. Except, of course, that this otherwise laudable, advanced, cosmopolitan version of “freedom” applies only to inanimate material objects. To be fair, it does also apply to immaterial objects such as transfers of capital that exist only as abstract ideas, entries in spreadsheets or bits of information.

But one only needs to try to catch a boat from Indonesia to Australia to find out how much this well-established “freedom” and crowning glory of inanimate objects applies to living, breathing, feeling, thinking human beings.

Nonetheless, though it may be a great hypocrisy, this “freedom” of inanimate objects to move across borders is well-established. Such is the world we live in, where consumer goods such as cars and washing machines have advanced rights that humans do not have. This principle is enshrined in international treaties such as the General Agreement on Tariffs and Trade, and the various protocols adhered to be all member States of the World Trade Organisation.

However, this glorious liberty granted to inanimate objects, and even abstract objects, does not quite apply to all objects. Exceptions can be made, provided there is a special reason for it.

And, our world, divided into nation-states, is so organised that the highest decision-making authorities in the world pertain to geographic regions established largely by war, conquest and colonisation. So there is no more sanctified reason to limit freedoms than the military interests of States. In particular, weapons of war have much less freedom to flow across borders. The flow of weapons is tightly regulated — or at least, when it suits a State’s interest to do so.

Such is the idiosyncrasy and backwardness of human civilization in the early 21st century. Rights are given to inanimate objects — even abstract immaterial objects — but not sentient beings. Power lies with a tumultuous collection of clashing commonwealths, whose military interests are the highest good. Destructive weapons plague the world, but weapons are almost alone among inanimate objects in being subject to regulation.

Weapons are deprived of the rights accorded to other inanimate objects, and in this lie with other lower classes of things, such as hazardous waste, disease carriers, dangerous chemicals, plants, animals, and human beings.

Share/Bookmark

Written by dan

April 20th, 2015 at 2:34 pm

## Why your calculator (and computer, and phone…) is a weapon

The Australian government may have classified your calculator — and phone, and computer, and every electronic device you own — as military weapons.

You wouldn’t think your phone, or calculator, or laptop computer, is a weapon on par with tanks, rockets, and missiles. But the Australian government may well have classified it as one, thanks to a very interesting display of scientific and mathematical ignorance.

Now, most people, I think, wouldn’t have too much of a problem with the government sensibly regulating things like munitions, artillery, and weapons of mass destruction. But if that regulation were not sensible, then there might be a problem. And if that regulation extended to include things like your iPad, then there might be a big problem. Unfortunately, the Australian government has quite possibly done precisely that.

The Australian government maintains a list of all the things it considers important to national defence and security. It’s called the Defence and Strategic Goods List. Goods on this list are tightly controlled: there are heavy penalties for proliferating them.

Now, to be fair, compiling such a list is not easy. The list needs to remain current with science and technology, which in many fields is rapidly advancing. Moreover, defining what is and isn’t a military-grade weapon may be a bit more difficult than you think. Some objects have dangerous military uses as well as safe civilian uses.

Nonetheless, there is very little to indicate that the Defence and Strategic Goods List has been designed with the requisite degree of diligence.

Others have raised issues about the List: for instance, the National Tertiary Education Union (NTEU) is running a campaign on the issue and has set up a very informative website about it. Even the Senate Foreign Affairs Defence and Trade Committee report on the topic concluded that the law “would benefit from further scrutiny”, with half the committee describing it as “a complex and flawed piece of legislation”.

That’s not to mention the specific issues have raised about its effects on various research fields. For instance, my colleague Kevin Korb at Monash has calculated that 18 out of 61 masters level courses in the Faculty of Information Technology would fall under the strict controls of the List.

As a mathematician, I want to focus on one particular part of the list: encryption. And this particular part of the list, properly understood, overreaches enormously into everyday life.

### Encryption: for people, not the State

But before going into the details of the List‘s definitions, it’s worth considering: why should encryption be regarded as a weapon in the first place?

Encryption is not a physical thing; messages and information are encrypted by algorithms running in programs on computers or other devices. An algorithm is a procedure, or recipe, that can be implemented on a computer; it’s an abstraction, an idea. Can an abstraction really be regarded as a weapon, or a “strategic good”?

Even if it can, encryption is by its nature not a uniquely military or intelligence thing. Anyone who wants to send a private communication on the internet does it by encryption. It’s a “dual use” technology, in the sense that it has both military and civilian uses. But there are dual use technologies like gas centrifuges, which have a small number of specific usages: gas centrifuges can be used for civilian nuclear reactors, and alternatively for nuclear weapons development. On the other hand, there are “dual use” technologies like cars, which are general purpose objects, used by almost everybody, for a wide variety of uses, but which nonetheless can also be useful to military and intelligence agencies. Encryption is much more like a car than a gas centrifuge.

Military and intelligence services may well use encryption so that their enemies can’t read their messages. But you and I also use encryption so that eavesdroppers can’t read our messages. Everyday users of the internet use encryption to safeguard their privacy. Consumers use encryption to guard against identity theft. Banks use encryption to assure customers of the integrity of financial transactions. Businesses use encryption to ensure the security of online transactions. Hospitals use encryption to ensure the privacy of patient medical records.

Basically, any time anything is done electronically with a need for privacy, encryption is used, and must be used. In a modern technologically advanced society, almost everybody uses it, whether they know it or not. It is far from the unique province of national security, military or intelligence agencies; it has become an essential and routine part of modern life.

When we don’t want our messages to be read by others, we can encrypt them; everybody needs to do this, should do this, and often does do this. So can the military; so can intelligence. What’s the difference?

Well, there is an important difference: ordinary people face highly technologically sophisticated adversaries.

On the one hand, recent military engagements have been fought in weak States such as Iraq, East Timor and Afghanistan. Those wars which have been fought in our name, when not killing hundreds of thousands of civilians, have been fought primarily against weak militaries and relatively unsophisticated armed groups (though, to be sure, these armed groups have sometimes possessed dangerous and lethal weapons, and effective organisation).

On the other hand, since the Snowden revelations — and much earlier for those who were paying attention — essentially all internet users have at least one known adversary snooping on their communications, which is extremely well financed, resourced, and technologically sophisticated: the NSA, along with its Five Eyes partners, which include Australia. Governments might rightly suspect that other governments are spying on them, but we know the NSA engages in mass surveillance of essentially the whole world; as such, citizens are arguably entitled to at least as much self-defence over their information, in the form of encryption, as States. Indeed, States have no inherent right to privacy — the whole point of Freedom of Information laws is that they should be transparent in their operations unless they have good reason — while an individual’s right to privacy is a fundamental human right.

As the comedian John Oliver pointed out in his recent interview with Edward Snowden, many people might not purport to care about surveillance, if they think they’re doing “nothing wrong”. But if it is made clear that mass surveillance means that the NSA has copies of your most private and embarrassing communications — because the nature of mass surveillance is to collect everything — then they might have a different view. Very few people would agree that the government should have copies of dick pics. And more people have sent dick pics than you might think.

Nonetheless, let’s assume for the purposes of argument that there is a justification for regarding at least some aspects of cryptography as “defence” or “strategic goods”. After all, there’s more to cryptography than encoding and decoding messages; encrypted messages can also be analysed, attacked, hacked; and some cryptographic algorithms are more secure than others. (Let’s also put aside the efforts of government, stretching back over decades now, to weaken cryptographic standards and harass researchers in the field.) If the Defence and Strategic Goods List only purported to regulate a truly ultra-secure encryption system, which was out of the reach of individual citizens, and hence was irrelevant to the everyday lives of ordinary people, it might not be quite as bad as if it covered encryption algorithms widely used and available to all.

Which it does. And much, much more — like calculators. But we might need to look at some mathematics in order to understand why.

### Encryption in the Defence and Strategic Goods List

Section 5A002.a.1.b.3 of the List (yes, it really has sub-sub-sub-sub-sections) declares certain things to be subject to its control:

5A002 “Information security” systems, equipment and components therefor, as follows:
a. Systems [and] equipment… for “information security”, as follows…
1. Designed or modified to use “cryptography” employing digital techniques performing any cryptographic function other than authentication or digital signature and having any of the following:
b. An “asymmetric algorithm” where the security of the algorithm is based on any of the following:
3. Discrete logarithms in a group… in excess of 112 bits

This definition appears extremely technical and advanced. But when those words are understood, your calculator — indeed any technology that can do multiplication and division — has just been described as a weapon.

Let’s see why.

### A little pure mathematics — groups

In pure mathematics — specifically, in abstract algebra — there are things called groups. Many of the things that scientists, engineers and students do every day involve groups. Like many concepts in pure mathematics, they are abstract objects: they are defined in terms of axioms, and anything that satisfies the axioms is a group. Many objects that engineers, scientists, and programmers work with every day are groups, and much of the arithmetic everyone knows from primary school can be understood as a special case of group theory.

Roughly speaking, a group — I’ll call it $G$ — is a set containing certain elements, with a certain operation. The operation could be anything, provided it satisfies the axioms. The operation gives you a way to take two elements $a,b$ of $G$ and get a third element $c$. You can denote the operation by a dot, as in

$\displaystyle a \cdot b = c.$

However, the operation must satisfy some requirements, such as: there must be an identity element that “does nothing”; and each element must have an inverse element that “undoes” it.

Sound confusing? Well, it’s an advanced concept and I don’t have space here to give you an abstract algebra course! But here are some examples.

For instance, the group $G$ could be the integers, or whole numbers (often written as $\mathbb{Z}$ ), and the operation could be addition $+$. Well then, when you put 2 and 2 together, you get 4. (See, abstract algebra is as easy as putting 2 and 2 together! Maybe.) When you put 7 and 2 together, you get 9. When you put 7 and -2 together, you get 5. When you put 0 and 11 together, you get 11. In fact, when you put 0 and any integer $n$ together, you get $n$, so 0 “does nothing”: 0 is the identity. And when you put 3 and -3 together, you get 0. When you put 7 and -7 together, you get 0. Each integer $n$ has an inverse, which is the negative $-n$ of that number. We can write these facts as

$\displaystyle 2 \cdot 2 = 4, \; 7 \cdot 2 = 9, \; 7 \cdot (-2) = 5, \; 0 \cdot 11 = 11, \; 0 \cdot n = n, \; 3 \cdot (-3) = 0, \; 7 \cdot (-7) = 0, \; n \cdot (-n) = 0.$

(Usually at school we reserve the dot symbol for multiplication! And, admittedly, mathematicians use the $+$ symbol for some types of groups too. But it’s important for our purposes to emphasise the group operation, so, despite being possibly confusing, I will always write it with a dot.)

For another example, the group $G$ could be the positive numbers (often written as $\mathbb{R}_+$ ), and the operation could be multiplication $\times$. When you put 2 and 2 together, you again get 4! (Again, as easy as putting 2 and 2 together! Again, maybe.) But now when you put 7 and 2 together, you get 14. When you put 2 and $\frac{1}{3}$ together, you get $\frac{2}{3}$. When you put 3 and $1.4$ together, you get $4.2$. When you put 1 and 17 together, you get 17. In fact, when you put 1 and any positive number $x$ together, you get $x$, so 1 “does nothing”: now 1 is the identity. When you put together 3 and $\frac{1}{3}$, you get 1; when you put together 7 and $\frac{1}{7}$, you get 1; and in general the inverse of each positive number $x$ is its reciprocal $\frac{1}{x}$.

$\displaystyle 2 \cdot 2 = 4, \; 2 \cdot \frac{1}{3} = \frac{2}{3}, \; 3 \cdot 1.4 = 4.2, \; 1 \cdot 17 = 17, \; 1 \cdot x = x, \; 3 \cdot \frac{1}{3} = 1, \; 7 \cdot \frac{1}{7} = 1, \; x \cdot \frac{1}{x} = 1.$

Is this reminding you of primary school arithmetic or high school algebra? Good, because you’ll need it to understand why your calculator has just been criminalised.

One last example is one you know intuitively when you tell the time. Let’s say we tell the time on a 12 hour clock. What time is it, 4 hours after 11 o’clock? It’s 3 o’clock. This means that, in clock arithmetic, $11 + 4 = 3$. When we add 11 and 4 in this way, we perform addition as usual but then take the remainder upon division by 12. This kind of arithmetic is known as “modular arithmetic” and it defines for us another group, often written $\mathbb{Z}_{12}$. This group consists of 12 elements, namely the numbers from 1 to 12, and the operation is “clock addition”, which amounts to adding the numbers and then taking the remainder upon division by 12. You can check that 12 is the identity.

OK, enough abstract algebra for now.

Returning to the DSGL definition, you’ll see that it refers to a

group… in excess of 112 bits.

What does this mean? Nothing, it’s nonsense! Groups don’t have bits in them, they have elements in them. It goes to show that you shouldn’t get people who don’t understand what they’re talking about to write laws.

But what I think the authors of the DSGL meant, was a group that requires more than 112 bits to describe an element: that is, a group with more than $2^{112}$ elements.

Now, $2^{112}$ is a rather enormous number. But it’s not so enormous you can’t write it down:

$\displaystyle 2^{112} = 5,192,296,858,534,827,628,530,496,329,220,096.$

Know any groups bigger than that? I do, and I just told you two of them. OK, the clock group $\mathbb{Z}_{12}$ only has 12 elements, which is slightly less than $2^{112}$. But how many elements are there in the group $\mathbb{Z}$ of integers? Or, how many elements are there in the group $\mathbb{R}_+$ of positive numbers? Infinitely many — staggeringly more than $2^{112}$. Indeed, compared to infinity, any finite number is basically nothing. So actually, when the DSGL refers to a “group… in excess of 112 bits”, it could be referring to… well, you know, just your usual number systems, and addition or multiplication.

### Discrete logarithms

Now, the next phrase to understand in the DSGL is “discrete logarithm” — something that sounds truly scary. Who even remembers what logarithms are, and what on earth are “discrete” ones?

Well, I’ll try to remind you of some high school algebra. Think back to when you learned about powers: for instance, $2^5$ usually means to multiply 2 together with itself 5 times. So, if you were asked to find $2^5$, you would do some repeated multiplication and get 32.

But suppose you were asked the reverse question: how many times do you need to multiply 2 by itself in order to get 32? What power of 2 gives you 32? From above, we know the answer is 5. And that is just another way of saying that the logarithm of 32 to base 2 is 5.

$\displaystyle 32 = 2^5 \; \text{means the same as} \; \log_2 32 = 5.$

That is, the logarithm of 32 to base 2 is the power to which you need to raise 2 in order to get 32. And more generally, the logarithm of $a$ to base $b$ is the power to which you need to raise $b$ in order to get $a$. Written in terms of equations,

$\displaystyle a = b^x \; \Leftrightarrow \; \log_b a = x.$

What does this have to do with groups? Well, just as we usually write an exponential like $2^5 = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2$ to mean the you multiply 5 twos together, we can do the same in any group. Instead of repeated multiplication, we now do the group operation repeatedly. So we write, for instance,

$\displaystyle g^5 = g \cdot g \cdot g \cdot g \cdot g$

to indicate that you do the group operation on 5 $g$‘s together.

This leads to some rather strange-looking results. For instance, let’s consider what exponentials mean in the group $\mathbb{Z}$ of integers with addition. Remember that in this group, the operation $\cdot$ means addition. So, for instance,

$\displaystyle 3^6 = 18,$

because you do the group operation — addition — on 3, 6 times, and $3+3+3+3+3+3 = 18$.

On the other hand, in the group $\mathbb{R}_+$ of positive numbers with multiplication, the group operation is multiplication. So in this group

$\displaystyle 3^6 = 729,$

which is a more standard notation! This is what you would normally mean by $3^6$; you multiply it together 6 times.

Finally, in the “clock arithmetic” group $\mathbb{Z}_{12}$,

$\displaystyle 3^6 = 6.$

Why? Because you add 3 to itself 6 times to get “18 o’clock”, which is 6 o’clock on a 12-hour clock.

Now, just as we can write exponentials, we can also write logarithms. Above, we wrote that, in the groups $\mathbb{Z}$, $\mathbb{R}_+$ and $\mathbb{Z}_{12}$ respectively,

$\displaystyle 3^6 = 18, \; 3^6 = 729, \; 3^6 = 6.$

Using the logarithm just how we did above, this means that, in the groups $\mathbb{Z}$, $\mathbb{R}_+$ and $\mathbb{Z}_{12}$ respectively,

$\displaystyle \log_3 18 = 6, \; \log_3 729 = 6 \; \text{and} \; \log_3 6 = 6.$

When you do a logarithm like this in a group, the exponent is always a whole number, and for this reason it’s called a discrete logarithm. (Well, there are some technicalities, but this is the gist of it.) And that is what the List is referring to.

Actually, the discrete logarithm in the group $\mathbb{Z}$ with addition is just a ridiculously fancy way of describing something you learned in primary school. What does

$\displaystyle \log_3 18$

mean in the group $\mathbb{Z}$? It’s asking: how many times do you have to add 3 to itself to get 18? The answer, as we wrote above, is 6. And this is all a very roundabout way of saying that 18 divided by 3 is 6.

So, when you’re talking about the group $\mathbb{Z}$ with addition, the “discrete logarithm” is just a ridiculously fancy way of talking about division: dividing one number by another.

And when the DSGL mentions “discrete logarithms in a group… in excess of 112 bits [sic]”, it covers the division of whole numbers. Therein lies the beginning of a serious problem.

Recall, the List (now annotated) refers to:

b. An “asymmetric algorithm” where the security of the algorithm is based on any of the following:
3. Discrete logarithms in a group… in excess of 112 bits division

You’d better hope there aren’t any asymmetric algorithms, where the security of the algorithm is based on division!

In the next section, I will show you an asymmetric algorithm where the security of the algorithm is based on division.

### Cryptographic algorithms

Now finally, we get to cryptography. The DSGL refers to an “asymmetric algorithm”. Helpfully, the DSGL has a definition section, which defines this phrase as meaning

a cryptographic algorithm using different, mathematically related keys for encryption and decryption.

Well, let’s start with what an algorithm is: an algorithm is just a clear, well-defined procedure that tells you how to do something. It’s like a recipe, except it’s a recipe so precise that it can be implemented on a computer.

A cryptographic algorithm is an algorithm that, as you might surmise, involves cryptography. When you want to send a message, and don’t want it to be read by eavesdroppers, you encrypt it: you apply some procedure to it, called an encryption algorithm. The data is then written in code, or encrypted, and can’t be read by anyone unless they have a secret key to decrypt it. When they do, they use the key on the encrypted message, applying a decryption algorithm, to recover the original message. Taken together, this encryption-and-decryption protocol forms a cryptographic algorithm.

Now, the encryption of a message usually uses a key, and the decryption of a message also uses a key. This key can be a message, a password, a number, or a chunk of data, or something else, but whatever it is, it involves some extra information that goes into the encryption or decryption, in addition to the message itself.

If the key is the same for both encryption and decryption, then the algorithm is called symmetric. If the encryption and decryption keys are different, then the algorithm is called asymmetric.

Now, there are some extraordinarily clever and elegant cryptographic algorithms out there. In one common type of asymmetric algorithm, called public key cryptography, the encryption key is made fully public and open to everyone to see, while the decryption key is kept secret. For instance, on my website you can get my public key, so if you want to send me a secret message you can encrypt it with that public key; but only I have the decryption key, (unless the NSA or ASIO has been snooping into my stuff), so only I can decrypt it.

But there are also some very basic cryptographic algorithms.

For instance, suppose I want to send you a message:

The arc of the moral universe is long, but it bends towards justice.

One of the simplest cryptographic algorithms is known as the Caesar cypher, so-called because Suetonius wrote that it was used by Julius Caesar. This algorithm just shifts every letter along the alphabet a fixed number of places. So, for instance, we might shift every letter three places, as Caesar did: so A becomes D, B becomes E, and so on, up to W becomes Z. Then the alphabet “cycles” so that X becomes A, Y becomes B and Z becomes C. The encrypted message is then

Wkh duf ri wkh prudo xqlyhuvh lv orqj, exw lw ehqgv wrzdugv mxvwlfh.

To decrypt the message, you just shift each letter back by 3!

In a certain sense, the Caesar cypher is based on addition and subtraction: in the above example, we “added 3” to each letter to encrypt, and “subtracted 3” to each letter to decrypt. We could say that the encryption key was 3, and the decryption key was -3.

What I’d like to do now is describe to you a similar idea based on multiplication and division.

The first step in this encryption algorithm — like most encryption algorithms used today — is to convert the message into a number using a standard encoding scheme. Hexadecimal numbers are usually used, because they work well with computers. When I convert my message above to numbers, using a standard scheme, and putting some spaces in, I obtain

54 68 65 20 61 72 63 20 6f 66 20 74 68 65 20 6d 6f 72 61 6c 20 75 6e 69 76 65 72 73 65 20 69 73 20 6c 6f 6e 67 2c 20 62 75 74 20 69 74 20 62 65 6e 64 73 20 74 6f 77 61 72 64 73 20 6a 75 73 74 69 63 65 2e

Importantly, although this number is s written in hexadecimal, this is just a number. In decimal it is (with spaces inserted)

18 987 169 229 968 478 188 669 534 957 610 737 354 921 264 295 841 525 766 864 288 444 422 566 874 896 162 027 606 162 208 969 778 556 762 033 277 602 447 021 524 083 143 238 081 863 623 539 907 326 688 954 151 036 206.

Now, I’m going to perform an encryption algorithm by choosing a secret key. My secret key will be the number 6. (Well, the key’s not so secret now…) There are many reasons to like the number 6.

My encryption algorithm will multiply the message by the key, because, why not. Multiplication is, after all, the name of the game. So I multiply my message by the key (6), and it becomes, in hexadecimal,

1f a7 25 ec 24 8a e5 2c 29 c6 4c 2b a7 25 ec 29 09 ca e4 88 8c 2c 09 67 8c 66 0a eb 45 ec 27 8b 2c 28 a9 c9 66 b0 8c 24 ec 0b 8c 27 8b 8c 24 e6 09 65 ab 2c 2b a9 cc c4 8a e5 ab 2c 27 ec 0b 4b a7 85 45 f1 4

If you try to convert that to text, you’ll get something completely unintelligible: it renders on my computer as

And, just in case our lawmarkers were afraid they didn’t cover every possibility, they also included in the same Act a section 14A which makes it a criminal offence to “publish” or “otherwise disseminate DSGL technology to the public, or to a section of the public, by electronic or other means”. Again, a penalty of 10 years in jail or $425,000 fine applies. However, there is an exception to this one, if the technology has already been lawfully made available to the public. Luckily, multiplication and division have already been made available to the public. Times tables are not yet illegal… I hope. (And in recent amendments in April 2015, this offence was limited to munitions; it no longer applies to dual use technologies. Phew!) ### Other concerns about cryptography Now, the idea of turning multiplication and division into weapons and criminalising their use is so ridiculous that it’s almost impossible to imagine the List being interpreted that way — despite the fact that, taken at face value, this is exactly what it says. But there are other, even greater concerns with the definition of cryptography in the List. Again, we put aside the question of whether it is legitimate to control cryptography at all. I only quoted one sub-sub-sub-sub-section of the List. The section on cryptography covers much more. It essentially covers any sufficiently “strong” cryptography, including symmetric algorithms with key lengths over 56 bits, and RSA with integers over “512 bits”. Now what is a strong key and what isn’t changes rapidly as technology advances. And I don’t think many in the field would say that these prescribed key lengths are so overwhelmingly ultra-secure that they should only be left to military or intelligence agencies. In fact, keys of this length are widely regarded as very weak. For instance, software engineers debate whether they should use 2048 or 4096 bits, well over the prescribed 512. It’s probably more accurate to say that the only cryptography not covered by the List is cryptography so weak that it would be foolish for anyone to use. Supplying it to someone outside Australia is again made into a crime with punishment of 10 years prison or a$425,000 fine.

Concerns over the contents of the list are not limited to cryptography: problems have been raised regarding its impact on various fields, including pharmaceuticals, and science generally.

The law which introduced the crimes of supplying and publishing DSGL technology is the Defence Trade Controls Act, passed in 2012. However, the criminal offences were not due to come into effect until 16 May 2015. With a deadline looming that could criminalise vast amounts of scientific research — including research which is entirely non-military-related — the law was amended and the changes came into effect on 2 April 2015.

These new changes do little to alleviate any of the concerns raised here. They do however provide a year of breathing room: the crimes of supplying and publishing DSGL technology now will not come into effect until 2 April 2016.

Now, while the criminal offences in the Defence Trade Controls Act are unique to Australia, the listing of “weapons” in the Defence and Strategic Goods List is not. Much of the List is based on the Wassenaar Arrangement, an international arms control agreement between 41 countries.

The section of the Australian List on cryptography is copied verbatim from the Wassenaar control list on “Information Security”.

So the criticisms of cryptography in the Australian List are not unique to Australia — they are common to any of the 41 States in the Wassenaar Arrangement.

Yes, that’s right — calculators, computers and phones are covered by international arms control treaties. The madness is worldwide; your calculator is part of the global arms trade.

Written by dan

April 19th, 2015 at 5:17 pm

format: plain


text:
SEARCH HOME
 Math Central Quandaries & Queries
 Question from Nazrul, a teacher: If x is proportional to y and y is proportional to z , how can I prove that (x^2+y^2)^3/2 is proportional to z^3

Nazrul,

To say that p is proportional to q means that there is a constant so that p is the constant times q.

• If x is proportional to y then there is a constant (I am going to call it C) so that x = Cy

• If y is proportional to z there is a constant (this one I'll call K) so that y = Kz.

Use these two facts to eliminate x and y from the expression (x2+y2)3/2, and express it in terms of z. Is the result proportional to z3?

Harley

Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.


text:
# [pstricks] [animate.sty] producing a sequence of Pstricks files

Herbert Voss Herbert.Voss at FU-Berlin.DE
Sun Feb 10 11:35:47 CET 2008

Patrick Drechsler schrieb:

> I am still trying to understand the contents of the links provided on
> this page. Although the examples by Manuel Luque look very cool, they
> are way over my head (mainly because my french is very rusty).
>
> Nevertheless, the examples for using the package "animate" are similar
> to the examples published with the documentation of the package. They
> use the *inline* capabilities to produce animations. As I wrote in my
> original mail:

\documentclass[12pt,a4paper]{article}
\usepackage{animate}
\usepackage{pstricks}

\begin{document}
\newcounter{count}

\noindent%
\begin{animateinline}[
begin={\begin{pspicture}(5,5)},
end={\end{pspicture}},
width=\linewidth,
controls]{5}
\whiledo{\thecount<5}{%
\newframe
\pscircle(\thecount,\thecount){1}
\stepcounter{count}%
}%
\end{animateinline}

\end{document}

latex->dvips->ps2pdf

Herbert


text:
• FEATURED

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

## Where to go to learn 3D modeling...complete beginner

Old topic!

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

28 replies to this topic

### #21MrDaaark  Members

Posted 18 February 2013 - 11:48 AM

Don't ever use .blend files with Unity. Every time you edit and save your .blend file, Unity responds by making a mess of everything. Export your blender files to fbx, and then put those in the Unity folder to be imported.

### #22Benderwiz  Members

Posted 22 February 2013 - 04:45 PM

Free!

Absolute Beginners Blender 3D tutorials

I watched some of his videos and recommend watching doing these tutorials before buying a book.

These tutorials will get you used to the interface and viewing in 3D space.

### #23kibikichu  Members

Posted 09 March 2013 - 11:04 PM

I would go Google the new Boston (sorry I don't have the link at the moment) the tutorials start from very very begging and is easy to understand. The site also has courses set up too,with projects and etc. It was sooooo helpful

### #24EddieV223  Members

Posted 10 March 2013 - 03:49 PM

Check out www.3dbuzz.com

If this post or signature was helpful and/or constructive please give rep.

// C++ Video tutorials

// Easy to learn 2D Game Library c++

SFML2.2 Tutorials http://www.sfml-dev.org/tutorials/2.2/

// Excellent 2d physics library Box2D

// SFML 2 book

### #25Serapth  Members

Posted 19 March 2013 - 01:17 PM

I've never been a huge fan of a lot of the Blender tutorials, as I don't really like video, and the best tutorials are video tutorials, or outdated.

So ive been slowly putting together a series of tutorials with a basic premise.  I assume my audience is a programmer with zero prior experience with blender.  Each tutorial is entirely static, with the exception of animated images ( no video ).  Each concludes with a reference table of the shortcuts used in the tutorial.

The end goal of the series is to have a tutorial that covers each area ( modelling, animating, texturing, rendering ).  It teaches only HOW, not technique... thats a subject for other more artistic minded people; and something for experience to teach you.

Right now though, I've only go through 3/4 of the modelling section, hope you find these useful, if nothing else, they are somewhat unique! ;)

Blender for Programmers -- Part 1: Introduction

Blender for Programmers -- Part 2: Selection and Navigation

Blender for Programmers -- Part 3: Introduction to 3D modelling

Then a somewhat related post I made earlier that is going to be incorporated into the above soon:

BMesh in Action: What's so special about ngons anyway?

### #26jwezorek  Members

Posted 20 March 2013 - 11:29 AM

I've never been a huge fan of a lot of the Blender tutorials, as I don't really like video, and the best tutorials are video tutorials, or outdated.

So ive been slowly putting together a series of tutorials with a basic premise.  I assume my audience is a programmer with zero prior experience with blender.  Each tutorial is entirely static, with the exception of animated images ( no video ).  Each concludes with a reference table of the shortcuts used in the tutorial.

The end goal of the series is to have a tutorial that covers each area ( modelling, animating, texturing, rendering ).  It teaches only HOW, not technique... thats a subject for other more artistic minded people; and something for experience to teach you.

Right now though, I've only go through 3/4 of the modelling section, hope you find these useful, if nothing else, they are somewhat unique! ;)

Blender for Programmers -- Part 1: Introduction

Blender for Programmers -- Part 2: Selection and Navigation

Blender for Programmers -- Part 3: Introduction to 3D modelling

Then a somewhat related post I made earlier that is going to be incorporated into the above soon:

BMesh in Action: What's so special about ngons anyway?

Haven't had time to read through your tutorials, but I'd like to thank you for doing this. I had the exact thought that someone should write a book (or tutorial series) called "Blender for Programmers".

One thing that you should really cover is the Python interface. Basically when I can't figure out how to do something in the Blender UI -- which is beyond often, I'm beyond a Blender newbie, I'm a Blender user who cobbles something together by google searching how to do it -- I usually end up writing a python script to do what I need through the script interface. Obviously this only works for relatively simple things but is good for programmers who just need to get something done.

### #27Serapth  Members

Posted 20 March 2013 - 12:07 PM

I've never been a huge fan of a lot of the Blender tutorials, as I don't really like video, and the best tutorials are video tutorials, or outdated.

So ive been slowly putting together a series of tutorials with a basic premise.  I assume my audience is a programmer with zero prior experience with blender.  Each tutorial is entirely static, with the exception of animated images ( no video ).  Each concludes with a reference table of the shortcuts used in the tutorial.

The end goal of the series is to have a tutorial that covers each area ( modelling, animating, texturing, rendering ).  It teaches only HOW, not technique... thats a subject for other more artistic minded people; and something for experience to teach you.

Right now though, I've only go through 3/4 of the modelling section, hope you find these useful, if nothing else, they are somewhat unique! ;)

Blender for Programmers -- Part 1: Introduction

Blender for Programmers -- Part 2: Selection and Navigation

Blender for Programmers -- Part 3: Introduction to 3D modelling

Then a somewhat related post I made earlier that is going to be incorporated into the above soon:

BMesh in Action: What's so special about ngons anyway?

Haven't had time to read through your tutorials, but I'd like to thank you for doing this. I had the exact thought that someone should write a book (or tutorial series) called "Blender for Programmers".

One thing that you should really cover is the Python interface. Basically when I can't figure out how to do something in the Blender UI -- which is beyond often, I'm beyond a Blender newbie, I'm a Blender user who cobbles something together by google searching how to do it -- I usually end up writing a python script to do what I need through the script interface. Obviously this only works for relatively simple things but is good for programmers who just need to get something done.

Thanks.

You know how we always give advice like "it doesn't matter which programming language you choose, they all work well" in the For Beginners threads... well, whenever I say this, I am lying a bit.  See, I hate Python.  I can't really put into words why, but after using dozens of programming languages in my life, Python and Perl ( and from my limited exposure, Objective C ) are the only two that I truly hate.  That language and I, we dont really see eye to eye.

So, I may not be the best person to write anything Python related. ;)  I've stayed away from Blender's programming side specifically because of the Python powered nature.

### #28jwezorek  Members

Posted 20 March 2013 - 04:01 PM

You know how we always give advice like "it doesn't matter which programming language you choose, they all work well" in the For Beginners threads... well, whenever I say this, I am lying a bit.  See, I hate Python.  I can't really put into words why, but after using dozens of programming languages in my life, Python and Perl ( and from my limited exposure, Objective C ) are the only two that I truly hate.  That language and I, we dont really see eye to eye.

Python doesn't bother me much, although I don't see what the reverence that some people  have for it is all about.  My only problem with Python is that I just don't see how not having to declare variables is ever helpful. But I don't hate it -- and co-routines are cool.

Perl on the other hand ... I mean, I just hate Perl. I would rather have a toe amputated than have to write something largish in Perl again ( I wouldn't want to write anything smallish either but would probably do so to save one of my toes). And further, I can't understand why anyone now or ever liked Perl -- it makes me question people's sanity, or at least wonder if their consciousness is fundamentally different than mine.

Edited by jwezorek, 20 March 2013 - 04:05 PM.

### #29Serapth  Members

Posted 21 March 2013 - 07:46 AM

You know how we always give advice like "it doesn't matter which programming language you choose, they all work well" in the For Beginners threads... well, whenever I say this, I am lying a bit.  See, I hate Python.  I can't really put into words why, but after using dozens of programming languages in my life, Python and Perl ( and from my limited exposure, Objective C ) are the only two that I truly hate.  That language and I, we dont really see eye to eye.

Python doesn't bother me much, although I don't see what the reverence that some people  have for it is all about.  My only problem with Python is that I just don't see how not having to declare variables is ever helpful. But I don't hate it -- and co-routines are cool.

Perl on the other hand ... I mean, I just hate Perl. I would rather have a toe amputated than have to write something largish in Perl again ( I wouldn't want to write anything smallish either but would probably do so to save one of my toes). And further, I can't understand why anyone now or ever liked Perl -- it makes me question people's sanity, or at least wonder if their consciousness is fundamentally different than mine.

Perl is one of the only languages I have developed a bias against.

Back when I worked as a rank and file programmer, I never really held much bias against other programmers, be it self taught, university educated, from a Java enterprise background or someone who worked on realtime systems.  They all had different approaches sure, but generally could get the job done and if they had the aptitude, they could work together in a team setting.

The one strong exception to this rule were the perl "programmers".  Not the people that automate their lives using perl scripts, instead the ones that made complete systems out of this hateful language.  These people quite honestly tended to be among the worst programmers I ever had to deal with.  Short sited, no concept of design, unwilling to take the time to actually learn the language they were using, etc...  Seeing C++ generated by a perl programmer was always... interesting.  Reinvented wheels and two letter variables everywhere...

Of course, those are only my experiences only, YMMV.

Old topic!

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


text:
HSC Science (Computer Science) 12th Board ExamMaharashtra State Board
Account
It's free!

Share

Books Shortlist

# Solution - If a=i+2j, b=−2i+j, c=4i+3j , find x and y such that c=xa+yb - HSC Science (Computer Science) 12th Board Exam - Mathematics and Statistics

ConceptLinear Combination of Vectors

#### Question

If bara=bari+2barj, barb=-2bari+barj,barc=4bari+3barj,  find x and y such that barc=xbara+ybarb

#### Solution

Given that  veca = hati +2hatj, vecb = −2hati +hatj, vecc = 4hati + 3hatj

We need to find x and y such that vecc = xveca + yvecb

Substituting the values of a, b and c, in  vec c = xveca + yvecb, we have,

4hati + 3hatj = x(hat i +2hatj )+ y (-2hati +hatj)

4hati + 3hatj = (x -2y)hat i + (2x + y) hatj

Comparing the coefficients of i and j on both the sides, we have,
x-2y= 4
and
2x + y = 3
Solving the above simultaneous equations, we have,
x = 2 and y = -1

Is there an error in this question or solution?

#### APPEARS IN

2014-2015 (March) (with solutions)
Question 1.2.5 | 2 marks

#### Video TutorialsVIEW ALL [1]

Solution for question: If a=i+2j, b=−2i+j, c=4i+3j , find x and y such that c=xa+yb concept: null - Linear Combination of Vectors. For the courses HSC Science (Computer Science), HSC Science (General) , HSC Arts, HSC Science (Electronics)
S


text:
# Isn't it infinity?

Calculus Level 3

How many functions are there such that $$f''(x)>0$$ for every $$x>0$$, $$f(1)=-5$$ and $$f(2)=-11$$ and f(0)=0 ? If the number of functions is $$n$$, then submit your answer as $$n!+n-1$$.

Notation: $$f''(x)$$ means second derivative of $$f(x)$$.

×


text:
# Better computation of the Jacobian matrix for algebraic solver

This came up in a conversation with @seantalts.

When solving an algebraic equation, we find y^* such that f(y^*, \theta) = 0 where \theta are our model parameters. We compute the jacobian matrix of y with respect to \theta using the implicit function theorem:

J = - [J^y(y^*, \theta)]^{-1} J^\theta(y^*, \theta)

where J^y is the Jacobian matrix of f with respect to y, etc.

Currently, I compute J^y and J^\theta separately using Jacobian(), but it could be more efficient to compute \tilde J := [J^y, J^\theta] in one go. The cost should be roughly halved, since it’s the same amount of sweeps in reverse-mode autodiff.

Any objections to this idea? If not, I’ll submit an issue, fix it, and do the PR.

That’s the way to do it – build up the full Jacobian and then partition it into the y and \theta blocks. It’s not so much about the number of sweeps here but rather the shared computations.

That said there is the potential for some addition improvements. If you don’t compute everything at once then you could compute J^{\theta} v in a single reverse mode sweep. If you compute and invert J^{y} separately you could then compute J v with an additional matrix-vector product and implement the function using the Jacobian-vector product formalism.

One could consider going even further and using verse mode to compute products of the form J^{y} b for iterative solution of J^{y} b = J^{\theta} v but my guess is that the autodiff overhead would render that less efficient than just computing J^{y} at once and explicitly inverting.

Nope. And Jacobian calcs should get faster and less memory intensive when we get forward-mode working.

Just make sure to test that.

There’s a potential for piggyback if Newton’s iteration is used to solve for y^{\ast}, since J^y is required anyway. When that’s the case, you don’t want to always compute J^y and J^{\theta} at the same time because J^y gets updated much more frequently. So maybe design accordingly based on the scenario, assuming Newton solver is still on the list.

@yizhang Newton solver is still on the list – I’ve just had a busy semester – , and Powell’s method also uses derivatives, so your comment applies there too. In the solver, J^y is computed at each iteration except at the solution, which is what we need for the sensitivities. The computation of J^y and J^\theta at the solution only happens inside the chain() method, so there shouldn’t be any redundant calculations.

@Bob_Carpenter
+1 for forward mode.
I’ll test the efficiency gain. When I say halved, I mean for computing the sensitivities, but at this point, most of the cost comes from solving the algebraic equation. I’ll check this too.

@betanalpha Calculating J^y v would work. Here v is the adjoint of y^* with respect to the log density, and is a member of the vari class. We would need a version of Jacobian() function that lets you specify an initial cotangent vector. Is there a way of doing this without digging to deep into Stan’s autodiff?

On the other hand, I’m not sure computing J^\theta and J^y v is more efficient than computing \tilde J. But worth trying out. What could also be valuable is computing J^y y^{(i)} in one sweep at each iteration of the solver.

I like the idea of sensitivity for J^y b = J^\theta v directly.

Yeah, this is all of the Jacobian-adjoint product infrastructure that @bbbales2 implemented. I thought there was a nice wiki page demonstrating the functionality but I couldn’t find it.

If only J^{y} y^{i} is needed for the Powell updates then you should definitely only compute that!

Relative efficiency can be worked out using the known scalings of reverse mode. If there are N states and K parameters then \tilde{J}, a N \times (N + K) matrix can be computed in N reverse mode sweeps. J^{\theta} v can be computed in one verse mode sweep. J^{y} would require N reverse mode sweeps, but they would be cheaper than the full reverse mode sweeps for \tilde{J} because the parameters would be treated as constants. Ultimately there’s going to be some transition for large enough K where computing the Jacobian adjoint product is more efficient than computing the full \tilde{J}.

If only J^y y^i is needed for the Powell updates then you should definitely only compute that!

Ok. I think the devil will be in the details here. If memory serves well, Eigen’s function for Powell’s method accepts J^y as an argument, but not a method to compute J^y y. But I need to break the code open, and take a closer look.

EDIT: you don’t need J^y y^i for the update, rather something of the form [J^y]^{-1}f(y^i) akin to what is used in Newton’s method. So computing the directional derivative at each iteration is not an interesting path.

EDIT 2: A small aside: Eigen does a lot of interesting manipulations on J^y (see the file HybridNonLinear.h in Eigen’s unsupported module). It notably finds it QR decomposition to compute [J^y]^{-1}f(y^i).

There are a couple examples for how the Jacobian-adjoint stuff @betanalpha mentioned pieces together over here: Adj_jac_apply, Adj_jac_apply

Lemme know if you end up trying it and it’s not magically working. The templating makes the compiler errors pretty annoying to dig through.

Alright, let’s give it a try.

For the INLA optimization problem, I think we would gain much from computing Jv with the Jacobian-vector product formalism. Indeed we have J^y in analytical form. J^\theta on the other hand is computed in n sweeps, where n is the dimension of y. In practice y is high-dimensional so this computation is very inefficient. With the right initial cotangent, we can do this in one sweep.

Now, let l be the log density and f the algebraic system. I’ll use the convention that J^x_y is the Jacobian of x with respect to y. From the chain rule and the implicit function theorem:

\begin{eqnarray} J^l_\theta & = & (J^y_\theta)^T (J^l_y)^T \\ & = & - (J^f_\theta)^T ([J^f_y]^{-1})^T J^l_y \\ & = & - (J^f_\theta)^T ([J^f_y]^T)^{-1} J^l_y \\ & =: & - (J^f_\theta)^T w \end{eqnarray}

where w is the wanted initial cotangent. I’m not sure how useful this is in general, but I’ll try it out on the specialized solver for the INLA problem.


text:
# Why free-fall acceleration is considered constant rather than increasing? [duplicate]

The force acting on a body of mass $$m$$ is $$mg$$, where $$g$$ is acceleration of free fall ! But why should there be a #uniform acceleration of free-fall in the first place? As per Newton's universal law of gravitation there's an inverse square law of force acting with respect to separation ; Thus as object falls towards Earth separation decreases and so the force, and hence acceleration, should likewise increase! How to reconcile this argument with a universally accepted constant acceleration $$g$$?

## marked as duplicate by user191954, Aaron Stevens, Alfred Centauri, Qmechanic♦Oct 4 '18 at 13:07

• Becuse problems with which we deal in mechanics are usually at the surface of earth and if there is any change in height it will be so less that it would not significantly change thhe value of g – Sourabh Oct 4 '18 at 11:08
• Possible duplicate of Why is acceleration due to gravity a constant? – user191954 Oct 4 '18 at 11:56

You're correct. The further away you are from Earth, the lesser the gravitational acceleration.

The way to reconcile that with the use of a constant $$g$$ for gravitational acceleration in most contexts is to look at how much your height is changing in the situation, and how much that would change the value of the acceleration.

You're likely to find that in most situations, the change in this acceleration is lower than the accuracy of the gravitational acceleration that you use. For example, even at 400 km above the Earths surface where satellites orbit, the acceleration due to gravity is still about 90% of the gravity on the surface.

People who design and analyze things that are far from the Earths surface do have to take the non-constant gravitational acceleration into effect. On the small scale it is usually applied to by the layman, the change is so small that it gets overshadowed by the lack of precision in all the values you use.

• Gotcha ! Strictly speaking free-fall acceleration g indeed increases, but for all practical purposes it hardly changes at all :g actually varies as 1/r², where r is the separation between the two centres of mass. Thus, even if dg/g = 2dr/r, the latter is barely of the order of 10⁻⁴ for the first 100 m height – Jean Luc Baudoin Oct 5 '18 at 16:39

You can reconcile this by the fact that Newton's gravitational law is nearly constant on such a small length scale.

We start with the inverse square law: $$\vec F=-\frac{GMm}{r^2}\hat r$$ where $$M$$ is the mass of the Earth, and $$m$$ is the mass of an object on the Earth's surface.

Now let's pick a point on the surface of the Earth a distance $$r_0$$ from the Earth's center (i.e., $$r_0$$ is the radius of the Earth, assuming a spherical Earth). The value of $$g$$ (the constant acceleration due to gravity at the Earth's surface) is then given by $$g=\frac{GM}{r_0^2}$$

Now, let's look at what the gravitational force is at a distance $$\Delta r$$ from the surface:

$$\vec F(r_0+\Delta r)\approx \vec F(r_0)+\Delta r\left.\frac{d\vec F}{dr}\right|_{r=r_0}=-\frac{GMm}{r_0^2}\hat r+\frac{2GMm}{r_0^3}\Delta r\ \hat r=-gm\ \hat r+\frac{2gm}{r_0}\Delta r\ \hat r$$

Now, typically when we are talking about accelerations on Earth's surface, we are looking at $$\Delta r\ll r_0$$ , or $$\frac{\Delta r}{r_0}\ll 1$$. (Or if you don't replace variables with $$g$$, you have $$\frac{\Delta r}{r_0^3}\ll \frac{1}{r_0^2}$$, or $$\Delta r \ll r_0$$). Therefore, it is a pretty good approximation that if you are looking at distances close to the Earth's surface, we can treat the gravitational force as constant. $$\vec F=-gm\ \hat r$$

From here, we can use Newton's second law for any object of mass $$m$$ accelerating near Earth's surface only due to the force of gravity $$\vec a = \frac{\vec F}{m}= -g\ \hat r$$ giving us our constant acceleration.


text:
# Difference between revisions of "2017 AMC 10A Problems/Problem 25"

## Problem

How many integers between $100$ and $999$, inclusive, have the property that some permutation of its digits is a multiple of $11$ between $100$ and $999?$ For example, both $121$ and $211$ have this property.

$\mathrm{\textbf{(A)} \ }226\qquad \mathrm{\textbf{(B)} \ } 243 \qquad \mathrm{\textbf{(C)} \ } 270 \qquad \mathrm{\textbf{(D)} \ }469\qquad \mathrm{\textbf{(E)} \ } 486$

## Solution 1

There are 81 multiples of 11. Some have digits repeated twice, making 3 permutations.

Others that have no repeated digits have 6 permutations, but switching the hundreds and units digits also yield a multiple of 11. Therefore, assign 3 permutations to each multiple.

There are now 81*3 = 243 permutations, but we have overcounted*. Some multiples of 11 have a zero, and we must subtract a permutation for each.

There are 110, 220, 330 ... 990, yielding 9 extra permutations

Also, there are 209, 308, 407...902, yielding 8 more permutations.

Now, just subtract these 17 from the total (243), getting 226. $\boxed{\textbf{(A) } 226}$

• Note: If short on time, note that 226 is the only answer choice less than 243, and therefore is the only feasible answer.

## Solution 3

We note that we only have to consider multiples of $11$ and see how many valid permutations each has. We can do casework on the number of repeating digits that the multiple of $11$ has:

$\textbf{Case 1:}$ All three digits are the same. By inspection, we find that there are no multiples of $11$ here.

$\textbf{Case 2:}$ Two of the digits are the same, and the third is different.

$\textbf{Case 2a:}$ There are $8$ multiples of $11$ without a zero that have this property: $121$, $242$, $363$, $484$, $616$, $737$, $858$, $979$. Each contributes $3$ valid permutations, so there are $8 \cdot 3 = 24$ permutations in this subcase.

$\textbf{Case 2b:}$ There are $9$ multiples of $11$ with a zero that have this property: $110$, $220$, $330$, $440$, $550$, $660$, $770$, $880$, $990$. Each one contributes $2$ valid permutations (the first digit can't be zero), so there are $9 \cdot 2 = 18$ permutations in this subcase.

$\textbf{Case 3:}$ All the digits are different. Since there are $\frac{990-110}{11}+1 = 81$ multiples of $11$ between $100$ and $999$, there are $81-8-9 = 64$ multiples of $11$ remaining in this case. However, $8$ of them contain a zero, namely $209$, $308$, $407$, $506$, $605$, $704$, $803$, and $902$. Each of those multiples of $11$ contributes $2 \cdot 2=4$ valid permutations, but we overcounted by a factor of $2$; every permutation of $209$, for example, is also a permutation of $902$. Therefore, there are $8 \cdot 4 / 2 = 16$. Therefore, there are $64-8=56$ remaining multiples of $11$ without a $0$ in this case. Each one contributes $3! = 6$ valid permutations, but once again, we overcounted by a factor of $2$ (note that if a number ABC is a multiple of $11$, then so is CBA). Therefore, there are $56 \cdot 6 / 2 = 168$ valid permutations in this subcase.

Adding up all the permutations from all the cases, we have $24+18+16+168 = \boxed{\textbf{(A) } 226}$.

## Solution 4

We can first overcount and then subtract. We know that there are $81$ multiples of $11$.

We can then multiply by $6$ for each permutation of these multiples. (Yet some multiples do not have six distinct permutations.)

Now divide by $2$, because if a number $abc$ with digits $a$, $b$, and $c$ is a multiple of $11$, then $cba$ is also a multiple of $11$ so we have counted the same permutations twice.

Basically, each multiple of $11$ has its own $3$ permutations (say $abc$ has $abc$ $acb$ and $bac$ whereas $cba$ has $cba$ $cab$ and $bca$). We know that each multiple of $11$ has at least $3$ permutations because it cannot have $3$ repeating digits.

Hence we have $243$ permutations without subtracting for overcounting. Now note that we overcounted cases in which we have $0$'s at the start of each number. So, in theory, we could just answer $A$ and then move on.

If we want to solve it, then we continue.

We overcounted cases where the middle digit of the number is $0$ and the last digit is $0$.

Note that we assigned each multiple of $11$ three permutations.

The last digit is $0$ gives $9$ possibilities where we overcounted by $1$ permutation for each of $110, 220, ... , 990$.

The middle digit is $0$ gives $8$ possibilities where we overcount by $1$. $605, 704, 803, 902$ and $506, 407, 308, 209$

Subtracting $17$ gives $\boxed{\textbf{(A) } 226}$.

Now, we may ask if there is further overlap (i.e if two of $abc$ and $bac$ and $acb$ were multiples of $11$). Thankfully, using divisibility rules, this can never happen, as taking the divisibility rule mod $11$ and adding, we get that $2a$, $2b$, or $2c$ is congruent to $0\ (mod\ 11)$. Since $a, b, c$ are digits, this can never happen as none of them can equal $11$ and they can't equal $0$ as they are the leading digit of a three-digit number in each of the cases.

## Solution 6 (1 but quicker)

The smallest multiple of $11$ above $100$ is $110 = 11 \cdot 10$, while the largest multiple of $11$ less than $999$ is $990 = 11 \cdot 90$. This means there are $90 - 10 + 1 = 81$ multiples of $11$ between $100$ and $999$.

As there are $3$ permutations for each multiple, we have $81 * 3 = 243$. However, we have overcounted, as numbers like $099$ shouldn't be counted. Looking at the answer choices, we notice there is only one that is less than $243$, and so we have our answer as $\boxed{\textbf{(A) } 226}$.

## Video Solution

Two different variations on solving it. https://youtu.be/z5KNZEwmrWM

https://youtu.be/MBcHwu30MX4 -Video Solution by Richard Rusczyk

~savannahsolver


text:
## Random affine code tree fractals and Falconer-Sloan condition

Type:
Type:
Site:
Date:
18/09/2015 - 11:10 - 12:10
Salle:
05
Orateur:
LI Bing
Localisation:
Université de technologie de Chine méridionale
Localisation:
République populaire de Chine
Résumé:

We calculate the almost sure dimension for a general class of random affine code tree fractals in $\mathbb R^d$. The result is based on a probabilistic version of the Falconer-Sloan condition $C(s)$ introduced in Falconer and Sloan (2009). We verify that, in general, systems having a small number of maps do not satisfy condition $C(s)$. However, there exists a natural number $n$ such that for typical systems the family of all iterates up to level $n$ satisfies condition $C(s)$. This is a joint work with Esa Järvenpää, Maarit Järvenpää, and Örjan Stenflo.