text:
# Machine Learning for Hackers, Chapter 12

In the final chapter the authors introduce Support Vector Machines (SVM). What SVM do are generalize linear decision boundaries for classification. Like the other chapters, this one avoids math and simply shows you how to use SVM in R. It then analyzes the spam mail dataset from chapter 3 using SVM, kNN and regularized logistic regression and compares their performance.

The first section of the chapter demonstrates SVM using a toy dataset. The dataset has two predictors (X and Y) and a response (a classification of 0 or 1). The dataset looks like this plotted:

I show this figure because the book is printed in black and white and you can’t tell class 0 from class 1 in the picture on page 276. That’s a problem that plagues this entire chapter. Anyway, what we have here is data that require a non-linear decision boundary. In other words we can’t draw a single straight line through the picture to indicate a boundary between the blue and red dots. This is where SVM comes in handy. Here’s the SVM code they use to analyze this dataset. As you’ll see they play around with the svm function from the e1071 package to show how changing certain parameters affects the quality of predictions. I didn’t get anything new out of this section that I felt compelled to blog about. It’s basically an extended example of how to use the svm function similar to what you might see on a help page. They do make use of the melt function from the reshape package, which is very cool and useful, but I already wrote about that in the Chapter 8 post.

The second section is “Comparing Algorithms”. They resurrect the spam dataset from chapter 3 and analyze it using SVM, kNN and regularized logistic regression. Recall the spam dataset was converted to a term document matrix (TDM) where the emails are the rows and the columns are terms. So email #1 would be row 1. In that row we would see the number of times the words in the column headers appeared. For example. the word “banner” appears o times in email #1. Column 1 of the spam dataset indicates whether or not the email is spam. They create testing and training sets and use those to create models and compare the different classification methods. Again, there’s nothing too fancy here where R programming is concerned, or at least nothing I haven’t already covered. They determine logistic regression works best for classifying spam email.

Now here’s something interesting worth noting. Instead of prepping the spam data as they did in Chapter 3, they skip directly to loading it into R as follows:

load('data/dtm.RData')

But how did they save that data as dtm.Rdata? By doing something like this:

save(dtm, file="dtm.RData")

…where dtm was a matrix. I say “matrix” because that’s what dtm.RData is when it gets loaded.

Another snippet worth noting is how they create their training and test sets. First they randomly select numbers as the indices for selecting the training data from the number of rows from the spam matrix. Then they take whatever numbers were not selected and make those the indices for the test data:

training.indices <- sort(sample(1:nrow(dtm), round(0.5 * nrow(dtm))))
test.indices <- which(! 1:nrow(dtm) %in% training.indices)

The dtm dataset has 3249 rows. So the sample function selects (without replacement) from the numbers 1 through 3249. The second argument to the sample function says how many to sample, which in this case is $0.5 \times 3249 = 1624.5$. That gets rounded to 1624 by the round function. So 1624 numbers are sampled without replacement from the numbers 1 through 3249. And then they get sorted in ascending order. Those are the indices for the training data. To get the test data, they use the value matching %in% operator to look for matches, but negate the matches to get all the numbers that were not selected with the sample function.

The code "1:nrow(dtm) %in% training.indices" returns a logical vector with 3249 elements. 1624 are TRUE, the rest are FALSE. The code "! 1:nrow(dtm) %in% training.indices" returns the opposite logical vector. Now 1624 are FALSE and the rest are TRUE. Finally, inserting that strip of code into the which function returns the indices of the vector that are FALSE. Therefore both training.indices and test.indices are vectors of numbers from 1:3249, with no overlap between them. For example:

> training.indices[1:10]
[1] 1 2 6 9 11 12 15 16 18 19
> test.indices[1:10]
[1] 3 4 5 7 8 10 13 14 17 24

These vectors of numbers are then used to select the training and test data as follows:

train.x <- dtm[training.indices, 3:ncol(dtm)]
train.y <- dtm[training.indices, 1]
test.x <- dtm[test.indices, 3:ncol(dtm)]
test.y <- dtm[test.indices, 1]

I thought that was good to go through and understand since all the functions in this section require data (or are capable of taking data) in this format. For example:

library('glmnet')
regularized.logit.fit <- glmnet(train.x, train.y, family = c('binomial'))
library('e1071')
linear.svm.fit <- svm(train.x, train.y, kernel = 'linear')
library('class')
knn.fit <- knn(train.x, test.x, train.y, k = 50)

And that does it for me! I'm ready to move on to another book.

# Machine Learning for Hackers, Chapter 11

Are you a heavy Twitter user? Would you like to build a custom recommendation system in R that will recommend new Twitter feeds for you to follow? If you answered “yes” to both questions then this is the chapter for you. Here’s the code. Have fun.

Now I don’t use Twitter, so this chapter was not very interesting for me. I should probably use Twitter and get with it and join the 2010’s. But at the moment I don’t, so building a Twitter recommendation system in R doesn’t do me any good. I guess I could have followed along and built the recommendation system in the book for one of the authors, but I just couldn’t motivate. It’s a lot of code that requires new packages. Plus there’s a section that requires using a program outside of R called Gephi. It’s an extremely specific case study. It’s not like some of the other chapters where they introduce a general machine learning method, like kNN or PCA, and show an example of how to use it. There is nothing general about this chapter. At one point they do make use of hierarchical clustering to find similarities between Twitter users. Clustering is a common machine learning tactic. But they only give it a couple of pages. I hate to sound down on the chapter. It’s well done and the authors put a lot of work into it. Personally, though, I just couldn’t get excited about it.

Having said that, I did see some interesting things in the R code that I wanted to file away and remember. The first was creating an empty vector. In a loop they run, they sometimes get a null result and want to store an empty vector for that pass. They do this as follows:

y <- c(integer(0), integer(0))

What caught my eye was the way rbind handles those vectors. It ignores them. I could see that being potentially useful. Here's a toy demonstration:

x <- c(5, 4)
y <- c(integer(0), integer(0))
z <- c(3, 2)
rbind(x,y,z)
[,1] [,2]
x     5    4
z     3    2

Another snippet I wanted to note was how to identify unique values in a matrix. You use the unique function, which I was familiar with. What I didn't know was that you can do it for a matrix by calling the columns of the matrix, like this:

mat <- matrix(floor(runif(10,2,8)),5,2)
mat
[,1] [,2]
[1,]        4      3
[2,]        2      7
[3,]        7      2
[4,]        3      7
[5,]        5      7
> unique(c(mat[,1],mat[,2]))
[1] 4 2 7 3 5

This chapter also used a base function that I had never seen before called duplicated. It returns a vector of True/False values that tells you whether or not the value occurs previously in the vector. I was surprised I hadn't heard of it before. Here's a demo of duplicated:

x <- c(1:5,2:6)
x
[1] 1 2 3 4 5 2 3 4 5 6
duplicated(x)
[1] FALSE FALSE FALSE FALSE FALSE TRUE TRUE TRUE TRUE FALSE
!duplicated(x)
[1] TRUE TRUE TRUE TRUE TRUE FALSE FALSE FALSE FALSE TRUE
x[duplicated(x)]
[1] 2 3 4 5
x[!duplicated(x)]
[1] 1 2 3 4 5 6

Finally they make use of sapply in one of their functions and I wanted to document its use. The suite of apply functions always give me trouble for some reason. I get the gist of what they do, I just have a hard time remember why I would want to use one over the other. Anyway, what they do is use sapply to run a function over each row of a matrix. That seems like a useful thing to remember. First let's create a 100 x 3 data frame of values:

a <- rnorm(100,2,4)
b <- rnorm(100,3,4)
c <- rnorm(100,5,4)
df <- data.frame(a,b,c)

Now, let's say I wanted to create a True/False vector indicating which rows contained a value less than 0. Here's how I can do that using sapply:

sapply(1:nrow(df), function(i) ifelse(any(df[i,]<0),1,0))

The authors did something similar to that and then used the vector of T/F values to subset another vector. Of course if I wanted to subset my example data frame above to show only rows that contain a value less than o, then I could do this:

subset(df, a < 0 | b <0 | c < 0)

So that's the helpful R code I gleaned from Chapter 11. I feel like there should be more. It's a long chapter with a lot of code. But much of it either involves functions from specific packages or uses common R functions I've already documented or know about. Next up is chapter 12, the final chapter.

# Machine Learning for Hackers, Chapter 10

k-nearest neighbors (kNN) is the topic of chapter 10. The authors say it’s the most intuitive of the machine learning algorithms covered in the book and I guess I would agree, provided you understand the euclidean distance formula, understand what a distance matrix is, Â and know a little about how R works.

They provide a toy dataset (named “df”) to demonstrate how kNN works. It looks like this:

         X        Y Label
1 2.373546 5.398106     0
2 3.183643 4.387974     0
3 2.164371 5.341120     0
4 4.595281 3.870637     0
5 3.329508 6.433024     0
6 2.179532 6.980400     0

Think of the rows as points lying in an XY plane. Notice they also have labels. The dataset has 100 rows, with 50 labeled 0 and 50 labeled 1. To run the kNN algorithm, we need to create a distance matrix that stores the distance between all the points. So row 1 of the distance matrix would have the distances of all points from the first point (2.373546, 5.398106). Row 2 would have the distances of all points from (3.183643, 4.387974). And so on. The authors actually write a function to create the distance matrix, which is good for illustrating how the distance matrix is created, but I want to note you can use the built-in “dist” function for this:

distance <- as.matrix(dist(df, diag=TRUE, upper=TRUE))

I set the "diag" and "upper" parameters to TRUE in order to match the matrix they create. The result is this:

 distance[1:3,1:3]
1        2         3
1 0.0000000 1.294845 0.2167983
2 1.2948454 0.000000 1.3954937
3 0.2167983 1.395494 0.0000000

That's just a portion of the matrix. The full matrix is 100 x 100. The first row (or first column) refers to point 1 Â (2.373546, 5.398106). distance[1,1] is 0 because that's how far point 1 is from itself. distance[1,2] is 1.294845 because that's how far point 2Â (3.183643, 4.387974) is from point 1. The distance between two points A($x_{1},y_{1}$) and B($x_{2},y_{2}$) is calculated using the Euclidean distance formula:

$AB = \sqrt{(x_{1}-x_{2})^{2} + (y_{1}-y_{2})^{2}}$ $1.294845 = \sqrt{(2.373546-3.183643)^{2} + (5.398106-4.387974)^{2}}$

Once we have our distance matrix, we can find the k-nearest neighbors for a particular point by sorting the row from smallest to greatest distance. We can use the order function to help us do this. For example, let's find the 5 nearest neighbors for the first point:

indices <- order(distance[1,])[2:6]
indices
[1] 46 3 36 13 29
distance[1,indices]
Â  Â  Â  Â 46   Â  Â  Â  3        36        13        29
0.1796931 0.2167983 0.2212696 0.2916801 0.3561144

The order function returns the index positions of the nearest neighbors in the distance matrix. The index position can also be thought of as the identifying point number. So the closest neighbor of point 1 is point 46. The second-closest neighbor of point 1 is point 3. The command "distance[1,indices]" shows us the 5 closest points and their distances. What are their labels?

df[indices,'Label']
[1] 0 0 0 0 0

They're all 0's. If we wanted to predict the label of point 1, we could use majority rule. In this case since the 5-nearest neighbors are all labeled "0", we would predict point 1 is also labeled "0". (In truth, it is.) The authors carry this out for the entire dataset of 100 points and correctly predict the label for 93 of them given their 5-nearest neighbors.

The case study in this chapter is recommending R packages. The dataset is a list of 2487 packages, listed 50 times over for 50 programmers, with an indicator of whether or not that package is installed for the programmer. Using kNN they build a list of 25 recommendations for each programmer. Here's the code.

Next up is Chapter 11, Analyzing Social Graphs. It looks like the case study will involve building an engine to recommend people to follow on Twitter. I guess I'm a poopy stick-in-the-mud because this doesn't appeal to me. I'm not really into the Twitter. But I'll keep an open mind, slog through it and learn as much as I can.

# Machine Learning for Hackers, Chapter 9

In this chapter we learn a little about Multidimensional Scaling, or MDS for short. Like PCA in Chapter 8, MDS is a topic usually taught in multivariate statistics classes. I guess it’s classified as machine learning because of the computing required to do it, though the same can be said of almost any statistical method. The MDS that is presented is the classical type (as opposed to the non-metric type). The case study is exploring similarity in the US Senate based on votes. As it turns out, a proper MDS analysis shows Democrats and Republicans indeed vote differently and are quite polarized. Not surprising but better than anecdotal evidence from some political pundit.

Now if you’ve been following my series of posts on this book (and I’m pretty sure you haven’t) then you know I don’t summarize the chapter but rather highlight the R code that I found interesting and new. But for the first time I really don’t have much to highlight. It’s a short chapter and the data for the case study required very little preparation. I was actually able to follow all the R code without running to the help pages and Google. Still, though, I feel like I should document something from this chapter.

How about reading in a bunch of files. I feel like this something I will forget how to do one day, so I should probably write about it to help form some memory. First they define a variable that stores a path and then they call the list.files function to create a vector of file names:

data.dir <- "data/roll_call/"
data.files <- list.files(data.dir)

Next they use the lapply function to create one big list object that contains the contents of all those files, which happen to be Stata data sets:

rollcall.data <- lapply(data.files, function(f)
read.dta(paste(data.dir, f, sep=""), convert.factors=FALSE))

So the lapply function applies the read.dta function to each element in the data.files vector, which is file name. But in the read.dta function you'll notice the paste function is called to create a full path with the file name. Just dandy. That never fails to impress.

If you want to inspect some of the data, you can't just do head(rollcall.data). Since it's a list object you have to do something like this:

head(rollcall.data[[1]])

That shows the first 6 rows of the data stored in the first list element.

Later on they use the strsplit function to split first and last names of senators by comma. I'm pretty sure I've posted about this before, but it doesn't hurt to mention it again. Running a vector through strplit returns a list. For example:

 strsplit(congress$name[1], "[, ]") [[1]] [1] "SHELBY" "" "RIC" If I just want the last name, I can do this:  strsplit(congress$name[1], "[, ]")[[1]][1]
[1] "SHELBY"

Now the authors use the strsplit function in an sapply function, like this:

congress.names <- sapply(congress$name, function(n) strsplit(n, "[, ]")[[1]][1]) That gives us this:  head(congress.names) SHELBY, RIC HEFLIN, HOW STEVENS, TH MURKOWSKI, DECONCINI, MCCAIN, JOH "SHELBY" "HEFLIN" "STEVENS" "MURKOWSKI" "DECONCINI" "MCCAIN" Notice each element in the vector has a "name". Ugly, I think, though it doesn't matter in the context of what they do. But what if you wanted a clean vector of last names without the "names"? You can do this: congress.names <- sapply(congress$name, function(n)
strsplit(n, "[, ]")[[1]][1],USE.NAMES = FALSE)
[1] "SHELBY"    "HEFLIN"    "STEVENS"   "MURKOWSKI" "DECONCINI" "MCCAIN"

Much better. Notice the USE.NAMES = FALSE setting. Pretty self-explanatory what it does.

If you want to see the rest of their code including how they carry out the MDS analysis and MDS clustering plots, see their git hub page. For more on how exactly MDS works, see Chapter 14 of A Handbook of Statistical Analyses Using R.

# Machine Learning for Hackers, Chapter 8

This is a tidy chapter on principle component analysis (PCA). There are many fine tutorials on PCA to be found on the internet. This one is special because it doesn’t start with a nice data set. They have to first beat it into shape. They’re goal is to develop a market index based on 25 stocks. They will do PCA and use the first component to develop an index.

After they read in a CSV file with the date, they have to translate a column of dates into a date object. They use a package called “lubridate” for this, but it seems the as.Date function works just as well. This is what I did:

prices <- read.csv('data/stock_prices.csv')
prices <- transform(prices, Date = as.Date(Date))

Next they have to reshape the data. The prices dataset looks like this:

 head(prices)
Date     Stock Close
1 2011-05-25 DTE 51.12
2 2011-05-24 DTE 51.51
3 2011-05-23 DTE 51.47
4 2011-05-20 DTE 51.90
5 2011-05-19 DTE 51.91
6 2011-05-18 DTE 51.68

They want to transform this so the column headers are the Date and all the Stocks. They use the cast function from the reshape package.

library(reshape)
date.stock.matrix <- cast(prices, Date ~ Stock, value = 'Close')

The result:

        Date   ADC   AFL ARKR AZPN  CLFD   DDR   DTE  ENDP FLWS     FR GMXR
1 2002-01-02 17.70 23.78 8.15 17.10 3.19 18.80 42.37 11.54 15.77 31.16 4.50
2 2002-01-03 16.14 23.52 8.15 17.41 3.27 18.55 42.14 11.48 17.40 31.45 4.37
3 2002-01-04 15.45 23.92 7.79 17.90 3.28 18.46 41.79 11.60 17.11 31.46 4.45
4 2002-01-07 16.59 23.12 7.79 17.49 3.50 18.30 41.48 11.90 17.38 31.10 4.38
5 2002-01-08 16.76 25.54 7.35 17.89 4.24 18.57 40.69 12.41 14.62 31.40 4.30
6 2002-01-09 16.78 26.30 7.40 18.25 4.25 18.41 40.81 12.27 14.27 31.05 4.25

Now after they do this they mention the new dataset has missing entries (NAs) that need to be removed. But they don't tell you how they found them. Furthermore they proceed to not just remove a row of NAs, but an entire column of a stock because it had a value on a day when all other stocks were NA! Here's what they do:

# remove a row and a column
prices <- subset(prices, Date != "2002-02-01")
prices <- subset(prices, Stock != "DDR")
date.stock.matrix <- cast(prices, Date ~ Stock, value = 'Close')

That reduces the data set to 2366 rows and 25 columns. Instead of 25 stocks, we now have 24. (Remember, the first column is Date.) What confused me is why they didn't do something like this:

date.stock.matrix <- na.omit(date.stock.matrix)

That reduces the data set by two rows to 2365 rows but keeps all the columns. That means you have 25 stocks to develop your index instead of 24. But let's back up for a moment and think about how they found those missing values in the first place. They don't tell you in the book. They just say that they notice they have missing entries and need to remove them. Here's one way you could find out if you didn't know whether or not there were missing values. First get the dimensions of your data frame:

dim(date.stock.matrix)
[1] 2367 26

Now run the following to see if the dimensions change:

dim(date.stock.matrix[complete.cases(date.stock.matrix),])
[1] 2365 26

They do! Two rows have missing values. But which two rows? Try this

row.has.na <- apply(date.stock.matrix, 1, function(x){any(is.na(x))})
date.stock.matrix[row.has.na,]

That returns the two rows in the data frame with missing values, in this case rows 22 and 875. Again, we can use the na.omit code above to clear out those rows. I'm not sure why the authors didn't do this. When they run their PCA on their final data set with 24 stocks, the first component accounts for 29% of the variance. But when I run it on the data set with all 25 stocks and only two rows removed, the first component accounts for almost 33% of the variance. Not a huge improvement, but still improvement.

A couple of other "that was cool" nuggets I took from this chapter were the way they looked at the correlation matrix (to get a feel if PCA was warranted) and their use of the melt function from the reshape package. First the correlation trick:

cor.matrix <- cor(date.stock.matrix[,2:ncol(date.stock.matrix)])
corrs <- as.numeric(cor.matrix)
library(ggplot2)
ggplot(data.frame(Correlation = corrs), aes(x = Correlation, fill = 1))
+ geom_density() + opts(legend.position = 'none')

They calculate the correlation matrix of the closing values, convert the correlation matrix to a vector, and then make a density plot. This visually shows you that most of the correlations are positive and that PCA doesn't seem out of the question. I thought that was a neat trick.

Now the melt function. They use this function to convert a data set with both their market index data and the DJI such that both can be plotted over time. Let's look at before and after and see what it does.

Before melt:

 head(comparison)
Dates MarketIndex       DJI
1 2002-01-02 -1.0346886 -0.3251888
2 2002-01-03 -1.0265119 -0.2602872
3 2002-01-04 -1.0199864 -0.2027079
4 2002-01-07 -1.0230787 -0.2439139
5 2002-01-08 -0.9953525 -0.2744783
6 2002-01-09 -0.9873846 -0.3115893

After melt:

alt.comparison <- melt(comparison, id.vars='Dates')
names(alt.comparison) <- c('Dates', 'Index', 'Price')
 head(alt.comparison)
Dates       Index      Price
1 2002-01-02 MarketIndex -1.0346886
2 2002-01-03 MarketIndex -1.0265119
3 2002-01-04 MarketIndex -1.0199864
4 2002-01-07 MarketIndex -1.0230787
5 2002-01-08 MarketIndex -0.9953525
6 2002-01-09 MarketIndex -0.9873846

So what they want to do is plot the indices over time and put them both on the same graph. In the first data set, each row is a date with both index values on that date. The melt function says to identify the other two columns by date. Each column name in the first data set becomes a grouping factor in the second data set. The values that are in columns 2 and 3 of the first data set are now all in column three in the second data set. It's hard to explain in words but makes sense if you stare at the before-and-after long enough.

# Machine Learning for Hackers, Chapter 7

The title of this chapter, “Optimization: Breaking Codes”, sounds more exciting than it really is. The code breaking is attempted via an optimization algorithm called the Metropolis method. The authors show you how to encrypt text using a simple Caesar cipher and then how to implement the Metropolis method to attempt to decipher the message. Their test message is “here is some sample text”. They encrypt it using the Caesar cipher, so it looks like “ifsf jt tpnf tbnqmf ufyu “. The encryption rule is simply replacing every letter with the following letter in the alphabet. The letter a is replaced with b, b with c, and so on until you replace z with a. They manage to decipher their test text through the course of 50,000 Metropolis steps (on the 45,609th attempt). I suppose this is a fun demonstration of optimization. It just seemed a little outdated. I guess I was expecting to see them crack an actual message from World War II or something.

They start the chapter by demonstrating how to use the R optim function. For some reason this function has always confused me. Probably because I don’t use it that often. But I have to say I feel much better about it now. They give clear demonstrations of its use and visually show you how it works. Their example involves the height and weight dataset from chapter 2. First we do linear regression and find coefficients for the slope and intercept. Then we find the same coefficients using optim. The function minimized in the call to optim is a hand-built sum of squared errors function. I thought this was a great way to demonstrate how optim works. But after this, they do something puzzling: they continue to demonstrate how to use optim with Ridge Regression. Now Ridge Regression is a type of regression that helps remedy multicollinearity. If you have predictor variables that are highly correlated, you may get some weird coefficients in your linear modelling results. I’m talking about getting a negative value where you would expect a positive value, that sort of thing. Ridge regression helps address this by “modifying the method of least squares to allow biased estimators of the regression coefficients” (Kutner, et al., p. 432). Knowing that, it doesn’t make much sense to demonstrate Ridge regression on height and weight data. There’s only one predictor. I thought maybe they were going to do more with Ridge regression in this chapter, but they don’t. They move on to code breaking. It just seemed out of place to bring up Ridge regression in the context of single predictor regression.

I won’t go into the code breaking program. The code is available on the book’s git hub page. What I wanted to review for my own benefit is their function for encrypting text using the Caesar cipher. I thought it was a good example of using R’s indexing capabilities with list objects. First we need a vector with the English alphabet and two empty list objects for the ciphers: one for encrypting text and another for deciphering text:

english.letters <- letters
caesar.cipher <- list()
inverse.caesar.cipher <- list()

Now we create the ciphers:

# need to use index %% 26 + 1 to handle letter "z" at end
# 26 %% 26 + 1 = 0 + 1 = 1
for (index in 1:length(english.letters))
{
caesar.cipher[[english.letters[index]]] <- english.letters[index %% 26 + 1]
inverse.caesar.cipher[[english.letters[index %% 26 + 1]]] <- english.letters[index]
}

The "index %% 26 + 1" confused me for a couple of reasons. First off, the %% operator means modulus and I'm used to see something like 12 %% 5, where the first number is bigger than the second. The answer to that is of course 2. If you divide 12 by 5 you get remainder 2, and that's what the %% operator returns. But in the code above, you'll notice the "index" value is less than 26 on every iteration except the last. How do you calculate something like 2 %% 26? I wasn't sure so I had to google around and figure it out. It turns out the modulus operation a %% n is defined as follows:

$a \, mod \, n = a - \lfloor \frac{a}{n} \rfloor \times n$

So, 2 %% 26 is calculated like so:

$2 \, mod \, 26 = 2 - \lfloor \frac{2}{26} \rfloor \times 26 = 2 - \lfloor 0.0769 \rfloor \times 26 = 2 - (0 \times 26) = 2$

Once I was clear on that, I was confused why we needed to use the %% operator at all. Again if you look at the code above, you'll see "index %% 26 + 1". When index = 2, "index %% 26" gives 2. When index = 3, "index %% 26" gives 3. And so on. Why not just use "index + 1"? Well, when we get to the letter "z", we need to substitute "a". The index number for "a" is 1. But if we do "index + 1", then we would get 27 at the letter "z" since its index number is 26. That would not index anything in the 26 element "english.letters" vector and produce an error. Therefore we need to use the %% operator to allows us to recycle through the numbers 1 - 26. When index = 26 (i.e., when we get to the letter "z"), we do 26 %% 26 + 1, which equals 1 since 26/26 has remainder equal 0.

Now that I understand how the ciphers are generated, I can print them and have a look if I like:

print(caesar.cipher) # encrypt text
print(inverse.caesar.cipher) # decipher text

Since these are lists, we investigate with indices using double brackets. For example, to see what we substitute for letter "h", we do the following:

caesar.cipher[["h"]]

That returns "i". It seems like a fun extension to this would be to create a general function that allowed you to specify the substitution index. In the Caesar cipher, this is 1. It would be neat to specify, say, 13 so "a" becomes "n", "b" becomes "o", and so on. Anyway, moving on...

Now we use the ciphers we just made to encrypt text. To do this the authors build two functions. The first encrypts text letter-by-letter using the cipher you give it. The second function encrypts words using the first function. Let's have a look at these:

apply.cipher.to.string <- function(string, cipher)
{
output <- ''
for (i in 1:nchar(string))
{
output <- paste(output, cipher[[substr(string, i, i)]], sep='')
}
return(output)
}
apply.cipher.to.text <- function(text, cipher)
{
output <- c()
for (string in text)
{
output <- c(output, apply.cipher.to.string(string, cipher))
}
return(output)
}

The first function loops through each letter of a word (or "string"). Using the substr function, we extract each letter, use that letter to look up the substitution in the cipher, and "paste" the substituted letter to the previously substituted letter. At the conclusion of the loop we have encrypted the word using our cipher. The second function uses this first function to encrypt whole phrases. Here is how the authors encrypt the message "here is some sample text" using the Caesar cipher:

apply.cipher.to.text(c('here', 'is', 'some', 'sample','text'), caesar.cipher)

That gives us "ifsf" "jt" "tpnf" "tbnqmf" "ufyu" . If we wanted to decipher the text, we would use the inverse cipher as follows:

apply.cipher.to.text(c('ifsf', 'jt', 'tpnf', 'tbnqmf', 'ufyu'), inverse.caesar.cipher)

Again it would be a good exercise to generalize these functions to accept a whole text file and return an encrypted text file. Not that I'm going to do that, but it sounds like it would make a good project assignment in some programming class.

# Machine Learning for Hackers, Chapter 6

Chapter 6 covers orthogonal polynomial regression, cross-validation, regularization and a touch of logistic regression. The case study is predicting popularity of O’Reilly’s top 100 books based on their back cover descriptions. As usual I picked up some useful tricks from this chapter. Let’s get into it.

If you have a data frame called “df” with a variable $x$ and you want to add, say, $x^{2}$ to it (and name it “X2”), you can do the following:

df <- transform(df, X2 = X ^ 2)

Now it turns out R has a function called poly that does this for you:

poly(X , degree=2, raw=TRUE)

So you could leave your data frame as is (say it has two columns, Y and X) and do polynomial regression like so:

lm(Y ~ poly(X, degree=2, raw=TRUE), data = df)

That's straight-up raw polynomial regression. If you leave out the "raw = TRUE" parameter (or set it to FALSE, its default value), the poly function generates orthogonal polynomials. As the book states: "instead of naively adding simple powers of x, we add more complicated variants of x that work like successive powers of x, but aren't correlated with each other in the way that $x$ and $x^{2}$ are." Two vectors are orthogonal when their dot product equals 0. You can verify the poly produces orthogonal vectors. Here's a simple example:

x <- 1:10
p <- poly(x, 2)
p[,1] %*% p[,2]

That returns 0. I don't understand how R creates these orthogonal vectors. It returns a couple of items called "alpha" and "norm2" which I'm pretty sure have something to do with it. But the help pages and Google searches yielded nothing. (Though I will say this guy's blog post was useful.) Anyway, they illustrate polynomial regression using some toy data:

set.seed(1)
x <- seq(0, 1, by = 0.01)
y <- sin(2 * pi * x) + rnorm(length(x), 0, 0.1)
df <- data.frame(X = x, Y = y)
# raw polynomial regression
m1 <- lm(Y ~ poly(X,degree=5,raw=TRUE), data=df)
# orthogonal polynomial regression
m2 <- lm(Y ~ poly(X,degree=5), data=df)

If you want to make predictions using your models, do something like this:

d <- seq(0,1,by = 0.05)
p1 <- predict(m1, data.frame(X=d))
p2 <- predict(m2, data.frame(X=d))

If you want to see how your model visually performs, do something like this:

plot(x, y, xlab = "X", ylab = "Y", las = 1, xlim = c(0, 1))
lines(d, p1, col = "red")
lines(d, p2, col = "blue")

Finally if you want to update your orthogonal model, you can do something like this:

m1.2 <- lm(Y ~ poly(X,degree=5,raw=TRUE)[,-4], data=df)
m1.3 <- lm(Y ~ poly(X,degree=5,raw=TRUE)[,c(-2,-4)], data=df)

Now they only play around with orthogonal regression for the most part and they use cross validation. They present a general way to randomly split data into a testing and training sets and then loop through polynomial degrees evaluating RMSE at each step for both the training and testing sets. See their 14th and 15th code snippets for this code. I think it's quite useful.

After this they go into Regularization, which is some heavy-duty black box stuff. I guess they do a good job of showing you how to do it using the "glmnet" package. Still, though, I have no idea what's going on under the hood. I would feel somewhat disingenuous using this for real. I have no doubt it works. I'm not questioning their application or the glmnet package. I just feel uneasy using methods that I don't understand. I'm always afraid someone will ask me to explain how it works.

Finally they use Regularization and logistic regression to build a model for predicting whether or not a book will be in the top 50 (of the 100 best selling books) given its back-cover description. Instead of summarizing that analysis I wanted to write a little about how they hammer the data into shape to analyze it. First they read in the data, then they load the "tm" package and start calling functions:

ranks <- read.csv('data/oreilly.csv', stringsAsFactors = FALSE)
library('tm')
documents <- data.frame(Text = ranks$Long.Desc.) row.names(documents) <- 1:nrow(documents) # not sure why this is necessary corpus <- Corpus(DataframeSource(documents)) corpus <- tm_map(corpus, tolower) corpus <- tm_map(corpus, stripWhitespace) corpus <- tm_map(corpus, removeWords, stopwords('English')) The last four lines is where the magic happens. First they make a "corpus". This is sort of like a list where the elements are text documents. The next line makes everything lower case. The next collapses multiple white space characters to a single blank. The last removes the most common words in English, like "the" and "an". When you're done, you can't view the corpus like you would a data frame. You can't just type the name at the command line and hit enter. You have to use the inspect() function, like this: inspect(corpus) # all documents corpus[[2]] # second document Pretty cool. But it's still not ready for regression analysis. You have to produce a Document Term Matrix (DTM) from your corpus. This is done like so: dtm <- DocumentTermMatrix(corpus) Easy enough. But, again, how to view it? Use the inspect() function, like this: # first five documents and first five terms inspect(dtm[1:3,1:5]) # all documents and first five terms inspect(dtm[,1:5]) The rows indicate the document (in this case numbered 1 - 100) and the column headers are the words (or terms). The values in the matrix tell you how many times the term appeared in a document. Here's a quick way to do some analysis on those terms: # find those terms that occur at least five times findFreqTerms(dtm, 5) The last step to get everything ready for analysis is to convert the DTM into a matrix: x <- as.matrix(dtm) We do this because the glmnet function requires the predictors to be in a matrix, and the DTM represents the predictors. (The response is an indicator: top-50 book or not.) Now the dimension of the dtm matrix is 100 x 5605! That's a lot of columns! The authors have this to say: "Because our data set has more columns than rows, unregularized regression will always produce an overfit model. For that reason, we have to use some form of regularization to get any meaningful results." They probably could have eliminated some of the columns. When I inspected the DTM I saw terms such as "!)</li", "#</--", "#</,", "#</em", "#</em," and "&". These are clearly just left over HTML codes. I can't see how they contribute to this analysis. But even if they were removed the matrix would still have many more columns than rows. # Machine Learning for Hackers, Chapter 5 This chapter covers linear regression. The case study is predicting page views for web sites given unique visitors, whether the site advertises, and whether the site is in English. The funny thing is that while they spend a lot of time explaining how to do linear regression in R, they never get around to explaining how to make a prediction using your regression model. (The name of the chapter is actually called “Regression: Predicting Page Views”.) I’ll explain how to do prediction in this post. But first I want to say the authors do a fine job of explaining the “big idea” of linear regression. It’s not an easy topic to cover in under 30 pages. If you’re new to the subject this is a great introduction. I highly recommend it. (And we all know my recommendation means a great deal.) So let’s say you follow along with the book and a create a linear model to predict page views given unique visitors: lm.fit <- lm(log(PageViews) ~ log(UniqueVisitors), data = top.1000.sites) Notice the log transformation. This is necessary since the data is not normally distributed. The results of the regression are as follows: Coefficients: Estimate Std. Error t value Pr(>|t|) (Intercept) -2.83441 0.75201 -3.769 0.000173 *** log(UniqueVisitors) 1.33628 0.04568 29.251 < 2e-16 *** --- Signif. codes: 0 â€˜***â€™ 0.001 â€˜**â€™ 0.01 â€˜*â€™ 0.05 â€˜.â€™ 0.1 â€˜ â€™ 1 Residual standard error: 1.084 on 998 degrees of freedom Multiple R-squared: 0.4616, Adjusted R-squared: 0.4611 F-statistic: 855.6 on 1 and 998 DF, p-value: < 2.2e-16 If we want to predict Page Views for a site with, say, 500,000,000Â Unique Visitors, we use the coefficient estimates to calculate the following: $-2.83441 + 1.33628*log(500,000,000)$ To easily do this in R we can submit code like this: new <- data.frame(UniqueVisitors = 500000000) exp(predict(lm.fit, new, interval = "prediction")) This gives us not only a prediction (fit) but a prediction interval as well (lwr and upr): fit lwr upr 1 24732846396 2876053856 2.12692e+11 Also notice we had to wrap the predict function in the exp function. That's because we ran the regression with the data transformed in the log scale. Once we make our prediction we need to transform it back to the original scale. I'm surprised the authors don't cover this. They do mention the predict function as a way to see what the regression model predicts for the original data values. But they don't talk about how to use your regression results to make a prediction for a new value that wasn't in your data. Perhaps that will be covered in future chapters. Another minor complaint I have is a statement they make on page 150 in the 2nd paragraph: "...the Residual standard error is simply the RMSE of the model that we could compute using sqrt(mean(residuals(lm.git) ^ 2))" where lm.fit is the model object created when regressing Page Views on Unique Visitors.Â That's incorrect. The residual standard error is computed for this model withÂ sqrt((sum(residuals(lm.fit)^2))/998), where 998 = 1000 - 2. In other words, instead of dividing the sum of the squared residuals by 1000 (i.e., taking the mean), we divide by the number of observations minus the number of coefficients in our model. In this case we have 1000 observations and two coefficients in our model (the intercept and slope). So we divide by 998. While I didn't learn anything new about linear regression in this chapter, I did learn something about plotting lm model objects in R. I've known for a while you can easily create diagnostic plots by submitting the plot function with a model object as the argument. This creates 4 plots in a 2 x 2 grid. What I learned in this chapter is that you can specify which plot is produced by issuing an additional argument "which = ". For example, to just see a plot of residuals versus fitted values, you submit plot(lm.fit, which = 1) The book says issuing this statement will "plot the residuals against the truth." I think "truth" should say "fitted values". I'm not sure I've ever heard "fitted values" referred to as the "truth". Anyway, as I said, I think this chapter is a solid introduction to linear regression. That's a good thing because it appears the next chapter steps it up a notch. # Machine Learning for Hackers, Chapter 4 This chapter explains how to create a ranking algorithm to prioritize email messages in your inbox. The authors mention Google popularizing the idea of creating a “priority inbox” and point to a paper that describes their strategies. They then proceed to use some of these strategies to create their own ranking program using emails from the SpamAssassin public corpus. This was a long and unpleasant chapter for me to slog through. For one I don’t think I will ever be asked to design a ranking algorithm for emails.Â I suppose this concept could be extended to other applications but the chapter doesn’t go there. Another sticking point was that the algorithm the authors build is necessarily incomplete because we’re only dealing with emails received (instead of both emails sent and received). The authors acknowledge this up front and say “the methods and algorithms used in this chapter should be considered as exercises only and not examples of how enterprise priority inbox systems should be implemented.” So I was learning how to implement something sort of like what Google does (but not really) that isn’t actually a traditional machine learning method. Personally that wasn’t huge motivation to pick through the authors’ butt-load of R code and figure out what they were doing. I don’t mean to be critical of the authors. I’m impressed with what they did. I mean, think about it: they wrote a dense 33-page chapter on how to build a ranking program in R as an exercise. That’s dedication. I guess I just couldn’t get rid of that nagging feeling that I would never make use of the material in this chapter in my professional life. So my goal became to study their R code and focus on becoming a better programmer. When all was said and done, their R code wasn’t too hard to follow. I thought they did a great job of breaking everything down into manageable functions. In fact I would say what they do in this chapter is provide a good model for building a long, complicated R program. Having said that, the portions that jumped out at me as being both unfamiliar and potentially useful were the sections that used regular expressions. I took a 4-week Coursera class that touched briefly on regular expressions. I also found this tutorial that I thought was useful. Other than that I really don’t know much about them.Â My impression of regular expressions is that unless you use them on a regular basis you’re not going to master them. So my strategy is to just know what they’re used for and remember that. When the time comes, I’ll have to dig in and figure out how to write them, because there is no way I’m going to teach myself how to use them and have total recall several months (or years) from now. The first instance they use regular expressions is to go through an email message and pull out the lines that contain “From:” in order to eventually strip out an email address: msg.vec[grepl("From: ", msg.vec)] The grepl function takes a regular expression as its first argument and returns a logical vector of TRUE/FALSE the same length as its second argument, the vector it combs looking for matches. So here msg.vec is the email message. grepl goes through each line and looks for the text “From: “. If it finds it, it returns TRUE, otherwise FALSE. This is no doubt the easiest example of a regular expression because it’s a literal string. But that first argument could be a really sophisticated regular expression. Finally, grepl is used to index msg.vec such that only lines with “From: ” are returned. Now the lines with “From: ” contain extraneous characters such as angle brackets and of course colons. To address this they use the strsplit function, which splits a character element into a list by a given regular expression. Here’s how they use it: strsplit(from, '[":<> ]') where “from” is the character element. Here’s an example of how it works: test <- "From: Test Guy " strsplit(test, '[":<> ]') [[1]] [1] "From" "" "Test" "Guy" "" [6] "test@guy.com" You can see it splits the character element by the characters in the regular expression. (The square brackets mean match anything inside the square brackets for one character position once and only once.) If I wanted to extract the email address, I could do the following: grepl("@", test2[[1]]) [1] FALSE FALSE FALSE FALSE FALSE TRUE That shows me which element contains the email address. So let’s save our strsplit result and use grepl to pull out the email address: test2 <- strsplit(test, '[":<> ]') test2[[1]][grepl("@", test2[[1]])] [1] "test@guy.com" Another function they use is the gsub function which basically does a search and replace based on a regular expression. Here’s an example: test <- " Â 20 Dec 2011 Â Â Â " test [1] " 20 Dec 2011 " gsub("^\\s+|\\s+$", "", test)
[1] "20 Dec 2011"

Notice the spaces before and after the date. The gsub function searches for leading or trailing spaces and replaces them with nothing. And behold that regular expression. Pretty, isn't it? The caret ^ means search the beginning, the "\s" meansÂ match any whitespace characters. The extra backslash "\" in front of it means escape the backslash in front of the "s"! (This is unique to R, I think.) The + sign means match the previous character 1 or more times. The pipe "|" means "or". So search for leading spaces OR trailing spaces. Â After the pipe is the search string for trailing spaces. It's just like the search string for leading spaces, except instead of a caret at the front, it has a dollar sign at the end, whichÂ means look only at the end of the target string.

Again, there's a massive amount of R programming going on in this chapter and I barely even began to scratch the outside of the wrapping around the surface. Even though I question how practical the actual program is, I do think it's an excellent example of how to organize and tackle a complicated and long project in R.

# Machine Learning for Hackers, Chapter 3

In this chapter you build a naive Bayes classifier to classify an email as spam or not spam (or “ham” as they call it) using only the body of the message. The idea is to take a bunch of spam messages and build a Term Document Matrix (TDM). A TDM is a big grid where the row labels are the terms in the spam emails and the column headers are the spam emails. If row 21 is “viagra” and column 20 is the 20th spam email, their cell [21,20] displays the number of times the word “viagra” appeared in that email. Using the TDM they create a data frame which contains the terms and the percentage of documents in which a given term occurs. For example, of the 500 spam emails, the term “html” appears in 33% of the messages. That gets treated as a conditional probability. The probability of seeing the term “html” in an email given the email is spam is 0.33. The same process is carried out for emails that are not spam. So we have two data frames of terms (one for spam and one for not spam) and their estimated probability ofÂ occurrence.

To classify a new email as either spam or not spam we compare it to both data frames and see which terms in the email are in the respective data frame. If a term is in the date frame, we pull out its probability. If not, we assign it a low probability of 0.000001. We multiply the probabilities together along with the prior probability of the message being spam, which they set as 0.5 for starters.

For example, say we have a message with 5 words in the body. None of the words in the email appear in the spam data frame, so we calculate $0.5*0.000001^{5}$. However say two of the words appear in the good email data frame, each with probability of 0.05 of occuring. So we calculate $0.5*0.05^{2}*0.000001^{3}$. Since the latter calculation is greater than the former, we classify the email as not spam. That’s how you do naive Bayes classification.

Now if you’re like me you’re probably thinking, where’s the denominator? I mean, I’m no Bayesian expert, but I do know Bayes’s theorem has a denominator. Well it turns out the denominator is the same in both calculations so they drop it. (I have to give a shout out to this guy’s explanation. That’s where I went to figure it out.) You’ll also notice we’re multiplying probabilities as if they’re independent. That’s the naive assumption here.

Using the language of the probability, here’s Bayes’s Theorem for two terms, where A = message is spam, B = some word, and C = some other word

$P(A|B \cap C ) = \frac{ P(B|A \cap C ) P(C|A) P(A) }{ P(B|C) P(C) }$

For not spam this is…

$P(A^{\prime} | B \cap C) = \frac{P(B|A^{\prime} \cap C)P(C|A^{\prime})P(A^{\prime})}{P(B|C)P(C)}$

Notice the denominators are the same so we can drop them when comparing the two. Since we’re also assuming independence, the numerator changes to $P(B|A)P(C|A)P(A)$ and $P(B|A^{\prime})P(C|A^{\prime})P(A^{\prime})$, respectively.

The book does not explain the classification algorithm in the detail I just did. I guess since the book is “for hackers” they didn’t want to get bogged down in math formulas and explanations of Bayes’s Theorem. I get that. But still I wanted to understand why it worked and not just how to do it R.

The R code itself for this chapter is not too hard to understand. A few nuggets I got out of it are…

The readLines() function will return each line of text as a separate element of a character vector.
The dir() function will return a listing of all file names in a directory.
The intersect() function will return the values in common between two vectors.


text:
# Thread: Finding the equation of a tanget line(derivative error)

1. ## Finding the equation of a tanget line(derivative error)

In order to find the equation of a tanget line, you need the slope.

the problem I was given is

f(x) = $((x^3)+4x-1)(x-2)$ and the point they want me to find it at is (1,-4)
my work so far has been
f'(x) = $(x-2)((3x^2)+4) + ((x^3) + 4x-1)$
f'(x) = $((3x^3)+4x-(6x^2)-8 + (x^3) +4x -1$
and finally
f'(x) = $(4x^3)+8x-(6x^2)-9$
Would I be correct in plugging two points into my final f'(x) in order to get the slope?

I thought I was done but, something is off in my logic and I'm not sure what.

2. f'(1) would be the slope(m).

and the equation of the tangent line can be found by:

$(y-y_1) = m(x-x_1)$

3. however, in the book they gave me the point (1,-4)

so plugging f'(1) I get -3.

and if slope is $rise/run$ then doesn't it make sense I should have to plug something else in as well? I tried however, I have not gotten the answer in the back of the book which is y = -3x -1..

So I am wondering if I perhaps did my derivative wrong?

4. The derivate is the slope

ie: $\dfrac{\text{ rise}}{\text{ run}} = f^{\prime}(x)$

From f(x) I would expand the brackets rather then use the product rule (but both work)

$(x-2)(x^3+4x-1) = (x^4+4x^2-x) + (-2x^3-8x+2) = x^4-2x^3+4x^2-9x+2$

That should be easier to derive

$f'(x) = 4x^3-6x^2+8x-9$

$f'(1) = 4-6+8-9 = -3$

edit: the error was in my derivative
edit2: don't want to make it too easy

5. Why doesn't it make sense? Do you mean that the slope of a line cannot be negative??

When a line has a positive slope it goes up left to right.

When a line has a negative slope it goes down left to right.

You have mentioned the answer at the back of the book is y = -3x-1..

So your slope is m = -3.

The point you have been given is $(x_{1}, y_{1}) = (1,-4)$

Now use $(y-y_1) = m(x-x_1)$ to find the equation of the tangent line..

6. So wait, if I have the derivative (which seems to be correct).

and I am given the point (1,-4) and I plug 1 into the derivative and get (1, -3), that is all I need to do for slope?

oh x.x duh.. -3 is the slope at 1,-4... now it makes a bit more sense.. lol. totally was not thinking about the fact that by plugging 1 into the derivative it was giving me the slope.. I for some reason was thinking I would have to plug another number like 2 into it and get the answer.. but, I'm mistaken.. laughable so.

7. f'(1)=-3. That is all you needed to do to find the slope!

format: plain


text:
# Project Euler Problem 11 (“Largest product in a grid”) in Python

Can this code in any way be improved or optimized? I'd appreciate any clever tricks or Pythonic expressions that may remove some more brute force elements from my solution.

Also, is there possibly a more intuitive way of approaching this problem that I couldn't see?

Problem statement: Largest product in a grid

In the 20×20 grid below, four numbers along a diagonal line have been marked in red [here bold].

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 102638 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 956394 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 177878 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 351400 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

My solution:

grid = [[8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8], [49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 4, 56, 62, 0], [81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 3, 49, 13, 36, 65], [52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56, 1, 32, 56, 71, 37, 2, 36, 91], [22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80], [24, 47, 32, 60, 99, 3, 45, 2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50], [32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70], [67, 26, 20, 68, 2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21], [24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72], [21, 36, 23, 9, 75, 0, 76, 44, 20, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95], [78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 4, 62, 16, 14, 9, 53, 56, 92], [16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17, 54, 24, 36, 29, 85, 57], [86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58], [19, 80, 81, 68, 5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 4, 89, 55, 40], [4, 52, 8, 83, 97, 35, 99, 16, 7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66], [88, 36, 68, 87, 57, 62, 20, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69], [4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36], [20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 4, 36, 16], [20, 73, 35, 29, 78, 31, 90, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54], [1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48]]

horizontal_max = max(grid[i][j]*grid[i][j+1]*grid[i][j+2]*grid[i][j+3] for i in range(20) for j in range(17))

vertical_max = max(grid[i][j]*grid[i+1][j]*grid[i+2][j]*grid[i+3][j] for i in range(17) for j in range(20))

diagonal1_max = max(grid[i][j]*grid[i+1][j+1]*grid[i+2][j+2]*grid[i+3][j+3] for i in range(17) for j in range(17))

diagonal2_max = max(grid[i][j]*grid[i-1][j+1]*grid[i-2][j+2]*grid[i-3][j+3] for i in range(3,20) for j in range(17))

max_max = max(horizontal_max, vertical_max, diagonal1_max, diagonal2_max)

print(max_max)

If you restricted your lines to 79 columns, as recommended by the Python style guide (PEP8), then we wouldn't have to scroll the code horizontally to read it here.

Anyway, all four loops have the same form:

max(grid[i][j]
* grid[i+i_step][j+j_step]
* grid[i+2*i_step][j+2*j_step]
* grid[i+3*i_step][j+3*j_step]
for i in range(i_min, i_limit)
for j in range(j_limit))

given particular choices of parameters i_step, j_step, i_min, i_limit and j_limit. So we can implement the program as a data-driven loop over those choice of parameters:

print(max(max(grid[i][j]
* grid[i+i_step][j+j_step]
* grid[i+2*i_step][j+2*j_step]
* grid[i+3*i_step][j+3*j_step]
for i in range(i_min, i_limit)
for j in range(j_limit)))
for i_step, j_step, i_min, i_limit, j_limit
in [( 0, 1, 0, 20, 17),  # horizontal
( 1, 0, 0, 17, 20),  # vertical
( 1, 1, 0, 17, 17),  # leading diagonal
(-1, 1, 3, 20, 17)]) # trailing diagonal

If you want to avoid writing out the multiplication, then the best approach would be to define a helper function, for example using functools.reduce and operator.mul:

from functools import reduce
from operator import mul

def product(iterable):
"""Return the product of the numbers in the iterable."""
return reduce(mul, iterable, 1)

and then:

print(max(max(product(grid[i+k*i_step][j+k*j_step] for k in range(4))
for i in range(i_min, i_limit)
for j in range(j_limit)))
for i_step, j_step, i_min, i_limit, j_limit
in [( 0, 1, 0, 20, 17),  # horizontal
( 1, 0, 0, 17, 20),  # vertical
( 1, 1, 0, 17, 17),  # leading diagonal
(-1, 1, 3, 20, 17)]) # trailing diagonal

• Thanks. If we wanted to use the length of the consecutive numbers (here, 4) as our parameter (instead of i_min, etc), e.g. so that there's less mental work involved for the user who isn't interested in understanding the logic of the algorithm, would we be able to avoid writing grid[][] four times? In math, one could use the ∏ (product) notation. Does Python offer a similar functionality? – Tian Jiang May 25 '15 at 1:07
• See updated answer. – Gareth Rees May 25 '15 at 12:34


text: Search for heavy particles decaying into top-quark pairs using lepton-plus-jets events in proton–proton collisions at $$\sqrts = 13$$s=13 $$\text TeV$$TeV with the ATLAS detector


text:
.tabbox {width:400px; margin-top: 15px;margin-bottom: 5px} .tabmenu {width:400px;height:28px;border-left:1px solid #CCC;border-top:1px solid #ccc;} .tabmenu ul {margin:0;padding:0;list-style-type: none;} .tabmenu li { text-align:center; float:left; display:block; width:99px; overflow:hidden; background-color: #f1f1f1; line-height:27px; border-right:#ccc 1px solid; border-bottom:#ccc 1px solid; display:inline;} .tabmenu .cli {text-align:center;float:left;display:block;width:99px;overflow:hidden;background-color: #fff;line-height:27px;border-right:#ccc 1px solid;border-bottom:#fff 1px solid;display:inline; cursor:pointer; color: #810505; font-weight:bold} #tabcontent {width:399px;background-color:#fff;border-left:#CCC 1px solid;border-right:#CCC 1px solid;border-bottom:#CCC 1px solid; height:60px;} #tabcontent ul {margin:0;padding:5px;list-style-type: none;} #tabcontent .hidden {display:none;} Search Browse by Issue Fig/Tab Adv Search
 HOME ABOUT JCST AUTHORS REVIEWERS PUBLISHED PAPERS FORTHCOMING PAPERS

›› 2010, Vol. 25 ›› Issue (4): 750-760.

• Special Section on Advances in Machine Learning and Applications •

### Multiple Hypergraph Clustering ofWeb Images by MiningWord2Image Correlations

Fei Wu(吴 飞), Senior Member, CCF, Ya-Hong Han(韩亚洪), and Yue-Ting Zhuang(庄越挺), Member, IEEE

1. College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China
• Received:2009-05-15 Revised:2010-02-11 Online:2010-07-09 Published:2010-07-09
• About author:
Fei Wu is a senior member of CCF. He received the B.S. degree from Lanzhou University, China, the M.S. degree from Macao University, China, and the Ph.D. degree from Zhejiang University, Hangzhou, China. His research interest includes multimedia retrieval and statistic learning.
Ya-Hong Han received the B.S. degree in 2000 from Zhengzhou University, China, the M.S. degree in 2003 from Hohai University, Nanjing, China. He is currently pursuing the Ph.D. degree at the College of Computer Science, Zhejiang University. His research interests are machine learning and multimedia retrieval.
Yue-Ting Zhuang is a Member of IEEE. He received the B.S., M.S., and Ph.D. degrees from Zhejiang University, Hangzhou, China, in 1986, 1989, and 1998, respectively. Currently, he is a professor and Ph.D. supervisor at the College of Computer Science, Zhejiang University. His research interests include multimedia databases, artificial intelligence, and video-based animation.
• Supported by:

Supported by the National Natural Science Foundation of China under Grant Nos. 90920303, 60833006; the National Basic Research 973 Program of China under Grant No. 2010CB327905; the Program for Changjiang Scholars and Innovative Research Team in University of China under Grant Nos. IRT0652, PCSIRT.

In this paper, we consider the problem of clustering Web images by mining correlations between images and their corresponding words. Since Web images always come with associated text, the corresponding textual tags of Web images are used as a source to enhance the description of Web images. However, each word has different contribution for the interpretation of image semantics. Therefore, in order to evaluate the importance of each corresponding word of Web images, we propose a novel visibility model to compute the extent to which a word can be perceived visually in images, and then infer the correlation of word to image by the integration of visibility with tf-idf. Furthermore, Latent Dirichlet Allocation (LDA) is used to discover topic information inherent in surrounding text and topic correlations of images could be defined for image clustering. For integrating visibility and latent topic information into an image clustering framework, we first represent textual correlated and latent-topic correlated images by two hypergraph views, and then the proposed Spectral Multiple Hypergraph Clustering (SMHC) algorithm is used to cluster images into categories. The SMHC could be regarded as a new unsupervised learning process with two hypergraphs to classify Web images. Experimental results show that the SMHC algorithm has better clustering performance and the proposed SMHC-based image clustering framework is effective.

 [1] Smeulders A W M et al. Content-based image retrieval: The end of the early years. IEEE Trans. PAMI, 2000, 22(12): 1349-1380. [2] Rege M, Dong M, Hua J. Graph theoretical framework for simultaneously integrating visual and textual features for efficient Web image clustering. In Proc. the 17th Int. Conf. World Wide Web 2008, Beijing, China, April 21-25, 2008, pp.317-326. [3] Jing F, Wang C et al. IGroup: A Web image search engine with semantic clustering of search results. In Proc. the 14th ACM Int. Conf. Multimedia, Singapore, Nov. 6-11, 2005, pp.377-384. [4] Cai D, He X et al. Hierarchical clustering of WWW image search results using visual, textual and link information. In Proc. the 13th ACM Int. Conf. Multimedia, New York, USA, Oct. 10-16, 2004, pp.952-959. [5] Saenko K, Darrell T. Unsupervised learning of visual sense models for polysemous words. In Proc. NIPS 2008, Vancouver, Canada, Dec. 8-11, 2008, pp.1393-1400. [6] Blei D, Ng A, Jordan M. Latent Dirichlet allocation. Journal of Machine Learning Research, Mar. 2003, 3: 993-1022. [7] Wu F, Liu Y, Zhuang Y. Tensor-based transductive learning for multi-modality video semantic concept detection. IEEE Transactions on Multimedia, 2009, 11(5): 868-878. [8] Yang Y, Zhuang Y, Wu F, Pan Y. Harmonizing hierarchical manifolds for multimedia document semantics understanding and cross-media retrieval. IEEE Transactions on Multimedia, 2008, 10(3): 437-446. [9] Wu F, Han Y, Zhuang Y, Shao J. Clustering web images by correlation mining of image-text. Journal of Software, http://www.jos.org.cn/1000-9825/3704.htm, 2010. (in Chinese) [10] Zhou D, Burges C J C. Spectral clustering and transductive learning with multiple views. In Proc. the 24th Int. Conf. Machine Learning, Corvallis, OR, 2007, pp.1159-1166. [11] Barnard K, Duygulu P et al. Matching words and pictures. Journal of Machine Learning Research, 2003, 3: 1107-1135. [12] Wang X J, Zhang L et al. Annotating images by mining image search results. IEEE Trans. PAMI, 2008, 30(11): 1919-1932. [13] Zhu X, Goldberg A et al. A text-to-picture synthesis system for augmenting communication. In Proc. the 22nd Conf. AAAI, Vancouver, Canada, July 22-26, 2007, pp.1590-1595. [14] Li H, Tang J et al. Word2Image: Towards visual interpretation of words. In Proc. the 16th ACM Int. Conf. Multimedia, Vancouver, Canada, Oct. 26-31, 2008, pp.813-816. [15] Xia D, Wu F, Zhuang Y. Search-based automatic Web image annotation using latent visual and semantic analysis. In Proc. the 9th Pacific Rim Conf. Multimedia, Tainan, China, Dec. 9-13, 2008. [16] Berg T, Forsyth D. Animals on the Web. In Proc. CVPR 2006, Washington, DC, USA, June 17-22, 2006, pp.1463-1470. [17] Zhou D, Huang J, Schõlkopf B. Learning with hypergraphs clustering, classification, and embedding. Advances in Neural Information Processing Systems, Vancouver/Whistler, Canada, Dec. 4-9, 2007, pp.1601-1608. [18] Golub G, Loan C. Matrix Computations. 3rd Edition, The Johns Hopkins University Press, 1996. [19] Griffiths T L, Steyvers M. Finding scientific topics. Proc. National Academy of Science, 2004, 101(Supp.1): 5228-5235. [20] Dhillon I S. Co-clustering documents and words using bipartite spectral graph partitioning. In Proc. KDD, San Francisco, USA, Aug. 26-29, 2001, 269-274. [21] LSCOM lexicon definitions and annotations version 1.0. In DTO Challenge Workshop on Large Scale Concept Ontology for Multimedia, Columbia University ADVENT Technical Report 117-2006-3, 2006. [22] Grubinger M, Clough P et al. The IAPR TC-12 Benchmark: A new evaluation resource for visual information systems. In Proc. Int. Workshop OntoImage'2006 Language Resources for Content-Based Image Retrieval, Genoa, Italy, May 22, 2006, pp.13-23. [23] Alexander S, Joydeep G. Cluster ensembles --- A knowledge reuse framework for combining multiple partitions. Journal Machine Learning Research, December 2002, 3: 583-617. [24] Long B, Zhang Z, Xu T. Clustering on complex graphs. In Proc. the 23rd Conf. AAAI 2008, Chicago, USA, July, 2008.
 No related articles found!
Viewed
Full text

Abstract

Cited

Shared
Discussed
 [1] Han Jianchao; Shi Zhongzhi;. Formalizing Default Reasoning[J]. , 1990, 5(4): 374 -378 . [2] Fei Xianglin; Liao Lei; Wang Hezhen; Wang Chengzao;. Structured Development Environment Based on the Object-Oriented Concepts[J]. , 1992, 7(3): 193 -201 . [3] wang Xuejun; Shi Chunyi;. A Multiagent Dynamic interaction Testbed:Theoretic Framework, System Architecture and Experimentation[J]. , 1997, 12(2): 121 -132 . [4] Li Minglu; Sun Yongqiang; Sheng Huany;. Nondeterministic Temporal Relations in Multimedia Data[J]. , 1997, 12(3): 244 -251 . [5] Zhang Chenghong; Hu Yunfa; Shi Baile;. A Reasoning Mechanism for DeductiveObject-Oriented Databases[J]. , 1997, 12(4): 337 -345 . [6] NIE Xumin; GUO Qing;. Renaming a Set of Non-Horn Clauses[J]. , 2000, 15(5): 409 -415 . [7] Peter M. Haverty, Zhi-Ping Weng, and Ulla Hansen. Transcriptional Regulatory Networks Activated by PI3K and ERK Transduced Growth Signals in Human Glioblastoma Cells[J]. , 2005, 20(4): 439 -445 . [8] Xu-Bin Deng, and Yang-Yong Zhu. L-tree Match: A New Data Extraction Model and Algorithm for Huge Text Stream with Noises[J]. , 2005, 20(6): 763 -773 . [9] Cliff Reader. AVS Intellectual Property Rights (IPR) Policy[J]. , 2006, 21(3): 306 -309 . [10] Fei-Long Tang, Ming-Lu Li, and Joshua Zhexue Huang. Automatic Transaction Compensation for Reliable Grid Applications[J]. , 2006, 21(4): 529 -536 .
 ISSN 1000-9000(Print)          1860-4749(Online) CN 11-2296/TP Home Editorial Board Author Guidelines Subscription Journal of Computer Science and Technology Institute of Computing Technology, Chinese Academy of Sciences P.O. Box 2704, Beijing 100190 P.R. China Tel.:86-10-62610746 E-mail: jcst@ict.ac.cn


text:
+1 vote
18 views

The value of $\sin ^2 5^{\circ} + \sin ^2 10^{\circ} + \sin ^2 15^{\circ} + \dots + \sin^2 90^{\circ}$ is

1. $8$
2. $9$
3. $9.5$
4. None of these

recategorized | 18 views

Answer = $C.$
We will make the pairs of $\sin^2\theta + \cos^2\theta$, where $\theta$ is ame for both $\sin$ and $\cos$

$$\sin^25^0 + \sin^285^0 = \sin^25^0 + \sin^2(90^0-5^0) = \sin^25^0 + \cos^25^0 =1$$

(Using $\color{blue}{\sin^2\theta + \cos^2\theta = 1}$)

$$\sin^2{85}^0 = \cos^25^0 (\color{blue}{\because \sin\theta = \cos({90^0-\theta})})$$

similarly,

$$\sin^210 \;and\; \sin^280$$

$$\vdots$$

$$\sin^245^0 = \bigg(\frac{1}{\sqrt2}\bigg)^2 = \frac{1}{2} = 0.5$$

$$\vdots$$

$$\sin^240^0 \;and\; \sin^250$$

$$\vdots$$

$$\sin^290^0 = (1)^2 = 1$$

So, this way $8$ pairs will be formed, leaving $\sin^245^0$ and $\sin^290^0$

But we know that:

$$\sin^245^0 = \bigg(\frac{1}{\sqrt2}\bigg)^2 = \frac{1}{2} = 0.5$$

$$\sin^290^0 = 1^2 = 1$$

So, answer $= 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 +0.5 = 8\times1 +0.5 =9.5$
by Boss (13.5k points)
edited by
+1
Edit:- answer is 9.5, not 8.5
0
Yes!

Thanks.

1
2
3
+1 vote


text:
# An entire function is identically zero?

I'm preparing for a PhD prelim in Complex Analysis, and I encountered this question from an old PhD prelim:

Suppose $f(z)$ is an entire function such that $|f(z)| \leq \log(1+|z|) \forall z$. Show that $f \equiv 0$.

Well, for $z=0$, $|f(0)| \leq 0$. On the other hand, for $z \neq 0$, $\log(1+|z|) > 0$, a positive constant. I'm guessing this would mean that $f$ turns out to be a bounded entire function, so then by Liouville's theorem, $f$ is constant, but this doesn't necessarily mean that $f \equiv 0$, does it? Am I wrong somewhere? Some guidance would be much appreciated!

-
Certainly, if $f$ is constant, then it's 0. (proof: $|f(0)| \leq 0 \Rightarrow f(0) = 0$.) –  user29743 Jul 16 '12 at 18:11
@countinghaus: So essentially, my proof is correct? –  Libertron Jul 16 '12 at 18:13
@countinghaus is right. But $|f(z)| \leq \log(1+|z|)$ doesn't imply that $f$ is bounded. –  joriki Jul 16 '12 at 18:13
yeah, we're not done yet, I was just saying that if you can get $f$ to be constant, then you're done. –  user29743 Jul 16 '12 at 18:14
@joriki: So what should be done with the issue where $|f(z)| \leq \log(1+|z|)$? Would exponentiating both sides of the inequality be of any help? –  Libertron Jul 16 '12 at 18:16

Since $f$ is entire it can be expressed as a power series that converges everywhere: $f(z) = \sum_{n=0}^\infty a_n z^n$. From $|f(0)| \leq 0$ we know that $f(0)=0$, hence $a_0 = 0$. So $g(z) := f(z)/z$ can be continued to an entire function that satisfies $$|g(z)| \leq \frac{\log(1+|z|)}{|z|} \quad \text{for all } z\neq 0.$$ The right side converges to zero for $|z| \to \infty$, in particular it is bounded. By Liouville's theorem, $g$ is constantly zero and so is $f$.

-
So from the above it follows that $$\log(1+|z|)=kz\,\,,\,k\in\Bbb C\,\,\,\text{a constant}?$$ –  DonAntonio Jul 16 '12 at 18:55
@DonAntonio I don't see how that follows from the above. –  marlu Jul 16 '12 at 19:07
Perhaps I misunderstood something @Marlu, but isn't this what you wrote in the last two lines of your answer? –  DonAntonio Jul 16 '12 at 19:11
Do you mean that the same reasoning as above would show that $\log(1+|z|)/z$ is constant? It doesn't because $g$ needs to be entire to apply Liouville's theorem. –  marlu Jul 16 '12 at 19:29
thanks. "Entire" precisely was what I missed. +1 –  DonAntonio Jul 16 '12 at 23:57

We will prove a slightly more genaral fact. The proof is based on this answer

Theorem. Let $f\in\mathcal{O}(\mathbb{C})$ and for all $z\in\mathbb{C}$ we have $|f(z)|\leq\varphi(|z|)$. Assume that $$\lim\limits_{R\to+\infty}\frac{\varphi(R)}{R^{p+1}}=0$$ then $f$ is a polynimial with $\deg (f)\leq p$.

Proof. Since $f\in\mathcal{O}(\mathbb{C})$, then $$f(z)=\sum\limits_{n=0}^\infty c_n z^n$$ for all $z\in \mathbb{C}$. Moreover, for all $R>0$ we have integral representation for coefficients $$c_n=\int\limits_{\partial B(0,R)}\frac{f(z)}{z^{n+1}}dz$$ Then, we get an estiamtion $$|c_n|\leq \oint\limits_{\partial B(0,R)}\frac{|f(z)|}{|z|^{n+1}}|dz|\leq \oint\limits_{\partial B(0,R)}\frac{\varphi(|z|)}{|z|^{n+1}}|dz|= \frac{2\pi R\varphi(R)}{R^{n+1}}= \frac{2\pi \varphi(R)}{R^{n}}$$ Hence for $n>p$ we obtain $$|c_n|\leq\lim\limits_{R\to+\infty}\frac{2\pi\varphi(R)}{R^n}= 2\pi\lim\limits_{R\to+\infty}\frac{1}{R^{n-p-1}}\lim\limits_{R\to+\infty}\frac{ R\varphi(R)}{R^{p+1}}=0$$ which implies $c_n=0$ for $n>p$. Finally we get $$f(z)=\sum\limits_{n=0}^p c_n z^n+\sum\limits_{n=p+1}^\infty c_n z^n=\sum\limits_{n=0}^p c_n z^n$$ This means that $f$ is a polynimial with $\deg(f)\leq p$.

For your particular problem $\varphi(R)=\log(1+R)$, and it is easy to check that $$\lim\limits_{R\to+\infty}\frac{\varphi(R)}{R}=0$$ Hence, $f(z)=c_0$ is a constant function. Moreover, $$|c_0|=|f(0)|\leq\log(1+|0|)=0$$ so $c_0=0$ and $f(z)=0$ for all $z\in\mathbb{C}$.

-
shouldn't there in the representation for $\,c_n\,$ be some factorial (I think it is $\,n!\,$ ) somewhere? –  DonAntonio Jul 16 '12 at 18:54
No, it shouldn't. –  Norbert Jul 16 '12 at 19:02

We already know that $f(0) = 0$. Now from $|f(z)| \leq \log(1 + |z|)$ and we get that on every circle of radius $R$ about the origin, $$|f^{(n)}(0)| \leq \frac{\log(1 + |R|) \times n!}{R^n} \hspace{5mm} \forall n \geq 1$$ by the Cauchy estimate. Since $R^n$ grows faster than $\log (1+ |R|)$ when $n \geq 1$, we see that $f^{(n)}(0) = 0$ for all $n \geq 1$. But we also know $f(0) = 0$ so that $f^{(n)}(0) = 0$ for all $n \geq 0$. Since $f$ is entire the identity principle implies $f \equiv 0$.

-


text:
# Properties of representations attached to p-adic modular forms

I found an old MOF post about representations attached to p-adic modular forms: Representations attached to p-adic modular forms and I have some follow up questions on the same topic.

If we have a classical form of weight k, it is know that the p-adic representation attached to the form is crystalline if p does not divide the level. It is de Rham in general and it has Hodge-Tate weights 0 and k-1.

My question is that if the form is not classical, then the weight is not an integer. Is this representation crystalline or de Rham? Can we say something about the Hodge-Tate weights?

There are two subtleties regarding how to formulate this question.

Firstly, there are several notions of "p-adic modular form". There's Hida's ordinary p-adic modular forms (a very small space); there's Coleman's overconvergent p-adic modular forms (a much bigger space); and there's Serre and Katz's space of p-adic modular forms, which is a vastly bigger space (too big to have a reasonable theory of eigenforms).

The second subtlety is that for the latter two definitions (Coleman or Serre-Katz) it is not true that a non-classical form has non-integer weight; there are non-classical forms of integer weight (lots of them).

With that out of the way: if f is in any of these spaces and its weight is non-integral, then the associated Galois representation isn't even Hodge--Tate, so it's certainly not de Rham or crystalline. The eigenvalues of its Sen operator are what they should be, i.e. 0 and $k - 1$ where $k$ is the weight (but you have to be careful what this means!).

If $f$ is of integer weight and it's ordinary, then it's classical and the local representation is de Rham. If it's overconvergent and has finite slope (i.e. defines a point on the eigencurve), then it might be non-classical, in which case then the local Galois rep is Hodge--Tate (with weights 0 and $k-1$), but it is never de Rham; this is a theorem of Kisin, from his big paper "Overconvergent modular forms and the Fontaine-Mazur conjecture". Kisin's work also shows that if $f$ is an overconvergent finite-slope non-classical eigenform, then $\mathbf{D}_{\mathrm{cris}}V_p(f)$ is 1-dimensional (and this crystalline period varies analytically in families).

As for the case of infinite-slope non-classical eigenforms, or non-overconvergent eigenforms, I don't know.

• Kisin proved that $\mathbb{D}_{cris} \mathrm{V}_p(f)^{\phi=a_p}$ is one dimensional, where $U_p(f)=a_p.f$. Why $\mathbb{D}_{cris} \mathrm{V}_p(f)$ is one dimensional? – Adel BETINA Apr 26 '16 at 9:21
• If it were two-dimensional $\mathbf{D}_{\mathrm{cris}}(V_p(f)$ would be crystalline, hence de Rham, but Kisin proved that $V_p(f)$ is only de Rham when $f$ is classical. – David Loeffler Apr 26 '16 at 14:30